]> 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\in {ℤ}_{p}^{*}$ that is a generator of a cyclic group of prime order $q$.

Then Alice picks a random $0\le x and sends ${g}^{x}$ to Bob, and Bob picks a random $0\le y and sends ${g}^{y}$ to Alice. They both compute their shared secret ${g}^{\mathrm{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}^{\mathrm{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}^{\mathrm{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\left({g}^{\mathrm{xy}}\right)$ 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 $\left\{{g}^{x},{g}^{y},B\left({g}^{\mathrm{xy}}\right),x,y←{ℤ}_{q}\right\}$ and $\left\{{g}^{x},{g}^{y},r,x,y←{ℤ}_{q},r←\left\{0,1\right\}\right\}$. More formally:

Theorem: If the CDH problem is $\left(t,\epsilon \right)$-hard then there is no $\left(t,\epsilon /128\right)$-distinguisher between

$\left\{{g}^{{x}_{1}},...,{g}^{{x}^{128}},{g}^{{y}_{1}},...,{g}^{{y}_{128}},K=B\left({g}^{{x}_{1}{y}_{1}}\right)\mid \mid ...\mid \mid B\left({g}^{{x}_{128}{y}_{128}}\right),\stackrel{‾}{x},\stackrel{‾}{y}←{ℤ}_{q}^{128}\right\}$

and

$\left\{{g}^{{x}_{1}},...,{g}^{{x}^{128}},{g}^{{y}_{1}},...,{g}^{{y}_{128}},K,\stackrel{‾}{x},\stackrel{‾}{y}←{ℤ}_{q}^{128},K←\left\{0,1{\right\}}^{128}\right\}$

Sketch of proof: distinguisher $⇒$ predictor for $i$th bit $⇒$ predictor for $B\left({g}^{\mathrm{xy}}\right)$ 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 $\left(t,\epsilon \right)$-Decisional Diffie-Hellman (DDH) assumption says that the distribution

$\left\{g,{g}^{a},{g}^{b},{g}^{c}\mid a,b,c←{ℤ}_{q}\right\}$

is $\left(t,\epsilon \right)$-indistinguishable from the distribution

$\left\{g,{g}^{a},{g}^{b},{g}^{\mathrm{ab}}\mid a,b←{ℤ}_{q}\right\}$

(In other words, given ${g}^{a}$ and ${g}^{b}$, ${g}^{ab}$ is indistinguishable from a random element, which implies that $⌊\mathrm{lg}q⌋$ bits of ${g}^{\mathrm{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=⌊\mathrm{lg}q⌋$, and suppose $\mid G\mid \approx {2}^{m}$. Set $e=m/3$, and let $H=\left\{{h}_{\lambda }\mid \lambda \in \Lambda \right\}:{ℤ}_{p}^{*}\to \left\{0,1{\right\}}^{m-2e}=\left\{0,1{\right\}}^{m/3}=\left\{0,1{\right\}}^{85}$. be almost universal. Then consider the following key exchange protocol:

Alice picks $x←{ℤ}_{q},{\lambda }_{1}←\Lambda$ and sends ${g}^{x},{\lambda }_{1}$ to Bob. Similarly, Bob picks $y←{ℤ}_{q},{\lambda }_{2}←\Lambda$ and sends ${g}^{y},{\lambda }_{2}$ to Alice. They both compute the secret key $\mathrm{SK}={h}_{{\lambda }_{1}\oplus {\lambda }_{2}}\left({g}^{\mathrm{xy}}\right)$.

Theorem: Assuming $\left(t,\epsilon \right)$-DDH on $G$, the distributions

$\left\{g,{g}^{x},{g}^{y},{\lambda }_{1},{\lambda }_{2},\mathrm{SK}\mid x,y←{ℤ}_{q},{\lambda }_{1},{\lambda }_{2}←\Lambda \right\}$

and

$\left\{g,{g}^{x},{g}^{y},{\lambda }_{1},{\lambda }_{2},R\mid x,y←{ℤ}_{q},{\lambda }_{1},{\lambda }_{2}←\Lambda ,R←\left\{0,1{\right\}}^{m/3}\right\}$

are $\left(t,\epsilon +1/{2}^{m/3}\right)$-indistinguishable.

Proof: Suppose $A$ is a $\left(t,\epsilon +1/{2}^{m/3}\right)$-distiguisher. Then we can construct a DDH-distiguisher $B$ as follows.

• $B$ is given a tuple $I=⟨g,{g}_{1},{g}_{2},{g}_{3}⟩\in {G}^{4}$.

• $B$ picks random ${\lambda }_{1},{\lambda }_{2}←\Lambda$, and computes $S={h}_{{\lambda }_{1}\oplus {\lambda }_{2}}\left({g}_{3}\right)$.

• $B$ gives the tuple $I\prime =⟨{g}_{1},{g}_{2},{g}_{3},{\lambda }_{1},{\lambda }_{2},S⟩$ to $A$, and outputs the output of $A$.

We show that $B$ is a $\left(t,\epsilon \right)$-DDH algorithm. Note

$\mid \mathrm{Pr}\left[B\left(I\right)\mid I-\mathrm{DDH}\right]-\mathrm{Pr}\left[B\left(I\right)\mid I-\mathrm{randg}3\right]\mid =\mid \mathrm{Pr}\left[A\left(I\prime \right)\mid I\prime -\mathrm{DDH}\right]-\mathrm{Pr}\left[A\left(I\prime \right)\mid I\prime -\mathrm{randg}3\mathrm{hash}\right]\ge \mid \mathrm{Pr}\left[A\left(I\prime \right)\mid I\prime -\mathrm{DDH}\right]-\mathrm{Pr}\left(A\left(I\prime \right)\mid I\prime -\mathrm{rand}01m3\right]\mid -\mid \mathrm{Pr}\left[A\left(I\prime \right)\mid I\prime -\mathrm{rand}01m3-\mathrm{Pr}\left[A\left(I\prime \right)\mid I\prime -\mathrm{randg}3\mathrm{hash}\right]\mid$

where we have used the inequality $\mid A+B\mid \ge \mid A\mid -\mid B\mid$. Now the first term is at least $\epsilon +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=\left\{{h}_{\lambda }:\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{l}{\right\}}_{\lambda \in \Lambda }$

$H$ is called a universal family of hash functions if for all $x\ne y\in \left\{0,1{\right\}}^{n}$ we have

${\mathrm{Pr}}_{h←H}\left[h\left(x\right)=h\left(y\right)\right]=1/{2}^{l}$

$H$ is almost universal if for all $x\ne y\in \left\{0,1{\right\}}^{n}$ we have

${\mathrm{Pr}}_{h←H}\left[h\left(x\right)=h\left(y\right)\right]=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\prime$ be distributions on $S$. For all $x\in S$, denote the probability of picking $x$ according to $D$ by $D\left(x\right)$, and for all $X\subseteq S$, define $D\left(X\right)={\sum }_{x\in X}D\left(x\right)$. Define the following:

• The collision probability of $D$ is $\mathrm{coll}\left(D\right)={\sum }_{x\in S}D\left(x{\right)}^{2}$.

• $D,D\prime$ are $\epsilon$-statistically indistinguishable if for all $X\subseteq S$, we have $\mid D\left(X\right)-D\prime \left(X\right)\mid <\epsilon$.

• $D$ is $\epsilon$-quasirandom if $D$ is $\epsilon$-statistically indistinguishable from the uniform distribution on $S$ (which we denote by $U\left(S\right)$. Hence for any subset $X\subseteq S$ we have $\mid D\left(X\right)-\mid X\mid /\mid S\mid \mid <\epsilon .$

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

$\mid {\mathrm{Pr}}_{x←D}\left[A\left(x\right)\text{accepts}\right]-{\mathrm{Pr}}_{x←U\left(S\right)}\left[A\left(x\right)\text{accepts}\right]\mid <\epsilon$

Proof: Let $T\subseteq S$ be $T\left\{x\mid A\left(x\right)\right\}$. Then

$\begin{array}{ccc}\mid {\mathrm{Pr}}_{x←D}\left[A\left(x\right)\right]-{\mathrm{Pr}}_{x←U\left(S\right)}\left[A\left(x\right)\right]\mid & =& \mid {\mathrm{Pr}}_{x←D}\left[A\left(x\right)\mid x\in T\right]\mathrm{Pr}\left[x\in T\right]\\ & +& {\mathrm{Pr}}_{x←D}\left[A\left(x\right)\mid x\notin T\right]\mathrm{Pr}\left[x\notin T\right]\\ & -& {\mathrm{Pr}}_{x←U\left(S\right)}\left[A\left(x\right)\mid x\in T\right]\mathrm{Pr}\left[x\in T\right]\\ & -& {\mathrm{Pr}}_{x←U\left(S\right)}\left[A\left(x\right)\mid x\notin T\right]\mathrm{Pr}\left[x\notin T\right]\mid \\ & =& \mid {\mathrm{Pr}}_{x←D}\left[x\in T\right]-{\mathrm{Pr}}_{x←U\left(S\right)}\left[x\in T\right]\mid \\ & =& \mid D\left(T\right)-U\left(T\right)\mid <\epsilon \end{array}$

Leftover Lemma: Let $G\subseteq \left\{0,1{\right\}}^{n}$, $\mid G\mid >{2}^{l}$. Let $e>0$ and let $H$ be an almost universal hash family from $\left\{0,1{\right\}}^{n}$ to $\left\{0,1{\right\}}^{l-2e}$. Then the distribution $\left\{\left(h,h\left(x\right)\right)\mid h←H,x←G\right\}$ is $1/{2}^{e}$-quasirandom on $H×\left\{0,1{\right\}}^{l-2e}$.

Proof: there are two steps to the proof.

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

$\mathrm{coll}\left(\left(h,h\left(x\right){\right)}_{h←H,x←G}\right)<\left(1+2/{2}^{2e}\right)/\mid H\mid {2}^{l-2e}$

Claim: Let $D$ be a distribution on a finite set $S$. If $\mathrm{coll}\left(D\right)<\left(1+2{\delta }^{2}\right)/\mid S\mid$ then $D$ is $\delta$-quasirandom.

Proof of claim: Suppose there exists some subset $X\subseteq S$ such that $D\left(X\right)\ge \mid X\mid /\mid S\mid +\delta$. Without loss of generality, assume equality holds (we can just increase $\delta$). We have $D\left(S\setminus X\right)=1-D\left(X\right)$. Then

$\begin{array}{ccc}\mathrm{coll}\left(D\right)& =& {\mathrm{Pr}}_{{x}_{1},{x}_{2}←D}\left[{x}_{1}={x}_{2}\right]\\ & =& {\mathrm{Pr}}_{D}\left[{x}_{1}={x}_{2}\mid {x}_{1}\wedge {x}_{2}\in X\right]\mathrm{Pr}\left[{x}_{1}\wedge {x}_{2}\in X\right]+{\mathrm{Pr}}_{D}\left[{x}_{1}={x}_{2}\mid {x}_{1}\wedge {x}_{2}\notin X\right]\mathrm{Pr}\left[{x}_{1}\wedge {x}_{2}\notin X\right]\\ & =& {\mathrm{Pr}}_{D}\left[{x}_{1}={x}_{2}\mid {x}_{1}\wedge {x}_{2}\in X\right]D\left(X{\right)}^{2}+{\mathrm{Pr}}_{D}\left[{x}_{1}={x}_{2}\mid {x}_{1}\wedge {x}_{2}\notin X\right]D\left(S\setminus X{\right)}^{2}\\ & \ge & 1/\mid X\mid D\left(X{\right)}^{2}+1/\mid S\setminus X\mid D\left(S\setminus X{\right)}^{2}\\ & =& D\left(X{\right)}^{2}/\mid X\mid +\left(1-D\left(X\right){\right)}^{2}/\left(\mid S\mid -\mid X\mid \right)\\ & =& 1/\mid S\mid +{\delta }^{2}/\mid X\mid +{\delta }^{2}/\left(\mid S\mid -\mid X\mid \right)\end{array}$

(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 $\mid X\mid =\mid S\mid /2$, thus we have

$\mathrm{coll}\left(D\right)\ge 1/\mid S\mid +4{\delta }^{2}/\mid S\mid \ge 1\mid S\mid +2{\delta }^{2}/\mid S\mid$

So by the first claim

$\mathrm{coll}\left(\left(h,h\left(x\right){\right)}_{h←H,x←G}\right)<\left(1+2\left(1/{2}^{e}{\right)}^{2}\right)/\mid H\mid {2}^{l-2e}$

and we have $\mid S\mid =\mid H\mid {2}^{l-2e}$, $\delta =1/{2}^{e}$. Then by the second claim, $\left(h,h\left(x\right)\right)$ 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

$\mathrm{min}-\mathrm{entropy}\left(D\right)=\underset{x\in S}{\mathrm{min}}\left\{-\mathrm{lg}D\left(x\right)\mid D\left(x\right)\ne 0\right\}.$

For example, the min-entropy of a point distribution is zero, and for the uniform distribution $U\left(S\right)$, it is $\mathrm{lg}\mid S\mid$.

Now suppose $G$ is a set with $\mid G\mid =\mid S\mid /{2}^{\delta }$. Then $\mathrm{min}-\mathrm{entropy}\left(U\left(G\right)\right)=\mathrm{lg}\mid S\mid -\delta$. Thus we see that $\mathrm{min}-\mathrm{entropy}\left(D\right)=\delta$ implies that for all $x\in S$ we have $D\left(x\right)\le {2}^{-\delta }$. Sometimes the distribution $D$ is referred to as a $\delta$-source. It turns out that it is possible to extract about $\delta$ bits from an arbitrary $\delta$-source.

Theorem: For any $l$, and $e\le l/2$, there exists a family $H$ of hash functions

$H=\left\{{h}_{\lambda }:\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{l-2e}{\right\}}_{\lambda \in \Lambda }$

such that

• $\mid H\mid =O\left(n{2}^{4\left(l-e\right)}\right)$ (only $4\left(l-e\right)+O\left(\mathrm{log}n\right)$ bits are needed to describe the family)

• For any distribution $D$ on $\left\{0,1{\right\}}^{m}$ with $\mathrm{min}-\mathrm{entropy}\left(D\right)=l$, the distribution $\left\{\left(h,h\left(x\right)\mid h←H,x←D\right\}$ 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.