]> Cryptography - Pseudo-Random Permutations

These are used to model block ciphers. The ideal block cipher is a collection E={π 1 ,...,π 2 s} of random permutations π i:{0,1 } n{0,1 } n, and encryption is described by C=π k(M), where k is the shared key in {1,...,2 s}, and decryption is M=π k 1 (C). Of course this is impossible to achieve in practice, so we use pseudo random permutations. We adopt the Luby-Rackoff definition ['88].

π:{0,1 } n×{0,1 } s{0,1 } n is a (t,ε,q)-PRP if

  • For any K{0,1 } s, π k is a one-to-one function from {0,1 } n to {0,1 } n.

  • For any K{0,1 } s, there is an "efficient" algorithm to evaluate π K(x).

  • For any t-time algorithm A we have

    Pr K{0,1 } s[A π K]Pr σ𝒫[A σ]<ε

    where A makes q oracle queries and 𝒫={π:{0,1 } n{0,1 } n,π a permutation } is the set of all permutations on {0,1 } n.

In other words, under a chosen plaintext attack, π K cannot be distinguished from a random permutation. But the definition does not cater for chosen ciphertext attacks, which inspires the following:

π:{0,1 } n×{0,1 } s{0,1 } n is a (t,ε,q)-SPRP (Strong PRP) if

  • For any K{0,1 } s, π k is a one-to-one function from {0,1 } n to {0,1 } n.

  • For any K{0,1 } s, there is an "efficient" algorithm to evaluate π K(x) and π K 1 (x).

  • For any t-time algorithm A we have

    Pr K{0,1 } s[A π K,π K 1 ]Pr σ𝒫[A σ,σ 1 ]<ε

    where A makes q oracle queries.

Suppose DES is a (t,ε,q)-PRP. Recall it acts as a permutation on 64 bits at a time. Using DES, can we build a PRP that acts on blocks twice as large, i.e. π:{0,1 } 128 ×{0,1 } 56 {0,1 } 128 ? In general, can we construct large SPRP's from smaller ones?

Luby-Rackoff Construction

We show how to construct a PRP from a PRF. Recall that given L,R{0,1 } n and f:{0,1 } n{0,1 } n, the Feistel permutation is D f(LR)=RLf(R). It is clear that D f:{0,1 } 2 n{0,1 } 2 n is a permutation.

Theorem: [LR] If f:{0,1 } n×{0,1 } s{0,1 } n is a (t,ε,q)-PRF then

  1. E K 1 ,K 2 ,K 3 LR=D F K 1 (D F K 2 (D F K 3 )) is a (T,ε+q 2 /2 n,q)-PRP.

  2. E K 1 ,K 2 ,K 3 ,K 4 LR=D F K 1 (D F K 2 (D F K 3 (D F K 4 ))) is a (T,ε+q 2 /2 n,q)-SPRP.

We cannot get away with fewer rounds. A permutation E constructed using only a two-round Feistel network cannot be a PRP, for if we let E(L,R)=(L,R), we would have E(LT,R)=(LT,R), which happens with very low probability for a random permutation.

Similarly, three-round Feistel does not produce SPRP's. [Exercise]

However, note that with two-round Feistel, E=D f 1 (D f 2 ) cannot be distinguished from a random permutation {0,1 } 2 n{0,1 } 2 n under a known (random) plaintext attack and ciphertext attack, that is, if we are given {(x 1 ,E(x 1 )),...,(x q,E(x q))} for random x 1 ,...,x q. This observation inspires the following:

Define condition (*) as follows: for all ij,x i Rx j R, and E(x i) LE(x j) L. (This condition does not hold for the attack on two-round Feistel.)

It turns out that when (*) holds, {(x 1 ,E(x 1 ),...,(x q,E(x q)} is from the same distribution as q input/output pairs of a random permutation.

In the Luby-Rackoff construction, the role of D f 1 ,D f 4 is to ensure condition (*) holds for D f 2 (D f 3 ). In fact, there is a better way of making sure the condition holds [NR'98]: replace D f 1 ,D f 4 by pairwise independent permutations:

Definition: H={h λ:AA} λΛ is a family of pairwise independent permutations if h λ is a permutation for any λΛ and for all αβA, we have

Pr hH[h(x)=αh(y)=β]=1 A1 A1

An example of such a family is

H={h a,b(x)=ax+bmodp} a𝔽 p *,b𝔽 p *,h a,b:𝔽 p𝔽 p,H=p(p1 )

is such a family.

Now suppose f:{0,1 } n×{0,1 } s{0,1 } n, and H={h λ:{0,1 } 2 n{0,1 } 2 n} λΛ. For M{0,1 } 2 n, define

E λ 1 ,λ 2 ,K 1 ,K 2 NR(M)=h λ 1 (D f K 1 (D f K 2 (h λ 2 (M))))

Theorem: If H is a family of pairwise independent permutations and f is a (t,ε,q)-PRF then E NR is a (t,2 ε+q 2 /2 n+q 2 /2 n+1 ,q)-SPRP for any q>0 .

So it is secure as long as q2 n/2 . For example, with DES, n=32 , so q2 16 , which is useless. (In contrast, AES has blocksizes of 128, 192 and 256 bits.)

Proof: Let 𝒫 2 n={{0,1 } 2 n{0,1 } 2 n permutaitons }, and write E for E NR. We use a hybrid argument. For all t-time A,

Pr K 1 ,K 2 {0,1 } s,λ 1 ,λ 2 Λ[A E K 1 ,K 2 ,λ 1 ,λ 2 ,E 1 ]Pr σ𝒫 2 n[A σ,σ 1 ] Pr K 1 ,K 2 {0,1 } s,λ 1 ,λ 2 Λ[A E K 1 ,K 2 ,λ 1 ,λ 2 ,E 1 ]Pr f 1 ,f 2 n,λ 1 ,λ 2 Λ[A E 1 ,E 1 1 ] + Pr f 1 ,f 2 n,λ 1 ,λ 2 Λ[A E 1 ,E 1 1 ]Pr[A RR 1 ,(RR 1 ) 1 ] + Pr[A RR 1 ,(RR 1 ) 1 ]Pr σ𝒫 2 n[A σ,σ 1 ]

(let us call the three quantities (1 ), (2 ) and (3 )) where E 1 λ 1 ,λ 2 ,f 1 ,f 2 =h λ 1 (D f 1 (D f 2 (h λ 2 ))) (that is, we replace the PRF's with random functions) and when A queries RR 1 and (RR 1 ) 1 , consistent random values are returned (i.e. consistent with previous values). [Hence it is not necessarily a permutation.]

It can be shown that (1 )2 ε, using the definition of PRF. It can also be shown that (3 )q 2 /2 2 n+1 using an information theoretic argument based on the birthday paradox. Lastly, (2 )q 2 /2 n, by using the fact that condition (*) holds.

The story so far:

one-way functionPRNG (BM)PRF (GGM)PRP (LR)

As for the converses, from the first assignment, we know that PRFPRNGone-way functions. We would like to know if PRPPRF. This is of practical interest because we would like to take off-the-shelf PRP's such as DES or AES and use them as PRF's (e.g. for MAC's).

If we simply use a PRP as a PRF: from above, a (t,ε,q)-SPRP on {0,1 } n is only a (t,ε+q 2 /2 n+1 ,q)-PRF (insecure for q2 n/2 ).

Another method[BI'99]: Let π:{0,1 } n×{0,1 } s{0,1 } n be a (t,ε,q)-PRP. Define F K 1 ,K 2 (x)=π K 1 (x)π K 2 (x). Then F K 1 ,K 2 is a (t,ε+q/2 n+(q/2 n) 3 /2 n,2 q)-PRF. (i.e. secure until q2 n/n 2 /3 ).

Yet another method[BI'99]: Define F K(x)=π K(x) 1 ...m for some mn. Then F K is a (t,ε+q2 m/2 /2 n,q)-PRF for any q<2 m. For example, for m=(2 /3 )n, we need q2 2 n/3 for security.

Now we have a good way of doubling the blocksize of DES. If try to use DES directy in the LR construction we have weak bounds. Instead, we shoould use DES K 1 DES K 2 .