[PRNG is an abbreviation for “Pseudo-Random Number Generator”, a
key core component of the key-generation in any cryptographic library.]
A few people have already commented on the issue itself – Debian issued, in 2006, a version of their Linux build that contained a modified version of OpenSSL. The modification has been found to drastically reduce the randomness of the keys generated by OpenSSL on Debian Linux and any Linux derived from that build (such as Ubuntu, Edubuntu, Xubuntu, and any number of other buntus). Instead of being able to generate 1024-bit RSA keys that have a 1-in-2^1024 chance of being the same, the Debian build generated 1024-bit RSA keys that have a 1-in-2^15 chance of being the same (that’s 1 in 32,768).
Needless to say, that makes life really easy on a hacker who wants to pretend to be a server or a user who is identifed as the owner of one of these keys.
The fun comes when you go to http://metasploit.com/users/hdm/tools/debian-openssl/ and see what the change actually was that caused this. Debian fetched the source for OpenSSL, and found that Purify flagged a line as accessing uninitialised memory in the random number generator’s pre-seeding code.
I thought I’d state that slowly for dramatic effect.
If they’d bothered researching Purify and OpenSSL, they’d have found this:
Which states (in 2003, three years before Debian applied teh suck patch) “No, it’s fine – the problem is Purify and Valgrind assume all use of uninitialised data is inherently bad, whereas a PRNG implementation has nothing but positive (or more correctly, non-negative) things to say about the idea.”
So, Debian removed a source of random information used to generate the key. Silly Debian.
But there’s a further wrinkle to this.
If I understand HD Moore’s assertions correctly, this means that the sole sources of entropy (essentially, “randomness”) for the random numbers used to generate keys in Debian are:
[Okay, so that’s not strictly true in all cases – there are other ways to initialise randomness, but these two are the fallback position – the minimum entropy that can be used to create a key. In the absence of a random number source, these are the two things that will be used to create randomness.]
If you compile C++ code using Microsoft’s Visual C++ compiler in DEBUG mode, or with the /GZ, /RTC1, or /RTCs flags, you are asking the compiler to automatically initialise all uninitialised memory to 0xcc. I’m sure there’s some similar behaviour on Linux compilers, because this aids with debugging accidental uses of uninitialised memory.
But what if you don’t set those flags?
It would be bad if “uninitialised memory” contained memory from other processes – previous processes that had owned memory but were now defunct – because that would potentially mean that your new process had access to secrets that it shouldn’t.
So, “uninitialised memory” has to be initialised to something, at least the first time it is accessed.
Is it really going to be initialised to random values? That would be such a huge waste of processor time – and anyway, we’re looking at this from the point of view of a cryptographic process, which needs to have strongly random numbers.
No, random would be bad. Perhaps in some situations, the memory will be filled with copies of ‘public’ data – environment variables, say. But most likely, because it’s a fast easy thing to do, uninitialised memory will be filled with zeroes.
Of course, after a few functions are called, and returned from, and after a few variables are created and go out of scope, the stack will contain values indicative of the course that the program has taken so far – it may look randomish, but it will probably vary very little, if any, from one execution of the program to another.
In the absence of a random number seed file, or a random number generator providing /dev/urand or /dev/random, then, an OpenSSL key is going to have a 1 in 32,768 chance of being the same as a key created on a similar build of OpenSSL – higher, if you consider that most PIDs fall in a smaller range.
So, here’s some lessons to learn about compiling other people’s cryptographic code:
This is one reason why I prefer to use Microsoft’s CryptoAPI, rather than libraries such as OpenSSL. There are others:
In fairness, there are reasons not to use CryptoAPI:
The lessons to learn from this episode are almost certainly not yet over. I expect someone to find in the next few weeks that OpenSSL with no extra source of entropy on some operating system or family of systems generates easily guessed keys, even using the “uninitialised memory” as entropy. I wait with ‘bated breath.