The Linux /dev/random LFSR

From: Patrick J. LoPresti (patl_at_users.sourceforge.net)
Date: 08/31/04 

Date: 31 Aug 2004 11:00:34 -0400

The Linux /dev/random code uses an LFSR as a stirring function. The
argument is that although this is not cryptographically strong, it
does not need to be. Fair enough. But I have a question.

Consider a proposed stirring function which simply takes the input
bits and XORs them against the current pool, cyclically. (So the
first input bit gets XORed into pool bit 0, the second into pool bit
1, and the 4097th into pool bit 0 again.)

Of course, this simple XOR is not cryptographically strong. But
neither is the LFSR. On the other hand, this XOR is both simpler and
faster.

My question is, what attack does the LFSR prevent which this does not?
Or, what problem does this proposal have which the LFSR does not?

 - Pat

Relevant Pages

  • Re: The Linux /dev/random LFSR
    ... > and XORs them against the current pool, ... this XOR is both simpler and faster. ... what attack does the LFSR prevent which this does not? ... Most raw entropy sources have a higher entropy in the lower order ...
    (sci.crypt)
  • Re: The Linux /dev/random LFSR
    ... this simple XOR is not cryptographically strong. ... >> neither is the LFSR. ... > Most raw entropy sources have a higher entropy in the lower order ... > your XOR some bits in the pool will have a low entropy. ...
    (sci.crypt)
  • Re: Pseudorandom Hashing
    ... > IIRC you XOR and feed back on the input, and just XOR on the output. ... Let me return to the topic of the LFSR. ... zeroes provided that the data going over the wire are random. ...
    (sci.electronics.design)
  • Re: Simple balanced pair-wise function
    ... You know the xor of two bits of the LFSR state. ... LFSR cipher is secure. ...
    (sci.crypt)