Overview
Syllabus
Intro
ECDSA and Schnorr Signatures
Risk of Biased/Leaky Randomness
Randomness Failure in the Real World
Contributions
ECDSA signing
Side channel attacks in scalar multiplication
Experimental setup
Cache-timing attacks on prime curves
Cache-timing attacks on binary curves
Software countermeasures
Main takeaways
The problem we tackle: 1-bit of nonce leakage
The problem we tackle: less than 1-bit of nonce leakage
How to attack the HNP
New attack records for the HNP!
The Fourier analysis-based attack?
Bleichenbacher's Attack High-level Overview
Step 1. Bias Function (Essentially DFT)
Handy Form of the Bias Function
Modeling Erroneous Input
Step 2. Detecting the Bias Peak (Naive Approach)
Problem: Naive Approach is inefficient!
Solution: Collision Search to Broaden the Peak
Collision Search Problem in Bleichenbacher's Framework
K-list Sum Algorithm for GBP (eg, X = 4)
Applying Howgrave-Graham and Joux's K-list Sum Algorithm
Unified Time Memory Data Tradeoffs
Tradeoff Graphs for 1-bit Bias
Experimental Results on Full Key Recovery
Conclusion
Taught by
TheIACR