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

[Florian Maury]

Le 01/12/2015 08:44, Peter van Dijk a écrit :
> On 1 Dec 2015, at 8:41, Peter van Dijk wrote:
>> On 30 Nov 2015, at 15:51, Roy Arends wrote:
>>> On 29 Nov 2015, at 23:20, Roy Arends wrote:
>>>> I am only able to generate about 16K unique keytags for a 2K
>>>> RSASHA256 KSK (*), even after generating hundreds of thousands of
>>>> keys in a loop.
>>>
>>> Peter van Dijk generated a large set of DNSKEYs with the same
>>> algorithm, flags and exponent and was able to generate a lot more
>>> unique keytags. Peter is using PowerDNS ’pdnssec add-zone-key’ which
>>> uses mbedTLS 2.1.0, while I was using dnssec-keygen and ldns-keygen
>>> which both used OpenSSL 0.9.8zg.
>>
>> I now have ~130k (different!) keys, with 32201 unique key tags. This
>> is almost twice as much as Roy had but it looks like it might top off
>> around 32k. Numbers at
>> https://gist.githubusercontent.com/anonymous/24749cea279ce2af2b9c/raw/b06fbc97791f376b2e5e15d0931e0ad1a7030e35/keytags.csv
>> for those who want to do stats.
>>
>> The csv should also be good to look at bit distributions. When I
>> looked yesterday (with around 15k keys) every bit had about a 50%
>> chance of being set, which suggested no bias to me, but this is not my
>> strong suit.
> 
> Sorry - that csv has counts, not actual key tag numbers. The full
> unsorted ungrouped list of key tags so far is at
> https://gist.githubusercontent.com/anonymous/e30b4c905501a7d6aeea/raw/478a46abf6c0011c9eabd10a1a875684f859bbdf/keytags

Hey everyone,

First for all, thank you Roy for bringing this up, and to you Peter for
sharing the keytags you have computed.

Just so you know, we have also tried to compute the keytag of "observed
in the wild" X.509 certificates containing RSA moduli and we obtained
the same kind of results. So, dnssec-keygen is in the clear.

Also, I saw someone wondering if the results could be influenced by a
bad randomness quality of current Linux /dev/urandom as opposed to
/dev/random. Studies proved that urandom randomness is as good as you
could wish for, and that you really need corner cases or to hate
yourself to use /dev/random [1][2].

So back to the keytag function. I seeked the help of Jérôme Plût, a
colleague from our cryptography laboratory. I would have never found
this without him.
This function is actually more of a mathematical operation than a hash
function (as in "mixing bits together to obtain a uniformly distributed
tag").
As it happens, the function is equivalent to an addition modulo (2^16)-1.
Since the RSA modulus is the result of a multiplication of two primes,
that cannot, by definition, be divided by the factors of 2^16-1 (namely
3, 5, 17, and 257), the RSA modulus cannot be divided by these factors.
This can be summarized by the following relation: the keytag is
congruent to the (RSA modulus + a constant) modulo 65535. The constant
is dependant of the flags, protocol, algorithm and the public exponent
as encoded in the RDATA field.
The fact that N cannot by divided by 3, 5, 17 and 257 means that there
are 2 * 4 * 16 * 256 values possible for the keytag of a RSA key =>
32768 values, as Peter discovered empirically.

Among these 32768 values, there remain some biases. Namely, empirically
93% of RSA moduli are congruent to 1 (mod 3) and only 7% are congruent
to 2 (mod 3). This is probably a consequence of the prime number
generation procedure (for example, some implementations restrict to
primes congruent to 1 (mod 6) for speed reasons, which has a very
reasonable impact on security). There is also a smaller bias in favor of
moduli congruent to 1 (mod 5) and an even smaller one for 1 (mod 17). A
more detailed look in the implementation would be needed to explain
this, but the security impact is probably very weak.

To the best of my knowledge, this keytag discovery has no immediate
security implication and it can simply be regarded as a DNSSEC fun fact.
Replacing the keytag computation function by another hashing function
should be possible, as this value is opaque, but it is probably not
worth the effort.

Cheers,
Florian Maury
ANSSI

[1] http://viccuad.me/blog/urandom-vs-random-for-dummies/ lists a number
of references of people also saying urandom is just fine.
[2]
https://blog.cloudflare.com/ensuring-randomness-with-linuxs-random-number-generator/