Tonnerre Lombard

A lot of confusion has turned up about the OpenSSL insecure PRNG vulnerability in Debian and related systems. This is an attempt to clear these up.

Which distributions were affected?

All distributions which pulled their OpenSSL changes directly from Debian. Those are namely:

Debian Etch and Lenny, Ubuntu/Kubuntu/Xubuntu and related, grml, Knoppix and all living customizations and Univention UCS 2.0. Other Linux distributions may also be affected.

Known not to be affected are: Fedora, Debian Sarge, NetBSD, OpenBSD, FreeBSD, DragonFlyBSD, MirBSD, Gentoo Linux, Univention UCS 1.x, Red Hat Enterprise Linux, OpenSuSE, SuSE Linux Enterprise, CentOS, pfSense, m0n0wall, Sun Solaris 10 and prior and OpenSolaris.

What exactly is the problem?

Due to a slightly misguided valgrind warning patch, the only “random” element used in key generation and other random number generation processes by Debian was the process ID. Since typical process IDs under Linux range from 0 to 65’535, there were only 65’536 possible different keys generated by the OpenSSL toolchain, also including SSH.

This means specificially that an attacker needs only 65’536 attempts to bruteforce a key generated by any Debian tool during this period of time. The impact of this depends on the usage of the key: for SSH user keys, it means that an attacker can impersonate the affected user and log in as the affected user to any system where the key is in the authorized_keys file. For keys used for certification and encryption, such as SSH host keys and SSL certificates, an attacker can impersonate the affected SSH or web server, and can potentially read currently running and recorded sessions, depending on the procedure used for session key establishment.

How can I figure out if my key was affected?

Debian and Ubuntu have released tools for key analysis which scan for patterns of the vulnerable keys by connecting to named hosts and looking into user’s home directories for authorized_keys files which contain the patterns. An updated version of OpenSSH for Debian and Ubuntu now ships with a tool to automatically discover and refuse the vulnerable keys.

My key is affected – what should I do?

The first point is of course to immediately update the affected packages if you use a Debian derived system. Then, generate new SSH keys and replace them on all systems where your old SSH keys are located. Replace them as well on the servers of this nasty customer who left for the concurrence – imagine what would happen if he found out that you left a vulnerable SSH key on his host and that his host was compromitted by your negligence.

All affected OpenSSL certificates should also be revoked immediately. Generate new certificates and let them be signed and re-issued through your CA. Commercial CAs should let you reissue the certificate with the same Subject until the end of the certification period you paid up to. Please note that revokation is a critical step here, otherwise people might still impersonate your old certificate which might, after all, still be valid.

Then make sure your infrastructure was not taken over by botnets through an insecure SSH key. Check for rootkits as well while you’re at it. If your log host is affected, tough luck.

How urgent is this? Will I have to act immediately?

Yes, this item requires your immediate attention as there are already botnets out there which search for accounts with vulnerable SSH keys. The question is not “Does someone care about me little Internet user?” — these bots are out to compromise hosts and to send SPAM and malware to other hosts. They don’t care if you are an attractive target, they attack anything they can find and try to send SPAM with it.

I have put my securely generated private SSH user key onto a Debian system. Should I replace it?

Yes. On a Debian system, your private key was not safe during the last 2 years. The system may have been compromitted during that time, or someone may even only have been eavesdropping your communication and have gained knowledge about your SSH key. You should definitely consider it compromitted.

I have put my securely generated public SSH user key onto a Debian system. Should I replace it?

This depends. If your key is an RSA key, it is not compromitted simply by putting the public key onto a server and authenticating against it. The SSH 2.0 protocol, as described in RFCs 4252 and 4253, part of the token being signed as challenge by the user is the “session identifier”, which is a hash from the key exchange. This effectively prevents replay attacks of authentication processes done using a non-vulnerable SSH key, because the random material used as challenge is not only controlled by the vulnerable SSH host, but also by the non-vulnerable client. Thus, the data your SSH key has to sign as a challenge is not vulnerable to the weak PRNG of the SSH server, and thus cannot compromise your key.

This is however not true for DSA keys. DSA has a weakness when used in the Diffie-Hellmann key exchange process, rendering it basically uneffective. If the attacker gets hold of the random number used by the Debian SSH server in the key exchange process, this can be used to calculate the private DSA key from the public key with a complexity of 2¹⁶, being 65’536.

