]> Cryptography - Session Key Construction: Extracting Randomness

Suppose Alice and Bob wish to perform a Diffie-Hellman key exchange. Then for some n they pick an n-bit prime p, and an element g p * that is a generator of a cyclic group of prime order q.

Then Alice picks a random 0 x<q and sends g x to Bob, and Bob picks a random 0 y<q and sends g y to Alice. They both compute their shared secret g xy. But this is not the whole story: now they must somehow derive a session key from this quantity. To an adversary, the session key should be indistinguishable from a random string.

In practice, an off-the-shelf hash function such as SHA1 is applied to some representation of g xy, and then the 128 LSBs are used as the key. Unfortunately the only known way to prove that this is secure is to "prove by assumption": i.e. concoct the Hash Diffie-Hellman assumption.

Security from the CDH assumption

One obvious way to proceed is to extract a hardcore bit of g xy. For example, using the Goldreich-Levin method, they can find a hardcore bit B, and to derive a 128-bit key, they simply perform 128 Diffie-Hellman exchanges and extract B(g xy) each time. This is secure provided we assume no efficient Computational Diffie-Hellman algorithm exists, for then the adversary should not be able to distinguish between the distributions {g x,g y,B(g xy),x,y q} and {g x,g y,r,x,y q,r{0,1 }}. More formally:

Theorem: If the CDH problem is (t,ε)-hard then there is no (t,ε/128 )-distinguisher between

{g x 1 ,...,g x 128 ,g y 1 ,...,g y 128 ,K=B(g x 1 y 1 )...B(g x 128 y 128 ),x,y q 128 }


{g x 1 ,...,g x 128 ,g y 1 ,...,g y 128 ,K,x,y q 128 ,K{0,1 } 128 }

Sketch of proof: distinguisher predictor for ith bit predictor for B(g xy) given g x,g y CDH algorithm.

However, this method is impractical as it requires one Diffie-Hellman exchange for each bit of the session key. Unfortunately, it is not known how to improve this method much without using a stronger assumption:

Security from the DDH assumption

The (t,ε)-Decisional Diffie-Hellman (DDH) assumption says that the distribution

{g,g a,g b,g ca,b,c q}

is (t,ε)-indistinguishable from the distribution

{g,g a,g b,g aba,b q}

