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

Automatic Search of Differential

De
50 pages
Automatic Search of Differential Path in MD4 G. Leurent Introduction MD4 Wang's attack Understand and automate Sufficient conditions Step operation SC Algorithm Differential Path Message difference Results Collisions 2nd preimage NMAC Attack Conclusion Automatic Search of Differential Path in MD4 Pierre-Alain Fouque, Gaetan Leurent, Phong Nguyen Laboratoire d'Informatique de l'Ecole Normale Superieure, Departement d'Informatique, 45 rue d'Ulm, 75230 Paris Cedex 05, France Ecrypt Hash Workshop, May 2007 1 / 37

  • laboratoire d'informatique de l'ecole normale

  • general design

  • merkle-damg˚ard block size

  • bits internal state

  • hash function


Voir plus Voir moins

Automatic
Search of
Differential
Path in MD4
G. Leurent
Introduction
MD4
Wang’s attack Automatic Search of Differential Path in MD4
Understand
and automate
Sufficient
conditions
Step operation Pierre-Alain Fouque, Ga¨etan Leurent, Phong Nguyen
SC Algorithm
Differential Path
Message
difference ´Laboratoire d’Informatique de l’Ecole Normale Sup´erieure,
Results D´epartement d’Informatique,
Collisions 45 rue d’Ulm, 75230 Paris Cedex 05, Francend2 preimage
NMAC Attack
Conclusion Ecrypt Hash Workshop, May 2007
1/ 37Automatic
Search of Motivation
Differential
Path in MD4
G. Leurent
Introduction
MD4
Wang’s attack
Why do we need an algorithm?
Understand
and automate Understanding
Sufficient
conditions
Step operation Improving
SC Algorithm
Differential Path New attacksMessage
difference
Results
Collisions Results
nd2 preimage
NMAC Attack Some improvement of known attacks
Conclusion
New attack against NMAC-MD4
2/ 37Automatic
Search of Outline
Differential
Path in MD4
G. Leurent 1 Introduction
The MD4 hash functionIntroduction
MD4 Wang’s attack
Wang’s attack
Understand
and automate 2 Understand and automate
Sufficient
conditions Sufficient conditions
Step operation
Step operationSC Algorithm
Differential Path SC Algorithm
Message
difference
Differential Path
Results
Collisions Message difference
nd2 preimage
NMAC Attack
3 Results
Conclusion
Collisions
Second preimage
NMAC Attack
4 Conclusion
3/ 37Automatic
Search of The MD4 hash function
Differential
Path in MD4 General design
G. Leurent
Introduction MD4 Design
MD4
Wang’s attack Merkle-Damg˚ard
Understand
and automate Block size: 512 bits
Sufficient
conditions
Step operation Internal state: 128 bits
SC Algorithm
Differential Path MD Strengthening
Message
difference
Results
Collisions M
nd2 preimage
NMAC Attack
Conclusion
M M M M0 1 2 3
F F F F D
h(M)IV H H H H0 1 2 3
4/ 37Automatic
Search of The MD4 hash function
Differential
Path in MD4 Compression function
G. Leurent
Compression Function Design
Introduction
MD4
Wang’s attack
mUnderstand iDavies-Meyer with aand automate
Sufficient Feistel-like cipher.conditions
Step operation H HSC Algorithm i−1 i
Differential Path C
Message
difference
Results
Collisions
nd Designed to be fast: 32 bit words, and operations available2 preimage
NMAC Attack in hardware:
Conclusion 32additions mod2 :⊞
boolean functions: Φi
rotations≪ si
Message expansion M =hM ,...M i →mh ,...m i0 15 0 47
4 words of internal state Q updated in rounds of 16 stepsi
5/ 37Automatic
Search of The MD4 hash function
Differential
Path in MD4 Compression function
G. Leurent
MD4 Step Update
Introduction
MD4
Wang’s attack
Q Q Q Qi−4 i−3 i−2 i−1Understand
and automate
Sufficient
conditions Φi
Step operation
SC Algorithm
Differential Path
Message mi
difference
Results
kCollisions i
nd2 preimage ≪ siNMAC Attack
Conclusion
Q Q Q Qi−3 i−2 i−1 i
Q = (Q ⊞Φ (Q ,Q ,Q )⊞m ⊞k )≪ si i−4 i i−1 i−2 i−3 i i i
6/ 37Automatic
Search of MD4 Collisions
Differential
Path in MD4
G. Leurent Wang in a nutshell
Introduction
1 Precomputation:
MD4
Wang’s attack Choose a message difference.
Understand Compute a differential path.and automate
Sufficient Derive a set of sufficient conditions.
conditions
Step operation
2 Collision search:SC Algorithm
Differential Path
Find a message that satisfies the set of conditions.Message
difference
Results
Collisions Main resultnd2 preimage
NMAC Attack We know a difference Δ and a set of conditions on the
Conclusion
internal state variables Q ’s, such that:i
If all the conditions are satisfied by the internal state
variable in the computation of H(M),
then H(M) = H(M +Δ).
7/ 37Automatic
Search of What is a differential path?
Differential
Path in MD4
G. Leurent
Introduction
MD4
Wang’s attack
Description
Understand
and automate
Specifies how the computations of H(M) and H(M +Δ)Sufficient
conditions
Step operation are related.
SC Algorithm
Differential Path The differences introduced in the message evolve in the
Message
difference
internal state.
Results
Collisions Differential attack with the modular difference.nd2 preimage
NMAC Attack 32Most of the work is modulo 2 , but we also need to
Conclusion
control bit differences.
8/ 37Automatic
Search of What is a differential path?
Differential
Path in MD4 Notations
G. Leurent
Introduction
NotationsMD4
Wang’s attack
Modular difference: δ(x,y) = y⊟x
Understand
and automate [31] [31] [0] [0]Wang’s difference: ∂(x,y) = y −x ,...y −xSufficient
conditions
Step operation NandHfor +1 and−1.
SC Algorithm
Differential Path [k]
Message x for the k +1-st bit of x.
difference

[0] [3,4] [30,31]
Results Compact notation: N ,HN ,NN
Collisions
nd2 preimage
NMAC Attack
Differential path notationsConclusion
′We consider a message M. M = M⊞Δ.
′The differential path specifies ∂Q = ∂(Q ,Q ).i i i
The desired values are ∂ .i
9/ 37Automatic
Search of Understanding Wang
Differential
Path in MD4
G. Leurent
Introduction
MD4
Wang’s attack
Understand
and automate Question
Sufficient
conditions How to compute the set of conditions?
Step operation
SC Algorithm
1Differential Path Derive a set of sufficient conditions from a
Message
difference differential path.
Results
2 Compute a differential path from a message difference.Collisions
nd2 preimage
NMAC Attack 3 Choose a message difference.
Conclusion
10/ 37

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