User: Password:
Subscribe / Log in / New account


The dangers of weak random numbers

By Jake Edge
February 20, 2008

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 cryptographically strong.

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.

Comments (12 posted)

New vulnerabilities

acroread: multiple vulnerabilities

Package(s):acroread CVE #(s):CVE-2008-0655 CVE-2008-0667 CVE-2008-0726
Created:February 18, 2008 Updated:March 3, 2008

From the SUSE advisory:

CVE-2008-0655: Multiple unspecified vulnerabilities in Adobe Reader and Acrobat before 8.1.2 have unknown impact and attack vectors.

CVE-2008-0667: The DOC.print function in the Adobe JavaScript API, as used by Adobe Acrobat and Reader before 8.1.2, allows remote attackers to configure silent non-interactive printing, and trigger the printing of an arbitrary number of copies of a document.

CVE-2008-0726: Integer overflow in Adobe Reader and Acrobat 8.1.1 and earlier allows remote attackers to execute arbitrary code via crafted arguments to the printSepsWithParams, which triggers memory corruption.

Gentoo 200803-01:04 acroread 2008-03-02
SuSE SUSE-SA:2008:009 acroread 2008-02-18
Red Hat RHSA-2008:0144-01 acroread 2008-02-22

Comments (none posted)

clamav: arbitrary file overwrite

Package(s):clamav CVE #(s):CVE-2007-6595
Created:February 18, 2008 Updated:August 8, 2008

From the CVE entry: ClamAV 0.92 allows local users to overwrite arbitrary files via a symlink attack on (1) temporary files in the cli_gentempfd function in libclamav/others.c or on (2) .ascii files in sigtool, when utf16-decode is enabled.

Gentoo 200808-07 clamav 2008-08-08
SuSE SUSE-SA:2008:024 clamav 2008-04-24
Mandriva MDVSA-2008:088 clamav 2007-04-17
Debian DSA-1497-1 clamav 2008-02-16

Comments (4 posted)

libimager-perl: buffer overflow

Package(s):libimager-perl CVE #(s):CVE-2007-2459
Created:February 20, 2008 Updated:February 20, 2008
Description: A buffer overflow in the read_4bit_bmp function in bmp.c in Imager 0.56 and earlier allows remote attackers to cause a denial of service (application crash) and possibly execute arbitrary code via 4-bit/pixel BMP files. NOTE: the provenance of this information is unknown; the details are obtained solely from third party information.
Debian DSA-1498-1 libimager-perl 2008-02-19

Comments (none posted)

pcre: buffer overflow

Package(s):pcre CVE #(s):CVE-2008-0674
Created:February 19, 2008 Updated:November 17, 2008
Description: A buffer overflow caused by a character class containing a very large number of characters with codepoints greater than 255 (in UTF-8 mode) may affect usages of pcre, when regular expressions from untrusted sources are compiled.
Gentoo 200811-05 php 2008-11-16
rPath rPSA-2008-0176-1 php 2008-05-23
Gentoo 200803-24:02 libpcre 2008-03-17
Fedora FEDORA-2008-1842 pcre 2008-03-06
rPath rPSA-2008-0086-1 pcre 2008-02-28
Mandriva MDVSA-2008:053 pcre 2007-02-28
Debian DSA-1499-1 pcre3 2008-02-19
SuSE SUSE-SR:2008:004 xdg-utils, clamav, wireshark, pcre 2008-02-22
Ubuntu USN-581-1 pcre3 2008-02-21
Fedora FEDORA-2008-1783 pcre 2008-02-19

Comments (none posted)

php: regression in PHP 4.4.7

Package(s):php CVE #(s):
Created:February 20, 2008 Updated:February 20, 2008
Description: PHP 4 has a GD related bug in version 4.4.7. This has been fixed in PHP5 and is fixed in PHP 4.4.8.
Slackware SSA:2008-045-03 php 2008-02-15

Comments (none posted)

Page editor: Jake Edge
Next page: Kernel development>>

Copyright © 2008, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds