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

[Richard Lamb]

Thank you very much Florian for this detailed explanation ...
and to Roy for bringing up this subject and "kicking the tires" of his own
car.
Together, this helps me sleep better at night.

-Rick


On Wed, Dec 2, 2015 at 1:16 AM, Florian Maury <florian.maury at ssi.gouv.fr>
wrote:

> 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/
> _______________________________________________
> dns-operations mailing list
> dns-operations at lists.dns-oarc.net
> https://lists.dns-oarc.net/mailman/listinfo/dns-operations
> dns-jobs mailing list
> https://lists.dns-oarc.net/mailman/listinfo/dns-jobs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.dns-oarc.net/pipermail/dns-operations/attachments/20151202/f54d26d5/attachment.html>