( 2)

. . >>

Jean-Sebastien Coron
Ecole Normale Superieure Gemplus Card International
45 rue d'Ulm 34 rue Guynemer
Paris, F-75230, France Issy-les-Moulineaux, F-92447, France

Abstract. Many applications rely on the security of their random num-
ber generator. It is therefore essential that such devices be extensively
tested for malfunction. The purpose of a statistical test is to detect spe-
ci c weaknesses in random sources.
Maurer's universal test is a very common randomness test, capable of
detecting a wide range of statistical defects. The test is based on the
computation of a function which is asymptotically related to the source's
entropy, which measures the e ective key-size of block ciphers keyed by
the source's output.
In this work we develop a variant of Maurer's test where the test function
is in theory exactly equal to the source's entropy, thereby enabling a
better detection of defects in the tested source.

1 Introduction
Random number generators are probably the most basic cryptographic prim-
itives. They are widely used for block cipher, public-key (e.g. RSA-moduli),
keystream generation and as passwords sources. In some algorithms (e.g. DSA)
or protocols (e.g. zero-knowledge), random numbers are intrinsic to the compu-
tation. In all these applications, security tightly depends on the randomness of
the source.
A pseudo-random generator is a deterministic polynomial time algorithm
that expands short seeds into longer bit sequences, which distribution is po-
lynomially-indistinguishable from the uniform probability distribution. In other
words, the output bits must appear to be statistically independent and uniformly
distributed. The rst pseudo-random generator was constructed and proved by
Blum and Micali, under the assumption that the discrete logarithm problem is
intractable on a non-negligible fraction of instances 2]. In the light of their prac-
tical and theoretical value, constructing pseudo-random generators is a major
concern. Procedures for ensuring the security of random number generators are
becoming of great importance with the increased usage of electronic communi-
cation 4].
It is nevertheless di cult to give a general and reliable measure of the cryp-
tographic quality of a pseudo-random sequence. In practice, many di erent tests
are carried on sequences generated by the random source to evaluate its perfor-
mance. These practical tests are divided into two groups : complexity tests and
statistical tests. Complexity tests evaluate how much of a generated string is re-
quired to reconstruct the whole string 8] while statistical tests evaluate whether
the generator's behaviour matches a speci c probabilistic model. We refer the
reader to 5] for a general treatment of randomness tests.
Maurer's universal test is based on the stationary ergodic source with -
nite memory statistical model 6]. This model allows the computation of the
source's entropy, which, in turn, measures the number of bits of "unpredictabil-
ity". Failure to provide such unpredictability can weaken severely the security
of a cryptosystem, as an attacker could use the reduction in entropy to speed-up
exhaustive search on an otherwise secure encryption algorithm.
However, Maurer's universal test only provides an asymptotic measure of
the source's entropy. In this paper, we show that with a simple transformation,
Maurer's test function can yield the source's entropy. Therefore the new test
enables a more accurate detection of defects in the tested source.
The paper is organized as follows: we rst recall the basic de nitions of the
stationary ergodic source model and the asymptotic relation between Maurer's
test function and the source's entropy. Then we propose a simple transformation
of Maurer's test so that the test function yields the source's entropy. Then we
study the distribution of the modi ed test and give a sample program. Finally,
we compare the performance of the two tests with respect to di erent random

2 Statistical model for a random source
2.1 De nition
Consider an information source S emitting a sequence U1; U2 ; U3 ; : : : of binary
random variables. S is a nite memory source if there exists a positive integer
M such that the conditional probability distribution of Un , given U1 ; : : : ; Un?1 ,
only depends on the last M bits emitted 6]:

PUn jU1 :::Un?1 (un ju1 : : : un?1 ) = PUn jUn?M :::Un?1 (un jun?M : : : un?1)
for n > M and for every binary sequence u1 ; : : : ; un ] 2 f0; 1gn. The smallest
M is called the memory of the source. The probability distribution of Un is thus
determined by the source's state n = Un?M ; : : : ; Un?1 ] at step n.
The source is stationary if it satis es :
PUn j n (uj ) = PU1 j 1 (uj )
for all n > M, for u 2 f0; 1g and 2 f0; 1gM .
The state-sequence of a stationary source with memory M forms a nite
Markov chain : the source can be in a nite number (actually 2M ) of states i ,
0 i 2M ?1, and there is a set of transition probabilities Pr( j j i ), expressing
the odds that if the system is in state i it will next go to state j . For a general
treatment of Markov chains, the reader is referred to 1].
For a general Markov chain with r states, let Pi(n) be the probability of being
in state i at time t = n and let P (n) be the "state distribution vector" at time
n, i.e., P (n) = P1(n) ; : : : ; Pr(n) ].
Let be the transition matrix of the chain, i.e., i; j = Pr( j j i ) where i; j
is the element in row i and column j of .
For state j at time n the source may originate from any state i at time
n ? 1 and thus :
Pj(n) = Pr( j j 1 )P1(n?1) + : : : + Pr( j j r )Pr(n?1)
which becomes in matrix notations :
P (n) = P (n?1)
For the class of ergodic Markov processes the probabilities Pj(n) of being in
state j after n emitted bits, approach (as n ! 1) an equilibrium Pj which
must satisfy the system of r linear equations :
>P Pj = 1
> j=1

