Protocol Fixes for KeyTrap Vulnerabilities

The 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.