[dns-operations] Why non-repeating transaction IDs?

Paul Vixie paul at vix.com
Thu Nov 1 17:15:19 UTC 2007

> >> What badness happens when there is a collision?
> >> Why do you need to avoid it?
> >
> > i'm using a per-socket array to demux responses.
> I don't think this answers my question.  Do you use the ID as an array
> index?  In this case, you can still get the next random number if the
> slot is already taken.  You can attach a list of pending queries to the
> bucket, too.

i don't, though.  (this is in a non-BIND recursive server i once wrote.)
the cost of coping with theoretically possible large numbers of collisions
probably entails a hash table per QID in that design.  it's much easier in
my opinion to pick an upstream socket (one of 16 in my case) that has at
least one open QID slot, and then pick an unused QID at random, using a
linear scan if there are too many collisions.  this gives a bernstein-like
effective 20-bit QID, runs like a bat out of hell in the average case, and
is simple and auditable even for corner cases.

> Sorry, I still don't get it why you significantly increase risk by not
> using a PRNG which is accepted to be at least halfway cryptographically
> strong (periodically rekeyed RC4, with the first few dozen bytes
> discarded, for instance).

i'm no crypto guy.  others here will have to comment on that aspect.

More information about the dns-operations mailing list