Cryptanalysis of a Hash Function Based on Quasi Cyclic Codes

Gaëtan Leurent

Description

Cryptanalysis of a Hash Function Based on Quasi-Cyclic Codes Pierre-Alain Fouque, Gaëtan Leurent École Normale Supérieure Paris, France

• security should


• problem means


• should behave


• ideal security


• ifsb hash


• cyclic attack


• quasi-cyclic codes


• hash function

Sujets

• Whirlpool
• Fouqué
• Hash function

Informations

• Publié par: pefav
• Nombre de lectures: 18
• Langue: English

Extrait

CryptanalysisofaHashFunctionBasedon
Quasi-CyclicCodes
Pierre-Alain Fouque, Gaëtan Leurent
École Normale Supérieure
Paris, FranceIntroduction TheIFSBHashFunction TheCyclicattack
HashFunctions
nF :f0, 1g !f0, 1g
Should behave “like a random oracle”...
Collisionattack
GivenF, findM = M s.t. F(M )= F(M ).1 2 1 2
n/2Ideal security: 2 .
Second-preimageattack
GivenF andM , findM = M s.t. F(M )= F(M ).1 2 1 1 2
nIdeal security: 2 .
Preimageattack
GivenF andH, findM s.t. F(M)= H.
nIdeal security: 2 .
G.Leurent (ENS) CryptanalysisofaHashFunctionBasedonQuasi-CyclicCodes766Introduction TheIFSBHashFunction TheCyclicattack
HashFunctions
nF :f0, 1g !f0, 1g
Should behave “like a random oracle”...
Collisionattack
GivenF, findM = M s.t. F(M )= F(M ).1 2 1 2
n/2Ideal security: 2 .
Second-preimageattack
GivenF andM , findM = M s.t. F(M )= F(M ).1 2 1 1 2
nIdeal security: 2 .
Preimageattack
GivenF andH, findM s.t. F(M)= H.
nIdeal security: 2 .
G.Leurent (ENS) CryptanalysisofaHashFunctionBasedonQuasi-CyclicCodes766Introduction TheIFSBHashFunction TheCyclicattack
HashFunctionDesign
Most hash functions are dedicated designs based on
symmetriccrypto concepts:
e.g. MDx, SHA-x, Whirlpool, RadioGatún, Grindahl, ...
Some designs are based on a provable security approach:
the security relies on a given hard problem
(likepublickeycrypto):
e.g. FSB, LASH, SWIFFT, SQUASH, ...
Proofofsecurityshouldbetakenwithcaution
I Many of them are asymptotic proofs but the
concrete function has a fixed size.
I Reduction to an NP-complete problem means thatsome
instance are hard, but the fixed instance could be easy.
I Sometimes the attack model is too weak.
G.Leurent (ENS) CryptanalysisofaHashFunctionBasedonQuasi-CyclicCodesIntroduction TheIFSBHashFunction TheCyclicattack
HashFunctionDesign
Most hash functions are dedicated designs based on
symmetriccrypto concepts:
e.g. MDx, SHA-x, Whirlpool, RadioGatún, Grindahl, ...
Some designs are based on a provable security approach:
the security relies on a given hard problem
(likepublickeycrypto):
e.g. FSB, LASH, SWIFFT, SQUASH, ...
Proofofsecurityshouldbetakenwithcaution
I Many of them are asymptotic proofs but the
concrete function has a fixed size.
I Reduction to an NP-complete problem means thatsome
instance are hard, but the fixed instance could be easy.
I Sometimes the attack model is too weak.
G.Leurent (ENS) CryptanalysisofaHashFunctionBasedonQuasi-CyclicCodesIntroduction TheIFSBHashFunction TheCyclicattack
HashFunctionDesign
Most hash functions are dedicated designs based on
symmetriccrypto concepts:
e.g. MDx, SHA-x, Whirlpool, RadioGatún, Grindahl, ...
Some designs are based on a provable security approach:
the security relies on a given hard problem
(likepublickeycrypto):
e.g. FSB, LASH, SWIFFT, SQUASH, ...
Proofofsecurityshouldbetakenwithcaution
I Many of them are asymptotic proofs but the
concrete function has a fixed size.
I Reduction to an NP-complete problem means thatsome
instance are hard, but the fixed instance could be easy.
I Sometimes the attack model is too weak.
G.Leurent (ENS) CryptanalysisofaHashFunctionBasedonQuasi-CyclicCodesIntroduction TheIFSBHashFunction TheCyclicattack
HashFunctionCryptanalysis
Many hash functions in use today are broken:
1990 MD4 design (Rivest)
1992 MD5
1995 SHA-1 design (NIST)
1996 MD4 collisions (Dobbertin)
2001 SHA-2 family design (NIST)
2004 MD5 collisions (Wangetal.)
2005 SHA-1 collision attack (Wangetal.)
Bestcollisionattacks
1MD4 Complexity 2 (Wangetal. – Sasakietal.)
22MD5 Cy 2 (Wangetal. – Klima)
60.xSHA-1 Complexity 2 (Wangetal. – Rechbergeretal.)
Real impact is unclear, but new designs are welcome (cf. SHA-3).
G.Leurent (ENS) CryptanalysisofaHashFunctionBasedonQuasi-CyclicCodesIntroduction TheIFSBHashFunction TheCyclicattack
HashFunctionCryptanalysis
Many hash functions in use today are broken:
1990 MD4 design (Rivest)
1992 MD5
1995 SHA-1 design (NIST)
1996 MD4 collisions (Dobbertin)
2001 SHA-2 family design (NIST)
2004 MD5 collisions (Wangetal.)
2005 SHA-1 collision attack (Wangetal.)
Bestcollisionattacks
1MD4 Complexity 2 (Wangetal. – Sasakietal.)
22MD5 Cy 2 (Wangetal. – Klima)
60.xSHA-1 Complexity 2 (Wangetal. – Rechbergeretal.)
Real impact is unclear, but new designs are welcome (cf. SHA-3).
G.Leurent (ENS) CryptanalysisofaHashFunctionBasedonQuasi-CyclicCodesIntroduction TheIFSBHashFunction TheCyclicattack
HashFunctionCryptanalysis
Many hash functions in use today are broken:
1990 MD4 design (Rivest)
1992 MD5
1995 SHA-1 design (NIST)
1996 MD4 collisions (Dobbertin)
2001 SHA-2 family design (NIST)
2004 MD5 collisions (Wangetal.)
2005 SHA-1 collision attack (Wangetal.)
Bestcollisionattacks
1MD4 Complexity 2 (Wangetal. – Sasakietal.)
22MD5 Cy 2 (Wangetal. – Klima)
60.xSHA-1 Complexity 2 (Wangetal. – Rechbergeretal.)
Real impact is unclear, but new designs are welcome (cf. SHA-3).
G.Leurent (ENS) CryptanalysisofaHashFunctionBasedonQuasi-CyclicCodesIntroduction TheIFSBHashFunction TheCyclicattack
Outline
TheIFSBHashFunction
Description
Previous cryptanalysis
Wagner’s Generalized Birthday
Linearization Attack
TheCyclicattack
Using Periodic Messages
Description of the attack
Solving the cyclic equations
Scope of the attack
G.Leurent (ENS) CryptanalysisofaHashFunctionBasedonQuasi-CyclicCodes