(In other words, given g a and g b, g ab is indistinguishable from a random element, which implies that lgq bits of g ab are simultanesouly secure given g a,g b.

Using this assumption allows a provably secure scheme for extracting a session key, via the left-over lemma.

Let p be a 1024-bit prime, and let q be a 255-bit prime such that G is a subgroup of p * of order q, and let g be a generator of G. Let m=lgq, and suppose G2 m. Set e=m/3 , and let H={h λλΛ}: p *{0,1 } m2 e={0,1 } m/3 ={0,1 } 85 . be almost universal. Then consider the following key exchange protocol:

Alice picks x q,λ 1 Λ and sends g x,λ 1 to Bob. Similarly, Bob picks y q,λ 2 Λ and sends g y,λ 2 to Alice. They both compute the secret key SK=h λ 1 λ 2 (g xy).

Theorem: Assuming (t,ε)-DDH on G, the distributions

{g,g x,g y,λ 1 ,λ 2 ,SKx,y q,λ 1 ,λ 2 Λ}


{g,g x,g y,λ 1 ,λ 2 ,Rx,y q,λ 1 ,λ 2 Λ,R{0,1 } m/3 }

are (t,ε+1 /2 m/3 )-indistinguishable.

Proof: Suppose A is a (t,ε+1 /2 m/3 )-distiguisher. Then we can construct a DDH-distiguisher B as follows.

  • B is given a tuple I=g,g 1 ,g 2 ,g 3 G 4 .

  • B picks random λ 1 ,λ 2 Λ, and computes S=h λ 1 λ 2 (g 3 ).

  • B gives the tuple I=g 1 ,g 2 ,g 3 ,λ 1 ,λ 2 ,S to A, and outputs the output of A.

We show that B is a (t,ε)-DDH algorithm. Note

Pr[B(I)IDDH]Pr[B(I)Irandg3 ]=Pr[A(I)IDDH]Pr[A(I)Irandg3 hash]Pr[A(I)IDDH]Pr(A(I)Irand01 m3 ]Pr[A(I)Irand01 m3 Pr[A(I)Irandg3 hash]

where we have used the inequality A+BAB. Now the first term is at least ε+1 /2 m/3 , while the second term is at most 1 /2 m/3 by the leftover lemma.

Leftover Lemma

The leftover lemma shows how to extracts randomness from a "defective" random source.

Definition: Let

H={h λ:{0,1 } n{0,1 } l} λΛ

H is called a universal family of hash functions if for all xy{0,1 } n we have

Pr hH[h(x)=h(y)]=1 /2 l

H is almost universal if for all xy{0,1 } n we have

Pr hH[h(x)=h(y)]=1 /2 l+1 /2 n.

A set of all linear congruential generators (modulo some prime p) is an example of an almost universal family of hash functions.

Definition: Let S be a finite set and D,D be distributions on S. For all xS, denote the probability of picking x according to D by D(x), and for all XS, define D(X)= xXD(x). Define the following:

  • The collision probability of D is coll(D)= xSD(x) 2 .

  • D,D are ε-statistically indistinguishable if for all XS, we have D(X)D(X)<ε.

  • D is ε-quasirandom if D is ε-statistically indistinguishable from the uniform distribution on S (which we denote by U(S). Hence for any subset XS we have D(X)X/S<ε.

Quasirandomness is useful. For suppose D is ε-quasirandom on S. Then for any algorithm A, we have

Pr xD[A(x)accepts]Pr xU(S)[A(x)accepts]<ε

Proof: Let TS be T{xA(x)}. Then

Pr xD[A(x)]Pr xU(S)[A(x)] = Pr xD[A(x)xT]Pr[xT] + Pr xD[A(x)xT]Pr[xT] Pr xU(S)[A(x)xT]Pr[xT] Pr xU(S)[A(x)xT]Pr[xT] = Pr xD[xT]Pr xU(S)[xT] = D(T)U(T)<ε

Leftover Lemma: Let G{0,1 } n, G>2 l. Let e>0 and let H be an almost universal hash family from {0,1 } n to {0,1 } l2 e. Then the distribution {(h,h(x))hH,xG} is 1 /2 e-quasirandom on H×{0,1 } l2 e.

Proof: there are two steps to the proof.

Claim: (proof omitted) because H is almost universal, the collision probability

coll((h,h(x)) hH,xG)<(1 +2 /2 2 e)/H2 l2 e

Claim: Let D be a distribution on a finite set S. If coll(D)<(1 +2 δ 2 )/S then D is δ-quasirandom.

Proof of claim: Suppose there exists some subset XS such that D(X)X/S+δ. Without loss of generality, assume equality holds (we can just increase δ). We have D(SX)=1 D(X). Then

coll(D) = Pr x 1 ,x 2 D[x 1 =x 2 ] = Pr D[x 1 =x 2 x 1 x 2 X]Pr[x 1 x 2 X]+Pr D[x 1 =x 2 x 1 x 2 X]Pr[x 1 x 2 X] = Pr D[x 1 =x 2 x 1 x 2 X]D(X) 2 +Pr D[x 1 =x 2 x 1 x 2 X]D(SX) 2 1 /XD(X) 2 +1 /SXD(SX) 2 = D(X) 2 /X+(1 D(X)) 2 /(SX) = 1 /S+δ 2 /X+δ 2 /(SX)

(Because we are considering collison probabilities, we can ignore the cases when only one of x 1 ,x 2 lies in X). The last line is minimized when X=S/2 , thus we have

coll(D)1 /S+4 δ 2 /S1 S+2 δ 2 /S

So by the first claim

coll((h,h(x)) hH,xG)<(1 +2 (1 /2 e) 2 )/H2 l2 e

and we have S=H2 l2 e, δ=1 /2 e. Then by the second claim, (h,h(x)) is 1 /2 e-quasirandom.

More Powerful Extractors

There are more effective techniques than the leftover lemma [SZ94]. Let D be a distribution on a finiste set S and define

minentropy(D)=min xS{lgD(x)D(x)0 }.

For example, the min-entropy of a point distribution is zero, and for the uniform distribution U(S), it is lgS.

Now suppose G is a set with G=S/2 δ. Then minentropy(U(G))=lgSδ. Thus we see that minentropy(D)=δ implies that for all xS we have D(x)2 δ. Sometimes the distribution D is referred to as a δ-source. It turns out that it is possible to extract about δ bits from an arbitrary δ-source.

Theorem: For any l, and el/2 , there exists a family H of hash functions

H={h λ:{0,1 } n{0,1 } l2 e} λΛ

such that

  • H=O(n2 4 (le)) (only 4 (le)+O(logn) bits are needed to describe the family)

  • For any distribution D on {0,1 } m with minentropy(D)=l, the distribution {(h,h(x)hH,xD} is 2 /2 e-quasirandom

The theorem is used to construct cryptosystems with exposure-resilience: even if an adversary learns "crazy" bits of a key, security is still maintained. The idea is to split a key into two parts, the first part specifies the hash function to use while the other bits are fed into the hash function.