[dns-operations] a maximum of about 16K possible DNSSEC keytags?

[Roy Arends]

Ben Laurie (Google, OpenSSL) and I chased down the last bit (no pun 
intended) of mystery. The following will explain why Peter and I saw 
slightly more than 32K and 16K keytags respectively.

Jerome has already explained why half of the keytags will not exist.

However, as Florian Maury wrote (paraphrasing Jérôme Plût) :

“As it happens, the function is equivalent to an addition modulo 
(2^16)-1.”

The crux is that the keytag algorithm in RFC4034 has a small, but 
important difference to an addition modulo (2^16)-1: the missing last 
‘carry’ that you would expect _if_ the function is equivalent to 
addition modulo (2^16)-1

The algorithm in Appendix B of RFC4034 is as follows:

unsigned int keytag
           (
            unsigned char key[],  /* the RDATA part of the DNSKEY RR */
            unsigned int keysize  /* the RDLENGTH */
           )
    {
            unsigned long ac;     /* assumed to be 32 bits or larger */
            int i;                /* loop index */

            for ( ac = 0, i = 0; i < keysize; ++i )
                    ac += (i & 1) ? key[i] : key[i] << 8;
            ac += (ac >> 16) & 0xFFFF;
            return ac & 0xFFFF;
    }

The result of the for loop is the sum of a serie of 16 bit values.

The line “ac += (ac >> 16) & 0xFFFF; “ causes the high 16 bits to be 
added to the original value.

However, there might be a carry as a result of that addition, which is 
ignored when doing returning ac & 0xFFFF (the next line).

As an example, assume that the for loop produces ac == 0x0040FFC6.
Top 16 bits (0x0040) added to the result: 0x0040 + 0x0040FFC6 == 
0x00410006
The returned result is 0x00410006 & 0xFFFF == 0x0006

If this would be equivalent to modulo (2^16)-1, then keep adding until 
the top 16 bits have no more carry bits:
		while (ac >> 16)
			ac = (ac & 0xFFFF) + (ac >> 16);

which causes the following:
assume again the value of ac=0x0040FFC6
first iteration:  0xFFC6 + 0x0040 = 0x00010006
second iteration: 0x0001 + 0x0006 = 0x0007

the equivalent addition modulo (2^16)-1:
assume again the value of ac=0x0040FFC6

    0x0040FFC6 % 0xFFFF = 0x0007

What that means is that next to the 32768 keytags (or 16384 in the 
RSA-prime compliant case), there can be a bunch of keytags that have the 
missing carry (and thus are one-off to the addition-modulo value).

The one-offs have keytags values below keysize/16 + 3.

Warm regards,

Roy

An example public key that illustrates the example above:

. IN DNSKEY 257 3 8 
AwEAAbyIo4Y/i6L0O2Tya35DMfChrUb2/r5Of/2+cxC7U4TQilenUgCH
				   jfx18SrOfSg+8MDgUTJQtrnxoGhUanSBQl67Mu1kAVIlZGlfb2Nk6h8l
				   K04lrt0q1WDgbuXaEQGGtioMF8OSD+fOmMlZkUBKqv9f9qFz7v0/xWsW
                     
X/Gt68QxHablaa2QeEHKIswWIF0vxGxHZrJVDFHtbn8m8gWrz+s3zk9n
				   wUVShyv/c0diirWX4zSsO9Z1VXO4gpgUew5B2W8ygNvnNulM8DcDwaDy
				   YP9xnsF2IpuqTRDQ4illZGrBB0tJwOD5w9yS5KK12LTWPp9yI9fIMdG8
				   qOWRp6MP2XM=

keytag(RDATA) == 6

RDATA%65535 == 7