Broken RSA Keys (part1: the problem)

Lots of stories circulating the news right now (such as this one) about RSA keys providing no security. The problem is not RSA. The problem is bad random seeds when you generated your keys. The solution: Generate new keys using good randomness.

The word for “randomness” is “entropy.” Entropy is the measure of unpredictability. A single fair coin toss represents a single bit of entropy.

For the moment, I’ll write about linux specifically. Much of this information comes from man (4) random.

/dev/random is gathered from hardware entropy sources, such as TPM and keyboard & mouse movements, and unpredictable disk seek times and supposedly unpredictable characteristics of the ethernet and hardware interrupts, etc. Since there is a limited amount of system entropy available, if you try to read /dev/random, your read will block (stall) until more bytes become available.

/dev/urandom is a pseudorandom number generator, based on hash algorithms or ciphers or similar. It is actually deterministic given the initial seed. This is a non-blocking device, so you can read infinite bytes from it as fast as the CPU can generate them. If you read enough data from /dev/urandom, it may exhaust any available entropy, and it will be reused. In other words, a pattern will emerge.

As entropy becomes available in /dev/random, it is fed into /dev/urandom. This helps to continually re-seed urandom and helps urandom to be more actually unpredictable. Basically, urandom is an amplifier of the true entropy.

Unfortunately, when a system is freshly installed, upon first boot, there hasn’t been much entropy gathered. It’s fairly deterministic. During first boot, even if you use urandom, it is only amplifying a very small amount of actual entropy. This is when your ssh keys get generated.

Clearly, you should generate new server ssh keys (and any other keys) sometime after you can assure sufficient entropy. The question is, how do you know you have sufficient entropy in your key generation process?

I’m going to answer this question in two parts, separately. Once for ssh, and once for openssl. Please see:
Broken RSA Keys (part 2: fixing ssh keys)
and
Broken RSA Keys (part 3: openssl)

Comments are closed.