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

[Mark Andrews]

> On 18 Jan 2019, at 1:32 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).
> 
> The key tag algorithm is an unfortunate design choice for representing
> RSA keys.

Not really.  You just need to be a able to quickly select between the
the keys in the DNSKEY RRset. There is enough space for this to be
a non-issue.

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

-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742              INTERNET: marka at isc.org