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

[Marek Vavruša]

On 30 November 2015 at 18:39, bert hubert <bert.hubert at netherlabs.nl> wrote:
> 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.

That's a reasonable assumption, but keytag calculation function
guarantees no such thing.

> 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
>>
> _______________________________________________
> 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