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

[Viktor Dukhovni]

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).

The key tag algorithm is an unfortunate design choice for representing
RSA keys.

-- 
	Viktor.