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

Warren Kumari warren at kumari.net
Fri Jan 18 14:30:16 UTC 2019

On Thu, Jan 17, 2019 at 9:41 PM Viktor Dukhovni <ietf-dane at dukhovni.org>
> 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:
while for mbedTLS which doesn't have this optimization it looks like:

For interest, the P and Q look for OpenSSL look like (note the X axis):

More detail / a very conversational writeup:


> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.dns-oarc.net/pipermail/dns-operations/attachments/20190118/fba0d21e/attachment.html>

More information about the dns-operations mailing list