Date: Thu, 01 Nov 2007 13:51:56 -0600
From: Theo de Raadt <deraadt@....openbsd.org>
To: ntn@...workontap.com
Cc: bugtraq@...urityfocus.com
Subject: Re: Comments re ISC's announcement on bind9 security 

> Given the extremely small amount of space for randomization (16-bit
> query ID's) does a cryptographically strong PRNG really make
> difference?

For a couple of decades the original algorithm was simply id++.  Yes,
it makes a difference to use a slightly more sophisticated and
essentially "resource-free" algorithm, at least against some of the
potential "attacks".

Not all attacks stand on their own.  The ID behaviour is typically
part of the problem space that an attacker has to deal with when some
other DNS problem is being attacked.

The main problem space people are talking regards DNS servers.  But
the same (or similar) algorithm can also be used in resolver libraries
(ie. inside libc) to deal with other (different or similar...)
potential "attacks".

The algorithmic complexity of going from id++ to something more
sophisticated places no great burden on anyone... the machines can
handle it... so why not just do it.  We don't need an uber-secure
PRNG.... since it is only a 16 bit exposed space.  But it is good if
it has a few other "characteristics".

> Aside from stopping an easy prediction, doesn't it just generate a
> little extra work for a determined malicious individual?

The worst case for the attacker requires 65536 responses instead of 1.

Some style of attacks can require less.

If the computation / network costs of predicting a 16-bit PRNG is
higher than the cost of simply slamming with 65536 packets, attackers
will use the latter method.

But there are always mitigating factors...  Maybe an attacker can't
generate that much traffic, or maybe he doesn't want to because he can
be spotted.. etc.  There are other factors that select against doing
DNS attacks like this, such as the various any-cast architecture some
servers are setup with.

It _is_ a 16 bit ID space, and that is not fixable inside the strict
DNS protocol, but that still leaves us room to do the best job with
what we have, rather than do nothing at all.  Some people appear to be
on the edge of arguing that we do nothing.

> Seems to be a moot point to me---whether the PRNG is
> cryptographically weak or not because of the small sequence number
> space. 

Around 10 years ago the PRNG used was id++.

I still think that the algorithm we invented as a group with Niels
Provos, David Mazieres, some researchers at Core SDI, and further
improved by David Wagner is better than what ISC is shipping.  We've
been using our algorithm for 10+ years, too.  Not just for DNS ID's
but also for the related problem of IP ID's.  Every packet our
machines generate hits the same algorithm, to help a bit with the IP
ID ++ issues.

Relative to the new ISC code... ours is not worse.  But it is simpler,
and non-heuristical in nature.  It is just plainly mathematical,
designed by math nerds who we asked to help.  And it is a lot less
code to do the same thing.

But perhaps it doesn't matter that much.  At least we are not back in the
days of id++ on all systems.  Though I suspect there are still lots of
DNS libraries and other similar subsystems.........

Powered by blists - more mailing lists