Subject: Re: randomid(3)
To: Jun-ichiro itojun Hagino <itojun@itojun.org>
From: Robert Elz <kre@munnari.OZ.AU>
List: tech-userlevel
Date: 09/11/2003 20:47:50
    Date:        Thu, 11 Sep 2003 08:15:43 +0900 (JST)
    From:        itojun@itojun.org (Jun-ichiro itojun Hagino)
    Message-ID:  <20030910231543.E7E8E8F@coconut.itojun.org>

  | 	i would recommend you to look at BIND9 source, which randomizes
  | 	DNS id field just like ours.

Maybe you'd like to point out just where to look, I've taken a quick
glance though its code, and can't find a reference to "arc4" anywhere
(not even in the dnssec code).   ("rc4" exists, but as the suffix of the
identifier "notifysrc4" which I'm pretty sure has nothing to do with
the arc4random() function "just like ours").

A few things to be aware of - nowhere did I say that there is any
problem with using a random number as the ID - any number is OK as
long as it serves its purpose, what matters is how much effort is
spent generating it, and what the benefit of that is.

I do see the ISC code using rand() to generate random numbers - there's
no problem with that for this purpose (I didn't look hard enough to
see if they're using the rand() results this way, but as rand() was
a 16 bit "random" number generator, and the id field is 16 bits, that
would be plausible).   rand() is easily cheap enough for the purpose,
and for a libc resolver, also easily good enough (id++ is good enough).

I also see the bind9 version of dig uses random() for the purpose - for
dig that's cheap enough (for libc, random() might be going just a bit
overboard in the cost/benefit stakes) - but I have no idea why exactly.
The version of dig that I prefer to use simply uses a constant as the
ID - it only ever sends one query (at a time), so has no need of the
ID to help it match the response with the query.   Anyone with the
ability to guess just when I am going to use dig, what server I am going
to query, and what question I am going to ask, is welcome to send me
a spoofed reply...    If they "guess" by packet sniffing, the id
value is useless as any kind of protection, so they have to use some
other method or they're not relevant.

I also see in the bind9 code (9.3 snapshot - the most recent from pkgsrc)
there's a resolver that uses "++" to generate id's, which is also perfectly
adequate for a resolver (whether that resolver code is used by anything
I didn't spend time to discover).

Do note here that there's a big difference between what is a sensible
thing for a libc stub resolver to do, and what is sensible for a DNS
cache to do - the attacks they are likely to be subject to, and the
vulnerabilities that they have, and the nature of their workload (the cache
sends MANY queries, and initialises rarely, most instances of the libc
resolver have an initialisition :: use ratio closer to 1::1)

But do point me at a part of the bind9 libc resolver code which is
using a random number generator with anything like the strength, and
computational complexity, of the one you added to NetBSD's resolver,
and I'll have no hesitation in talking to its authors and requesting
that they remove it.   But I have to be able to find the code in question
in order to do that, and since you apparently have, I'm sure you'll be
willing to save me the effort.

kre