Introduction Concatenated Hashes and Variations Trojan Messages Conclusion

Second Preimage

Description

Introduction Concatenated Hashes and Variations Trojan Messages Conclusion Herding, Second Preimage and Trojan Message Attacks Beyond Merkle-Damgård Elena Andreeva1 Charles Bouillaguet2 Orr Dunkelman2 John Kelsey3 1K.U. Leuven, ESAT/COSIC, Leuven-Heverlee, Belgium 2École Normale Supérieure, Paris, France 3NIST, Gaithersburg, MD, USA SAC 2009

• beyond merkle-damgård


• h1 h2 h3


• hash functions


• most hash functions


• ecole normale

Sujets

• Antécédent (mathématiques)
• Hash function
• École normale

Informations

• Publié par: pefav
• Nombre de lectures: 26
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Introduction Concatenated Hashes and Variations Trojan Messages Conclusion
Herding, Second Preimage and Trojan Message
Attacks Beyond Merkle-Damgård
1 2Elena Andreeva Charles Bouillaguet
2 3Orr Dunkelman John Kelsey
1K.U. Leuven, ESAT/COSIC, Leuven-Heverlee, Belgium
2École Normale Supérieure, Paris, France
3NIST, Gaithersburg, MD, USA
SAC 2009Collision Find M = M s.t. H(M ) = H(M ).1 2 1 2
n=2Ideal security: 2 .
2nd-preimage Given M , find M = M s.t. H(M ) = H(M ).1 2 1 1 2
nIdeal security: 2 .
Preimage Given y, find M s.t. H(M) = y.
nIdeal security: 2 .
Herding Choose y, then given P, find S s.t. H(PjjS) = y.
nIdeal security: 2 .
Introduction Concatenated Hashes and Variations Trojan Messages Conclusion
Hash Functions Cryptanalysis
nH :f0;1g 7!f0;1g
Should behave “like a random oracle”.
66Herding Choose y, then given P, find S s.t. H(PjjS) = y.
nIdeal security: 2 .
Introduction Concatenated Hashes and Variations Trojan Messages Conclusion
Hash Functions Cryptanalysis
nH :f0;1g 7!f0;1g
Should behave “like a random oracle”.
Collision Find M = M s.t. H(M ) = H(M ).1 2 1 2
n=2Ideal security: 2 .
2nd-preimage Given M , find M = M s.t. H(M ) = H(M ).1 2 1 1 2
nIdeal security: 2 .
Preimage Given y, find M s.t. H(M) = y.
nIdeal security: 2 .
66Introduction Concatenated Hashes and Variations Trojan Messages Conclusion
Hash Functions Cryptanalysis
nH :f0;1g 7!f0;1g
Should behave “like a random oracle”.
Collision Find M = M s.t. H(M ) = H(M ).1 2 1 2
n=2Ideal security: 2 .
2nd-preimage Given M , find M = M s.t. H(M ) = H(M ).1 2 1 1 2
nIdeal security: 2 .
Preimage Given y, find M s.t. H(M) = y.
nIdeal security: 2 .
Herding Choose y, then given P, find S s.t. H(PjjS) = y.
nIdeal security: 2 .
66Introduction Concatenated Hashes and Variations Trojan Messages Conclusion
Iterated Hashing
Most hash functions are iterated hash functions.
Classical Example : The Merkle-Damgård Mode of Operation
I Split M into m-bit blocks : M = m ;m ;:::;m0 1 r
I Pad the last block (include binary encoding ofjMj)
n+m n
I Iterate a compression function f :f0;1g !f0;1g
m m m m0 1 2 r
f f f f
h h h H(M)IV 1 2 3Introduction Concatenated Hashes and Variations Trojan Messages Conclusion
Generic Attacks
The combination of:
I A compression function f
()I A mode of operation H
fresults in a full hash function H .
In This Talk
Attacks against the modes of operation
I Works for all f : generic attacks
I Model f as a Random Oracle (worst case assumption)
n=2 nI Collisions on f costs 2 , [2nd] preimage costs 2Introduction Concatenated Hashes and Variations Trojan Messages Conclusion
Joux’s Multicollision for Merkle-Damgård [CRYPTO’04]
kFor the cost of k collisions, we can build a 2 -multicollision
I At each step, find a colliding block pair starting from the last
chaining value
kI 2 paths between IV and hk
m m m1 2 3
IV h h h h1 2 3 k
0 0 0m m m1 2 3
Works because of the iterated structure of H !Introduction Concatenated Hashes and Variations Trojan Messages Conclusion
The Herding Attack for Merkle-Damgård [EUROCRYPT’06]
Commit to h, receive P, find S s.t. H(PjjS) = h.
How?
x3 1 Build “diamond structure”
x1 I Binary tree of height ‘
x4 I Collision tree
‘ h2 ‘I Maps 2 chaining values to h
x m5 n=2+‘=2+2I Built in time 2
x2
0x6 m
2 Commit to h
0f (x ;m) = f (x ;m ) = x5 6 2n ‘
2 Find x that “Connects” h to the diamond (cost: 2 ).p
3 Assemble parts to form suffix S.
Introduction Concatenated Hashes and Variations Trojan Messages Conclusion
The Herding Attack: Online Phase
x3
x1
x4P
‘h hIV P 2
x5
x2
x6
n=2+‘=2+2Offline Build diamond, commit to h (cost: 2 )
1 Receive and hash prefix P.3 Assemble parts to form suffix S.
Introduction Concatenated Hashes and Variations Trojan Messages Conclusion
The Herding Attack: Online Phase
x3
x x1
x4P
h hIV P
x5
x2xjf (h ;x) = xP j x6
n=2+‘=2+2Offline Build diamond, commit to h (cost: 2 )
1 Receive and hash prefix P.
n ‘2 Find x that “Connects” h to the diamond (cost: 2 ).p