Laziness isn't the main quality of a programmer, but it is the important one. It was laziness that led some programmers to write programs which automatically tidy their programs or at least warn about suspicious constructions. Great, isn't it? Well, just until the moment you exactly know what such a warning means and not blindly follow instructions of such program.
Because of a warning of an automatic check tool there were removed two lines of the code from the md_rand.c file. Random numbers generators are vital for the cryptography. In public key cryptography they help computers to choose one unique key from the huge amount of other possible keys. In normal conditions there is almost zero probability that two computers will create two identical keys.
Removing these two lines crippled the random number generator so hardly, that OpenSSL was able to create only 2^15 keys. It is a ridiculously small number! My two years old workstation with Intel Core Duo processor is able to create all possible 1024 bit keys in several hours.
Pretty scary situation! Everyone can the have key for login to my computers. Everyone can sign emails and pretend they are from me.
I have used Debian GNU/Linux since my Linux days started. I do not blame Debian Developers, they have been creating great operating system for my computers and everyone has right to do mistakes. In Czech there is saying "Kdo nic nedělá, ten nic nezkazí" (translation?). But this mistake was really BIG.
I'm responsible for computers with 50 CPUs at minimum, they are crunching OGR-25 in their free time, and I never tried to create a few millions of private keys, just to be sure they are really unique. No one did since September 2006 until 13th May 2008.
Weak OpenSSH keys
At first moment it was critical to identify weak ssh keys used for access to all my computers. In the debian-security mailing list it was very quickly announced a dowk.pl script, it was followed by an openssh-blacklist package. The openssh-blacklist package is used by the new version 1:4.7p1-9 of openssh-server to prevent users with weak keys from login into protected computer. The new openssh-client package provides another tool for checking for weak keys. It is called ssh-vulnkey and in my option it provides better output than the dowk.pl script.
The problem was that the openssh-blacklist package had only few blacklists and also it was completely missing information about the source of these blacklists. I had the same problem with the dowkd.pl script, so I decided to take the keys from metasploit project, verify few thousands of them and prepare my own openssh-blacklist package.
My package is no longer needed. The official openssh-blacklist package in version 0.3 contains the same keys as my version. It's now in unstable/Sid, I hope it will reach Etch soon.
Sadly, the ssh blacklist can not be used for x509. Keys created with ssh-keygen and openssl req have the different exponent. Because of this fact, it was needed to create another blacklists for OpenSSL.
Weak OpenSSL keys
At CESNET we run Certification Authority which is used for several grid project, for eduroam.cz, for Shibboleth federation and for other internal purposes. We wanted to notify our users about weakness of their keys as soon as possible. At the beginning I was using brute force to get all keys. I discovered that for each pid I was getting two different keys. Later I realized that this is related to the .rnd file.
When the .rnd file doesn't exist OpenSSL creates one key and if it exists it create different key. Both keys have to be considered as compromised. In fact, there is also third key which is created when OpenSSL is used with the -rand argument pointing to a non existing file. I do not list those keys, because I don't believe someone could be so stupid to use OpenSSL this way.
x86_64:~# export MAGICPID=1 x86_64:~# export LD_PRELOAD=/root/getpid-preload/getpid.so x86_64:~# rm ~/.rnd x86_64:~# openssl req -new -noout -nodes -batch >/dev/null 2>&1 ; \ openssl rsa -noout -modulus <privkey.pem | sha1sum 854fa1125fa30b81063ea5f2b4780de47f44c56b - x86_64:~# openssl req -new -noout -nodes -batch >/dev/null 2>&1 ; \ openssl rsa -noout -modulus <privkey.pem | sha1sum 4d88a39034e63d668bf8cdfc07ce58eebfc624ec - x86_64:~# openssl req -new -noout -nodes -batch >/dev/null 2>&1 ; \ openssl rsa -noout -modulus <privkey.pem | sha1sum 4d88a39034e63d668bf8cdfc07ce58eebfc624ec - x86_64:~# rm ~/.rnd x86_64:~# openssl req -new -noout -nodes -batch >/dev/null 2>&1 ; \ openssl rsa -noout -modulus <privkey.pem | sha1sum 854fa1125fa30b81063ea5f2b4780de47f44c56b - x86_64:~# openssl req -new -noout -nodes -batch \ -rand /tmp/nonexistent >/dev/null 2>&1 ; \ openssl rsa -noout -modulus <privkey.pem | sha1sum b9f2ccd7451017587286aa8753747ccbf42c56fe - x86_64:~# openssl req -new -noout -nodes -batch \ -rand /tmp/nonexistent >/dev/null 2>&1 ; \ openssl rsa -noout -modulus <privkey.pem | sha1sum b9f2ccd7451017587286aa8753747ccbf42c56fe - x86_64:~# ls -l /tmp/nonexistent ls: /tmp/nonexistent: No such file or directory
I created keys for RSA 1024, 2048, 4096 for 32 and 64 bit Intel platforms. I hope it cover almost all keys we have issued. I created example.tar.bz which contains only 108 private keys for those who are interested in verification of my work. I do not think it is a good idea to publish the rest.
Thanks to this databases we found and revoked about 200 weak keys. Luckily only 4 of them were used as personal signing keys. The rest was used as server certificates and those are easily replaceable.
What still worries me is a CRL distribution. My email client Thunderbird, and my web browser Firefox do not download CRL automatically. I have to choose "Preference" -> "Advanced" -> "Encryption" -> "Revocation Lists". It downloads CRL only the first time when configured, but it never updates them. I need to search how to push CRL into their databases.
Debian Wiki is the most complete resource.
Metasploit pages about this problem are also very useful.
Better do it yourself and THINK!