The sanctity of the dev/random random number generator used in the Linux kernel has been a hot-button issue for more than a month. A petition posted to change.org in September to remove RdRand from dev/random, for example, was met with fury from Linus Torvalds who called the developer who posted it “ignorant,” suggesting not so nicely too that the developer learn more about cryptography.

Now a host of researchers from New York University and Northeastern University have cast doubt on the two Linux pseudo RNGs overall, dev/random and dev/urandom. In a paper released this week, “Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is Not Robust,” the researchers explain attacks that demonstrate inherent weaknesses in the respective algorithms, and also propose what they say is a simpler and more efficient PRNG.

“We show several attacks proving that these PRNGs are not robust according to our definition, and do not accumulate entropy properly. These attacks are due to the vulnerabilities of the entropy estimator and the internal mixing function of the Linux PRNGs,” the researchers wrote in their paper. “These attacks against the Linux PRNG show that it does not satisfy the ‘robustness’ notion of security, but it remains unclear if these attacks lead to actual exploitable vulnerabilities in practice.”

This is not the first time hardware-based security operations have been challenged in the academic world. Most recently, a team of researchers demonstrated how they were able to insert malware onto a chip, yet to detection mechanisms, the chip appears to be unchanged. They did so by changing the dopant polarity of transistors, leaving wiring and other circuitry untouched; dopant is added to semiconductors enabling it to conduct electricity.

The PRNG attacks against dev/random take issue with the randomness of the numbers being generated and how the PRNG could be manipulated in order for a third party to be able to guess or view a key. This is exactly the issue that forced RSA Security’s hand with regard to the Dual EC DRBG algorithm. RSA recommended to developers to stop using the RNG for fear that it might be compromised in some way by an intelligence agency. RSA’s recommendation came on the heels of a similar missive from NIST; Dual EC DRBG is the default random number generator for a number of RSA products including the BSAFE crypto libraries and RSA key management product RSA Data Protection Manager.

While there are no immediate fears the Linux PRNG in dev/random is compromised, the researchers do painstakingly look at the behavior of the entropy estimator and the mixing function used to refresh its internal state, the paper said.

“We have shown vulnerabilities on the entropy estimator due to its use when data is transferred between pools in Linux PRNG,” the paper said; the researchers, as a result, recommend that the functions of a PRNG do not rely on such an estimator.

Categories: Vulnerabilities

Comments (4)

  1. FDunn
    1

    C’mon Linus, don’t take it so dang personally. This is the reason for open-source projects, so they can be improved on to make the Open Source products more robust and hence attractive to enterprises. The more reproducible the “random” seed the more time it will take to break into the encrypted item.
    In addition the notoriety of the U.S. Intelligence agencies for “breaking” weak encryption is a known factor. Also they have ALMOST unlimited budgets for attempting to “break” new forms of encryption.

    God bless,
    FDunn

    • A. C.
      2

      While I’m not a security “expert,” I am sufficiently knowledgeable to understand the shortcomings of the proposal scoffed at by Mr. Torvalds and why it was not better than what’s already in the code. I haven’t checked but chances are he didn’t personally write the RNG code, though he might have personally reviewed it. So, that wasn’t a matter of Mr. Torvalds taking it personally.

      If the NYU & Northeastern researchers are correct, and it should be checked independently, then there may, in fact, be a problem that has to be addressed.

  2. FDunn
    3

    My Bad:
    “The more reproducible the “random” seed the more time it will take to break into the encrypted item.”
    Should read:
    “The more reproducible the “random” seed the LESS time it will take to break into the encrypted item.”

  3. doubting thomas
    4

    i’d never heard /dev/random referred to as something anyone regarded sanctimoniously; maybe it’s just who i hang out with but the pseudo-randomness of computer generated *anything* is pretty well respected.

    consider that linus was not disagreeing with the notion that randomness could be improved, but with the way in which this guy was proposing that it change (and possibly the avenue for the suggestion; why resort to change.org when you can start a collaborative discussion on open mailing lists?)

Comments are closed.