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

[bert hubert]

On Sun, Nov 29, 2015 at 11:20:52PM +0000, Roy Arends 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.

Hi Roy,

http://imgur.com/oWtVuqf shows that after 200k attempts you should have hit
nearly 65k tags.

And in fact, http://imgur.com/S09btiw shows that you should hit 16k within
20k attempts.

This all given that randomly generated keys generate randomly distributed
tags, which seems to be a reasonable assumption.

I'm ashamed to admit that a quick search did not bring back to mind the
right formulas for actually calculating this distribution. But here is some
C++ 2011 which does the job in a second:

#include <bitset>
#include <iostream>
using namespace std;

int main()
{
  int totset=0;
  bitset<65535> s;
  
  for(int tries=0;tries < 1000000; ++tries) {
    auto cand = random() % 65535;
    if(!s[cand]) {
      ++totset;
      s[cand]=true;
    }
    cout<<tries<<'\t'<<totset<<'\n';
  }
}

And "inb4" /dev/urandom, I know this is the system random library. Also,
'brew' gnuplot has a horrible color scheme.
	
	Bert


> 
> 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.
> 
> 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.
> 
> Anyone able (willing) to explain the math, please?
> 
> Roy
> 
> (*) 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
>