<div dir="ltr"><br><br>On Thu, Jan 17, 2019 at 9:41 PM Viktor Dukhovni <<a href="mailto:ietf-dane@dukhovni.org">ietf-dane@dukhovni.org</a>> wrote:<br>><br>> On Fri, Jan 18, 2019 at 06:39:49AM +1100, Mark Andrews wrote:<br>><br>> > > Or is that "a million to one" shot?<br>> ><br>> > Or should that be a 65536 to 1 shot?<br>><br>> Actually for RSA keys, the key tag space is noticeably smaller.<br>> The key tag is essentially the key reduced modulo 65535, but since<br>> the key is co-prime to 65535, which factors as 3 * 5 * 17 * 257,<br>> there would be only ~16384 different ids, but because the key tag<br>> algorithm does not fold in the carry bits from the last addition<br>> we end up with 32768 possible tag values for RSA.<br>><br>> However, if the RSA keys are generated with OpenSSL, the two primes<br>> factors are both 2 mod 3 (avoiding 3 as a factor of (p-1) and (q-1)),<br>> but then the modulus is 1 mod 3, which takes the range back down<br>> 16392 different tags (with a slightly uneven distribution).<br><br><div><br>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 :-))<br><br>OpenSSL generates primes using:<br>static int probable_prime(BIGNUM *rnd, int bits)<br>which calls<br>BN_priv_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)<br>from  crypto/bn/bn_prime.c<br><br><a href="https://www.openssl.org/docs/manmaster/man3/BN_priv_rand.html">https://www.openssl.org/docs/manmaster/man3/BN_priv_rand.html</a> tells us:<br>"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."<br><br>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:<br><a href="https://www.kumari.net/images/stories/RSA_Primes/modulus_OpenSSL.png">https://www.kumari.net/images/stories/RSA_Primes/modulus_OpenSSL.png</a><br>while for mbedTLS which doesn't have this optimization it looks like:<br><a href="https://www.kumari.net/images/stories/RSA_Primes/modulus_mbedTLS_stock.png">https://www.kumari.net/images/stories/RSA_Primes/modulus_mbedTLS_stock.png</a><br><br>For interest, the P and Q look for OpenSSL look like (note the X axis):<br><a href="https://www.kumari.net/images/stories/RSA_Primes/figure_openssl_primes.png">https://www.kumari.net/images/stories/RSA_Primes/figure_openssl_primes.png</a><br><br>More detail / a very conversational writeup: <a href="https://www.kumari.net/index.php/random/99-implementation-differences-in-n-bit-rsa-keys">https://www.kumari.net/index.php/random/99-implementation-differences-in-n-bit-rsa-keys</a><br><br>W<br> <br>><br>><br>> The key tag algorithm is an unfortunate design choice for representing<br>> RSA keys.<br>><br>> --<br>>         Viktor.<br>> _______________________________________________<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">https://lists.dns-oarc.net/mailman/listinfo/dns-operations</a><br>> dns-operations mailing list<br>> <a href="https://lists.dns-oarc.net/mailman/listinfo/dns-operations">https://lists.dns-oarc.net/mailman/listinfo/dns-operations</a><br><br><br><br>--<br>I don't think the execution is relevant when it was obviously a bad idea in the first place.<br>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.<br>   ---maf</div></div>