Transcript True Random Number Generators

Random Number Generators for
Cryptographic Applications
(Part 2)
Werner Schindler
Federal Office for Information Security (BSI), Bonn
Bonn, January 24, 2008
Outline (Part 2)
 Repetition
 Design
of crucial facts
and evaluation criteria for physical RNGs
 general
advice
 stochastic
model
 entropy
 online
 AIS
tests, tot test, self test
31 and ISO 18031
 Conclusion
Schindler
24.01.2008
Slide 2
Classification
RNG
deterministic
pure
non-deterministic (true)
hybrid
physical
pure
Schindler
hybrid
24.01.2008
non-physical
pure hybrid
Slide 3
General Requirements (I)
R1: Random numbers should not show statistical
weaknesses (i,e., they should pass statistical
“standard tests”).
R2: The knowledge of subsequences of random
numbers shall not allow to practically compute
predecessors or successors or to guess them with
non-negligibly larger probability than without
knowledge of these subsequences.
Schindler
24.01.2008
Slide 4
General Requirements (II)
R3: It shall not be practically feasible to compute
preceding random numbers from the internal state or
to guess them with non-negligibly larger probability
than without knowledge of the internal state.
R4: It shall not be practically feasible to compute
future random numbers from the internal state or to
guess them with non-negligible larger probability than
without knowledge of the internal state.
Schindler
24.01.2008
Slide 5
Ideal RNGs
 Even
with maximum knowhow, most powerful
technical equipment and unlimited computational
power an attacker has no better strategy than
“blind guessing” (brute force attack).
 Guessing
n random bits costs 2n-1 trials in average.
 The
guess work remains invariant in the course of
the time.
 An
ideal RNG clearly meets Requirements R1 - R4
 An
ideal RNG is a mathematical construct.
Schindler
24.01.2008
Slide 6
PTRNG (schematic design)
analog
noise
source
external interface
digital
algorithmic
postprocessing
(optional; with or
without memory)
digitised analog signal
(das-random numbers)
Schindler
buffer
(optional)
internal r.n.
24.01.2008
external r.n.
Slide 7
Noise source
 The
noise source is given by dedicated hardware.
 The
noise source exploits, for example,
 noisy
diodes
 free-running
 radioactive
 quantum
oscillators
decay
photon effects
 ...
Physical RNGs (should) aim at information
theoretical security.
Schindler
24.01.2008
Slide 8
Development and Security Evaluation
of PTRNGs
The challenge is threefold:
 Development
and implementation of a strong RNG
design
 Verification
that design and implementation are
indeed strong
 effective
detection mechanisms for possible nontolerable weaknesses of random numbers while the
PTRNG is in operation
Schindler
24.01.2008
Slide 9
 The
central part of a PTRNG security evaluation is to
verify Requirement R2.
 R1
is easy to fulfil and to check. Apart from very
unusual designs R3 and R4 are “automatically”
fulfilled.
Schindler
24.01.2008
Slide 10
Optimal guessing strategy
 Let
X denote a random variable that assumes
values in a finite set S = {s1, ... ,st}.
 The
optimal guessing strategy begin with those
values that are assumed with the largest
probability.
Schindler
24.01.2008
Slide 11
Guess work and entropy (I)
 Goal
of a PTRNG security evaluation:
Try to estimate the expected number of guesses that
is necessary to find a random number with a certain
(reasonable) probability.
 For
real-world PTRNGs it is usually yet not feasible
to determine this value directly.
 Instead,
entropy shall provide a reliable estimator.
 Goal:
Determine (at least) a lower bound for the
entropy per bit (general purpose RNG).
Schindler
24.01.2008
Slide 12
Evaluation
Note: Entropy is a property of random variables and
not of values that are assumed by these random
variables (here: random numbers).
 In
particular, entropy cannot be measured as
temperature, voltage etc.
 General
entropy estimators for random numbers do
not exist.
Schindler
24.01.2008
Slide 13
Warning
Warning
Warning
 The
test values of Maurer‘s „universal entropy test“
and of Coron‘s refinement are closely related to the
entropy per random bit if the respective random
variables fulfil several conditions.
 If
these conditions are not fulfilled (e.g. for pure
DRNGs!) the test value need not be related to the
entropy.
 The
adjective “universal” has caused a lot of
confusion in the past.
Schindler
24.01.2008
Slide 14
Fundamental model assumptions
 We
interpret random numbers as realizations of
random variables.
 Although
entropy is a property of random variables
in the following we loosely speak of the “(average)
entropy per random number” instead of “(average)
gain of entropy per corresponding random
variable”.
 A reliable
security evaluation of a PTRNG should
be based on a stochastic model.
Schindler
24.01.2008
Slide 15
Guess work and entropy (II)
 The
min entropy is the most conservative entropy
measure. For arbitrary distribution of X a lower
bound for the guesswork can be expressed in
terms of the min entropy while the Shannon
entropy may pretend larger guess work.
Schindler
24.01.2008
Slide 16
Conditional entropy (I)
Let X1,X2,... denote random variables that assume
values in a finite set S = {s1, ... ,st}. The conditional
entropy
H(Xn+1 | X1,...,Xn) =
 H(Xn+1 | X1=x1,...,Xn=xn) * Prob(X1 = x1,…,Xn = xn)
x1,...,xnS
quantifies the increase of the overall entropy when
augmenting Xn+1 to the sequence X1,...,Xn.
Schindler
24.01.2008
Slide 17
Conditional entropy (II)
H(X1,...,Xn, Xn+1) =
H(X1,...,Xn) H(Xn+1 | X1,...,Xn) = ... =
H(X1) H(X2 | X1) ... H(Xn+1 | X1,...,Xn)
This formula is very useful to determine the entropy
of dependent sequences.
There is no pendant for the min entropy.
Schindler
24.01.2008
Slide 18
Guess work and entropy (III)
 Assume
that X1,X2,... denotes a sequence of binaryvalued iid (identically and identically distributed)
random variables. Unless n is too small
H(X1,X2,...,Xn)/n  log2(E(number of guesses per bit))
 The
assumption “iid” may be relaxed, e.g. to
“stationary with finite memory”.
the random variables X1,X2,...,Xn are ‘close’ to the
uniform distribution all parameters  give similar
Renyi entropy values.
 If
Schindler
24.01.2008
Slide 19
Guess work and entropy (IV)
 (At
least) the internal random numbers usually fulfil
both the second and the third condition.
 Hence
we use the Shannon entropy in the
following since it is easier to handle than the min
entropy ( conditional entropy).
Schindler
24.01.2008
Slide 20
The stochastic model (I)

Goal: Estimate the increase of entropy per internal
random number
 Ideally, a stochastic model should specify a family
of probability distributions that contains the true
distribution of the internal random numbers.
 It should at least specify a family of distributions
that contain the distribution of the
 das random numbers or
 of ‚auxiliary‘ random variables
that allow to estimate the increase of entropy per
internal random number.
Schindler
24.01.2008
Slide 21
Example 5: Coin Tossing

PTRNG: A single coin is tossed repeatedly.
"Head" (H) is interpreted as 1, "tail" (T) as 0.

Stochastic model:
 The
observed sequence of random numbers (here:
heads and tails) are interpreted as values that are
assumed by random variables X1,X2,… .
random variables X1,X2, … are assumed to be
independent and identically distributed.
(Justification: Coins have no memory.)
 The
p
Schindler
: = Prob(Xj = H)  [0,1] with unknown parameter p
24.01.2008
Slide 22
Example 5: Coin Tossing (II)

Note: A physical model of this experiment
considered the impact of the mass distribution of
the coin on the trajectories. The formulation and
verification of the physical model is much more
complicated than for the stochastic model.
Schindler
24.01.2008
Slide 23
The stochastic model (II)

A stochastic model is not equivalent to a physical
model. In particular, it does not provide the exact
distribution of the das random numbers or the
internal numbers in dependency of the
characteristics of the components of the analog
part.
 Instead, the stochastic model only specifies a class
of probability distributions which shall contain the
true distribution (see also Example 5).
 The class of probability distributions usually
depends on one or several parameters.
Schindler
24.01.2008
Slide 24
The stochastic model (III)

The stochastic model shall be verified by
measurements / experiments.
 The parameter(s) of the true distribution are
guessed on basis of measurements.
 The stochastic model allows the design of effective
online tests that are tailored to the specific RNG
design.
Schindler
24.01.2008
Slide 25
Example 5: Coin Tossing (III)
Entropy estimation (based on the stochastic model):
• Observe a sample x1,x2, …, xN.
Set ~p := #j  N | xj = H / N
~
• To obtain an estimator H(X1) for H(X1)
~
substitute p
into the entropy formula:
~
~
~
~
~
H(X1) = - ( p* log2 (p) + (1-p) * log2(1-p))
Schindler
24.01.2008
Slide 26
The stochastic model (IV)

For PTRNGs the justification of the stochastic
model is usually more complicated and requires
more sophisticated arguments.

To estimate entropy the parameter(s) are
estimated first, and therefrom an entropy estimate
is computed (cf. Example 5).

If the random numbers are not independent the
conditional entropy per random bit has to be
considered.
Schindler
24.01.2008
Slide 27
Example 6 (I)
PTRNG design proposed in [Tk]
ring oscillator 1
43 bit LFSR
k bit
permutation
permutation
k bit
ring oscillator 2
output
(internal
random
number)
37 bit CASR
CASR = Cellular Automaton Shift Register (GF(2)-linear)
Schindler
24.01.2008
Slide 28
Example 6 (II)
Two free-running ring oscillators clock the LFSR and
the CASR, respectively.
The intermediate time between two outputs of random
numbers shall exceed a minimum number of LFSR
and CASR cycles.

noise source: ring oscillators

das random numbers: number of cycles of the LFSR
and CASR between subsequent calls of the RNG

internal state: current states of the LFSR and CASR

internal random number: k-bit output string
Schindler
24.01.2008
Slide 29
Example 6 (III): Dichtl’s attack

Original parameters: k =32

Assume that the attacker knows
 the
three following 32-bit random numbers
 the
number of intermediate cycles of the LFSR and
CASR.
 all
implementation details (permutation etc.)

Notation: state of the LFSR at time t=0: (a1,...,a43)
state of the CASR at time t=0: (a´1,...,a´37)

This gives an (over-determined!) system of
96 GF(2)-linear equations in 80 variables
with solution (a1,...,a43,a´1,...,a´37).
Schindler
24.01.2008
Slide 30
Example 6 (IV)
 Original parameters: k = 32;
minimum waiting time between two outputs:
86 LFSR cycles, 74 CASR cycles
Goal: Determine the conditional entropy
H(Yn+1| Y1, ...,Yn)
(internal random numbers)
in dependency of k and the time between two outputs
of random numbers.
Schindler
24.01.2008
Slide 31
Example 6 (V)
Upper entropy bound:
At least in average,
H(Yn+1| Y1, ...,Yn)  H(V1,n+1) + H(V2,n+1)
where the random variables V1,n+1 and V2,n+1 describe
the number of cycles of the two ring oscillators
between two calls of the RNG
Lower entropy bound: Estimate the entropy from
below that the output function extracts from the
internal state.
Schindler
24.01.2008
Slide 32
Example 6 (VI)

In [Sch3] a thorough analysis of the PTRNG design
is given. Both a lower and an upper entropy bound
per internal random bit are given that depend on
 the
intermediate time between subsequent outputs
in multiples of the average cycle time
 the
jitter of the ring oscillators
 the
bit length k of the internal random numbers.
Schindler
24.01.2008
Slide 33
Example 6 (VII): Numerical values


 = average cycle length
 = 0.01  (optimistic assumption)
