[Pkg-sysvinit-devel] init.d/urandom : saving random-seed

[Jerry Leichter]

On Aug 1, 2010, at 10:34 AM, Henrique de Moraes Holschuh wrote:

> (Please keep all CCs).
>
> On Sun, 01 Aug 2010, Jerry Leichter wrote:
>> file might be reused:  Stir in the date and time and anything else
>> that might vary - even if it's readily guessable/detectable - along
>
> Well, yes, we have several *guessable* sources of variable data  
> available
> during early userspace that we could use.  We can also distill them  
> through
> sha256.
>
> But it would add very little variation across reboots of the same  
> box, and
> that variation is easily guessable....
I discussed this in the rest of my message.  Apparently I wasn't  
explicit enough.

Consider the overall situation.  We have a large number of systems out  
there. They reboot here and there.  Each of them saves their previous  
PRNG state, and uses it on reboot.  Sometimes, the PRNG state is not  
saved, and a second reboot uses the same state.

Attackers do *not* have access to the saved state.  They *can*,  
however, observe the values produced by the PRNG.  (In practice, they  
get a noisy, incomplete sampling through things like generated keys,  
but let's make the safe assumption that they see the complete  
stream.)  Thus, they can easily check that a given system is  
generating the same sequence of values, so presumably didn't update  
its state.  Thus, it will continue to produce the same values for a  
while (until it can gather enough entropy).

Now consider the situation where a rebooting system stirs in the date  
and time, the MAC and IP addresses of the first couple of messages it  
sees, whatever.  Given a properly implemented PRNG, the output stream  
will look nothing like the output stream it produced the last time  
around.  (Flipping one bit of input to something like SHA-1 flips, on  
average, about half the output bits.)

Sure, an attacker who *knew* the saved state could easily *guess* the  
low-entropy inputs, match what the system emits, and break security.   
But the problem here is entirely different:  Recognizing that the  
stream it's seeing is the result of a small tweak applied to an  
unknown previous state.  If someone an show a solution to that  
problem, I'll withdraw my suggestion.  But I doubt any simple attack  
of this sort exists.

If an attacker can't recognize systems that are re-using state, it has  
to try attacking all of them.  Think about what that attack looks  
like.  When the system works as it's supposed to, the state is saved  
over the reboot, so the reboot effectively never occurred.  The extra  
guessable state makes no difference:  In this situation, we're  
assuming that the PRNG is secure.  When a restart does occur, the  
attacker is seeing two (or more) continuations from the same *unknown*  
internal state, using different guessable - assume known - small  
tweaks, and he must predict the future outputs.  It's kind of a  
related-key attack, and doesn't look easy.  In fact, if the number of  
tweaked bits is small, it doesn't look like there's even enough  
information available to solve it in principle.  (With enough reboots  
without a state update, the bits accumulate.)  But there are likely  
situations it's plausible.  In those - use a true RNG.
                                                         -- Jerry