6
$\begingroup$

I have read this article and I do somehow "understand" that the reduction of entropy makes it easier to guess.

But how exactly can the security be reduced by that? Can you give a concrete scenario, where a poor (P)RNG leads to security issues?

$\endgroup$
  • 1
    $\begingroup$ would a sample from "recent" history suffice (aka Debian OpenSSL bug)? $\endgroup$ – SEJPM May 24 '16 at 19:46
  • $\begingroup$ You are not talking about "Heartbleed", are you? If it is caused by a poor RNG, I'd love to hear more. (edit: seems not to bee heartbleed, though never heard of it, thanks) $\endgroup$ – exilit May 24 '16 at 19:50
  • $\begingroup$ No, heartbleed was a "regular" bug in the OpenSSL library, the Debian OpenSSL bug was a flaw in Debian's OpenSSL version $\endgroup$ – SEJPM May 24 '16 at 19:52
  • 1
    $\begingroup$ Obligatory XKCD. This happens a lot, in a form or another, e.g. this. $\endgroup$ – fgrieu May 24 '16 at 20:12
  • $\begingroup$ What happens if you "randomly" set the combination on your luggage to 0 0 0 0 0? $\endgroup$ – Matt Nordhoff May 25 '16 at 2:50
8
$\begingroup$

Suppose that you generate a brand new RSA key pair, that you will use, say, to authenticate yourself when connecting to a SSH server. This will be done through some library that implements RSA key pair generation (say, OpenSSL). That library will produce the key elements by generating random integers of the right length until such integers appear to be prime number.

The random generation uses a seed obtained from "true randomness" and then expanded into an arbitrarily long sequence of random bits with a cryptographically secure PRNG. The point is to make it infeasible for an attacker to predict the bits you came up with.

Now suppose that the seed is of low entropy (e.g. 40 bits) or the PRNG is poorly designed and reduces the entropy. Saying "40 bits entropy" more or less means "there are only 240 possible values for the seed or internal PRNG state". Take note that in the synthetic description above, the conversion from seed to generated private key is completely deterministic. Thus, an attacker can generate all these 240 states, and, for each of them, work out the private key that your application would have come up with, starting with that seed value. It then suffices for the attacker to check these keys against your public key (which is public, as the name says) to learn your private key. And impersonate you. Which is bad.

This actually happened in Debian in 2008 and people had to regenerate new SSH keys (both client and server).

$\endgroup$
  • $\begingroup$ They were relying on uninitialized data for security? They don't know how much entropy that had, and it could be zero. $\endgroup$ – user253751 May 25 '16 at 0:14
  • 1
    $\begingroup$ @immibis They weren't relying on it. They thought it was a cute idea — at best, it would add some entropy; at worst, it would add nothing. Harmless. The harm came when the code was changed again, inadvertently breaking everything. $\endgroup$ – Matt Nordhoff May 25 '16 at 2:37
  • $\begingroup$ @MattNordhoff If I'm understanding correctly, the harm came from removing the code that used uninitialized data as randomness. That implies the system was relying on that uninitialized data for randomness. Otherwise, removing it wouldn't break things. $\endgroup$ – user253751 May 25 '16 at 2:41
  • 2
    $\begingroup$ @immibis Removing that line of code was harmless. The problem was they also removed a separate, but identical line of code, unaware it was critically important. $\endgroup$ – Matt Nordhoff May 25 '16 at 2:48
5
$\begingroup$

The 2012 paper: Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices.

In this case the RNG itself was ok, but poor (ie predictable) entropy was used to seed it. The abstract opens:

RSA and DSA can fail catastrophically when used with malfunctioning random number generators.

So that seems to fit your question. The authors did a survey of SSL/TLS servers on the open internet and found that

0.75% of TLS certificates share keys due to insufficient entropy during key generation, ... Even more alarmingly, we are able to obtain RSA private keys for 0.50% of TLS hosts and 0.03% of SSH hosts, because their public keys shared nontrivial common factors due to entropy problems, and DSA private keys for 1.03% of SSH hosts, because of insufficient signature randomness.

Their guess is that most of these vulnerable devices are headless embedded devices that are generating keys on first boot using basically only the entropy (seed values) they came out of the factory with.

$\endgroup$
  • $\begingroup$ Do you happen to know whether any institutions having interest in security issues of the Internet have reacted to the paper you cited? (Or even to a paper of A.. K. Lenstra et al. cited in it?) $\endgroup$ – Mok-Kong Shen May 27 '16 at 8:35
  • $\begingroup$ @Mok-KongShen Sorry, I have no idea :-( $\endgroup$ – Mike Ounsworth May 27 '16 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.