[dns-operations] a maximum of about 16K possible DNSSEC keytags?

[Roy Arends]

Florian and Jerome, this is freakin’ awesome. Thanks Gents!

I’ve add some stuff inline.

On 2 Dec 2015, at 9:16, Florian Maury wrote:

> As it happens, the function is equivalent to an addition modulo 
> (2^16)-1.

This observation puzzled me at first, but there is a very good reference 
on that particular statement:

https://tools.ietf.org/html/draft-heikkila-ip-checksum-00

Section 3 and further

> Since the RSA modulus is the result of a multiplication of two primes,
> that cannot, by definition, be divided by the factors of 2^16-1 
> (namely
> 3, 5, 17, and 257), the RSA modulus cannot be divided by these 
> factors.

Indeed.

> This can be summarized by the following relation: the keytag is
> congruent to the (RSA modulus + a constant) modulo 65535. The constant
> is dependant of the flags, protocol, algorithm and the public exponent
> as encoded in the RDATA field.

Indeed.

> The fact that N cannot by divided by 3, 5, 17 and 257 means that there
> are 2 * 4 * 16 * 256 values possible for the keytag of a RSA key =>
> 32768 values, as Peter discovered empirically.

This took me a second.

N mod 3 gives 2 possible values
N mod 5 gives 4 possible values
N mod 17 gives 16 possible values
N mod 257 gives 256 possible values

any combination of those (2*4*16*256) allows for 32768 different values 
:-) right?

Okay!

But I got 16384.

> Among these 32768 values, there remain some biases. Namely, 
> empirically
> 93% of RSA moduli are congruent to 1 (mod 3) and only 7% are congruent
> to 2 (mod 3). This is probably a consequence of the prime number
> generation procedure (for example, some implementations restrict to
> primes congruent to 1 (mod 6) for speed reasons, which has a very
> reasonable impact on security).

Ah indeed. it seems that openssl avoids primes that are congruent to 1 
modulo 3, so that will cause the available solution space to be reduced 
to 4*16*256 == 16384

HURRAAAAAHHHHH!

> To the best of my knowledge, this keytag discovery has no immediate
> security implication and it can simply be regarded as a DNSSEC fun 
> fact.

It helps a bit when there is more than one key available, but yeah, no 
immediate implication.

> Replacing the keytag computation function by another hashing function
> should be possible, as this value is opaque, but it is probably not
> worth the effort.

Nah, not worth it. That would mean we would need to roll the key 
type…. again…. plus the signalling, plus the versioning.

Thanks again Florian and Jerome!

This was fun.

Roy