Amit Klein has been looking into pseudo-random number generators (PRNG) again. He
has found a number of problems in the algorithms that make it easier to
guess the next number generated. Much like his earlier work on Berkeley
Internet Name Daemon (BIND), Klein found that with a small amount of
traffic, predicting the next DNS transaction ID or IP fragmentation ID is
possible. Anything that uses random numbers for security purposes—as
opposed to, say, choosing which fortune to
deliver—needs to ensure that their random numbers are
In his report,
Klein looks at a specific algorithm that has been implemented, with slight
variations, in multiple places. It was introduced into OpenBSD in 1997 to
randomize two 16-bit IDs to protect against predictability. Prior
to that, both DNS transaction IDs and IP fragmentation IDs were essentially
just incrementing counters. Various attacks, like idle scanning and DNS cache
poisoning were possible because those IDs could be predicted.
The OpenBSD PRNG algorithm was then used in their BIND 9
implementation, replacing the solution that Internet Systems Consortium
(ISC)—maintainer of BIND—had used. ISC added a random number
for the 16-bit DNS transaction ID, instead of an incrementing counter, as
part of BIND 9. Klein's earlier work found problems with that
PRNG—avoided by the OpenBSD version—leading to a certain
amount of smugness
on the part of the OpenBSD folks.
It is clear that the OpenBSD algorithm is better than the one ISC
introduced in BIND 9, but Klein was still able to find ways to break it.
The method requires much more computation than was needed to crack BIND 9
transaction IDs, roughly six minutes of computation on a fairly high-end
processor. Klein presents various ideas to parallelize the algorithm for
multi-core or multi-processor computation that could bring that number way
down. So, there is no working exploit available, but it is well
within the grasp; a determined attacker could make use of the techniques to
poison the cache of OpenBSD servers.
In addition, Klein found ways to exploit the IP fragmentation ID
predictability to do idle scanning, host operating system fingerprinting,
and other kinds of information leaks; it may also be possible to inject an
attacker-controlled packet into a TCP/IP connection, called a blind data
injection. The belief in the strength of the OpenBSD PRNG made it an attractive
option for others in the BSD family to adopt. NetBSD, FreeBSD, and
DragonFly BSD all adopted a variant of the algorithm for the IP
fragmentation ID, as did the FreeBSD-derived Mac OS X.
It should be noted that only OpenBSD and Mac OS X enable the fragmentation
ID randomization by default, the others have a setting for it, but their
default behavior is sequential IDs (i.e. id++) which is clearly even easier
to predict. The security team for each of the OSes had a fairly
predictable response, with one notable exception. NetBSD, FreeBSD, and DragonFly
BSD all changed the PRNG algorithm for less predictability; Apple claimed
to be working on the problem but could not provide a timeline for a fix.
The exceptional response came from OpenBSD, who are "completely
uninterested in the problem," according to an email from the OpenBSD
coordinator (presumably Theo de Raadt) that Klein quotes. The email goes
on to say that the problem is "completely irrelevant in the real world."
This kind of bluster is surprising from the OS that prides itself on
security; it was, after all, the first to introduce randomization of these
IDs. It may be that exploiting the predictability is hard to do, but
Klein's techniques clearly reduce the search space drastically which is not
what you want from a PRNG. The other BSDs found it important enough to
change, what does OpenBSD know that they don't?
It would be foolish for Linux users to write this off as a "BSD
problem"—though the random numbers used for IP fragmentation IDs by
Linux are considered to be cryptographically strong—because there
very well may be problems elsewhere in Linux or the applications that are
typically run on it. We are not immune to making mistakes, so all uses of
random numbers should be scrutinized. New development needs to remember
these lessons of the past as well, so that we can avoid this kind of
problem in the future.
to post comments)