Linux RNG paper

[Benny Pinkas]

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:solinym at gmail.com] 
Sent: Thursday, March 23, 2006 9:56 AM
To: Heyman, Michael
Cc: cryptography at metzdowd.com; zvikag at cs.huji.ac.il; benny at cs.haifa.ac.il
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 majordomo at metzdowd.com