True Random Number Generators Secure in a
Changing Environment管理的四大职能
Boaz Barak,Ronen Shaltiel,and Eran Tromer
Department of Computer Science and Applied Mathematics
Weizmann Institute of Science,Rehovot,ISRAEL
Email:{boaz,ronens,tromer}@wisdom.weizmann.ac.il
Abstract.A true random number generator(TRNG)usually consists
of two components:an“unpredictable”source with high entropy,and a
randomness extractor—a function which,when applied to the source,
produces a result that is statistically clo to the uniform distribution.
春天的图片景色When the output of a TRNG is ud for cryptographic needs,it is pru-
dent to assume that an adversary may have some(limited)influence on
元朝地图
the distribution of the high-entropy source.In this work:
1.We define a mathematical model for the adversary’s influence on the
source.
2.We show a simple and efficient randomness extractor and prove that香芋排骨的做法
it works for all sources of sufficiently high-entropy,even if individual
bits in the source are correlated.
3.Security is guaranteed even if an adversary has(bounded)influence
on the source.
Our approach is bad on a related notion of“randomness extraction”
which emerged in complexity theory.We stress that the statistical ran-
domness of our extractor’s output is proven,and is not bad on any
unproven assumptions,such as the curity of cryptographic hash func-
tions.
A sample implementation of our extractor and additional details can be
found at a dedicated web page[Web].
1Introduction
1.1General tting
It is well known that randomness is esntial for cryptography.Cryptographic schemes are usually designed under the assumption of availability of an endless stream of unbiad and uncorrelated random bits.However,it is not easy to obtain such a stream.If not done properly,this may turn out to be the Achilles heel of an otherwi cure ,Goldberg and Wagner’s attack on the Netscape SSL implementation[GW96]).
In this work we focus on generating a stream of truly random bits.This is the problem of constructing a true random number generator(TRNG).The usual way to construct such a generator consists of two components:
1.Thefirst component is a device that obtains some digital data that is unpre-
dictable in the n that it has high entropy.1This data might come from various sources,such as hardware devices bad on thermal noi or radioac-tive decay,a ur’s keyboard typing pattern,or timing data from the hard disk or network.We stress that we only assume that this data has high en-tropy.In particular,we do not assume that it has some nice structure(such as independence between individual bits).We call the distribution that is the result of thefirst component the high-entropy source.
2.The cond component is a function,called here a randomness extractor,
which is applied to the high-entropy source in order to obtain an output string that is shorter,but is random in the n that it is distributed ac-cording to the uniform distribution(or a distribution that is statistically very clo to the uniform distribution).
Our focus is on the cond component.The goal of this work is to construct a single extractor which can be ud with all types of high-entropy sources,and that can be proven to work,even in a model that allows an adversary some control over the source.
Running a TRNG in adversarial environments.The high entropy source ud in a TRNG can usually be influenced by changes in the physical environment of the device.The changes can include changes in the temperature,changes in the voltage or frequency of the power supply,exposure to radiation,etc..In addition to natural changes in the physical environment,if we are using the output of a TRNG for cryptographic purpos,it is prudent to assume that an adversary may be able to control at least some of the parameters.Of cour, if the adversary can have enough control over the source to ensure that it has zero entropy then,regardless of the extractor function ud,the TRNG will be completely incure.However,a reasonable assumption is that the adversary has only partial control over the source in a way that he can influence the source’s output,but not remove its entropy completely.
1.2Our results
In this paper,we suggest a very general model which captures such adversarial changes in the envir
onment and show how to design a randomness extractor that will be cure even under such attacks.
In all previous designs we are aware of,either there is no mathematical treat-ment or the source of random noi is assumed to have a nice mathematical structure(such as independence between individual samples).As the nature of cryptanalytic attacks cannot be foreen in advance,it is hard to be convinced
of the curity of a TRNG bad on a t of statistical tests that were performed on a prototype in ideal conditions.We also remark that it may be dangerous to assume that the source of randomness has a nice mathematical structure, especially if the environment in which the TRNG operates may be altered by an adversary.
Our extractor is simple and efficient,and compares well with previous de-signs.It is bad on pairwi-independent hash function[WC81].2Our approach is inspired by a somewhat different notion of“randomness extractors”defined in complexity theory(e surveys[NTS99,Sha02]and Section1.3).
Our design works in two phas:
Preprocessing:In this pha the manufacturer(or the ur)choos a string πwhich we call a public parameter.This string is then hardwired into the implementation and need not be kept cret.The same stringπcan be distributed in all copies of the randomness extractor device,and will be ud whenever they are executed.(We discuss this in detail in Section1.4). Runtime:In this pha the randomness extractor gets data from the high-entropy source and its output is a function of this data and the public pa-rameterπ.高考进行时
The analysis guarantees that ifπis chon appropriately in the preprocessing pha and the high-entropy source has sufficient entropy then the output of the TRNG is esntially uniformly distributed even when the environment in which the TRNG operates is altered by an adversary.This guarantee holds as long as the adversary has limited influence on the high-entropy source.
In particular,we make no assumption on the structure of the high-entropy distribution except for the necessary assumption that it contains sufficient en-tropy.Existing designs of high-entropy sources em to achieve this goal.
1.3Previous works
Randomness extractors ud in practice.As far as we are aware,all extractors previously ud in pra
ctice as a component in a TRNG,fall under the following two categories:
Designs assuming mathematical structure The are extractors that work under the assumption that the physical source has some“nice”mathematical structure.
An example of such an extractor is the von Neumann extractor[vN51],ud in the design of the Intel TRNG[JK99].On input a source X1,...,X n the von Neumann extractor considers successive pairs of the form X2i,X2i+1;for each pair,if X2i=X2i+1then X2i is nt to the output,otherwi nothing it nt.The von Neumann extractor works if one assumes that the all bits in the source are independent and are identically distributed.That is,each
bit in the source will be equal to1with the same probability p,and this will happen independently of the values of the other bits.However,it may fail if different bits are correlated or have different bias.
Other constructions that are sometimes ud have every bit of the output be XOR of bits in the source that are“far from each other”.Such constructions assume that the“far away”bits are independent.
RFC1750[ErCS94]also suggests some heuristics such as applying a Fast Fourier Transform(FFT)or
a compression function to the source.However, we are not aware of any analysis of the conditions on the source under which the heuristic will provide a uniform output.
Applying a cryptographic hash function Another common , [ErCS94],[Zim95])is to extract the randomness by a applying a crypto-graphic hash function(or a block cipher)to the high-entropy source.The result is expected to be a true random(or at least pudo-random)out-put.As there is no mathematical guarantee of curity,confidence that such constructions work comes from the extensive cryptanalytic rearch that has been done on the hash function.However,this rearch has mostly been concentrated on specific“pudorandom”,collision-resistance)of the functions.It is not clear whether this rearch applies to the behavior of such hash functions on sources where the only guaran-tee is high entropy,especially when the sources may be influenced by an adversary that knows the exact hash function that is ud. Randomness extractors in complexity theory The problem of extracting randomness from high-entropy distributions is also considered in complex-ity theory(for surveys,e[NTS99,Sha02]).However,the model considered there allows the adversary to have full control over the source distribution.
The sole restriction is that the source distribution has high entropy.One pays a heavy price for this generality:it is impossible to extract randomness by a deterministic randomness extractor.3Conqu
ently,this notion of ran-domness extractors(defined in[NZ96])allows the extractor to also u few additional truly random bits.The rationale is that the extractor will output many more random bits than initially spent.While this concept proves to be very uful in many areas of computer science,it does not provide a way to generate truly random bits for cryptographic applications.4
Nevertheless,our solution us techniques from this area.For the reader familiar with this area,we remark that our solution builds on obrving that a weaker notion of curity(the one described in this paper)can be
guaranteed even when the few additional random bits are chon once and for all by the manufacturer and made public.
1.4Advantages and disadvantages of our scheme.
The main advantage of our scheme is that it is proven to work for every high-entropy source,provided that the adversary has only limited control on the distribution of the source.By contrast,previous schemes are either known to fail for some very natural high-entropy ,the von Neumann’s extractor), or lack a relevant formal analysis(e above).
Efficiency.It is natural to measure the performance of a randomness extractor in terms of the cost per output bit.This measure depends on the following factors:
1.Cost:The speed and size of the hardware or software implementation of the
extractor.
2.Entropy rate:The amount of entropy contained in the source.
3.Entropy loss:The difference between the amount of entropy that the high-
entropy source contains and the number of bits extracted.
Our design allows tuning the running time and entropy loss as a function of the expected entropy rate and the desired resiliency against adversarial effects on the source.This tuning helps to achieve good overall performance in different scenarios.We discuss specific scenarios below.
In general,our approach is quite simple and efficient and is suitable for a hardware implementation.Its cost is comparable to that of cryptographic hash functions,and it can provably achieve low entropy loss and extract more than half of the entropy prent in the source(by comparison,the von Neumann extractor extracts at most half of the entropy)5.
运球变向
Example:low entropy rate.For example,consider the ca where the source is the typing patterns of a ur.In this ca the speed at which one can sample the high-entropy source is comparatively slow,and furthermore sampling the source may be expensive.It is thus crucial to minimize entropy loss and extract as much as possible from the entropy prent in the source.Our design allows extracting3/4of the entropy in the source at a slight cost to the running time. In this ca,the running time is less significant as the bottleneck is the sampling speed from the random source.
Example:high entropy rate.Consider the ca where the source is sampling of thermal noi.Now the running time is important and we can tune our design to work faster at the cost of higher entropy loss.国内景点排行榜
The existence of a formal proof of curity can be helpful when optimizing the implementation.Our proof shows that any implementation of“universal hash
functions”(or“ℓ-wi independent hash functions”)suffices for our random-ness extractor.Thus,a designer can choo the most efficient implementation hefinds and optimize it to suit his particular architecture.This is contrast to cryptographic hash functions,which do not have a proof of curity and where the effect of ,removing a round)is unknown,and thus such opti-mizations are not recommended in practice.
A public parameter.One disadvantage of our scheme is the fact that it us a public parameter.6The curity of the scheme is proven under the assumption that the parameter is chon at random.This parameter needs to be chon only once and the resulting scheme will be cure with extremely high probability.
We stress that we do not assume that this parameter is kept cret.More-over,this parameter can be chon once and for all by the manufacturer and hardwired into all copies of the device.We also do not assume that the distri-bution of the high-entropy source is completely independent from the choice of this parameter—our model allows this distribution to be partially controlled by a computationally-unbounded adversary that knows the public parameter.
Note that a public parameter is necessary to obtain the curity properties that we require.
2The formal model
2.1Preliminaries寂灭为乐
Min-Entropy.The min-entropy of the source X,denoted by min-Ent(X),the maximal number k such that for every x∈X,Pr[X=x]≤2−k.
Remark1.Min-entropy is a stricter notion than the standard(Shannon)en-tropy,in the n that the min-entropy of X is always smaller than or equal to the Shannon entropy of X.
It is easy to e that it is impossible to extract m bits from a distribution X with min-Ent(X)≤m−1.This is becau such a distribution gives probability at least2−(m−1)to some element x.It follows that for any candidate extractor function E:{0,1}n→{0,1}m the element y=E(x)has probability at least 2−(m−1)and thus E(X)is far from being uniformly distributed.
We conclude that having min-entropy larger than m is a necessary condition for randomness extraction.In this paper we show that having min-entropy k slightly larger than m is a sufficient condition.
Statistical Distance.We u dist(X,Y)to denote the statistical distance between X and Y that is:1
6The description of many hash functions and block ciphers includes various mi-arbitrary constants;arguably the can also be considered public parameters.
