[dns-operations] [Ext] real world keytag collision example

[Warren Kumari]

On Thu, Jan 17, 2019 at 9:41 PM Viktor Dukhovni <ietf-dane at dukhovni.org>
wrote:
>
> On Fri, Jan 18, 2019 at 06:39:49AM +1100, Mark Andrews wrote:
>
> > > Or is that "a million to one" shot?
> >
> > Or should that be a 65536 to 1 shot?
>
> Actually for RSA keys, the key tag space is noticeably smaller.
> The key tag is essentially the key reduced modulo 65535, but since
> the key is co-prime to 65535, which factors as 3 * 5 * 17 * 257,
> there would be only ~16384 different ids, but because the key tag
> algorithm does not fold in the carry bits from the last addition
> we end up with 32768 possible tag values for RSA.
>
> However, if the RSA keys are generated with OpenSSL, the two primes
> factors are both 2 mod 3 (avoiding 3 as a factor of (p-1) and (q-1)),
> but then the modulus is 1 mod 3, which takes the range back down
> 16392 different tags (with a slightly uneven distribution).


Actually, I **think** it is even smaller than that -- both primes will
always have their top bits set (this might be a property of what you said
above, but my eyes glazed over while trying to work it out :-))

OpenSSL generates primes using:
static int probable_prime(BIGNUM *rnd, int bits)
which calls
BN_priv_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)
from  crypto/bn/bn_prime.c

https://www.openssl.org/docs/manmaster/man3/BN_priv_rand.html tells us:
"The top parameters specifies requirements on the most significant bit of
the generated number. ... If it is BN_RAND_TOP_TWO, the two most
significant bits of the number will be set to 1, so that the product of two
such random numbers will always have 2*bits length."

I think that this is so that one doesn't have to worry about underflow when
doing P*Q (you want the product of P and Q to be N bits - you can guarantee
that by making sure that the top bits are set) -- anyway, it means that the
distribution of moduli for OpenSSL (and GnuTLS) looks like:
https://www.kumari.net/images/stories/RSA_Primes/modulus_OpenSSL.png
while for mbedTLS which doesn't have this optimization it looks like:
https://www.kumari.net/images/stories/RSA_Primes/modulus_mbedTLS_stock.png

For interest, the P and Q look for OpenSSL look like (note the X axis):
https://www.kumari.net/images/stories/RSA_Primes/figure_openssl_primes.png

More detail / a very conversational writeup:
https://www.kumari.net/index.php/random/99-implementation-differences-in-n-bit-rsa-keys

W

>
>
> The key tag algorithm is an unfortunate design choice for representing
> RSA keys.
>
> --
>         Viktor.
> _______________________________________________
> dns-operations mailing list
> dns-operations at lists.dns-oarc.net
> https://lists.dns-oarc.net/mailman/listinfo/dns-operations
> dns-operations mailing list
> https://lists.dns-oarc.net/mailman/listinfo/dns-operations



--
I don't think the execution is relevant when it was obviously a bad idea in
the first place.
This is like putting rabid weasels in your pants, and later expressing
regret at having chosen those particular rabid weasels and that pair of
pants.
   ---maf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.dns-oarc.net/pipermail/dns-operations/attachments/20190118/fba0d21e/attachment.html>