Introduction Application to Lesamnta Application to XTEA Application to ESSENCE

Charles Bouillaguet

Description

Niveau: Supérieur, Licence, Bac+1
Introduction Application to Lesamnta Application to XTEA Application to ESSENCE Another Look at Complementation Properties Charles Bouillaguet, Orr Dunkelman, Gaëtan Leurent, Pierre-Alain Fouque École Normale Supérieure Paris, France L0 R0 L1 R1 K1 F L0 ? ? R0 ? ? L1 ? ? R1 ? ? K1 ? ? F G. Leurent (ENS) Another Look at Complementation Properties FSE 2010 1 / 28

• l0 r0


• l0 ? ?


• complementation properties


• des's complementation


• k1 ?


• l1 r1


• k? k1


• ecole normale

Sujets

• Fouqué
• École normale

Informations

• Publié par: profil-ontoe-2012
• Nombre de lectures: 8
• Langue: English

Extrait

Introduction Application to Lesamnta Application to XTEA Application to ESSENCE
Another Look at Complementation Properties
Charles Bouillaguet, Orr Dunkelman,
Gaëtan Leurent, Pierre-Alain Fouque
École Normale Supérieure
Paris, France
L R L a R a0 0 0 0
K K a1 1
F F
L R L a R a1 1 1 1
G. Leurent (ENS) Another Look at Complementation Properties FSE 2010 1 / 28Introduction Application to Lesamnta Application to XTEA Application to ESSENCE
DES’s Complementation Property
L RI If the key is bitwise complemented, 0 0
Kso are all the subkeys. 1
K! K ,K ,... ,K and1 2 16 F
K! K ,K ,... ,K1 2 16
I If the state is also complemented
the input to theF function is the same. L R1 1
L R0 0I Therefore the output is the same.
0 K1R = L F(K R )0 1 01
F
I DES’s complementation property:
DES (P) = DES (P)KK
L R1 1
G. Leurent (ENS) Another Look at Complementation Properties FSE 2010 2 / 28Introduction Application to Lesamnta Application to XTEA Application to ESSENCE
DES’s Complementation Property
L RI If the key is bitwise complemented, 0 0
Kso are all the subkeys. 1
K! K ,K ,... ,K and1 2 16 F
K! K ,K ,... ,K1 2 16
I If the state is also complemented
the input to theF function is the same. L R1 1
L R0 0I Therefore the output is the same.
0 K1R = L F(K R )0 1 01
F
I DES’s complementation property:
DES (P) = DES (P)KK
L R1 1
G. Leurent (ENS) Another Look at Complementation Properties FSE 2010 2 / 28Introduction Application to Lesamnta Application to XTEA Application to ESSENCE
DES’s Complementation Property
L RI If the key is bitwise complemented, 0 0
Kso are all the subkeys. 1
K! K ,K ,... ,K and1 2 16 F
K! K ,K ,... ,K1 2 16
I If the state is also complemented
the input to theF function is the same. L R1 1
L R0 0I Therefore the output is the same.
0 K1R = L F(K R )0 1 01
F
I DES’s complementation property:
DES (P) = DES (P)KK
L R1 1
G. Leurent (ENS) Another Look at Complementation Properties FSE 2010 2 / 28Introduction Application to Lesamnta Application to XTEA Application to ESSENCE
DES’s Complementation Property
L RI If the key is bitwise complemented, 0 0
Kso are all the subkeys. 1
K! K ,K ,... ,K and1 2 16 F
K! K ,K ,... ,K1 2 16
I If the state is also complemented
the input to theF function is the same. L R1 1
L R0 0I Therefore the output is the same.
0 K1R = L F(K R )0 1 01
F
I DES’s complementation property:
DES (P) = DES (P)KK
L R1 1
G. Leurent (ENS) Another Look at Complementation Properties FSE 2010 2 / 28Introduction Application to Lesamnta Application to XTEA Application to ESSENCE
DES’s Complementation Property
I L RIf the key is bitwise complemented, 0 0
so are all the subkeys. K1
K! K ,K ,... ,K and1 2 16
FK! K ,K ,... ,K1 2 16
I If the state is also complemented
the input to theF function is the same. L R1 1
L R0 0I Therefore the output is the same.
0 K1R = L F(K R )0 1 01
F
I DES’s complementation property:
DES (P) = DES (P)KK
L R1 1
G. Leurent (ENS) Another Look at Complementation Properties FSE 2010 2 / 28Introduction Application to Lesamnta Application to XTEA Application to ESSENCE
DES’s Complementation Property
L RI If the key is bitwise complemented, 0 0
Kso are all the subkeys. 1
K! K ,K ,... ,K and1 2 16 F
K! K ,K ,... ,K1 2 16
I If the state is also complemented
the input to theF function is the same. L R1 1
L R0 0I Therefore the output is the same.
0 K1R = R11
F
I DES’s complementation property:
DES (P) = DES (P)KK
L R1 1
G. Leurent (ENS) Another Look at Complementation Properties FSE 2010 2 / 28Introduction Application to Lesamnta Application to XTEA Application to ESSENCE
DES’s Complementation Property
L RI If the key is bitwise complemented, 0 0
Kso are all the subkeys. 1
K! K ,K ,... ,K and1 2 16 F
K! K ,K ,... ,K1 2 16
I If the state is also complemented
the input to theF function is the same. L R1 1
L R0 0I Therefore the output is the same.
0 K1R = R11
F
I DES’s complementation property:
DES (P) = DES (P)KK
L R1 1
G. Leurent (ENS) Another Look at Complementation Properties FSE 2010 2 / 28Introduction Application to Lesamnta Application to XTEA Application to ESSENCE
Other similar properties
I Complementation property on LOKI:
E (Pa) = E (P)aKa K
I Equivalent keys of TEA:
E (P) = E (P)KD Kmsb
I Pseudo-collisions in CHI:
CF(H,M) = CF(H,M)
I Pseudo-collisions in MD5:
48CF(HD ,M) = CF(H,M) with probability 2msb
G. Leurent (ENS) Another Look at Complementation Properties FSE 2010 3 / 28Introduction Application to Lesamnta Application to XTEA Application to ESSENCE
Generalization of the complementation property
Definition (Self-similarity relation in a block cipher)
Invertible and easy to compute transformationsf,y andq such that:
8K,P : E (f(P)) = q(E (P))y(K) K
Definition (Self-similarity relation in a compression function)
Invertible and easy to compute transformationsf,y andq such that:
8H,M : CF(f(H),y(M)) = q(CF(H,M))
I We also consider probabilistic relations.
I Broad definition.
I Related key differential.
I Related key slide attack.
I Rotational cryptanalysis.
G. Leurent (ENS) Another Look at Complementation Properties FSE 2010 4 / 28