Time
k
internal state
entropy per random number
(increase of entropy)
10000 
1
4,209
0.943
10000 
2
4.209
0.914
10000 
3
4.209
0.866
60000 
1
6.698
0.991
Schindler
24.01.2008
Slide 34
Example 7
internal
random
numbers
Schindler
24.01.2008
Slide 35
sw(1)=5
sw(2)=5
sw(3)=7
sw(4)=6
sw(5)=8
time
0
s
|
2s
= clock signal
3s
4s
5s
| = (0-1)-comparator switch
swn= # (0-1) crossings in time interval ((n-1)s,ns]
das random number: rn = swn
internal random number: yn+1 = yn + rn+1 (mod 2)
Schindler
24.01.2008
Slide 36
Strategy
 Goal: Determine (at least a lower bound for)
H(Yn+1 | Y0, ...,Yn)
Remark: Example 7 contains joint research work
with Wolfgang Killmann.
Schindler
24.01.2008
Slide 37
Notation
 t1,t2,....: time periods between subsequent
switches of the comparator
 zn: smallest index m for which t0+t1+t2+...+tm>sn
 wn = t0+t1+t2+...+tm -sn
(or, equivalently, wn  t0+t1+t2+...+tm (mod s) )
wn denotes the time between sn and the next
comparator switch
Schindler
24.01.2008
Slide 38
Stochastic model (II)
 It is reasonable to assume that the noise source
is in equilibrium state shortly after start-up.
  The stochastic process T1,T2,... is assumed to
be stationary (not necessarily independent !).
Schindler
24.01.2008
Slide 39
Stochastic Model (III)
The das random numbers in Example 6 and
Example 7 (and the das random numbers of other
RNGs designs) can be modelled as follows:
T1,T2,… are stationary
Rn := Zn- Zn-1
with Zn := min {m  N | T0 + … + Tm >sn}
Schindler
24.01.2008
Slide 40
General remark
 Even if two different RNG designs fit to this model
the distribution of the random variables T1,T2,… and
thus of R1,R2,... may be very different.
Schindler
24.01.2008
Slide 41
Stationarity
 The stochastic process T1,T2,... is assumed to be
stationary
Under weak assumptions (essentially, the partial
sums T1+T2 +... + Tm (mod s) should tend to the
uniform distribution on [0,s))
it can be shown that the sequences
W1,W2,... and R1,R2,... are stationary, too.
Strategy: Study the stochastic process R1, R2,...
first.
Schindler
24.01.2008
Slide 42
Stochastic model (IV)
Definition
 V(u) := # 0-1 switchings in [0,u]
 μ = E(Tj)
 σ² := generalized variance of T1,T2,...
 ( . ):= cumulative distribution function of the
standard normal distribution
Schindler
24.01.2008
Slide 43
Auxiliary variables
Lemma: For u = v ∙ μ
Pr ob(V( v )
vk 
v  (k  1) 
 k )  (
 )  (
 ) für k  1
k 
k 1 
Pr ob(V( v )

 0)  1  ((v  1)  )

Schindler
24.01.2008
Slide 44
Entropy (II)
Under mild regularity assumptions on the random
variables Tj the term
H ( Rn 1 | R0 ,..., Rn ) 
min{ H (V( s u ) ) | u  [0,   a ]} Pr ob(Wn    a )
with moderate a>0 should provide a conservative
estimate for H(Rn+1 | R0,...Rn). The size of a depends
on the distribution of the random variables Tj .
Schindler
24.01.2008
Slide 45
Autocovariance
Theorem 1 : Let GW(.) denote the cumulative
distribution function of Wn . Then
js
(i) E ( R 1 +...+ R j ) k 
 E (V
( js u )
+1|W0=u)k GW(du)
0
js
  E (V(js u ) +1)k GW(du)
