# [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
(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

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

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

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