LadderLeak

Explore a comprehensive presentation on LadderLeak, delivered by Diego F. Aranha and Akira Takahashi at the Workshop on Attacks in Cryptography (WAC 2020). Delve into the intricacies of ECDSA and Schnorr signatures, examining the risks associated with biased or leaky randomness in cryptographic systems. Discover real-world examples of randomness failures and learn about contributions to the field. Investigate side-channel attacks in scalar multiplication, including cache-timing attacks on prime and binary curves. Analyze the problem of nonce leakage, exploring attacks on the Hidden Number Problem (HNP) and Bleichenbacher's attack. Gain insights into Fourier analysis-based approaches, collision search techniques, and the K-list sum algorithm. Examine unified time-memory-data tradeoffs and experimental results on full key recovery. Enhance your understanding of cryptographic vulnerabilities and potential countermeasures in this in-depth 46-minute talk.

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