Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Introduction Concatenated Hashes and Variations Trojan Messages Conclusion

De
58 pages
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


Voir plus Voir moins

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

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin