To identify sources of distributed denial-of-service attacks, path traceback mechanisms have been proposed. Traceback mechanisms relying on probabilistic packet marking (PPM) have received most attention, as they are easy to implement and deploy incrementally. In this paper, we introduce a new concept, namely Groups Of Strongly SImilar Birthdays (GOSSIB 1 ), that can be used by to obtain effects similar to a successful birthday attack on PPM schemes. The original and most widely known IP traceback mechanism, compressed edge fragment sampling (CEFS), was developed by Savage et al. [SWKA00]. We analyze the effects of an attacker using GOSSIB against CEFS and show that the attacker can seed misinformation much more efficiently than the network is able to contribute real traceback information. Thus, GOSSIB will render PPM effectively useless. It can be expected that GOSSIB has similar effects on other PPM traceback schemes and that standard modifications to the systems will not solve the problem.