intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

the context security of symmetric primitives is mainly heuristic, e.g. lack of attacks whose complexity is less than brute-force attacks partial provable security (e.g. against linear and differential cryptanalysis for AES) provable security when some components are “idealized” (e.g. for DES in the Luby-Rackoff model where internal functions are pseudorandom) very few examples of symmetric primitives with reductionist security proofs: VSH [ContiniLS06], QUAD [BerbainGP06] our work: we propose to build efficient symmetric primitives (mostly block ciphers here) whose security can be reduced to the problem of generic attacks on simple schemes

SAC 2008 – Patarin, Seurin

1/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

outline the general idea of the Russian Dolls construction generic attacks on Feistel schemes example of construction with Feistel schemes practical instantiations conclusion and further work

SAC 2008 – Patarin, Seurin

2/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

the Russian Dolls construction aims at using the results on “generic attacks” to build secure symmetric primitives “generic attack“ means any attack performed on a scheme where components are “idealized”: e.g. on a Feistel scheme with perfectly random internal functions $

fi ← − Func({0, 1}n, {0, 1}n), i ∈ [1..r]

SAC 2008 – Patarin, Seurin

3/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

the Russian Dolls construction the design strategy is as follows: starting from a Feistel scheme with r rounds and perfectly inner random functions from n bits to n bits, we evaluate its security in view of the best generic attacks we decrease the size of the key r × n2n by instantiating each inner random function by a Feistel scheme with r0 rounds and inner random functions from n/2 bits to n/2 bits, again evaluating the security in view of the best generic attacks we iterate the process until the size of the key (made of the innermost random functions) reaches a practical size . . .

SAC 2008 – Patarin, Seurin

4/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

IT-secure block ciphers previously proposed provably secure block-ciphers such as C and KFC [BaignèresF06] are information-theoretically secure against limited adversaries however information-theoretic results give a security in Ω(2n) queries for a number of rounds r > 5 ; it decreases with the size of blocks and are useless in the Russian Dolls construction on the contrary, we start from complexity assumptions on generic attacks and obtain primitives with a reductionist security proof

SAC 2008 – Patarin, Seurin

5/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

security of the Russian Dolls construction the security of the construction is characterized by the following theorem: if E is an (, T ) -secure PRP with key space Perm(D1)×· · ·× Perm(Dl) , and E(i) , i = 1..l , are (i, T ) -secure PRPs on Di with key space Ki , then E0 defined on key space K1 × · · · × Kl by

E0K1,...,Kl (·) = EE(1),...,E(l) (·) K1

is an ( +

Pl

SAC 2008 – Patarin, Seurin

i=1 i , T ) -secure

Kl

PRP.

6/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

generic attacks on Feistel schemes brute-force attacks: exhaustive search on the key space, q = O(r2n) 2rn2n queries, T = O(2 ) computations on 3 and 4 rounds, best attacks match the information-theoretic bound: on Ψ(3) , CPA attack with q, T = O(2n/2) , CPCA attack with q, T = 3 on Ψ(4) , CPA attack with q, T = O(2n/2) “signature” attacks: a Feistel permutation has always an even signature; this leads to a distinguisher with q = O(22n) , T = O(22n) ; this is independent of the number of rounds!... but once this “global” property is suppressed (i.e. one tries to distinguish a Feistel scheme from an even random permutation), complexity of best generic attacks grows exponentially with the number of rounds

SAC 2008 – Patarin, Seurin

7/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

generic attacks on Feistel schemes best known attacks against r -round Feistel schemes, r > 5 have been described in [Patarin04] these are iterated attacks of order 2, and are based on the computation of the transition probabilities (a.k.a. “H coefficients”) for couples of plaintexts/ciphertexts pairs (x1, y1), (x2, y2) :

$ (r) (r) Pr f1, . . . , fr ← − Func({0, 1}n, {0, 1}n) : Ψf1,...,fr (x1) = y1, Ψf1,...,fr (x2) = y2

closed formula have been given for these transitions probabilities in [Patarin01], and enable to compare them to the transition probability for a random permutation: ∗

$

2n

Pr = Pr P ← − Perm({0, 1} ) : P(x1) = y1, P(x2) = y2 =

SAC 2008 – Patarin, Seurin

8/16

1 22n(22n − 1) Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

