lambdafuWe found a critical vulnerability in #PuTTY SSH client with NIST P-521 keys, that allows private key recovery from only 60 signatures, CVE-2024-31497! If you use #Putty or #Filezilla with ECDSA P-521, upgrade now and generate a new key! Joint work with @Skrillor!
Each (EC)DSA signature needs a secret number only used once ("nonce"). If the nonce is revealed, reused, or in biased (not fully random), an attacker can use the signatures to recover the private key, which is bad. So, randomness and secrecy of nonces is super important.
Many programs use random nonces 🎲, but some, including PuTTY, generate them deterministically 🧮from the private key and the message to be signed. PuTTY uses SHA-512(ID || SHA-512(x) || SHA1(m)) modulo group size as a pseudo-random nonce. Can you see a problem? 🤔
For DSA (160 bit) and ECDSA P-256/P-384, the modulo is so small that a 512 bit number wraps around often, and the output looks pseudo-random. Not so for P-521! Here the modulo is a no-op, and the high 9 bits of the nonce are always zero! This is enough to allow an attack!
The attack on ECDSA with biased nonces is a standard technique. An attacker collects at least 521/9≈58 signatures from signed Git commits or victim logins into the attacker's SSH server. A bit of math allows the attacker to calculate the private key offline.
Using recent versions of the attack by Albrecht/Heninger, we can calculate the private key from 58 PuTTY P-521 signatures with a 50% probability (59 sigs: 94% success, 60 sigs: 100% success). https://eprint.iacr.org/2020/1540 Shout out to Julian Nowakowski for helping us understand the math!
PuTTY 0.81 has been fixed to use a more secure nonce generation (RFC6979 by Thomas Pornin). Filezilla Client 3.67.0 also includes a fixed version of PuTTY. Git Tortoise and WinSCP also ship with a bundled PuTTY, but no update is available yet. 🤞