[dns-operations] a maximum of about 16K possible DNSSEC keytags?
bert hubert
bert.hubert at netherlabs.nl
Mon Nov 30 17:39:55 UTC 2015
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
>
More information about the dns-operations
mailing list