0
(ii) For k = 2, j=1,2, ... this provides the autocorrelation function of the stationary process R1,R2,...
(iii) If the Tj are iid the above formula is exact. If these
Tj have continuous cumulative distribution function
F(.) then GW(u) = (1-F(u)) /.
Schindler
24.01.2008
Slide 46
Entropy (III)
Theorem 2 (special case): Assume that the
random variables T1,T2, ... are iid with continuous
cumulative distribution function F(∙). Then
 F (u)
1
H ( Rn 1 | R0 ,..., Rn )   H (V( s u ) )

0
s
Schindler
24.01.2008
du
Slide 47
0.000
0.002
0.004
0.006
Periods between successive 0-1-switchings
0
200
400
600
800
imp_mess
Schindler
24.01.2008
Slide 48
Example 7 (II)
 Experimental results: 105 random bits per second
with entropy per bit > 1-10-5.
Numerical values: Erlang (2,)-distribution
a) s = 6*E(T1):
Var(R1)=3.4 , corr(R1,R2)=-0.06,
corr(R1,R3)=-0.004, ...
b) s = 9*E(T1):
Var(R1)= 4.95, corr(R1,R2)= -0.046,
corr(R1,R3)= -0.00005, ...
Schindler
24.01.2008
Slide 49
PTRNGs in operation: Potential risks
 Worst case: total breakdown of the noise source
Ageing effects, tolerances of components of the
noise source and external influences might cause the
generation of random numbers with unacceptably low
quality.
Such events must be detected certainly so that
appropriate responses can be initiated.
Schindler
24.01.2008
Slide 50
Security measures
goal
tot-test
shall detect a total breakdown of the
noise source very soon
startup test
shall ensure the functionality of the
PTRNG when it is started
online test
shall detect non-tolerable weaknesses or
deterioration of the quality of random
numbers sufficiently soon
Schindler
24.01.2008
Slide 51
Example 8: LFSR (linear feedback shift register)
das-r.n.
algorithmic postprocessing
internal r.n.
...
...
worst case scenario: total breakdown of the noise
source, inducing constant das-random numbers
entropy / bit = 0, ... but ...
internal r.n.s: good statistical properties!!!
Schindler
24.01.2008
Slide 52
Example 8 (II)
 Statistical blackbox tests that are applied to the
internal random numbers will not even detect a total
breakdown of the noise source (unless the linear
complexity profile is tested).
 Instead, the online test should be applied to the
das random numbers (typical situation).
Schindler
24.01.2008
Slide 53
General Remark
 The online test should be tailored to the particular
RNG (  stochastic model).
 In Example 5 (coin tossing) a monobit test would
be appropriate.
 In [Sch1] a generic two-step procedure for the tot
test, the startup test and the online test is
introduced.
Schindler
24.01.2008
Slide 54
Noise alarms
 A failure of the online test, the tot test or the
startup test causes a noise alarm.
 (At least) the online test is usually realized by
statistical tests. Consequently, „false noise alarms“
may occur.
 The probability for a false noise alarm depends on
the significance level of the statistical tests and the
evaluation rules.
Schindler
24.01.2008
Slide 55
Consequences of a noise alarm
The consequences of a noise alarm may depend on
the conditions of use. Possible reactions:
 The PTRNG is shut down.
 A human operator or the PTRNG software initiates
an „emergency test“. Depending on the outcome of
this emergency test the PTRNG is either shut down
or put into operation again.
 audit of noise alarms
…
Schindler
24.01.2008
Slide 56
ITSEC and CC
ITSEC (Information Technology Security Evaluation
Criteria) and CC (Common Criteria)
 provide evaluation criteria for IT products which
shall permit the comparability between
independent security evaluations.
 A product or system that has successfully been
