Eat Your Entropy and Have it Too - Recover RNGs.pdf

(713 KB) Pobierz
How to Eat Your Entropy and Have it Too —
Optimal Recovery Strategies for Compromised RNGs
Yevgeniy Dodis 1? , Adi Shamir 2 , Noah Stephens-Davidowitz 1 , and Daniel Wichs 3??
1 Dept. of Computer Science, New York University.
2 Dept. of Computer Science and Applied Mathematics, Weizmann Institute.
3 Dept. of Computer Science, Northeastern University.
Abstract. Random number generators (RNGs) play a crucial role in many cryptographic schemes and proto-
cols, 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 ecient 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 entropyusedbytheRNG, 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 eciency 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 eciency of any recovery
mechanism in our very general model of the problem.
1Introduction
Randomness is essential in many facets of cryptography, from the generation of long-term cryptographic
keys, to sampling local randomness for encryption, zero-knowledge proofs, and many other randomized
cryptographic primitives. As a useful abstraction, designers of such cryptographic schemes assume a source
of (nearly) uniform, unbiased, and independent random bits of arbitrary length. In practice, however, this
theoretical abstraction is realized by means of a Random Number Generator (RNG), whose goal is to
quickly accumulate entropy from various physical sources in the environment (such as keyboard presses or
mouse movement) and then convert it into the required source of (pseudo) random bits. We notice that a
highly desired (but, alas, rarely achieved) property of such RNGs is their ability to quickly recover from
? Research partially supported by gifts from VMware Labs and Google, and NSF grants 1319051, 1314568, 1065288, 1017471.
?? Research partially supported by gift from Google and NSF grants 1347350, 1314722.
various forms of state compromise, in which the current state S of the RNG becomes known to the attacker,
either due to a successful penetration attack, or via side channel leakage, or simply due to insucient
randomness in the initial state. This means that the state S of practical RNGs should be periodically
refreshed using the above-mentioned physical sources of randomness I. In contrast, the simpler and much
better-understood theoretical model of pseudorandom generators (PRGs) does not allow the state to be
refreshed after its initialization. To emphasize this distinction, we will sometimes call our notion an “RNG
with input”, and notice that virtually all modern operating systems come equipped with such an RNG with
input; e.g., /dev/random [Wik04] for Linux, Yarrow [KSF99] for MacOs/iOS/FreeBSD and Fortuna [FS03]
for Windows [Fer13].
Unfortunately, despite the fact that they are widely used and often referred to in various standards [ISO11,
Kil11,ESC05,BK12], RNGs with input have received comparatively little attention from theoreticians. The
two notable exceptions are the works of Barak and Halevi [BH05] and Dodis et al. [DPR + 13]. The pioneer-
ing work of [BH05] emphasized the importance of rigorous analysis of RNGs with input and laid their first
theoretical foundations. However, as pointed out by [DPR + 13], the extremely clean and elegant security
model of [BH05] ignores the “heart and soul” issue of most real-world RNGs with input, namely, their
ability to gradually “accumulate” many low-entropy inputs I into the state S at the same time that they
lose entropy due to premature use. In particular, [DPR + 13] showed that the construction of [BH05] (proven
secure in their model) may always fail to recover from state compromise when the entropy of each input
I 1 ;:::;I q is suciently small, even for arbitrarily large q.
Motivated by these considerations, Dodis et al. [DPR + 13] defined an improved security model for RNGs
with input, which explicitly guaranteed eventual recovery from any state compromise, provided that the
collective fresh entropy of inputs I 1 ;:::;I q crosses some security threshold , irrespective of the entropies
of individual inputs I j . In particular, they demonstrated that Linux’s /dev/random does not satisfy their
stronger notion of robustness (for similar reasons as the construction of [BH05]), and then constructed a
simple scheme which is provably robust in this model. However, as we explain below, their robustness model
did not address the issue of eciency of the recovery mechanism when the RNG is being continuously used
after the compromise.
The Premature Next Problem. In this paper, we extend the model of [DPR + 13] to address some
additional desirable security properties of RNGs with input not captured by this model. The main such
property is resilience to the “premature next attack”. This general attack, first explicitly mentioned by
Kelsey, Schneier, Wagner, and Hall [KSWH98], is applicable in situations in which the RNG state S has
accumulated an insucient amount of entropy e (which is very common in bootup situations) and then must
produce some outputs R via legitimate “next” calls in order to generate various system keys. Not only is this
R not fully random (which is expected), but now the attacker can potentially use R to recover the current
state S by brute force, eectively “emptying” the e bits of entropy that S accumulated so far. Applied
iteratively, this simple attack, when feasible, can prevent the system from ever recovering from compromise,
irrespective of the total amount of fresh entropy injected into the system since the last compromise.
At first, it might appear that the only way to prevent this attack is by discovering a sound way to
estimate the current entropy in the state and to use this estimate to block the premature next calls. This is
essentially the approach taken by Linux’s /dev/random and many other RNGs with input. Unfortunately,
sound entropy estimation is hard or even infeasible [SV03, FS03] (e.g., [DPR + 13] showed simple ways to
completely fool Linux’s entropy estimator). This seems to suggest that the modeling of RNGs with input
should consider each premature next call as a full state compromise, and this is the highly conservative
approach taken by [DPR + 13] (which we will fix in this work).
Fortuna. Fortunately, the conclusion above is overly pessimistic. In fact, the solution idea already comes
from two very popular RNGs mentioned above, whose designs were heavily aected by the desire to overcome
the premature next problem: Yarrow (designed by Schneier, Kelsey and Ferguson [KSF99] and used by
MacOS/iOS/FreeBSD), and its refinement Fortuna (subsequently designed by Ferguson and Schneier [FS03]
and used by Windows [Fer13]). The simple but brilliant idea of these works is to partition the incoming
entropy into multiple entropy “pools” and then to cleverly use these pools at vastly dierent rates when
2
producing outputs, in order to guarantee that at least one pool will eventually accumulate enough entropy
to guarantee security before it is “prematurely emptied” by a next call. (See Section 4 for more details.)
Ferguson and Schneier provide good security intuition for their Fortuna “pool scheduler” construction,
assuming that all the RNG inputs I 1 ;:::;I q have the same (unknown) entropy and that each of the pools can
losslessly accumulate all the entropy that it gets. (They suggest using iterated hashing with a cryptographic
hash function as a heuristic way to achieve this.) In particular, if q is the upper bound on the number of
inputs, they suggest that one can make the number of pools P=log 2 q, and recover from state compromise
(with premature next!) at the loss of a factor O(logq)in the amount of fresh entropy needed.
Our Main Result. Inspired by the idea of Fortuna, we formally extend the prior RNG robustness notion
of [DPR + 13] to robustness against premature next. Unlike Ferguson and Schneier, we do so without making
any restrictive assumptions such as requiring that the entropy of all the inputs I j be constant. (Indeed,
these entropies can be adversarily chosen, as in the model of [DPR + 13], and can be unknown to the RNG.)
Also, in our formal and general security model, we do not assume ideal entropy accumulation or inherently
rely on cryptographic hash functions. In fact, our model is syntactically very similar to the prior RNG
model of [DPR + 13], except: (1) a premature next call is not considered an unrecoverable state corruption,
but (2) in addition to the (old) “entropy penalty” parameter , there is a (new) “time penalty” parameter
1, measuring how long it will take to recover from state compromise relative to the optimal recovery
time needed to receive bits of fresh entropy. (See Figures 2 and 3.)
To summarize, our model formalizes the problem of designing an ecient recovery mechanism from
state compromise 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 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 extending our model to handle premature next calls, we define the generalized Fortuna construc-
tion, which is provably robust against premature next. Although heavily inspired by actual Fortuna, the
syntax of our construction is noticeably dierent (See Figure 5), since we prove it secure in a stronger model
and without any idealized assumptions (like perfect entropy accumulation, which, as demonstrated by the
attacks in [DPR + 13], is not a trivial thing to sweep under the rug). In fact, to obtain our construction, we:
(a) abstract out a rigorous security notion of a (pool) scheduler; (b) show a formal composition theorem
(Theorem 2) stating that a secure scheduler can be composed with any robust RNG in the prior model
of [DPR + 13] to achieve security against premature next; (c) obtain our final RNG by using the provably
secure RNG of [DPR + 13] and a Fortuna-like scheduler (proven secure in our significantly stronger model).
In particular, the resulting RNG is secure in the standard model, and only uses the existence of standard
PRGs as its sole computational assumption.
Constant-Rate RNGs. In Section 5.4, we consider the actual constants involved in our construction,
and show that under a reasonable setting or parameters, our RNG will recover from compromise in =4
times the number of steps it takes to get20to30kB of fresh entropy. While these numbers are a bit high,
they are also obtained in an extremely strong adversarial model. In contrast, remember that Ferguson and
Schneier informally analyzed the security of Fortuna in a much simpler case in which entropy drips in at
a constant rate. While restrictive, in Section 6 we also look at the security of generalized Fortuna (with
a better specialized scheduler) in this model, as it could be useful in some practical scenarios and allow
for a more direct comparison with the original Fortuna. In this simpler constant entropy dripping rate,
we estimate that our RNG (with standard security parameters) will recover from a complete compromise
immediately after it gets about2to3kB of entropy (see Section 6.2), which is comparable to [FS03]’s
3
(corrected) claim, but without assuming ideal entropy accumulation into the state. In fact, our optimized
constant-rate scheduler beats the original Fortuna’s scheduler by almost a factor of2in terms of entropy
eciency.
Rate Lower Bound. We also show that any “Fortuna-like construction” (which tries to collect entropy
in multiple pools and cleverly utilize them with an arbitrary scheduler) must lose at least a factor (logq)
in its “entropy eciency”, even in the case where all inputs I j have an (unknown) constant-rate entropy.
This suggests that the original scheduler of Fortuna (which usedlogq pools which evenly divide the entropy
among them) is asymptotically optimal in the constant-rate case (as is our improved version).
Semi-Adaptive Set-Refresh. As a final result, we make progress in addressing another important
limitation of the model of Dodis et al. [DPR + 13] (and our direct extension of the current model that
handles premature nexts). Deferring technical details to Section 7, in that model the attacker A had very
limited opportunities to adaptively influence the samples produced by another adversarial quantity, called
the distribution sampler D. As explained in there and in [DPR + 13], some assumption of this kind is necessary
to avoid impossibility results, but it does limit the applicability of the model to some real-world situations.
As the initial step to removing this limitation, in Section 7.1 we introduce the “semi-adaptive set-refresh”
model and show that both the original RNG of [DPR + 13] and our new RNG are provably secure in this
more realistic adversarial model.
Other Related Work. As we mentioned, there is very little literature focusing on the design and analysis
of RNGs with inputs in the standard model. In addition to [BH05,DPR + 13], some analysis of the Linux
RNG was done by Lacharme, Röck, Strubel and Videau [LRSV12]. On the other hand, many works showed
devastating attacks on various cryptographic schemes when using weak randomness; some notable examples
include [GPR06,KSWH98,NS02,CVE08,DGP07,LHA + 12,HDWH12].
2Preliminaries
Entropy. For a discrete distribution X, we denote its min-entropy byH 1 (X)=min x $ X flogPr[X=x]g.
We also define worst-case min-entropy of X conditioned on another random variable Z by in the following
conservative way:H 1 (XjZ)=log([max x;z Pr[X=xjZ=z]]). We use this definition instead of the
usual one so that it satisfies the following relation, which is called the “chain rule”:H 1 (X;Z)H 1 (Z)
H 1 (XjZ).
Pseudorandom Functions and Generators. We say that a functionF:f0;1g ` f0;1g m ! f0;1g m
is a (deterministic)(t;q F ;")-pseudorandom function (PRF) if no adversary running in time t and making
q F oracle queries toF(key;)can distinguish betweenF(key;)and a random function with probability
greater than " when key $ f0;1g ` . We say that a functionG:f0;1g m ! f0;1g n is a (deterministic)
(t;")-pseudorandom generator (PRG) if no adversary running in time t can distinguish betweenG(seed)
and uniformly random bits with probability greater than " when seed $ f0;1g m .
Game Playing Framework. For our security definitions and proofs we use the code-based game-playing
framework of [BR06]. A game GAME has an initialize procedure, procedures to respond to adversary oracle
queries, and a nalize procedure. A game GAME is executed with an adversary A as follows: First, initialize
executes, and its outputs are the inputs to A. Then A executes, its oracle queries being answered by
the corresponding procedures of GAME. When A terminates, its output becomes the input to the nalize
procedure. The output of the latter is called the output of the game, and we let GAME A ) y denote the
event that this game output takes value y. A GAME denotes the output of the adversary and Adv GAM A =
2Pr[GAME A )1]1. Our convention is that Boolean flags are assumed initialized to false and that the
running time of the adversary A is defined as the total running time of the game with the adversary in
expectation, including the procedures of the game.
4
3RNGwithInput:ModelingandSecurity
In this section we present formal modeling and security definitions for RNGs with input, largely follow-
ing [DPR + 13].
Definition 1 (RNG with input). An RNG with input is a triple of algorithms G=(setup; refresh; next)
and a triple(n;`;p)2N
3 where n is the state length, ` is the output length and p is the input length of G:
– setup: a probabilistic algorithm that outputs some public parameters seed for the generator.
– refresh: a deterministic algorithm that, given seed, a state S 2f0;1g n and an input I 2f0;1g p , outputs
a new state S 0 =refresh(seed;S;I)2f0;1g n .
– next: a deterministic algorithm that, given seed and a state S 2 f0;1g n , outputs a pair(S 0 ;R)=
next(seed;S)where S 0 2f0;1g n is the new state and R 2f0;1g ` is the output.
Before moving to defining our security notions, we notice that there are two adversarial entities we need
to worry about: the adversary A whose task is (intuitively) to distinguish the outputs of the RNG from
random, and the distribution sampler D whose task is to produce inputs I 1 ;I 2 ;:::; which have high entropy
collectively, but somehow help A in breaking the security of the RNG. In other words, the distribution
sampler models potentially adversarial environment (or “nature”) where our RNG is forced to operate.
3.1 Distribution Sampler
The distribution sampler D is a stateful and probabilistic algorithm which, given the current state , outputs
a tuple( 0 ;I;;z)where: (a) 0 is the new state for D; (b) I 2 f0;1g p is the next input for the refresh
algorithm; (c) is some fresh entropy estimation of I, as discussed below; (d) z is the leakage about I
given to the attacker A. We denote by q D the upper bound on number of executions of D in our security
games, and say that D is legitimate ifH 1 (I j j I 1 ;:::;I j1 ;I j+1 ;:::;I q D ;z 1 ;:::;z q D ; 0 ;:::; q D ) j for
all j 2f1;:::;q D g where( i ;I i ; i ;z i )=D( i1 )for i 2f1;:::;q D g and 0 =0. 1
We explain [DPR + 13]’s reason for explicitly requiringD to output the entropy estimate j . Most complex
RNGs are worried about the situation where the system might enter a prolonged state where no new entropy
is inserted in the system. Correspondingly, such RNGs typically include some ad hoc entropy estimation
procedure E whose goal is to block the RNG from outputting output value R j until the state has not
accumulated enough entropy (for some entropy threshold ). Unfortunately, it is well-known that even
approximating the entropy of a given distribution is a computationally hard problem [SV03]. This means
that if we require our RNG G to explicitly come up with such a procedure E, we are bound to either place
some significant restrictions (or assumptions) on D, or rely on some hoc and non standard assumptions.
Indeed, [DPR + 13] demonstrate some attacks on the entropy estimation of the Linux RNG, illustrating how
hard (or, perhaps, impossible?) it is to design a sound entropy estimation procedure E. Finally, we observe
that the design of E is anyway completely independent of the mathematics of the actual refresh and next
procedures, meaning that the latter can and should be evaluated independently of the “accuracy” of E.
Motivated by these considerations, [DPR + 13] do not insist on any “entropy estimation” procedure as
a mandatory part of the RNG design. Instead, they place the burden of entropy estimations on D itself.
Equivalently, we can think that the entropy estimations j come from the entropy estimation procedure E
(which is now “merged” with D), but only provide security assuming that E is correct in this estimation
(which we know is hard in practice, and motivates future work in this direction).
However, we stress that: (a) the entropy estimates j will only be used in our security definitions, but
not in any of the actual RNG operations (which will only use the input I returned by D); (b) we do not
insist that a legitimate D can perfectly estimate the fresh entropy of its next sample I j , but only provide a
lower bound j that is legitimate. For example, D is free to set j =0as many times as it wants and, in this
case, can even choose to leak the entire I j to A via the leakage z j ! More generally, we allow D to inject new
1 Since conditional min-entropy is defined in the worst-case manner, the value j in the bound below should not be viewed
as a random variable, but rather as an arbitrary fixing of this random variable.
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin