Table of contents

Attacking the SHA Hash Function Family

Overview of Presentation

Defining SHA-0 and SHA-1

Message Padding

Iteration over Message Blocks

SHA-0 Compression: Expansion

SHA-1 Compression: Expansion

Compression: Round i

Compression: f^(i)

Birthday Attack

Fundamental Attack on SHA-0

Approach

SHI1 Compression: Round i

Fundamental Weakness of SHI1

Message Perturbation

Perturbation: Round i

Perturbation: Round i + 1

Perturbation: Round i + 1 (2)

Perturbation: Round i + 2

Perturbation: Round i + 2 (2)

Perturbation: Round i + 3

Perturbation: Round i + 3 (2)

Perturbation: Round i + 4

Perturbation: Round i + 4 (2)

Perturbation: Round i + 5

Perturbation: Round i + 5 (2)

Perturbation Summary

Disturbance Vector

Perturbation Mask

Corrective Masks

Global Differential Mask

Solution

Generalizing the Attack

SHI2 Compression: Round i

Compression: f^(i) (2)

Adapting the Attack

Bit Flipping and B, C, D

Changes in XOR

Changes in MAJ

Changes in IF

Ramifications of IF

Evaluating Probability of Success

Generalizing the Attack (2)

SHI3 Compression: Round i

Adapting the Attack (2)

Avoiding Carries

What if W_1^(i) = 0 is Perturbed to 1?

Then W_6^(i+1) = 1 Avoids a Carry

And W_1^(i+2) = 1 Might Avoid One Too

Avoid Carries by Restricting Messages

Disturbance Vector for SHI3

Generalizing the Attack (3)

SHA-0 Compression: Round i

Adapting the Attack (3)

Changes in IF (SHI2)

Changes in Changes in IF

Changes in MAJ (SHI2)

Changes in Changes in MAJ

Disturbance Vector for SHA-0

Generalizing the Attack (4)

SHA-1 Compression: Expansion (2)

Applicability to SHA-1

Neutral Bit Attack on SHA-0

Approach (2)

Neutral Bit

2-Neutral Set

Choosing r

Finding 2-Neutral Sets

Effectiveness of Attack

SHA-0 Difficulty and Number of Rounds

Relaxing Restrictions in the SHA-0 Attack

Approach (3)

Restrictions on Disturbance Vector

Why Relax the Restrictions?

Eliminated Restrictions

Techniques

Improved Disturbance Vector for SHA-0

Attacking SHA-1

Approach (4)

Disturbance Vector of Words

Finding Disturbance Vectors

No More Restrictions

Results

Conclusions

References

Author: Paul Kuliniewicz

E-mail: kuliniew@purdue.edu

Homepage: http://web.ics.purdue.edu/~kuliniew/wp/

Further information:
This presentation covers four papers that discuss techniques for finding collisions in the SHA-0 and SHA-1 hash functions. This presentation was originally given to the CERIAS Security Reading Group at Purdue University on November 7, 2005.