Almost two years ago in 2006 Debian decided to clean up their OpenSSL implementation. They found a few lines of code that were causing Valgrind and Purify to complain about access to uninitialized memory. Without a major investigation into the purpose of the suspect lines of code they were simply removed. All basic tests continued to pass with the lines of code removed and Purify and Valgrind both stopped complaining about the improper memory access. The change was forgotten and everyone believed that the OpenSSL implementation was working just fine.
For the purposes of all the OpenSSL algorithms there was no deficiency. Encryption and decryption and hashes would be calculated correctly. The problem was that the PRNG used for generating keys by the OpenSSL library had been crippled when those critical lines were removed back in 2006. This was not discovered until just this week when Luciano Bello discovered that without those lines the only ‘random’ data used to seed the PRNG was the PID of the OpenSSL process. On many Linux systems the PID is limited to a positive signed 16 bit value. This means there are only 32,767 possibilities. When new keys and certificates were generated by OpenSSL they relied on this number to provide all of their entropy.
The consequence of this bug is that from September 2006 until May 2008 there were only 32,767 possible keys that could be generated by OpenSSL. Several individuals have generated “black lists” of every possible key that this OpenSSL implementation could generate. According to some reports this entire list can be generated in a couple hours. This weakness affects any key generated by OpenSSL including SSH and DNSSEC keys among others.
Many machines will fail to be updated in a quick manner after the discovery of this vulnerability. There are already many botnets which spread by simply brute forcing common username and password combinations over SSH. It will probably not be long until some of these networks are modified to start attempting RSA authentication using the faulty OpenSSL keys. These attacks will not take long to develop and have the potential to compromise large numbers of machines. It is important for administrators to note that even if they replace and upgrade the OpenSSL package they must recreate and replace any keys or certificates generated by the broken OpenSSL kit.
The moral for developers is to always be sure you understand the impact of your code changes. This goes extra for critical libraries like OpenSSL. Minor and seemingly inconsequential changes can leave major problems festering undetected for years. There may also be some changes in the way that Debian developers work with the developers of other related software packages like OpenSSL. Hopefully increased communication between the development teams in the future can prevent this kind of bug from recurring.
May 16th, 2008 at 8:33 am
This problem is of course not limited to debian servers, since any SSH server which has a compromised key (possibly generated elsewhere) in a user’s authorized_keys file will be vulnerable. All SSH server operators should scan their systems’ users immediately for vulnerable keys. I have used the pre-generated vulnerable key lists to run some attempted auths automatedly (and somewhat naïvely) against my own machine, and can run about 50 keys per second with a simple one-line perl script (using ssh-agent to try 7 keys per connection attempt). The openssh daemon only logs the connection attempts, but *not* the failures when you pass a non-valid key. 50 keys/second means the entire 32k RSA-2048 keyspace can be attempted in about 10 minutes against a single server. This could trivially be parallelized in a botnet. If I were to pick a username to try all the keys against, I’d probably suggest something like “root”.
How long before we start seeing tens of thousands of compromised unix systems out there being added to the botnets?