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

Roy Arends roy at dnss.ec
Fri Dec 4 01:42:19 UTC 2015

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 

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 == 
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,


An example public key that illustrates the example above:

. IN DNSKEY 257 3 8 

keytag(RDATA) == 6

RDATA%65535 == 7

More information about the dns-operations mailing list