Outline ECHO Attack Conclusion

pages

Documents

Écrit par
Pierre-Alain Fouque

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

136

Poids de l'ouvrage

1 Mo

echo

attack conclusion

start collision

mc sb

sr mc

Voir

Publié par

pefav

Nombre de lectures

136

Poids de l'ouvrage

1 Mo

Memory Fouqué

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äﬀer-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äﬀer-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äﬀer-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äﬀer-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äﬀer-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äﬀer-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