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.