Full Report
The digital signature algorithm (DSA) requires a number used once (nonce). If this number isn't random, then it's trivial to recover the private key. This is how Geo Hotz hacked the Playstation 3 back in the day. Apparently, it's not JUST completely random. If there is missing randomness, then it's also possible to recover the private key. It's even one of the final questions on cryptopals. Many programs use random nonces. However, some generate them deterministically via hashing and modulo over the ECDSA group, which is effectively random. For the P-521 curve, the number is so large that the upper 9 bits are guaranteed to be 0. Using the biased nonce attack, as seen in cryptopals, it's possible to get the private key in about 521/9=58 signatures with over 90% probability. I don't understand the math on this but it's still interesting. Crazy to find this in Putty, such a popular product. Many cryptography things have unexpected footguns and should always be reviewed by professionals.
Analysis Summary
Directly based on the technical details provided and the specific incident involving PuTTY's implementation of the P-521 curve, here is the summarized vulnerability report.
# Vulnerability: Deterministic Nonce Generation Bias in PuTTY (P-521)
## CVE Details
- **CVE ID:** CVE-2024-31497
- **CVSS Score:** 8.1 (High)
- **CWE:** CWE-330: Use of Insufficiently Random Values / CWE-1241: Use of Predictable Algorithm in Individual Decisions
## Affected Systems
- **Products:** PuTTY, Pageant, and other products incorporating PuTTY’s SSH client components (e.g., FileZilla, WinSCP, TortoiseGit, TortoiseSVN).
- **Versions:** PuTTY versions 0.68 through 0.80.
- **Configurations:** Systems using **ECDSA P-521** authentication keys. Other curve types (Ed25519, NIST P-256) are notably unaffected by this specific bias.
## Vulnerability Description
The vulnerability stems from a flaw in how PuTTY generated the "k" value (nonce) for ECDSA signatures using the P-521 curve. To avoid reliance on poor system entropy, PuTTY implemented a deterministic nonce generation via hashing.
However, because the P-521 curve order is not a power of 2 (it is a 521-bit prime), and the hash used was shifted/masked, the resulting nonces were not uniformly distributed. Specifically, the top 9 bits of every nonce were consistently zero. This "biased nonce" is a classic cryptographic weakness. Using Lattice Reduction techniques (Hidden Number Problem), an attacker can mathematically recover the private key if they can observe enough signatures.
## Exploitation
- **Status:** PoC and mathematical proof available.
- **Complexity:** High (Requires capture of ~60 signatures and advanced cryptographic computation).
- **Attack Vector:** Network (An attacker-controlled SSH server or a passive observer of a Git-over-SSH session can collect the necessary signatures).
## Impact
- **Confidentiality:** Total (Full recovery of the user's private SSH key).
- **Integrity:** Total (Attacker can impersonate the user on any system trusting the compromised key).
- **Availability:** None.
## Remediation
### Patches
- **PuTTY:** Upgrade to version **0.81**.
- **FileZilla:** Upgrade to version **3.67.0**.
- **WinSCP:** Upgrade to version **6.3.3**.
- **TortoiseGit:** Upgrade to version **2.15.0.1**.
### Workarounds
- **Key Revocation:** Users who have used ECDSA P-521 keys with affected versions must consider those keys **compromised**. The fix in the software prevents future leaks but cannot "un-leak" a key that has already signed ~60 messages.
- **Migration:** Revoke old P-521 keys from `authorized_keys` files and generate new keys (preferably using Ed25519).
## Detection
- **Indicators of Compromise:** Recovery of the private key is silent. Detection depends on identifying unauthorized logins using the specific P-521 key.
- **Detection Methods:** Review SSH server logs for the use of ECDSA-SHA2-P521 keys. Security teams can use scripts to identify if any keys in their environment are of the vulnerable P-521 type.
## References
- **Vendor Advisory:** hxxps[://]www[.]chiark[.]greenend[.]org[.]uk/~sgtatham/putty/wishlist/vuln-p521-bias[.]html
- **OSS-Security Research:** hxxps[://]www[.]openwall[.]com/lists/oss-security/2024/04/15/6
- **Cryptopals Challenge Reference:** hxxps[://]cryptopals[.]com/sets/8/challenges/62