Quest for missing keytags
Roy Arends | DNS-OARC | 1 April 2016

Pubquiz question:
What is a DNSKEY Key Tag
A.

a 16 bit value in the DNSKEY RDATAB.

a physical tag that you’d hang on your key ringC.

a 16 bit value in the DS and RRSIG RDATA

D.

a special variation of the game of tag.

| 2

Why did I look into this?
2010, first root KSK published,2015, I started working on my testbed| 3

Why did I look into this?
2010
2015

| 4

Why did I look into this?
2010
2015
I wanted to use those as keytags for my testbed.
You can’t simply assign a keytag to a dnskey.
RFC4034:“the algorithm for calculating the Key Tag is almost but not completely
identical to the familiar ones-complement checksum used in manyother Internet protocols.”| 5Simple loop

while true
do dnssec-keygen –a RSASHA256 –f KSK –b 2048 .
done

| 6

Simple loop

while true
do dnssec-keygen –a RSASHA256 –f KSK –b 2048 .
doneThis only generated about 16K keys
I was expecting 64K keys
keytags 02010 and 02015 were absent| 7Simple loop

while true
do dnssec-keygen –a RSASHA256 –f KSK –b 2048 .
doneFirst clue by Duane Wessels:
dnssec-keygen won't generate a new key if:• the new key tag conflicts with an existing key tag + revoke bit• the new key tag + revoke bit conflicts with an existing key tag
Nice! Well observed.

| 8

Less Simple loop

while true
do dnssec-keygen –a RSASHA256 –f KSK –b 2048 .\>> taglist
rm K\.+008*;
done
This simply removes keys after they’re created, but adds the tag to alist.

| 9Less Simple loop

while true
do dnssec-keygen –a RSASHA256 –f KSK –b 2048 .\>> taglist
rm K\.+008*;
done
This simply removes keys after they’re created, but adds the tag to alist.
sort –u taglist | wc –l
16387

| 10

Less Simple loop

while true
do dnssec-keygen –a RSASHA256 –f KSK –b 2048 .\>> taglist
rm K\.+008*;
done
This simply removes keys after they’re created, but adds the tag to alist.
sort –u taglist | wc –l16387
Wait, what? Not 16384?

| 11

It’s the tool, try a different one.

while true
do ldns-keygen –a RSASHA256 –k –b 2048 .
done
Nice and simple. No undocumented features.
Allows for foot shooting.

| 12

It’s the tool, try a different one.

while true
do ldns-keygen –a RSASHA256 –k –b 2048 .
done
Nice and simple. No undocumented features.
ls K.*private | wc –l
16385

| 13

It’s the tool, try a different one.

while true
do ldns-keygen –a RSASHA256 –k –b 2048 .
done
Nice and simple. No undocumented features.
ls K.*private | wc –l16385
Still, not high enough.

| 14

Meanwhile, via Twitter| 15

Meanwhile, via Twitter| 16

So, it could be the library
DNSSEC-Keygen and ldns-keygen use OpenSSL
pdnssec uses mbedTLS
Is this a bug in OpenSSL?

| 17

So, it could be the library
DNSSEC-Keygen and ldns-keygen use OpenSSL
pdnssec uses mbedTLS
Is this a bug in OpenSSL?
“KEYSTARVE” [goes and registers name]| 18But…. On DNS-OperationsPeter van Dijk:
I now have ~130k (diﬀerent!) keys, with 32201 unique key tags. This isalmost twice as much as Roy had but it looks like it might top oﬀ around
32k.

| 19

But…. On DNS-OperationsPeter van Dijk:
I now have ~130k (diﬀerent!) keys, with 32201 unique key tags. This isalmost twice as much as Roy had but it looks like it might top oﬀ around
32k.

| 20

Now what…
Three different tools
Two different libraries
Three issues:
1)
2)
3)

Not enough keytags (expected 64K, got less)Off by a few keytags (16387, 16385, 32769)
One library produces 50% of the other library| 21

Is it the keytag function?
The keytag function is very similar to a radix minus one complement
function. Very similar to the Internet Header Checksum.
So, generate 2048 random bits in pairs of 2 byte words and do an
Internet Header Checksum over that.
while true
do jot -r 128 0 65535 | awk \'{s+=$1} END {print (s + int(s/65536))%65535}’ \>>test
done
sort –u test | wc –l65536| 22

It is not the keytag function
The keytag function is very similar to a radix minus one complement
function. Very similar to the Internet Header Checksum.
So, generate 2048 random bits in pairs of 2 byte words and do an
Internet Header Checksum over that.
•It is not the keytag function| 23

It is not the keytag function
The keytag function is very similar to a radix minus one complementfunction. Very similar to the Internet Header Checksum.
So, generate 2048 random bits in pairs of 2 byte words and do an
Internet Header Checksum over that.
••

It is not the keytag function
It is not the library| 24

It is not the keytag function
The keytag function is very similar to a radix minus one complement
function. Very similar to the Internet Header Checksum.
So, generate 2048 random bits in pairs of 2 byte words and do an
Internet Header Checksum over that.
•••

