<div dir="ltr">Thank you very much <span style="font-size:12.8px">Florian </span>for this detailed explanation ... <div>and to Roy for bringing up this subject and "kicking the tires" of his own car.</div><div>Together, this helps me sleep better at night.</div><div><br></div><div>-Rick</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Dec 2, 2015 at 1:16 AM, Florian Maury <span dir="ltr"><<a href="mailto:florian.maury@ssi.gouv.fr" target="_blank">florian.maury@ssi.gouv.fr</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">Le 01/12/2015 08:44, Peter van Dijk a écrit :<br>
> On 1 Dec 2015, at 8:41, Peter van Dijk wrote:<br>
</span><span class="">>> On 30 Nov 2015, at 15:51, Roy Arends wrote:<br>
</span><span class="">>>> On 29 Nov 2015, at 23:20, Roy Arends wrote:<br>
>>>> I am only able to generate about 16K unique keytags for a 2K<br>
>>>> RSASHA256 KSK (*), even after generating hundreds of thousands of<br>
>>>> keys in a loop.<br>
>>><br>
</span><span class="">>>> Peter van Dijk generated a large set of DNSKEYs with the same<br>
>>> algorithm, flags and exponent and was able to generate a lot more<br>
>>> unique keytags. Peter is using PowerDNS ’pdnssec add-zone-key’ which<br>
>>> uses mbedTLS 2.1.0, while I was using dnssec-keygen and ldns-keygen<br>
>>> which both used OpenSSL 0.9.8zg.<br>
>><br>
>> I now have ~130k (different!) keys, with 32201 unique key tags. This<br>
>> is almost twice as much as Roy had but it looks like it might top off<br>
>> around 32k. Numbers at<br>
>> <a href="https://gist.githubusercontent.com/anonymous/24749cea279ce2af2b9c/raw/b06fbc97791f376b2e5e15d0931e0ad1a7030e35/keytags.csv" rel="noreferrer" target="_blank">https://gist.githubusercontent.com/anonymous/24749cea279ce2af2b9c/raw/b06fbc97791f376b2e5e15d0931e0ad1a7030e35/keytags.csv</a><br>
>> for those who want to do stats.<br>
>><br>
>> The csv should also be good to look at bit distributions. When I<br>
>> looked yesterday (with around 15k keys) every bit had about a 50%<br>
>> chance of being set, which suggested no bias to me, but this is not my<br>
>> strong suit.<br>
><br>
> Sorry - that csv has counts, not actual key tag numbers. The full<br>
> unsorted ungrouped list of key tags so far is at<br>
> <a href="https://gist.githubusercontent.com/anonymous/e30b4c905501a7d6aeea/raw/478a46abf6c0011c9eabd10a1a875684f859bbdf/keytags" rel="noreferrer" target="_blank">https://gist.githubusercontent.com/anonymous/e30b4c905501a7d6aeea/raw/478a46abf6c0011c9eabd10a1a875684f859bbdf/keytags</a><br>
<br>
</span>Hey everyone,<br>
<br>
First for all, thank you Roy for bringing this up, and to you Peter for<br>
sharing the keytags you have computed.<br>
<br>
Just so you know, we have also tried to compute the keytag of "observed<br>
in the wild" X.509 certificates containing RSA moduli and we obtained<br>
the same kind of results. So, dnssec-keygen is in the clear.<br>
<br>
Also, I saw someone wondering if the results could be influenced by a<br>
bad randomness quality of current Linux /dev/urandom as opposed to<br>
/dev/random. Studies proved that urandom randomness is as good as you<br>
could wish for, and that you really need corner cases or to hate<br>
yourself to use /dev/random [1][2].<br>
<br>
So back to the keytag function. I seeked the help of Jérôme Plût, a<br>
colleague from our cryptography laboratory. I would have never found<br>
this without him.<br>
This function is actually more of a mathematical operation than a hash<br>
function (as in "mixing bits together to obtain a uniformly distributed<br>
tag").<br>
As it happens, the function is equivalent to an addition modulo (2^16)-1.<br>
Since the RSA modulus is the result of a multiplication of two primes,<br>
that cannot, by definition, be divided by the factors of 2^16-1 (namely<br>
3, 5, 17, and 257), the RSA modulus cannot be divided by these factors.<br>
This can be summarized by the following relation: the keytag is<br>
congruent to the (RSA modulus + a constant) modulo 65535. The constant<br>
is dependant of the flags, protocol, algorithm and the public exponent<br>
as encoded in the RDATA field.<br>
The fact that N cannot by divided by 3, 5, 17 and 257 means that there<br>
are 2 * 4 * 16 * 256 values possible for the keytag of a RSA key =><br>
32768 values, as Peter discovered empirically.<br>
<br>
Among these 32768 values, there remain some biases. Namely, empirically<br>
93% of RSA moduli are congruent to 1 (mod 3) and only 7% are congruent<br>
to 2 (mod 3). This is probably a consequence of the prime number<br>
generation procedure (for example, some implementations restrict to<br>
primes congruent to 1 (mod 6) for speed reasons, which has a very<br>
reasonable impact on security). There is also a smaller bias in favor of<br>
moduli congruent to 1 (mod 5) and an even smaller one for 1 (mod 17). A<br>
more detailed look in the implementation would be needed to explain<br>
this, but the security impact is probably very weak.<br>
<br>
To the best of my knowledge, this keytag discovery has no immediate<br>
security implication and it can simply be regarded as a DNSSEC fun fact.<br>
Replacing the keytag computation function by another hashing function<br>
should be possible, as this value is opaque, but it is probably not<br>
worth the effort.<br>
<br>
Cheers,<br>
Florian Maury<br>
ANSSI<br>
<br>
[1] <a href="http://viccuad.me/blog/urandom-vs-random-for-dummies/" rel="noreferrer" target="_blank">http://viccuad.me/blog/urandom-vs-random-for-dummies/</a> lists a number<br>
of references of people also saying urandom is just fine.<br>
[2]<br>
<a href="https://blog.cloudflare.com/ensuring-randomness-with-linuxs-random-number-generator/" rel="noreferrer" target="_blank">https://blog.cloudflare.com/ensuring-randomness-with-linuxs-random-number-generator/</a><br>
<div class="HOEnZb"><div class="h5">_______________________________________________<br>
dns-operations mailing list<br>
<a href="mailto:dns-operations@lists.dns-oarc.net">dns-operations@lists.dns-oarc.net</a><br>
<a href="https://lists.dns-oarc.net/mailman/listinfo/dns-operations
dns-jobs" rel="noreferrer" target="_blank">https://lists.dns-oarc.net/mailman/listinfo/dns-operations<br>
dns-jobs</a> mailing list<br>
<a href="https://lists.dns-oarc.net/mailman/listinfo/dns-jobs" rel="noreferrer" target="_blank">https://lists.dns-oarc.net/mailman/listinfo/dns-jobs</a></div></div></blockquote></div><br></div>