Introduction Concatenated Hashes and Variations Trojan Messages Conclusion

pages

English

Documents

Écrit par
Second Preimage

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

English

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

Langue

English

Poids de l'ouvrage

1 Mo

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

Publié par

pefav

Nombre de lectures

Langue

English

Poids de l'ouvrage

1 Mo

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 , ﬁnd M = M s.t. H(M ) = H(M ).1 2 1 1 2
nIdeal security: 2 .
Preimage Given y, ﬁnd M s.t. H(M) = y.
nIdeal security: 2 .
Herding Choose y, then given P, ﬁnd 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, ﬁnd 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 , ﬁnd M = M s.t. H(M ) = H(M ).1 2 1 1 2
nIdeal security: 2 .
Preimage Given y, ﬁnd 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 , ﬁnd M = M s.t. H(M ) = H(M ).1 2 1 1 2
nIdeal security: 2 .
Preimage Given y, ﬁnd M s.t. H(M) = y.
nIdeal security: 2 .
Herding Choose y, then given P, ﬁnd 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, ﬁnd 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, ﬁnd 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 suﬃx 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+2Oﬄine Build diamond, commit to h (cost: 2 )
1 Receive and hash preﬁx P.3 Assemble parts to form suﬃx 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+2Oﬄine Build diamond, commit to h (cost: 2 )
1 Receive and hash preﬁx P.
n ‘2 Find x that “Connects” h to the diamond (cost: 2 ).p