> P
Pi Pr( j j i ) r?1
Pj = for 1 j
In the case of a source with memory M, each of the 2M states has at most
two successor states with non-zero probability, depending on whether a zero or
a one is emitted. The transition probabilities are thus determined by the set of
conditional probabilities pi = Pr(1j i ), 0 i 2M ? 1 of emitting a one from
each state i . The transition matrix is thus de ned by :
if j = 2i + 1 mod 2M
mod 2M
i; j = : 1 ? pi if j = 2i
0 otherwise
The entropy of state i is then Hi = H(pi ), where H is the binary entropy
function :
H(x) = ?x log2 x ? (1 ? x) log2 (1 ? x)
The source's entropy is then the average of the entropies Hi (of states i )
weighted with the state-probabilities Pi :
HS = P i Hi
Let us now assume that the random source is used to generate the N-bit key
of a block cipher and let n(q) be the number of N-bit keys that must be tested
(in decreasing probability order) in order to reach an overall success probability
of q. Shannon proved (see 7], theorem 4) that for q 6= 0 and q 6= 1 :
lim log2N = HS
This shows that when an ergodic stationary source is used to key a block
cipher, the entropy HS is closely related to the number of keys an attacker has
to try in order to nd the right key. In other words, the entropy measures the
e ective key-size of a cryptosystem keyed by the source's output.

2.2 Probability of a bit sequence
In this section we compute the probability of emitting a bit sequence, which
will be used in section 7.2. Starting from a state distribution vector W =
W1 ; : : : ; Wr ], the probability of emitting a bit b 2 f0; 1g is :
Pr bjW] = Wi i; j (1)
where the sum is taken over the couples fi; jg for which b is emitted during
the transition from i to j .
Let (b) be the transition matrix corresponding to an emitted bit b :
if bit b is
(b)i; j = 0 i; j otherwise emitted from i to j

It follows that = (0) + (1) and equation (1) becomes :
Pr bjW] = W (b)U where U = 4 . 5
By iteration, the probability of emitting the sequence b = b0 ; : : : ; bn ] from
the state distribution vector W is :

Pr bjW] = W (b0 ) (b1 ) : : : (bn )U
and with (b) = (b0 ) (b1 ) : : : (bn ) the probability of appearance of se-
quence b is :

Pr b] = P (b)U
3 Maurer's universal test and the source's entropy
3.1 Maurer's test
Maurer's universal test 6] takes as input three integers fL; Q; Kg and a (Q+K)
L = N-bit sample sN = s1 ; : : : ; sN ] generated by the tested source. The param-
eter L is chosen from the interval 6; 16]. The sequence sN is partitioned into non-
overlapping L-bit blocks. For 1 n Q + K, let bn(sN ) = sL(n?1)+1 ; : : : ; sLn]
denote the n-th L-bit block of sN .
The rst Q blocks of the sequence are used to initialize the test; Q should be
chosen to be at least 10 2L in order to have a high likelihood that each of the
2L blocks of L bits occurs at least once in the rst Q blocks. The remaining K
blocks are used to compute the test function fTU : B N ! IR :
1 X
fTU (sN ) = K log2 An (sN ) (2)
where B denotes the set f0; 1g and An (sN ) the minimum distance between
the n-th block and any similar preceding block :
if 8i < n; bn?i (sN ) 6= bn (sN )
An (sN ) = :
minfi : i 1; bn(sN ) = bn?i (sN )g otherwise.

