Christian Huitema's blog

Cloudy sky, waves on the sea, the sun is

Self-keying domain names

31 Dec 2010

The concept of “self-keying” domain names emerged as a parallel thread in the discussion of P2P DNS name. I have investigated this kind of names for some time, and I believe that I can make a fairly simple proposal. By nature, the “self-keying” idea implies that the name will be the base32 encoding of a binary hash. My priority is to enable some form of “hash compression” so the base32 string is not overly long and unwieldy.

There is a limit to how short a binary name can be. Suppose that we forgot all notion of security and just wanted to pick random numbers. The random numbers will have to be large enough to avoid collisions, and that probably mean dealing with the birthday problem. If we expect a top level domain to support 1 million users, the random number shall be at least 2x20 = 40 bits. If we want to scale to 100 million, we need at least 54 bits. That number might be reduced if the creator of a name could test in real time whether the name is already “taken,” but we should not bank on that too much, as we cannot predict that P2P names will be reachable on line all the time. In practice, it might be reasonable to expect a name size of 60 bits, which can be encoded in 12 base 32 characters and would enable scaling of a P2P domain to 1 billion names.

We probably don’t want names to be much longer than 12 characters, as in “A2F3G5HXT97E.KEY.” We may want to throw in some hyphens for “punctuation,” as in “A2F3-G5HX-T97E.KEY” to help reading, making the name just slightly harder to read than, for example, a social security number. Not exactly a marketing delight, but it could work. The problem of course is that a 60 bit hash code is rather easy to crack. We need some additional protection. We can reuse here the “call sign” idea, requiring that the hash code has some strong properties, such as a certain number of Z trailing zeroes. The effective strength of the hash code would then be 60+Z. Given enough efforts, names can be generated with proper strength.

If we want to implement these concepts, we can extend the DNSSEC architecture to support “self-keying” names. The key used to verify the name can be encoded in the DNSKEY record specified by DNSSEC. The main part of the proposal is the definition of a new “DNS SALT” record that would contain the information necessary for that verification, including a pointer to the verification algorithm.

The verification of a “self-keying” name would proceed as follow:

Specifying a DNSSALT record is fairly straightforward. The first octet or two would contain the algorithm identifier. The following octets would contain the data used for the verification, and their format would be specified together with the algorithm. A base algorithm could be implemented around the SHA-256 standard. In that base algorithm, the DNSSALT record would contain 5 fields:

To verify the name, a resolver would first verify that the sum L+Z is large enough to be secure, and that the name contains L base32 characters. If that is true, the resolver will build an octet string by concatenating the parent domain name, the content of the DNSKEY record designated by the tag, and the content of the DNSSALT record. It will then compute the SHA256 hash of that string, and verify that the least significant Z bits of the hash are all zeroes, and that the 5xL most significant bits match the L base32 characters of the name. If all that is true, the name is considered a valid “trust anchor.”

The name itself is generated using a reverse process. First select the key and the desired values Z and L. Select the parent domain, pick an initial salt, format the DNSKEY and DNSSALT records, construct the binary string and compute the SHA256 hash. If the last Z bits are not all zeroes, pick a different salt and repeat. Once a proper salt has bit found, create the name from the base32 encoding of the most significant 5xL bits of the hash code. Voila, a self-keying name.

Of course, if we want to standardize self-keying doamin names, we will need something a bit more elaborate than this one-page summary. We will need to specify the format in detail, explain the security issues, and of course deal with various patent considerations, including the “call sign” patent. I am curious to see whether there is enough interest to go forward with the proposal.