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
_______________________________________________
Pkg-sysvinit-devel mailing list
[email protected]
http://lists.alioth.debian.org/mailman/listinfo/pkg-sysvinit-devel
