Slashdot Mirror
Debian Bug Leaves Private SSL/SSH Keys Guessable
SecurityBob writes "Debian package maintainers tend to very often modify the source code of the package they are maintaining so that it better fits into the distribution itself. However, most of the time, their changes are not sent back to upstream for validation, which might cause some tension between upstream developers and Debian packagers. Today, a critical security advisory has been released: a Debian packager modified the source code of OpenSSL back in 2006 so as to remove the seeding of OpenSSL random number generator, which in turns makes cryptographic key material generated on a Debian system guessable. The solution? Upgrade OpenSSL and re-generate all your SSH and SSL keys. This problem not only affects Debian, but also all its derivatives, such as Ubuntu." Reader RichiH also points to Debian's announcement and Ubuntu's announcement.
Ubuntu got an updated advisory at http://www.ubuntu.com/usn/usn-612-2
I'm sure the problem will be fixed if the developers acknowledge that the problem exists. Not a big worry.
Yes, it is a big worry because any keys generated with this package are now potentially suspect. This means that anybody who's used Debian or a Debian derived distribution like Ubuntu needs to go back and destroy all host and personal keys generated since 2006. All of those keys are potentially guessable.
And that's a real vulnerability. Early versions of Netscape's SSL implementation (the first SSL implementation) were trivially crackable because of just such a vulnerability.
Need a Python, C++, Unix, Linux develop
Um.... it doesn't matter if it's been patched, you still have to regenerate all your keys.
There most certainly is something to see here, this is kind of a big deal.
It was reading from initialized memory to for the seed value, leading to valgrind warnings. See the original Debian bug report: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=363516
Downloading the patch is step one - you also need to regenerate any certificates made with OpenSSL since 2005, since they can't be guaranteed to be secure.
This has the potential to turn into a huge pain in the arse for Debian based shops, who will need to reissue SSL certificates, SSH keys, and a whole host of other essential elements of their security infrastructure.
Uhhm, no. If you generated a key using the affected packages (ssh-keygen), as a user, your key needs to be replaced.
Apparently, OpenSSL was using uninitialized memory as a source of randomness. This made valgrind complain about the program, and some enterprising programmer decided to fix it by clearing the memory before use.
No, the random text your put in can be random or not. What they were talking about is a number generator that was used or applied to an algorithm that decided the prime of your key in so that the same algorithm wouldn't be used on two machines on the first then second keys. Without the random number generator, you could theoretically guess the algorithm used to generate the key based of the actions of another install and then decipher the key to gain access to whatever it was protecting.
To simplify and generalize it, if every machine uses X+1*256 to get a 256 bit key equal to 768, then you could reverse that and know X would =2 (3*256=768) and fake the credentials. The random number generator should change that to X+R*256 which make reversing the key harder because you can only solve to X+R=3 now. In practice, it will be a really larger number and a lot different process though. I can't say that I fully understand it but that simplification should show the difference well enough to give an Idea of where the problem is.
Check out this bug report and tell me they weren't just being arrogant:
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=363516
Says the first comment to the patch, in regards to what is being reversed:
"What it's doing is adding uninitialised numbers to the pool to create random numbers."
OpenSSL having more-random numbers vs. Valgrind looking good. And Valgrind won?
The consensus in the bug report seems to be not to do it, but then someone adds the patch anyways.
Not entirely true. Keys generated before the patch made it to the repos are safe - and I think quite a lot of debian boxes are old enough (I know I've got one.) There's a link in the advisory to a tool that checks if the keys are vulnerable.
This doesn't change the fact that this is a really serious fuckup. Debian lost quite some credibility in my eyes.
The original change was tracked in the debian Bugtracking system at: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=363516
The offending patch: http://svn.debian.org/viewsvn/pkg-openssl/openssl/trunk/rand/md_rand.c?rev=141&view=diff&r1=141&r2=140&p1=openssl/trunk/rand/md_rand.c&p2=/openssl/trunk/rand/md_rand.c
The fix: http://svn.debian.org/viewsvn/pkg-openssl/openssl/trunk/crypto/rand/md_rand.c?rev=300&view=diff&r1=300&r2=299&p1=openssl/trunk/crypto/rand/md_rand.c&p2=/openssl/trunk/crypto/rand/md_rand.c
The patch that broke it was checked in by Kurt Roeckx [kroeckx@debian.org]. Don't know if he broke it or if he was just the gatekeeper for checkins. See:
http://svn.debian.org/viewsvn/pkg-openssl/openssl/trunk/rand/md_rand.c?rev=141&view=diff&r1=141&r2=140&p1=openssl/trunk/rand/md_rand.c&p2=/openssl/trunk/rand/md_rand.c which shows the change that introduced the bug; and its parent node:
http://svn.debian.org/viewsvn/pkg-openssl/openssl/trunk/rand/?rev=141#dirlist which shows the maintainer responsible.
From looking at this patch, I think this is what happened. valgrind complained about a rather unusual coding convention in ssleay_rand_bytes. This is a function that returns random data into a buffer. However, before writing into the buffer, it reads from the buffer and incorporates the old contents into the internal random state. valgrind complained about this use of an output buffer for input. Normally you would never want to use potentially uninitialized data like this, but in this case it is OK as all that is being done is the data is being folded into the random state. In the worst case, this can't hurt, and maybe it will help, if the old data had some randomness.
Anyway, valgrind complained about it, and the maintainer commented out the use of the buffer. That would actually be OK, it is not a big deal. But the implementor made a mistake, and also commented out another similar usage, in a different function, ssleay_rand_add. This was a huge mistake, as the purpose of ssleay_rand_add is to add randomness into the random state. In that function, buf is an INPUT buffer, and adding it into the random state is perfectly legitimate, in fact it is the whole purpose of the function. But apparently because it looked similar to the questionable usage in ssleay_rand_bytes, the maintainer commented out the code in ssleay_rand_add at the same time. (I don't know whether valgrind also complained about this second usage, but if so, it was mistaken. I think it's more likely that the maintainer just got fooled and over-generalized from the valgrind complaint.)
So the whole thing was an attempt to clean up code and remove warnings, but the fix accidentally broke a crucial piece of functionality, rendering ssleay_rand_add completely non-functional. So any attempt to add randomness into the RNG state, such as for seeding purposes, is ineffective. The random state ends up with much less variability, and therefore all the crypto is weak. As Bruce Schneier points out, bad crypto looks much the same as good crypto, so it took this long to notice it.
Hats off to the reviewer who picked up on the problem. Don't know who it was, but the same Kurt Roeckx [kroeckx@debian.org] checked in the fix.
I think the problem is not the removal of the use of uninitialized memory as source of randomness. Instead it is the wrong way it is done, removing nearly all sources of randomness as a result. By the way, the fixed package still don't use the uninitialized memory as source of randomness.
It's not seeding too often that's the problem, it's seeding with predictable data and expecting that data to be random. The time is very predictable, and contains very little entropy (randomness).
If you seed very often with data containing a lot of entropy (for example, radioactive decay), then there's no problem. It's also not a problem to add the time in the mix if you mark it as having almost no entropy.
But that doesn't fix all of the machines that my public key (generated on Ubuntu) resides on that do not run Ubuntu. So yes fixing Ubuntu machines is easy, it is a PITA to have to go and re-upload my public key to all of these hosts.
Actually, here is where the Debian maintainer brought this up with upstream, and he was not told how stupid it was, in fact the Debian maintainer says, "the pool might receive less entropy." and upstream says, "If it helps with debugging, I'm in favor of removing them."
Actually, any DSA key *used* on a box with the bad SSL packages may be compromised:
From http://wiki.debian.org/SSLkeys
Additionally, some DSA keys may be compromised in the following situations:
* key generated with broken openssl = bad
* key generated with good openssl and used to ssh from a machine with bad ssl = bad
* key generated with good openssl and used to ssh from a machine with good ssl = good
This is because the random numbers used during the signature process must also be good.
From what I undestood, with my limited cryptographic knowledge and my total reluctance to dig into all the details of the sources, what happens is that when you asked your debian box to generate a key, it did so without integrating enough random data in its choice. That means that a brute force attack will not have to try every key to find yours but only a small subset, depending on the knowledge it has about your machine and its state when it generated the keys.
There is no such thing as a master key, but it would mean that several different servers may have generated the same "random" keys and that a clever attacker could create a dictionary of plausible keys (or, more plausibly, an algorithm to generate them) and try all of them on your server with a good chance to have one of them working. The dictionary would probably be huge however. A good measure would be to block an IP on SSH after a reasonnable number of failures (like 100)
The Wise adapts himself to the world. The Fool adapts the world to himself. Therefore, all progress depends on the Fool.
Especially when they won't work anymore:
The GP poster said the same thing, but this is for the benefit of other readers who were skeptical that any such policy was in place.
So, basically, once you upgrade, you'll have no apparent way to access your other machines [1] to upload your new key. That's just spiffy!
[1] Uninstall openssh-blacklist first.
Dewey, what part of this looks like authorities should be involved?
It is even worse than this. Passwords that were used on a server with a weak DSA key may be compromised, as well:
From http://wiki.debian.org/SSLkeys
Seriously guys, take a few minutes to understand the code before hacking on it. If it was written by a n00b, you need to understand it to make sure they didn't do other stuff wrong. If it was written by someone competent (which is probably the case for openssl), then you need to make sure you're not the one making the mistake. In this case, to make it work with valgrind, the patch should have been to debian/rules, simply changing the way Configure was called.
If I read the published "weak key detector" script correctly, Debian OpenSSHs will always generate one out of a fixed set of 262148 possible keypairs. Do the math yourself. If you know those keys, this is a 5-minute brute force attack.
No, I don't think you're quite correct. The original patch in that thread is not what actually was applied. There are two functions, one for seeding the pseudo-random number generator, and one for getting random data out of it. The one for getting random data out was actually mixing in some uninitialized data into the entropy pool. This is not particularly harmful, but not particularly helpful either, and it caused Valgrind to complain. So, the maintainer removed that line, but also removed the line that mixes in the value provided to seed the random number in the first place (maybe it was being called with unitialized data at some point, too).
See my comment here for more details: http://reddit.com/info/6j7a9/comments/c03zxko
Incorrect, no matter what Ben claims. According to http://www.openssl.org/support/, openssl-dev is for the developers of openssl itself. To quote the list description: Discussions on development of the OpenSSL library. Not for application development questions!
So yes, perhaps Kurt could have been more explicit in his description of what he was trying to do, but he was definitely using the appropriate address to reach the developers.
noah
The problem is, OpenSSL needed a buffer in which to XOR several sources of randomness, including /dev/random. OpenSSL didn't bother initializing the buffer, because doing so just eats CPU cycles, and a possibly random buffer is marginally better than a non-random one. However, the Debian patch removed *all* of the randomness except for the PID, leaving the user with one of just 262148 (or so) distinct keypairs. The tool that checks if your keys have been conpromised has a list of all of those keypairs and checks if your keypair appears.
Nothing for 6-digit uids?
I cann't claim to 100% understand the situation but after glancing trough the logs of the discussions and of the patches the conclusion I came to was this - OpenSSL used supposed randomness of the uninitialized memory as an added source of entropy (interesting hack, but not an example of good coding as such). Valgring caught that problem and the Debian maintainer during a cleanup fixed it. Making such a fix can be considered a preventive step against possible attack vectors by poisoning the uninitialized memory. He took it up to upstream, they did not raise red flags, but did not quite merge the âclean upâ(TM) patch either. It fell through the cracks.
The problem is that in the same file, in another function all other sources of entropy were being merged into the pool of randomness using exactly the same code line as the one code line flagged by Valgrind. The maintainer assumed that the second code line has a similar function to the first and commented that one as well. AFAIK that also did not show up in the emails to the upstream list.
So we have:
* Upstream using clever hacks that rely on uninitialized memory having some randomness to it
* Upstream using same code and same variable names to describe different things
* Upstream having no comments in the code explaining the two things above
* Maintainer slightly over-generalizing a change
* A bug slipping trough the cracks in the review processes
* Another Debian Developer discovering the bug and recognizing its significance despite all of the above
* Debian project coming out and admitting all of the above and scrambling to get fixes out to its users ASAP
I am impressed by the swift action of the people involved in fixing this. And while I think everyone can find some lesson be learned here, I think this is another good example of free software in action. And I hope that in the aftermath of this we will find ways to prevent this from happening in the future without stifling our progress.
http://www.aigarius.com/blog/2008/05/14/too-similar-to-be-different/