Debian and the OpenSSL PRNG

[PRNG is an abbreviation for “Pseudo-Random Number Generator”, a key core component of the key-generation in any cryptographic library.]

Warning: Choking HazardA 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.

So. They. Removed. The. Line.

I thought I’d state that slowly for dramatic effect.

If they’d bothered researching Purify and OpenSSL, they’d have found this:

http://rt.openssl.org/Ticket/Display.html?id=521&user=guest&pass=guest

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:

  1. The Process ID (from 1 to 32,767)
  2. The contents of an uninitialised area in the process’ memory
  3. uh… that’s it.

[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?

What does “uninitialised memory” contain?

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:

  1. Don’t ever compile cryptographic code in release mode, because you will optimize away lines that clear secrets from memory.
  2. Don’t ever compile cryptographic code in debug mode, because you will initialize memory that is expected to be uninitialised and random.
  3. Don’t ever modify cryptographic code, even if it throws up warnings. You don’t understand what you’re doing.
  4. Don’t ever compile cryptographic code, because you don’t know what you are doing.

Why I use CryptoAPI

This is one reason why I prefer to use Microsoft’s CryptoAPI, rather than libraries such as OpenSSL. There are others:

  1. It’s not my fault if something goes wrong with the crypto.
  2. The users will apply patches to the crypto, and I don’t have to go persuading my users to apply the patches.
  3. There’s a central place where administrators will expect to find crypto keys, and it’s well-protected.
  4. The documentation for CryptoAPI is far better than the documentation for OpenSSL, which is at best confusing, and at worst, non-existent.

In fairness, there are reasons not to use CryptoAPI:

  1. New algorithms are made available for new versions of Windows, and not backported readily to older versions. With a library you ship, you get to decide which version customers can run – unless someone else comes and installs another version.
  2. Microsoft’s documentation is better, but it’s still not perfect. Once in a while, it’s not even correct. At least if you have the source code, and are insanely motivated, you can find out what the truth of a matter is.

We’ll still be learning lessons for a while…

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.

9 Responses to Debian and the OpenSSL PRNG

  • Harry Johnston says:

    I don’t know this for a fact, but my understanding is that the line of code that was incorrectly removed was only using uninitialized data on the first iteration. On the remaining iterations it was adding various other sources of entropy.

  • alunj says:

    Other sources of entropy would have increased the number of possible keys, wouldn’t they?
    As I acknowledged in my article, there are other sources of entropy – a file containing a random seed, or the random device. However, the random device isn’t there on all machines, and a user may not care about creating a random seed file. In such base configurations, it appears, all you get is the PID and the uninitialised data.
    If there were more entropy than that, HD Moore’s keys wouldn’t work, would they?

  • Harry Johnston says:

    “Other sources of entropy would have increased the number of possible keys, wouldn’t they?”

    Originally, yes; but the code change in question prevented not only the uninitialized data from being included in the seed but also all the other sources of entropy included in the original algorithm (except the PID).

    I assume the code looked something like this, although of course not as obvious:

    char buffer[buf_size];

    while (some-condition) {

    insert-entropy-into-prng(&buffer);
    get-some-entropy(&buffer);

    }

    and the change made was equivalent to removing the call to insert-entropy-into-prng. (!)

    Once again, for emphasis – this is based on what I’ve previously read about the issue, I may have been misinformed or have misinterpreted it.

  • davidw says:

    You have the story wrong:

    The Debian guy commented out two lines of code. One of those directly added contents of an uninitialized buffer to the pool, stirring things up slightly.

    But he also commented out another line, with far more drastic consequences. It seems that there is a function in the code that provides the major source of randomness. The Debian guy also commented out the line of code that adds the output of this function to the pool.

    See

    http://www.links.org/?p=328

  • alunj says:

    You are right. I have the story wrong.
    There were two lines of code – one from the seed function, and one from the function that, as you say, adds entropy of the calling program’s choosing. The latter is still an issue – a program that encrypts using known values and a user’s chosen entropy is no good if it ignores the entropy.
    However, the part that’s the big deal here is the line in the “add random bytes to seed” function.
    So my description is wrong – instead of removing the small uninitialised buffer entropy only, the seed function removed all sources of entropy – even on machines with dedicated hardware random number generators!
    Every time a piece of code said “here’s some entropy to add to the seed to make it more random”, the function said “I’m not touching that, it might be uninitialised”.
    Contrary to my earlier assertion, then, if you generated a key on OpenSSL or any program that called OpenSSL, on a Debian Linux or derivative build, your keys are weak and must be regenerated.
    It’s unconscionable that someone would check in this code, and that noone of the “many eyeballs” noticed it.

  • Kieran says:

    From my reading the only source of entropy was the process id, all others would be ignored. Is this thinking correct?

    Once that line had been removed, yes, the only entropy being added by the call to ssleay_rand_add was the PID, which usually numbers under 32,768.
  • Harry Johnston says:

    OK, that makes more sense than my version. On the other hand, it means it was an even sillier mistake than I originally thought!

  • Ya wrote:
    > At least if you have the source code, and are insanely motivated, you can find out what the truth of a matter is.

    ??? The Debian guys had the source code. Is insane motivation enough? Doesn’t it also require deep knowledge of cryptography to be able to divine anything resembling “truth” here? If you have the source and the ability to modify it, chances are much better than you’ll do something that will someday end up in an Alun Jones blog post. :)

  • alunj says:

    Actually, it didn’t really require much knowledge of crypto to realise that something was wrong with the change made by the Debian folks.
    It’s clear that a buffer is passed in to this function to “add” it to something in a crypto function – once out of several times, the buffer comes from uninitialised memory, and this is what caused the Purify / Valgrind errors.
    If the Debian guys had simply ‘fixed’ the one call that supplied uninitialised data, life wouldn’t have been so bad. Instead of fixing the call, they fixed the function, so that the function essentially did nothing with its main parameter.
    That should have been a clue that they were neutering an important operation of the function.
    A little knowledge is clearly a dangerous thing.

Leave a Reply

Your email address will not be published. Required fields are marked *


*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>