The original NSEC record for DNSSEC had the drawback that it made it possible to enumerate the complete zone by querying for any nonexisting domain and itterate through all the valid domains. The solution for that was NSEC3 introduced in RFC5155.
However NSEC3 does not completely solve the problem. An attacker can still collect most/all the NSEC3 records for a domain by querying for random domain names. As soon as the attacker know the hashing parameters he can also verify if the random domain names fall into an interval covered by an NSEC3 record already collected, thus limit the number of DNS queries in order to not attract attention. With all the NSEC3 records collected a dictionary attack with likely domain names can be performed without the authoritative DNS server knowing or having any way to protect against it.
This page used to contain an idea for a solution to that problem. However the idea turned out not to work, so I have removed it again. Instead I suggest that if anybody want to design a protocol to replace NSEC3, they should take a look at some of the cryptographic research in the area. A good starting point is Mercurial Commitments with Applications to Zero-Knowledge Sets.
A different approach
Given my previous failure it may seem like hubris to publish another idea, yet I am taking the chance. This idea doesn't try to remain backward compatible, but instead replace NSEC3 with something similar, but incompatible.
The idea is to replace the itterated salted hash with a three step algorithm consisting of hash, sign, hash. The two hashes could still be SHA1, but they don't have to be the same hash. In particular the first of the two hashes could very well have a longer output, but the last hash could still be SHA1 to avoid producing longer labels. The signature algorithm must be one that produce deterministic signatures (such as RSA), and it must not use the same key as used for signing the zone.
The introduction of the extra asymmetric primitive introduce the extra randomness that salting used to introduce. Thus there is no longer any need for salting. The key is rotated every time the zone is resigned. Hash collisions are handled just like with regular NSEC3, by doing it all over again with a newly generated keypair (in NSEC3 it was a salt rather than a keypair).
The assymetric primitive requires more computation, thus itterating the algorithm would be a bad idea, thus this new algorithm would not specify any itteration count. However the assymetric primitive also eliminates the need for the itteration as the complete function can no longer be computed by the client, which do not know the secret key being used. Any NXDOMAIN response must include the signature as an additional record such that the client can verify correctness of the hash value.
The last hashing step concatenate the signature and the requested domain. This is done in order to ensure that even if the signature scheme is broken it would only allow an attacker to enumerate the zone. It would not allow forging any NXDOMAIN responses as that would still require a collision in the last hashing step. The hashing steps could also concatenate the public key as a sort of salting, though it is unclear if any security is gained from that.
The wire format of NSEC3 can be retained by defining a new value for the hash function and redifining the salt to be the public key. The itteration count must be set to zero by the server, and the validator must treat any nonzero value as an invalid response.
Posted 2011 July 20th, last updated 2011 July 21st.