It is not the keytag function
It is not the library
It is not the tools| 25

It is not the keytag function
The keytag function is very similar to a radix minus one complement
function. Very similar to the Internet Header Checksum.
So, generate 2048 random bits in pairs of 2 byte words and do an
Internet Header Checksum over that.
•••

It is not the keytag functionIt is not the library
It is not the tools(and hopefully not the user)

| 26

?
| 27

Florian Maury and Jérôme PlûtThe Internet Header Checksum is equivalent toaddition modulo 65535| 28

Florian Maury and Jérôme PlûtThe Internet Header Checksum is equivalent toaddition modulo 65535
Assuming a 32 bit number ($num) this means:($num AND 65535) + ($num >> 16)
is equivalent to$num % 65535| 29

Florian Maury and Jérôme Plût$num % 65535
In our case, $num contains the RDATA of the DNSKEY.
For all the keys generated, the RDATA part contains a constant:(RDLENGTH,PROTOCOL,ALGORITHM, EXPONENT)
And a variable part:
The RSA modulus, which consist of two prime factors P and Q| 30

Florian Maury and Jérôme PlûtTherefore, we have$num % 65535
Is equivalent to:(constant + P*Q) % 65535
Is equivalent to:(constant % 65535) + ((P*Q) % 65535 )| 31

Florian Maury and Jérôme PlûtIgnoring the constant part we have:(P*Q) % 65535
We know that P and Q are very large primes.
65535 has factors: 3, 5, 17, 257
Since (P, Q, 3, 5, 17 and 257)are co-prime,
P, Q can’t be divided by 3, 5, 17 and 257
and(P*Q) % 3, 5, 17 or 257 will never be 0| 32

Florian Maury and Jérôme Plût(P*Q) % 3, 5, 17 or 257 will never be 0(P*Q) % 3 has 2 solutions (not 3)(P*Q) % 5 has 4 solutions (not 5)(P*Q) % 17 has 16 solutions (not 17) and(P*Q) % 257 has 256 solutions (not 257)
So, (P*Q) % 65535 has 2*4*16*256 solutions| 33

Florian Maury and Jérôme Plût(P*Q) % 3, 5, 17 or 257 will never be 0(P*Q) % 3 has 2 solutions (not 3)(P*Q) % 5 has 4 solutions (not 5)(P*Q) % 17 has 16 solutions (not 17) and(P*Q) % 257 has 256 solutions (not 257)
So, (P*Q) % 65535 has 2*4*16*256 solutions, or32768 different keytags| 34Hoorah!
Three issues, one solved:1)
2)
3)

SOLVED: Not enough keytags (expected 64K, got less)Off by a few keytags (16387, 16385, 32769)
One library produces 50% of the other library| 35

Off by a few
Very similar is not exactly the same
The last part of the key-tag function in RFC4034 reads as follows:
ac += (ac >> 16) & 0xFFFF;
return ac & 0xFFFF;
If the previous line result in a carry (value > 65535), the latter line
ignores it.
Hence, some off by a few keytags are a result of that.

| 36

Hoorah!
Three issues, two solved:1)
2)
3)

SOLVED: Not enough keytags (expected 64K, got less)
SOLVED: Off by a few keytags (16387, 16385, 32769)
One library produces 50% of the other library| 37

Half the keyspace
Peter, using mbedTLS was able to produce twice as many keytags.
OpenSSL only generates safe primes:
P = 2 * P` + 1 where P` is also prime.
That implies that P mod 3 is never 1 (and thus always 2)
So: P*Q=M(P mod 3) * (Q mod 3) = M mod 3
2 * 2 = 4 mod 3
M mod 3 is 1. Always| 38

Half the keyspace(P*Q) % 3, 5, 17 or 257 will never be 0(P*Q) % 3 has 2 solutions (not 3)(P*Q) % 5 has 4 solutions (not 5)(P*Q) % 17 has 16 solutions (not 17) and(P*Q) % 257 has 256 solutions (not 257)
So, (P*Q) % 65535 has 2*4*16*256 solutions, or32768 different keytags| 39

Half the keyspace(P*Q) % 3, 5, 17 or 257 will never be 0(P*Q) % 3 will always be 1
(P*Q) % 3 has 1 solution (not 3)(P*Q) % 5 has 4 solutions (not 5)(P*Q) % 17 has 16 solutions (not 17) and(P*Q) % 257 has 256 solutions (not 257)
So, (P*Q) % 65535 has 1*4*16*256 solutions, or

32768 different keytags
16384| 40

Hoorah!
Three issues, two solved:1)
2)
3)

SOLVED: Not enough keytags (expected 64K, got less)
SOLVED: Off by a few keytags (16387, 16385, 32769)
SOLVED: One library produces 50% of the other library| 41

Thanks toWarren Kumari
Ben Laurie
Florian Maury
Jérôme PlûtJean-René ReinhardPeter van Dijk
Bert HubertDavid Conrad
And all who have participated in the discussions on dns-operations| 42

Questions?

| 43