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

Warren Kumari warren at kumari.net
Mon Nov 30 16:45:51 UTC 2015

Nah, I *think* that that is an acceptable number -- this is an almost
perfect example of a birthday attack.

Birthday attacks are weird -- During discussions on the IEEE Mac
Randomization experiments I had a flaming row ^w^w polite disagreement with
Dan Harkins about the likelihood of collisions of multiple stations each
choose a MAC address at random. I asserted that if there were 24bits of
random space (>16million), 1000 machines each choosing an MAC address at
random would very seldom collide.

Turns out I was completely wrong -- there will be a collision once every
~34 times.
This was, um, surprising to me.

I ended up writing an appspot app to allow people to play with the numbers:

'm too lazy to redo the code to calculate in the opposite direction, but
with a 64K space (2^16), you only need 302 keys to have a >50% chance of a
collision, and things go rapidly downhill from there (as you fill in the

Birthday attacks are weird.

On Mon, Nov 30, 2015 at 11:25 AM Jim Reid <jim at rfc1035.com> wrote:

> On 30 Nov 2015, at 15:56, Warren Kumari <warren at kumari.net> wrote:
> > Currently I have generated 9209, and 7285 of them are unique.
> A 25% collision rate is nasty.
> Looks like your /dev/urandom is not much better than Dilbert's. :-)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.dns-oarc.net/pipermail/dns-operations/attachments/20151130/81104fac/attachment.html>

More information about the dns-operations mailing list