Heftrig, EliasEliasHeftrigSchulmann, HayaHayaSchulmannVogel, NiklasNiklasVogelWaidner, MichaelMichaelWaidner2024-08-072024-08-072024https://publica.fraunhofer.de/handle/publica/47291410.1145/3673422.3674902The security and availability of DNS are of major concern for many critical Internet services. Recently, KeyTrap algorithmic complexity Denial of Service attacks were demonstrated against DNSSEC-validating DNS resolvers [6]. The attacks exploit the validation complexity in DNSSEC to stall DNS resolvers, some for as long as 16h with just a single DNS response. Although short term patches were immediately implemented by the vendors, the attack can still produce a heavy load in some patched DNS resolvers. This work proposes new protocol-level mitigations for the KeyTrap vulnerabilities, using a new DNSSEC record that outlaws keytag collisions while ensuring backward compatibility. Further, this work raises the question of how much RFCs could and should dictate implementation-level limits to prevent DoS through complex validation routines. With our discussions, we aim to provide a solid foundation to improve the DNSSEC standard, mitigating KeyTrap and providing more robust recommendations for DNS implementations in the future.enconference paper