DNS cache poisoning is a persistent game of attack and defense, posing an enduring challenge for the DNS community. Significant efforts have been made to uncover, detect, and mitigate vulnerabilities that increase the risk of cache poisoning. However, no work has systematically revisited whether the original cache poisoning attack based on the Birthday Paradox remains effective. In this work, we introduce RebirthDay, a novel DNS cache poisoning attack targeting recursive resolvers and forwarders, reviving the classic DNS Birthday attack that no longer works since 2002. RebirthDay exploits newly uncovered, protocol-compliant vulnerabilities in DNS extension implementations to bypass the query aggregation mechanism intended to prevent DNS Birthday attacks that has not been well understood. We uncovered that 18 out of 22 mainstream DNS software are vulnerable due to weaknesses in the processing of a DNS extension (i.e., ECS option), specifically lacking or incorrectly implemented ECS coherence checks when handling DNS queries and responses, demonstrating the widespread susceptibility to RebirthDay. These flaws could be exploited to circumvent the query aggregation mechanism and launch RebirthDay attacks. Through comprehensive evaluation, we showed that RebirthDay attacks are highly practical and can have significant real-world impact, affecting 16 router vendors, 14 public DNS services, and 365K (15%) open DNS resolvers. We have reported the identified vulnerabilities to affected vendors and discussed mitigation solutions with them. To date, we have received acknowledgments from 8 vendors, including BIND, Unbound, PowerDNS, and Quad9, and have been assigned 50 CVE-ids. Our study emphasizes the need for greater attention to the importance of ECS verification and DNS extension implementations, revealing new security risks introduced by them.

In recent years, large-scale network outages caused by DNS misconfigurations have become increasingly common. The intricate inter-domain dependencies, along with emerging mechanisms (Such as DNSSEC, EDNS, and 0x20), have made DNS resolution increasingly complex and fault localization more challenging. We present RMap, a tool that rapidly probes all potential resolution chains of a domain, reveals its resolution dependency topology, and detects security risks. We experimentally demonstrate the effectiveness of RMap and its broad applicability. Our findings reveal that domain configurations in real-world environments remain concerning, with potential issues observed even in several well-known top-level domains. RMap is avaliable in https://github.com/ahlien/rmap.