Re: [dsfjdssdfsd] Discussion: Malicious Entropy Attacks: Eggs, and Baskets

[ianG <[e-mail]>]

> Theodore Ts'o <[e-mail]>

> On Tue, Mar 11, 2014 at 07:13:44PM +0000, Alyssa Rowan wrote:
>>> B. A 'running' state, which uses that key, holds it securely,
>>> and runs a good deterministic random bit generator to generate
>>> as much randomness as we need [up to some limit].
>>> 
>>> Specifically, djb advocates running A -then- run B (presumably,
>>> up to some defined limit, as no DRBG is sound _ad infinitum_,
>>> then we'd have to block and go back to A to gather another
>>> key?).
> I'll note that an criteria for judging RNG's which is very popular 
> with academics who love to write papers poking (theoretical) holes 
> into random number generators is how quickly a RNG can recover
> from state compromise.
> 
> One of the reasons why some people love RNG's such as Fortuna and 
> Yarrow is that it is specifically designed to recover from state 
> compromises --- and the scheme which djb has suggested would do
> poorly on that particular metric.
> 
> Does it matter?  Well, entire virtual forests of electronic trees
> have been felled by people speculating on whether fast/reliable
> recovery from state recovery is critically important compared to
> other design considerations.
> 
> Personally, my take is that if you can compromise the state of the 
> RNG, you can probably far more damage, so I'm not convinced state 
> compromise is a very high priority threat to defend against.  But 
> there are tons and tons of academic papers which are convinced
> that any RNG which doesn't worry about this attack is Fatally
> Flawed.



Responding to Ted to highlight the opposing view, ... Schneier in a
sense responds in today's Cryptogram:


** *** ***** ******* *********** *************
    The Security of the Fortuna PRNG

Providing random numbers on computers can be very difficult.  Back in
2003, Niels Ferguson and I designed Fortuna as a secure PRNG.
Particularly important is how it collects entropy from various
processes on the computer and mixes them all together.

While Fortuna is widely used, there hadn't been any real analysis of
the system.  This has now changed.  A new paper by Yevgeniy Dodis, Adi
Shamir, Noah Stephens-Davidowitz, and Daniel Wichs provides some
theoretical modeling for entropy collection and PRNG.  They analyze
Fortuna and find it good but not optimal, and then provide their own
optimal system.

Excellent, and long-needed, research.

http://eprint.iacr.org/2014/167

Fortuna:
https://www.schneier.com/fortuna.html
** *** ***** ******* *********** *************



Which abstract aptly describes the approach of the threat model, and
the challenges that it inspires, as well as promising a solution:


** *** ***** ******* *********** *************
   How to Eat Your Entropy and Have it Too
      --
   Optimal Recovery Strategies for Compromised RNGs

Yevgeniy Dodis and Adi Shamir and Noah Stephens-Davidowitz and Daniel
Wichs

Abstract: Random number generators (RNGs) play a crucial role in many
cryptographic schemes and protocols, but their security proof usually
assumes that their internal state is initialized with truly random
seeds and remains secret at all times. However, in many practical
situations these are unrealistic assumptions: The seed is often
gathered after a reset/reboot from low entropy external events such as
the timing of manual key presses, and the state can be compromised at
unknown points in time via side channels or penetration attacks. The
usual remedy (used by all the major operating systems, including
Windows, Linux, FreeBSD, MacOS, iOS, etc.) is to periodically
replenish the internal state through an auxiliary input with
additional randomness harvested from the environment. However,
recovering from such attacks in a provably correct and computationally
optimal way had remained an unsolved challenge so far.

In this paper we formalize the problem of designing an efficient
recovery mechanism from state compromise, by considering it as an
online optimization problem. If we knew the timing of the last
compromise and the amount of entropy gathered since then, we could
stop producing any outputs until the state becomes truly random again.
However, our challenge is to recover within a time proportional to
this optimal solution even in the hardest (and most realistic) case in
which (a) we know nothing about the timing of the last state
compromise, and the amount of new entropy injected since then into the
state, and (b) any premature production of outputs leads to the total
loss of all the added entropy {\em used by the RNG}, since the
attacker can use brute force to enumerate all the possible low-entropy
states. In other words, the challenge is to develop recovery
mechanisms which are guaranteed to save the day as quickly as possible
after a compromise we are not even aware of. The dilemma that we face
is that any entropy used prematurely will be lost, and any entropy
which is kept unused will delay the recovery.

After developing our formal definitional framework for RNGs with
inputs, we show how to construct a nearly optimal RNG which is secure
in our model. Our technique is inspired by the design of the Fortuna
RNG (which is a heuristic RNG construction that is currently used by
Windows and comes without any formal analysis), but we non-trivially
adapt it to our much stronger adversarial setting. Along the way, our
formal treatment of Fortuna enables us to improve its entropy
efficiency by almost a factor of two, and to show that our improved
construction is essentially tight, by proving a rigorous lower bound
on the possible efficiency of any recovery mechanism in our very
general model of the problem.
** *** ***** ******* *********** *************





(caveat, I haven't read the paper, so have no idea if the holy grail
is delivered)

iang