[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
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
More information about the dns-operations
mailing list