LINEBURG

ñòðàíèöà 1 |

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

coron@clipper.ens.fr coron@gemplus.com

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

sources.

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 :

8r

>P Pj = 1

>

>

> j=1

<

r

>

> P

Pi Pr( j j i ) r?1

Pj = for 1 j

>

>

:

i=1

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 :

8

if j = 2i + 1 mod 2M

pi

<

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 :

X

HS = P i Hi

i

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 :

n(q)

lim log2N = HS

N!1

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 :

X

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 :

23

1

Pr bjW] = W (b)U where U = 4 . 5

.

.

1

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 :

Q+K

1 X

fTU (sN ) = K log2 An (sN ) (2)

n=Q+1

where B denotes the set f0; 1g and An (sN ) the minimum distance between

the n-th block and any similar preceding block :

8

if 8i < n; bn?i (sN ) 6= bn (sN )

n

<

An (sN ) = :

minfi : i 1; bn(sN ) = bn?i (sN )g otherwise.

(3)

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

memory.

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]) :

X

KL = ? Pr b] log2 Pr b] (4)

b2BL

X

FL = ? Pr b; j] log2 Pr jjb] (5)

b2BL?1; j2B

L

KL = 1 X F

GL = L L (6)

i

i=1

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

N

US of random binary variables and the entropy of L-bit blocks of S :

1

Z

h i

4

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 :

Q+K

g (sN ) = 1 X g(A (sN ))

fTU K n=Q+1 n

gN

The mean of fTU (US ) for S is given by :

X

gN N

E fTU (US )] = Pr An (US ) = i]g(i)

i1

with

X

N Pr bn = b; bn?1 6= b; : : : ; bn?i+1 6= b; bn?i = b]

Pr An (US ) = i] = (8)

b2BL

If we assume that the L-bit blocks are statistically independent, the above

probability factors into :

X

N Pr b]2 (1 ? Pr b])i?1

Pr An (US ) = i] =

b2BL

and we get :

X

N

E fTU (US )] = Pr b] g (Pr b]) (9)

b2BL

where :

1

X

(1 ? x)i?1 g(i)

g (x) = x

i=1

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

X

ti?1 g(i) = ? log2 (1 ? t) =

(1 ? t) log(2) i=1 i

i=1

and we get :

g(1) = 0

g(i + 1) ? g(i) = i log(2) for i 1;

1

Hence we can de ne a modi ed version of Maurer's test which test parameter

fTU (sN ) is computed using :

H

Q+K

1 X

fTU (sN ) = K

H g(An (sN )) (11)

n=Q+1

i?1

1 X1

g(i) = log(2) (12)

k=1 k

and equation (3) for the de nition of An (sN ).

N

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 :

HN

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 ),

H

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

H H

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-

H

H

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

N )] = c(L; K)2 Var log2 An (R )]

Var f (R

TU K

Similarly, we can de ne cH (L; K) to be the corrective factor by which the

H

standard deviation of the modi ed test parameter fTU is reduced compared to

what it would have been if the An -terms were independent :

N

Var fTU (RN )] = cH (L; K)2 Var g(An (R ))]

H

K

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 ))]

2

1 i?1

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

?L

=2 2

k=1 k log(2)

i=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 :

i?1

1 X 1:

g(i) = log(2) k

k=1

As in 3], the factor cH (L; K) can be approximated for K 33 2L by :

L

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

H

normal distribution of mean E fTU (RN )] = L and standard deviation :

H

q

= c(L; K) Var g(An (RN ))]=K

ñòðàíèöà 1 |

Copyright © Design by: Sunlight webdesign