3.2 Asymptotic entropy relation
As will be justi ed later, Maurer's test function is closely related to the source's
entropy. It follows that Maurer's universal test is able to detect any of the sta-
tistical defects that can be modeled by an ergodic stationary source with nite
Let KL be the entropy of L-bit blocks, GL the per-bit entropy of blocks of
L bits and FL the entropy of the L-th order approximation of the source (see
Shannon 7]) :
KL = ? Pr b] log2 Pr b] (4)
FL = ? Pr b; j] log2 Pr jjb] (5)
b2BL?1; j2B
KL = 1 X F
GL = L L (6)
In 3] we proved the following asymptotic relation between the expectation of
Maurer's test function for a stationary ergodic source S outputting a sequence
US of random binary variables and the entropy of L-bit blocks of S :
h i
N )] ? KL = C = e? log2 d = ?0:8327462
lim E fTU (US (7)
L!1 0

In the next section we improve the performance of Maurer's test by modifying
the test function so that its expectation yields the source's entropy, instead of
having an asymptotical relation.

4 Improving Maurer's universal test
Maurer's test function is de ned as the average of the logarithm to the base two
of the minimum distances between two similar blocks. Here we generalize the
de nition of the test parameter to any function g : IN ! IR of the minimum
distance between two similar blocks :
g (sN ) = 1 X g(A (sN ))
fTU K n=Q+1 n
The mean of fTU (US ) for S is given by :
gN N
E fTU (US )] = Pr An (US ) = i]g(i)
N Pr bn = b; bn?1 6= b; : : : ; bn?i+1 6= b; bn?i = b]
Pr An (US ) = i] = (8)
If we assume that the L-bit blocks are statistically independent, the above
probability factors into :
N Pr b]2 (1 ? Pr b])i?1
Pr An (US ) = i] =
and we get :
E fTU (US )] = Pr b] g (Pr b]) (9)
where :
(1 ? x)i?1 g(i)
g (x) = x
Equation (9) shows that the mean value of the generalized test may be inter-
preted as the expectation of a random variable W = W(X) which hits the value
g (Pr b]) with probability Pr b]. However, the entropy of L-bit blocks KL (equa-
tion (4)) can be viewed as the expectation of a random variable W 0 = W 0 (X)
which takes the value ? log2 (Pr b]) with probability Pr b].
In order to determine the expectation of the test with the entropy of L-bit
blocks, we have to solve the following equation :
g (x) = ? log2 (x) (10)
Letting t = 1 ? x, equation (10) yields :
1 1
1 X ti
ti?1 g(i) = ? log2 (1 ? t) =
(1 ? t) log(2) i=1 i
and we get :
g(1) = 0
g(i + 1) ? g(i) = i log(2) for i 1;

Hence we can de ne a modi ed version of Maurer's test which test parameter
fTU (sN ) is computed using :
1 X
fTU (sN ) = K
H g(An (sN )) (11)
1 X1
g(i) = log(2) (12)
k=1 k
and equation (3) for the de nition of An (sN ).
The mean value of this new test function taking as input a sequence US
generated by an ergodic stationary source S is equal to the entropy of L-bit
blocks of S :
E fTU (US )] = KL (13)

5 Distribution of the modi ed test parameter
To tune the test's rejection rate, one must rst know the distribution of fTU (RN ),
where RN denotes a sequence of N bits emitted by a binary symmetric source
(BSS, i.e. a truly random source). A sample sN would then be rejected if the
number of standard deviations separating its fTU (sN ) from E fTU (RN )] exceeds
a reasonable constant.
In this section we compute the mean and standard deviation of the modi ed
test parameter for a BSS under the reasonable assumption that Q ! 1 (in
practice, Q should be larger than 10 2L).
From equations (11 and 12) the expected value E fTU (RN )] of the test pa-
rameter fTU for a BSS is given by :
1 i?1
H (RN )] = 1 X Pr An (RN ) = i] X 1
E f TU (14)
k=1 k
log(2) i=2
Using equation (8) we have for a BSS :
Pr An (RN ) = i] = 2?L(1 ? 2?L )i?1 for i 1 (15)
and with equation (14) :
1 i?1
H (RN )] = 2?L X(1 ? 2?L)i?1 X 1 = L
E f TU
k=1 k
log(2) i=2
Thus the mean of the test parameter for a truly random source is simply
equal to L, the length of the blocks in the tested sequence. Note that this result
is straightforward considering equation (13) since the entropy KL of L-bit blocks
is equal to L for a truly random source.
For statistically independent random variables the variance of a sum is the
sum of variances but the An -terms in (11) are heavily inter-dependent; of course,
the same holds for Maurer's original test function (2). Consequently, Maurer
introduced in 6] a corrective factor c(L; K) by which the standard deviation
of fTU is reduced compared to what it would have been if the An -terms were
independent :
N )] = c(L; K)2 Var log2 An (R )]
Var f (R
Similarly, we can de ne cH (L; K) to be the corrective factor by which the
standard deviation of the modi ed test parameter fTU is reduced compared to
what it would have been if the An -terms were independent :
Var fTU (RN )] = cH (L; K)2 Var g(An (R ))]
The variance of the An -terms can be easily computed using equation (15) :

Var g(An (RN ))] = E (g(An (RN ))2 ] ? E g(An (RN ))]

1 i?1
?L X(1 ? 2?L)i?1 X 1 2
=2 2

k=1 k log(2)
In 3] we have computed the exact value of the factor c(L; K), while only a
heuristic estimate of c(L; K) was given in 6].
The expression of cH (L; K) is very similar to the one of c(L; K) given in
3] as one should simply replace the terms in the formulae containing log2 i by :
1 X 1:
g(i) = log(2) k
As in 3], the factor cH (L; K) can be approximated for K 33 2L by :
cH (L; K)2 = d(L) + e(L)K 2
and Var g(An (RN ))], d(L) and e(L) are listed in table 1 for 3 L 16 and
L ! 1.
This approximation is su cient because the test must be performed with
K 1000 2L.
To summarize, the distribution of fTU (RN ) can be approximated by the
normal distribution of mean E fTU (RN )] = L and standard deviation :
= c(L; K) Var g(An (RN ))]=K

( 2)

. . >>

Copyright Design by: Sunlight webdesign