Summary

• Change any key pair generated using an affected version of the pseudo-random number generator. This applies both to the user and host SSH keys, and is of course also valid for certificates.
• If you have used a DSA key or certificate on a host affected by the vulnerability, it must be regenerated.
• Assume that all data read from and written to a vulnerable machine may be intercepted and/or tampered with, like if no crypto layer had been applied in the first place.
• RSA keys used to authenticate to vulnerable hosts are secure.

Acknowledgements

Special thanks for this goes to Steven M. Bellovin, who took the time to go through an analysis of this entire process with me and to clear up my misunderstandings about the OpenSSH challenge-response procedure.

(Original source)

The big run on valgrind way back in 2005 to 2006 has already demanded its first prominent victim: the OpenSSL implementation shipped with Debian.

Way back in May 2006, one of the Debian developers ran valgrind on OpenSSL in an attempt to make it more secure. Along the findings of valgrind was an uninitialized buffer named buf in the ssleay_rand_add function in openssl/crypto/rand/md_rand.c. The programmer simply commented out the MD_Update call which added the random data to the pool in order to fix the presumed flaw.

This blind patch was not exactly the correct thing to do. The data contained in buf was exactly the random pool initialization data, which was now no longer being added.

Apparently, the OpenSSL team also had its part in this game though. The Debian developer sent the patch upstream, and it was approved for debugging purposes by the OpenSSL team. Apparently, this was slightly misunderstood by the Debian developer, so he committed the now-defunct MD based PRNG into the Debian codebase.

According to the audit trail of the corresponding Debian bug, the Debian SSL team approved the patch and released a “fixed” package in May 2006.

The impact

As soon as the new OpenSSL release was deployed, the Debian users would now create keys using an MD as pseudo random number generator with hardly any modifications in the randon pool. As a short explanation to non-cryptographers: it was not really random.

The Debian Security team then discovered certain patterns which would emerge magically in most of their SSH and SSL keys, as well as keys from all other products which were based on OpenSSL. After several days if not weeks of analysis, the culprit had been tracked down to be that precise valgrind-triggered change.

The effect of this could be observed in the past couple of days by close followers of the Debian community. All of a sudden, the web certificates changed, all authorized_keys files were removed from the project servers, and some SSH host keys had changed, even though non of them had expired. This confused the Debian community very much, and was perceived as “A large security incident immediately ahead”.

With the release of the Debian Security Advisory today, this expectation was finally fulfilled, and the incident was indeed a major one: users were asked to regenerate all OpenSSL generated cryptographic keys since May 2006. A script was released to detect and warn about common patterns(!) in the various key files.

Lessons learned

There are certainly various lessons to be learned from this, both on the cryptographic, the programming and the practical side.

1. Don’t blindly trust valgrind’s output.
   This has been repeated over and over again. If valgrind finds a presumed flaw in your code, it does not necessarily mean it is really a flaw. It must be investigated very thoroughly by the programmer, and not patched away lightly just because it’s there.
2. Cryptography may be counter intuitive to a programmer.
   I personally can’t stop repeating this. What might appear as a runtime optimization to a programmer can indeed be a timing based information disclosure on the cryptographic level, and what might look like an uninitialized variable might actually not want to be zeroed out.
   This is also an argument against GnuTLS I keep repeating. Cryptography is not something which can be handled just like that by any good programmer. One needs at least a diploma in maths and programming plus be a very focused computer geek and close follower of the cryptographic community to even be able to touch cryptographic products successfully. This is the reason why I have major concerns with the GNU community rewriting an SSL implementation from scratch just because they do not like the OpenSSL license.
3. A diversification of infrastructures may be useful at times.
   This might be a bit counter-intuitive to those who followed the argument from the last paragraph, but the sole reason why the chain of trust did not break for the Debian team was that besides their working OpenSSL PKI, they also had a working, trusted and distributed GnuPG PKI. Thus, even though all OpenSSL keys were compromitted, the GnuPG keys could still be used to verify the origin of various security credentials and to verify that the new key material et cetera was indeed originating from the Debian project.

That said, I would like to proudly add that neither the NetBSD base nor the pkgsrc version of OpenSSL are affected by this bug.

Audit trail

• 22:20: Added more precise information on what keys and certificates changed
• 23:25: Added reference to what exactly happened to get the patch approved

(Original source)