Skip to content

daedalus/BreakingECDSAwithLLL

Repository files navigation

lint_python GitHub issues GitHub forks GitHub stars

BreakingECDSAwithLLL

Breaking ECDSA (not so broken) with LLL

The main idea behing this attack is the theorem of the great numbers, if you have a crypto funcion and lots of samples (signatures) generated with a private key having a bias in the nonce generation, then they will tend to converge to a single point which happens to be the private key, this is equal to solving the hidden number problem. And for solving it we employ Lenstra-Lenstra-Lovasz lattice reduction algorithm.

The main counter measure against this kind of attack is using deterministic signatures like Z=H(h||d), where Z is the digest, H is a crypto-secure hash funcion, h the nonce, and d our private key. This is needed in order to have a even distributed, random looking nonce.

Heavily based on previous work

https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-care/
https://www.youtube.com/watch?v=6ssTlSSIJQE

First install dependencies:

sudo apt-get install sagemath python3-ecdsa

Then run:

# (Victim) 
# This will generate 6 weak signatures with a known key, args:(privkey,bits,nonces)
python3 weak_signature_generator.py e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 176 6 > nonces.csv

# (Attacker) 
# Will find the private key if LLL converges, args:(bits,nonces)
python3 crack_weak_ECDSA_nonces_with_LLL.py nonces.csv 176 6 | grep -e e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

This PoC was referenced in CVE-2024-31497 on 4/16/2024.

Releases

No releases published

Packages

No packages published

Languages