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

[Marek Vavruša]

Disclaimer: I'm hardly an expert on hash functions (heck I don't even
like them), just an implementer.

On 30 November 2015 at 00:20, Roy Arends <roy at dnss.ec> wrote:
> I am only able to generate about 16K unique keytags for a 2K RSASHA256 KSK
> (*), even after generating hundreds of thousands of keys in a loop.
>
> I expected the entire 16 bit keytag space used (i.e. 64K keytags), as the
> keytag is simply the sum of the DNSKEY RDATA (as a series of two byte
> values) with the high two bytes of the resulting 32 bit value added to the
> low 2 byte without carry.

That's a reasonable expectation, alas hash functions have collisions.
If you have one hash in 16 bit space, then the probability of being
unique is 1 (as there is nothing to collide with),
if you add another one, the chance is (2^16 - 1) / (2^16), for third
the chance is previous multiplied
with (2^16 - 2) / 2^16, ... if you do the math, it's very unlikely
that 2K hashes (keytags) will be unique within 2^16 possible values
(presuming the hash function is unbiased, which isn't the case).

The RFC4034 describes something resembling IP checksum and even says
"almost but not completely identical to the familiar ones-complement
checksum".
Funnily, there's no complement in the described algorithm. It's a
simple sum of bytes with final mixing, so it's useful for, well ...
checksumming and not hashing,
as it guarantees nothing about collisions. It's prone to a lot of
stuff - position changes [1], zeroes [2] and no avalanche effect.
Using it for pseudo-unique identifiers is unfortunate, but it's
sufficient to: check if there's such key at all (no false negatives),
distinguish in a small set of keys.
It's not okay to: distinguish in large set of keys, expect any good properties.

> Since the RDATA contains 256 bytes of modulus (a result of multiplying two
> randomly generated 128 byte primes), I thought it had a fair amount of
> entropy so that the resulting key tags would be nicely distributed.
>
> Apparently not.

That depends on the source of entropy and RNG quality. If the RNG used
to generate keys has low entropy then the generated keys will have low
entropy as well.
A weak hash function doesn't help here, but the number of unique
keytags should rise nevertheless (the quality of the hash functions
determines how quickly),
so I suspect the weak entropy of the key rdata here.

> Anyone able (willing) to explain the math, please?
>
> Roy

Hope it's any help.

Marek

[1]: e.g. "\x1\x2\x3" csum is same as "\x3\x2\x1"
[2]: e.g. "\x1\x2\x3" csum is same as "\x1\x2\x2\x0"

> (*) The same is true of a 512 bit RSASHA256 ZSK, though those are a
> different set of 16K unique keytags.
>
> _______________________________________________
> dns-operations mailing list
> dns-operations at lists.dns-oarc.net
> https://lists.dns-oarc.net/mailman/listinfo/dns-operations
> dns-jobs mailing list
> https://lists.dns-oarc.net/mailman/listinfo/dns-jobs