Practical Start Collision Attacks on the 76 Step SHA-1

Explore practical free-start collision attacks on the 76-step SHA-1 in this 23-minute video lecture. Delve into security notions, Merkle-Damgård hash functions, and the SHA-1 compression function. Learn about Wang collisions, preimage detours, and the significance of free-start attacks. Examine linear part selection, non-linear path construction, and acceleration techniques. Discover how to implement these attacks using GPU architecture, with code snippets and performance results provided. Gain insights into the vulnerabilities of cryptographic hash functions and the methods used to exploit them.

Syllabus

Intro
Three security notions (informal)
Merkle Damgård hash functions
Additional security notions for MD
What did we do?
The SHA-1 hash function
SHA-1 compression function
Round function in a picture
Wang collisions
Preimage detour
The point of free-start
The point of free start in a picture
Sooo, what do we need to do?
Linear part selection
Linear path in a picture (part 1/2)
Non-linear part construction
Non-linear path in a picture
Accelerating techniques
Let's sum up
Same thing in a picture
Let's use a GPU!
Architecture imperatives
Snippets in a picture
GPU results