Outline ECHO Attack Conclusion

Pierre-Alain Fouque

Description

Outline ECHO-256 Attack Conclusion Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function Jérémy Jean and Pierre-Alain Fouque Ecole Normale Supérieure FSE'2011 February 14, 2011 FSE'2011 – Jérémy Jean and Pierre-Alain Fouque Ecole Normale Superieure Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function 1/19

• echo


• attack conclusion


• bmc


• start collision


• mc sb


• bsr


• sr mc

Sujets

• Memory
• Fouqué

Informations

• Publié par: pefav
• Nombre de lectures: 136
• Poids de l'ouvrage: 1 Mo

Extrait

Outline ECHO-256 Attack Conclusion
Practical Near-Collisions and Collisions on
Reduced-Round ECHO-256 Compression Function
Jérémy Jean and Pierre-Alain Fouque
Ecole Normale Supérieure
FSE’2011
February 14, 2011
FSE’2011 – Jérémy Jean and Pierre-Alain Fouque Ecole Normale Superieure
Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function 1/19Outline ECHO-256 Attack Conclusion
Outline
Outline of the talk
Outline
Previous cryptanalysis
Description of ECHO-256
Collision attack on 4-round ECHO-256
Rebound attacks and improvements
FSE’2011 – Jérémy Jean and Pierre-Alain Fouque Ecole Normale Superieure
Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function 2/19Outline ECHO-256 Attack Conclusion
Cryptanalysis
Previous cryptanalysis of ECHO-256
Hash function
Rounds Time Memory Type Reference
112 85:35/8 2 2 collision [Schläffer-eprint10]
Compression function
Rounds Time Memory Type Reference
64 323/8 2 2 free-start collision [Peyrin-C10]
96 323/8 2 2 semi-free-start collision [P
96 324.5/8 2 2 distinguisher [Peyrin-C10]
36 164/8 2 2 new
52 164/8 2 2 semi-free-start collision new
160 1286/8 2 2 collision, chosen salt [Schläffer-eprint10]
160 1287/8 2 2 distinguisher, chosen salt
Permutation
Rounds Time Memory Type Reference
182 378/8 2 2 distinguisher [SLWSO-A10]
151 678/8 2 2 [NayaPlasencia-eprint10]
FSE’2011 – Jérémy Jean and Pierre-Alain Fouque Ecole Normale Superieure
Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function 3/19Outline ECHO-256 Attack Conclusion
Description of ECHO-256 of the hash function
ECHO-256
Merkle-Damgård construction
HAIFA design (counter & salt)
2048-bit internal state as a 44 matrix of AES states
8-round AES-based permutation : BSB, BSR, BMC
Output transformation : compress and truncate
2 rounds AES AES MixColumns
0 0
1 1BSB BSR BMC
2 2
3 3
FSE’2011 – Jérémy Jean and Pierre-Alain Fouque Ecole Normale Superieure
Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function 4/191 round of AES 1 round of AES
SuperSBox SuperMixColumns
SB SR MC SB SR MC BSR BMC
SR SB MC SB SR BSR MC BMC
Outline ECHO-256 Attack Conclusion
Description of ECHO-256
Alternative view
Breaking down to the AES-state level of operations
SuperSBox = SB–MC–SB [LMRRS-A09, GP-FSE10]
SuperMixColumns = MC–BMC [Schläffer-SAC10]
BSB BSR BMC
FSE’2011 – Jérémy Jean and Pierre-Alain Fouque Ecole Normale Superieure
Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function 5/19SuperSBox SuperMixColumns
SR SB MC SB SR BSR MC BMC
Outline ECHO-256 Attack Conclusion
Description of ECHO-256
Alternative view
Breaking down to the AES-state level of operations
SuperSBox = SB–MC–SB [LMRRS-A09, GP-FSE10]
SuperMixColumns = MC–BMC [Schläffer-SAC10]
BSB BSR BMC
SB SR MC SB SR MC BSR BMC
1 round of AES 1 round of AES
FSE’2011 – Jérémy Jean and Pierre-Alain Fouque Ecole Normale Superieure
Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function 5/191 round of AES 1 round of AES
Outline ECHO-256 Attack Conclusion
Description of ECHO-256
Alternative view
Breaking down to the AES-state level of operations
SuperSBox = SB–MC–SB [LMRRS-A09, GP-FSE10]
SuperMixColumns = MC–BMC [Schläffer-SAC10]
BSB BSR BMC
SB SR MC SB SR MC BSR BMC
SR SB MC SB SR BSR MC BMC
SuperSBox SuperMixColumns
FSE’2011 – Jérémy Jean and Pierre-Alain Fouque Ecole Normale Superieure
Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function 5/19Outline ECHO-256 Attack Conclusion
Description of ECHO-256
SuperSBox
Description
Super transformation used in [LMRRS-A09, GP-FSE10]
SuperSBox = SB–MC–SB
Works on 32-bit AES-columns
P( ! exists) 1=2IN OUT
SuperSBox
SB MC SB
IN OUT
FSE’2011 – Jérémy Jean and Pierre-Alain Fouque Ecole Normale Superieure
Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function 6/19Outline ECHO-256 Attack Conclusion
Description of ECHO-256
MixColumns and BigMixColumns
4 parallel applications of MixColumns/BigMixColumns
MixColumns BigMixColumns
MC MC
MC MC
MC MC
MC MC
MC : AES MixColumns
FSE’2011 – Jérémy Jean and Pierre-Alain Fouque Ecole Normale Superieure
Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function 7/19Outline ECHO-256 Attack Conclusion
Description of ECHO-256
SuperMixColumns
1616 matrix of SMC
Super transformation introduced in [Schläffer-SAC10]
Works on 161 byte-slices
M =M
M (M from MixColumns)SMC
Branch number = 8 (optimal : 17)
24Sparse paths : 4! 16! 4, p = 2
SuperMixColumns
MC BMC
one slice
FSE’2011 – Jérémy Jean and Pierre-Alain Fouque Ecole Normale Superieure
Practical Near-Collisions and Collisions on Reduced-Round ECHO-256 Compression Function 8/19p