Weekly Edition
Return to the Security page
| |||||||||||||
The dangers of weak random numbersAmit 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. (Log in to post comments)
The dangers of weak random numbers Posted Feb 21, 2008 5:34 UTC (Thu) by cventers (guest, #31465) [Link] One place I've seen atrocious PRNG use is in web applications. Web app developers often roll their own salt generators, or session token generators, or random password generators... then rely on a libc rand seeded by the process ID, for example, to generate far too little entropy with far too little quality. One of the things I find unfortunate is when a particular class of security problem (say, XSRF) is well known but ignored by so many developers. Especially when you find those problems on a library level.
The dangers of weak random numbers Posted Feb 21, 2008 7:48 UTC (Thu) by nix (subscriber, #2304) [Link] One of my past workplaces used a random number generator seeded by an unintentional buffer read-overrun for years before anyone noticed. (Given that it was also deriving AES keys from that excellent source of secrets, getuid(), expecting any sort of randomness tests to be performed on the RNG was perhaps expecting too much.)
The dangers of weak random numbers Posted Feb 21, 2008 14:38 UTC (Thu) by liljencrantz (subscriber, #28458) [Link] In all fairness, I think one should mostly fault the libc developers for implementing a shoddy default rng, not the web developers for using it. It is in my opinion a reasonable assumption (Though I know it is often not a correct assumption) that the platforms default rng should generate numbers with reasonable entropy.
The dangers of weak random numbers Posted Feb 21, 2008 17:28 UTC (Thu) by bronson (subscriber, #4806) [Link] I disagree. Cryptographically strong random numbers take a lot more CPU time to compute (assuming you don't have a HW accelerator). Since the vast majority of C programs don't need strong random numbers anyway, why should we waste all that energy? In addition, creating strong random numbers is hard! The proper algorithm strongly depends on the problem you're trying to solve. The libc developers can't possibly know why you want these numbers so they punted. And I think they were right. Anyone who believes that there is a one-size-fits-all PRNG algorithm has never tried to write one. :)
The dangers of weak random numbers Posted Feb 21, 2008 21:12 UTC (Thu) by liljencrantz (subscriber, #28458) [Link] It's true that the libc developers can't know why you want a random number, it's definitely also true that one size does not fit all. But the libc implementation is the worst kind of compromise as it is neither fast nor secure. If you want lots of numbers, you will get a lot better performance out of e.g. Mersenne twister, and if you want something even remotely secure, you need to use a special purpose cryptographic algorithm. As near as I can tell, the only situation you would ever want to use the libc random number generator is when you really don't care about either performace or security. Couldn't they at least have done one of the two?
The dangers of weak random numbers Posted Feb 21, 2008 23:06 UTC (Thu) by bronson (subscriber, #4806) [Link] That's a good point. I can't think of a single thing the libc implementation excels at. I understand why they punted on security, but that's no reason to punt on everything!
The dangers of weak random numbers ... 10 years on Posted Feb 21, 2008 8:47 UTC (Thu) by stuart (subscriber, #623) [Link] So the 1997 OpenBSD modifications to the id generation code stood the test of time for over 10 years. In today's world, that's impressive. It's unsurprising that someone has eventually found a way of exploiting weakness in the code. I find it a little strange that the OpenBSD team *appear* to be sticking their heads in the sand but knowing them, they'll quietly fix the issues sooner or later once they deem them to be real. Enjoyable article though -- thanks. Now if only openntpd and ISC ntpd could not suck.
The dangers of weak random numbers Posted Feb 21, 2008 14:36 UTC (Thu) by kirkengaard (subscriber, #15022) [Link] The more I learn, the more I find that it's dangerous to have non-cryptographically-strong RNGs. As you say, for anything more than picking which fortune entry to display, i.e. for anything greater than toy problems, you very quickly rise into areas where exploitation of predictability is problematic. People get used to practicing with a "sufficiently random" idea, and it leaks into implementations in areas where it becomes a problem. Communication is an access point; memory mapping is an access point; program input is an access point; data storage is an access point; data output is an access point. As to the OpenBSD response, this shouldn't be terribly surprising, given that having a name for security becomes momentum. We've seen them brush security problems under the table before, for love of keeping that "0 holes" statistic alive.
The dangers of weak random numbers Posted Feb 21, 2008 17:51 UTC (Thu) by bronson (subscriber, #4806) [Link] OK, what RNG would you choose and why? Please quantify. I'm just kidding -- a proper answer to this question would require writing a book. And endless debate. And the answer would change every five years. Ultimately, if you need soemthing done correctly to the last bit, would you really trust all the libcs in the world? My only problem with libc's rand() is the name. It's a flat out lie! No wonder it's confusing. It should have been called "prand" or "living_in_sin_rand" or something.
The dangers of weak random numbers Posted Feb 22, 2008 12:17 UTC (Fri) by jzbiciak (✭ supporter ✭, #5246) [Link] What I don't understand is why hardware RNGs aren't more common. A number of embedded CPUs contain them, but not the bulk of mainstream CPUs. They take up so little silicon compared to everything else, and provide such high quality results that they really ought to be ubiquitous. Sure, if you introduced them on mainstream CPUs today, it'd still be 5 years before they were everywhere, so you'd still have to implement other techniques in the meantime. But, those could be a bridge to a better overall solution rather than a road to more hand wringing in 5 or 10 years when somebody finds the next weakness.
The dangers of weak random numbers Posted Feb 22, 2008 2:19 UTC (Fri) by jschrod (subscriber, #1646) [Link] This also depends on the purpose of your RNG usage. Just this week, for example, I needed one to select a pseudo-random set of documents (out of 400,000) to pass them to human reviewers for inspection. For such a task, I don't care at all if it's cryptographically-strong or not, I simply use libc's rand(). I don't even care that it's very slow, getting the data for these 400,000 documents out of the database and generating/formatting them already needed enough time...
The dangers of weak random numbers Posted Feb 21, 2008 22:33 UTC (Thu) by ortalo (subscriber, #4654) [Link] As a fellow reader, I would really be interested in knowing why OpenBSD's team (either Theo de Raadt or someone else) did not react much (technically speaking I mean). Wouldn't that be a nice occasion for a "spicy" interview? Well, I have other less serious conjectures. That security page deserves more animation: vulnerability, patch, vulnerability, patch, ... It starts to get boring. (I acknowledge the offending software changes regularly and brings some diversity.) Hey, maybe that's why they did not react: what about keeping a vulnerability this time? This one would be a nice candidate IMHO. In the same vein, maybe they are preparing the honeypot-ready-by-default-killer-feature?
|
|||||||||||||