Following Travis' message, let me first describe the main results of the paper. The paper provides a concise algorithmic description of the Linux random number generator (LRNG), which is quite complex and is based on the use of shift registers and of several SHA-1 operations. Identifying the algorithm was no simple task, due to the length of the code and the lack of documentation. The paper shows that the forward security of the LRNG algorithm is susceptible to an attack, although at a cost of 2^64 to 2^96 operations. This attack enables to compute, given the current state of the LRNG, several previous outputs of the generator. This means that if you break into a Linux machine you can learn about past keys which were generated by the LRNG, which could affect SSL or SSH connections, etc. (BTW, even without this attack, the algorithm used by the LRNG makes it trivial to compute the last output of the generator given the current state, even if the last output was computed a while ago.)
In addition, the paper contains a simple analysis of the amount of entropy which is added to the generator in one typical implementation, an analysis of the security of an implementation on a disk-less system, and a description of some vulnerabilities of the current implementation (including an easy denial of service attack). As for Travis' first comment, the paper mentions that an attacker which has access to the hard disk can change the LRNG state file which is stored there between reboots. This attack might be relevant to scenarios where the system checks during reboot that device drivers etc. were not changed, but does not perform a similar check of the LRNG state file. As for the second comment, it seems to reiterate the observation given in the paper that if the data that is used to refresh the generator has little entropy, then an attacker which knows the state of the generator at a certain time and observes later LRNG outputs can find out what values were used to refresh the generator. Benny -----Original Message----- From: Travis H. [mailto:[EMAIL PROTECTED] Sent: Thursday, March 23, 2006 9:56 AM To: Heyman, Michael Cc: cryptography@metzdowd.com; [EMAIL PROTECTED]; [EMAIL PROTECTED] Subject: Re: Linux RNG paper I have examined the LRNG paper and have a few comments. CC'd to the authors so mind the followups. 1) In the paper, he mentions that the state file could be altered by an attacker, and then he'd know the state when it first came up. Of course, if he could do that, he could simply install a trojan in the OS itself, so this is not really that much of a concern. If your hard drives might be altered by malicious parties, you should be using some kind of cryptographic integrity check on the contents before using them. This often comes for free when encrypting the contents. 2) His objection against using keyboard data is perhaps just an indication that reseeding of the pool should occur with sufficient entropy that the values cannot efficiently be guessed via brute force search and forward operation of the PRNG. If the reseeding is of insufficient to deter brute force input space search, other bad things can happen. For example, in the next paragraph the author mentions that random events may reseed the secondary pool directly if the primary pool is full. If an attacker were to learn the contents of the secondary pool, he could guess the incremental updates to its contents and compare results with the real PRNG, resulting in an incremental state-tracking attack breaking backward security until a reseed from the primary is generated (which appears to have a minimum of 8 bytes, also perhaps too low). The answer is more input, not less. It's annoying that the random number generator code calls the unpredictable stuff entropy. It's unpredictability that we're concerned with, and Shannon entropy is just an upper bound on the predictability. Unpredictability cannot be measured based on outputs of sources, it must be based on models of the source and attacker themselves. But we all know that. Maybe we should invent a term? Untropy? And now a random(3) tangent: While we're on the subject of randomness, I was hoping that random(3) used the old (TYPE_0) implementation by default... lots of DoS tools use it to fill spoofed packet fields, and one 32-bit output defines the entire state of the generator --- meaning that I could distinguish DoS packets which had at least 32 bits of state in them from other packets. However, it appears that Linux and BSD both use a TYPE_3 pool, which makes such simple techniques invalid, and would probably require identification of a packet stream, instead of testing packets one by one. Since use of a real pool has put it beyond my interest and perhaps my ability, I'm giving the idea away. Email me if you find a really good use for PRNG analysis of this sort. For a TYPE_0 generator, the equation is: i' = (i * 1103515245 + 12345) & 0x7fffffff As far as low-hanging fruit goes, the higher generator types still never set the highest order bit (RAND_MAX is 0x7fffffff), and the outputs are unaltered pool contents. -- Security Guru for Hire http://www.lightconsulting.com/~travis/ -><- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]