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.