evaluated is awarded with an internationally
recognized IT security certificate.
Schindler
24.01.2008
Slide 57
CC: Evaluation of Random Number Generators
ITSEC, CC and the corresponding evaluation
manuals do not specify evaluation criteria for random
number generators.
In the German evaluation and certification scheme the
evaluation guidance document
AIS 31: Functionality Classes and Evaluation
Methodology for Physical Random Number
Generators
has been effective since September 2001
Schindler
24.01.2008
Slide 58
AIS 31
distinguishes between two functionality classes
with increasing requirements
P1 (for less sensitive applications as, for
instance, IVs that are transmitted in clear)
P2 (for sensitive applications as, for instance,
the generation of session keys, signature
parameters, ephemeral keys)
Schindler
24.01.2008
Slide 59
AIS 31: Reference Implementation
 The AIS 31 is technically neutral. The applicant for
a certificate has to give evidence that the PTRNG
meets all requirements.
 The AIS 31 has been well-tried in a number of
product evaluations.
 A reference implementation of the applied
statistical tests can be found
www.bsi.bund.de/zertifiz/zert/interpr/ais_cc.htm
Schindler
24.01.2008
Slide 60
Alternative security paradigm
 The crucial points of an AIS 31 evaluation are the
understanding of the design and the effectiveness of
the online test.
Alternative approach (e.g., ANSI X9.82, Part 2 (draft)):
 complex algorithmic postprocessing algorithm with
memory that meets requirements R1-R3.
Schindler
24.01.2008
Slide 61
Alternative security paradigm:
Advantages and disadvantages
 (+) minor requirements on the understanding of
the RNG design
 (+) minor requirements on the effectiveness of the
online tests
 (-) requires a time-consuming postprocessing
algorithm
 (-) possibly (without being noticed!) only practical
security
 (-) requires the protection of the internal state
Schindler
24.01.2008
Slide 62
ISO / IEC 18031 „Random Bit Generation“
 covers
all classes of RNGs
 PTRNGs: Allows
design principles that either
follow the AIS 31 or the ANSI X9.82 (draft)
approach
 considers
also the correctness of the
implementation
Schindler
24.01.2008
Slide 63
Final remark
Combining
a
strong noise source

with effective online tests

and a strong algorithmic postprocessing algorithm
provides two security anchors which ensure
theoretical security and computational security,
respectively.
Schindler
24.01.2008
Slide 64
Contact
Federal Office for Information Security
(BSI)
Prof. Dr. Werner Schindler
Godesberger Allee 185-189
53175 Bonn
Tel: +49 (0)3018-9582-5652
Fax: +49 (0)3018-10-9582-5652
[email protected]
www.bsi.bund.de
www.bsi-fuer-buerger.de
Schindler
24.01.2008
Slide 65
Ersatzfolien

ERSATZFOLIEN
Schindler
24.01.2008
Slide 66
Entropy (Shannon Entropy)
Definition: Let X denote a random variable that
assumes values in a finite set S = {s1, ... ,st}. The
(Shannon) entropy of X is given by
H(X) =
_
t
 Prob(X= sj)* log2 (Prob(X=sj))
j=1
Remark: (i) 0  H(X)  log2| S |
(ii) Shannon entropy is (maybe the most) important
representative of a family of entropy definitions.
Schindler
24.01.2008
Slide 67
Renyi Entropy
For 0     the term
t
1
__
H(X) =
log2  Prob(X= sj)
1- 
j=1
denotes the Renyi entropy of X to parameter .
As a function of  the Rényi entropy is monotonously
decreasing.
The most important parameters are  = 1 (Shannon
entropy) and  =  (or more precisely,   ; minentropy).
H(X) = min {- log2(Prob(X=sj)) | j  t}
Schindler
24.01.2008
Slide 68
Evaluation aspects: PTRNGs vs. NPTRNGs
The noise source of a physical TRNG
•
dedicated hardware
•
behaves essentially identical for all copies
•
allows accurate modelling and analysis
The entropy source of a non-physical TRNG
•
exploits system data or human interaction
•
may show very different behaviour for different
exemplars of the RNG
•
does usually not allow an accurate, universally
valid model
Schindler
24.01.2008
Slide 69