generic attacks on Feistel schemes the attack proceeds as follows (for r even): one asks for the encryption of random pairs (x1, x2) , y1 = E(x1) , y2 = E(x2) , such that x1R = x2R the probability that x1L ⊕ x2L = y1L ⊕ y2L is slightly higher in the case of Ψ(r) than for a random permutation:

Ψ Pr (x1, x2) −−→ (y1, y2) = Pr∗ 1 + (r)

1

2(r/2−2)n

this is detectable when one does ' 2(r−3)n tests the total complexity of the attack is O(2(r−4)n) (note: for r > 7 one needs > 1 permutation)

SAC 2008 – Patarin, Seurin

9/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

conjecture on the best generic attacks we conjecture that the previously described attacks are the best possible ones Let n > 2 and r > 5 be two integers. Then the best advantage of any adversary trying to distinguish Ψ(r) from an even T random permutation with less than T computations is 2(r−4)n . arguments in favor of this conjecture: best attacks on Ψ(3) and Ψ(4) are iterated attacks of order 2: this conjecture is a generalization of the cases r = 3, 4 the computation of transition probabilities for t -uples, t > 3 becomes very involved: best attacks are probably iterated attacks of order 2

SAC 2008 – Patarin, Seurin

10/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

construction with balanced Feistel schemes

SAC 2008 – Patarin, Seurin

11/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

construction with balanced Feistel schemes we want to build a block cipher from 2n bits to 2n bits, with security 2α , using balanced Feistel schemes we denote s the number of iterations of the Russian Dolls construction and r1, . . . , rs the number of rounds of the Feistel schemes at the i -th iteration of the construction at iteration i , the internal functions of the Feistel scheme are from n bits to 2i−1 bits; hence we choose the number of rounds such that

2

(ri −4)

n i−1 2

n 2

i−1

> 2α

we stop the process when the number of bits to store rs+1 functions from n n s bits to 2 2s bits is greater then the number of bits to store one function n n of 2s−1 bits to 2s−1 bits

SAC 2008 – Patarin, Seurin

12/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

construction with balanced Feistel schemes the key is constituted by the r1 × r2 · · · × rs innermost random functions; the length of the key is

r1 · r2 · · · rs ·

n 2

s−1

·2

n s−1 2

and encryption/decryption requires r1 × r2 · · · × rs table look-ups asymptotically, for s = log(n) − c (i.e. the key is constituted from functions from 2c+1 bits to 2c+1 bits): the number of rounds at each iteration is ri = poly(n) the length of the key is poly(n)log(n) the security, according to our conjecture, is Adv 6 SAC 2008 – Patarin, Seurin

T 2

2poly(n)−O(log n)

13/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

practical instantiations we want to build a block cipher from 2n = 128 bits to 2n = 128 bits, with security 2α = 280 optimal number of iterations s = 5 with: number of rounds: r1 = 6 , r2 = 7 , r3 = 10 , r4 = 16 , r5 = 28 key constituted of functions from 4 bits to 4 bits key size = 6 × 7 × 10 × 16 × 28 × 4 · 24 ' 1.5 MB encryption/decryption requires 6 × 7 × 10 × 16 × 28 = 188 160 TLU alternative with only s = 4 iterations number of rounds: r1 = 6 , r2 = 7 , r3 = 10 , r4 = 16 key constituted of functions from 8 bits to 8 bits key size = 6 × 7 × 10 × 16 × 8 · 28 ' 1.7 MB encryption/decryption requires 6 × 7 × 10 × 16 = 6 720 TLU SAC 2008 – Patarin, Seurin

14/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

conclusion and further work the Russian Dolls design strategy enables to build symmetric primitives quite efficient (implementable) and with a security reduction to the (conceptually simple) problem of generic attacks a lot of possible construction remain to explore, mainly based on unbalanced Feistel schemes, with contracting or expanding functions (generic attacks studied in [PatarinNB06,07]) one may also explore the construction of PRFs or PRNGs based on this design principle other direction for further work: obtain security results pointing in the direction of our conjecture (proving it will reveal hard since it is linked to the P vs. NP problem)

SAC 2008 – Patarin, Seurin

15/16

Orange Labs

intro

the Russian Dolls construction

generic attacks

application to Feistel

example parameters

conclusion

thanks for your attention!

questions?

SAC 2008 – Patarin, Seurin

16/16

Orange Labs