Townsend Security Data Privacy Blog

RSA Key Vulnerability and Random Number Generation

Posted by Patrick Townsend on Feb 16, 2012 8:18:00 AM

rsa rng key problemThe last few days has seen a number of new reports about a security vulnerability in RSA public/private keys in use on the Internet. The vulnerability has to do with duplicate keys, and not with any weakness in the cryptographic algorithm itself. But it is disturbing information because public/private key encryption is crucial to the security of web sites and a number of other secure applications and services.

The news is based on the work of academic researchers and you can read the paper here.

While the researchers did not identify the cause of the duplicate keys, a number of us are guessing that the problem lies in random number generation. It is really easy to create bad random number generators, and hard to get it right and prove that you have it right. So any sloppiness in your engineering processes related to RNG can lead to this type of problem. There are not a lot of applications in use that create RSA public/private keys and X509 certificates, so the problem may be limited to a small number of these applications. But at this time there is no indication of which RSA key generation routines may be at fault.

How bad is this problem and should you worry about it?

At this point I don’t think there are any known attacks or breaches based on this vulnerability. It may have happened, but it hasn’t been reported yet. However, while the original researchers did not disclose their methods for identifying the duplicate RSA keys, it doesn’t seem hard to think of ways to do this. That being said, I am not sure how easy it would be to mount an effective attack even if you know about the duplicate keys. A lot is still unknown about this vulnerability.

I think Bruce Schneier has a good take on this issue. If you are concerned about this potential problem, you can read his comments here.

Are there bad random number generators in the wild?

You bet. Some years ago we found one on the IBM i (AS/400, iSeries) platform. In the early days of the IBM i platform you could use a system API named CEERAN0 to generate random numbers. We were shocked to learn how poor this RNG application is. It would start generating collisions within about 30,000+ cycles. That is really bad. It turns out that IBM also provides a cryptographically secure RNG application, but the older one still exists and we’ve seen it used in vendor and customer applications.

So, the obvious question is how can you know if a random number generator is good? One place to start is with the National Institute of Standards and Technology (NIST). NIST publishes guidelines on proper RNG methods, and a certification program. You can read the NIST recommendations for certifying random number generators here (warning: heavy lifting ahead).

insist on nistNIST also has a certification program for random number generators and vendors like us can submit our work to independent labs that perform NIST testing. All of our cryptographic solutions have been through this testing. It is also important to note that encryption key management systems that undergo FIPS 140-2 certification also go through full RNG testing. Our Alliance Key Manager if FIPS 140-2 certified and the RNG routines were NIST certified as a part of that process. We’ve also certified our RNG implementations on a variety of platforms including the IBM i. The list of vendors who have completed certification are here.

While I don’t think NIST certifications are a perfect indicator of good cryptographic implementations, I certainly wouldn’t accept any encryption key management or cryptographic solution that had not been through an independent certification process.

Proper random number generation is crucial to secure cryptographic systems. You can’t leave RNG to chance (sorry about that).

When more information is available on the RSA vulnerability I’ll give you an update. 

For more information on the importance of encryption key management, download our white paper "Key Management in the Multi-Platform Envrionment" and learn how to overcome the challenges of deploying encryption key management in business applications.

Stay safe.

Patrick

Click me

Topics: Encryption, encryption key, RSA