PuTTY vulnerability vuln-p521-bias

Home | FAQ | Feedback | Licence | Updates | Mirrors | Keys | Links | Team
Download: Stable · Snapshot | Docs | Changes | Wishlist

summary: NIST P521 private keys are exposed by biased signature generation
class: vulnerability: This is a security vulnerability.
priority: high: This should be fixed in the next release.
absent-in: 0.67
present-in: 0.68 0.69 0.70 0.71 0.72 0.73 0.74 0.75 0.76 0.77 0.78 0.79 0.80
fixed-in: c193fe9848f50a88a4089aac647fecc31ae96d27 (0.81)

Every version of the PuTTY tools from 0.68 to 0.80 inclusive has a critical vulnerability in the code that generates signatures from ECDSA private keys which use the NIST P521 curve. (PuTTY, or Pageant, generates a signature from a key when using it to authenticate you to an SSH server.)

This vulnerability has been assigned CVE-2024-31497. It was discovered by Fabian Bäumer and Marcus Brinkmann of the Ruhr University Bochum; see their write-up on the oss-security mailing list.

The bad news: the effect of the vulnerability is to compromise the private key. An attacker in possession of a few dozen signed messages and the public key has enough information to recover the private key, and then forge signatures as if they were from you, allowing them to (for instance) log in to any servers you use that key for. To obtain these signatures, an attacker need only briefly compromise any server you use the key to authenticate to, or momentarily gain access to a copy of Pageant holding the key. (However, these signatures are not exposed to passive eavesdroppers of SSH connections.)

Therefore, if you have a key of this type, we recommend you revoke it immediately: remove the old public key from all OpenSSH authorized_keys files, and the equivalent in other SSH servers, so that a signature from the compromised key has no value any more. Then generate a new key pair to replace it.

(The problem is not with how the key was originally generated; it doesn't matter whether it came from PuTTYgen or somewhere else. What matters is whether it was ever used with PuTTY or Pageant.)

The good news: the only affected key type is 521-bit ECDSA. That is, a key that appears in Windows PuTTYgen with ecdsa-sha2-nistp521 at the start of the 'Key fingerprint' box, or is described as 'NIST p521' when loaded into Windows Pageant, or has an id starting ecdsa-sha2-nistp521 in the SSH protocol or the key file. Other sizes of ECDSA, and other key algorithms, are unaffected. In particular, Ed25519 is not affected.

Details of the error:

All DSA signature schemes require a random value to be invented during signing, known as the 'nonce' (cryptography jargon for a value used only once), or sometimes by the letter k. It's well known that if an attacker can guess the value of k you used, or find any two signatures you generated with the same k, then they can immediately recover your private key.

This means that it's dangerous to generate DSA signatures on systems with no high-quality source of randomness. Significantly more dangerous than generating the encryption keys for a single session: a leak of the private key compromises far more than one SSH session.

For this reason, since PuTTY was developed on Windows before it had any cryptographic random number generator at all, PuTTY has always generated its k using a deterministic method, avoiding the need for random numbers at all. The clever trick is to compute a secure hash whose input includes the message to be signed and also the private key. Secure hash output is indistinguishable from random data (or else the hash function isn't doing its job), and this generation method can't be repeated by an attacker who's trying to find out the private key – if they could generate the same hash input as you, they'd already have the private key.

This technique is now mainstream, and RFC 6979 documents a specific well-known way of doing it. But PuTTY didn't follow that specification, because we started doing the same thing in 2001, and the RFC wasn't published until 2013.

PuTTY's technique worked by making a SHA-512 hash, and then reducing it mod q, where q is the order of the group used in the DSA system. For integer DSA (for which PuTTY's technique was originally developed), q is about 160 bits; for elliptic-curve DSA (which came later) it has about the same number of bits as the curve modulus, so 256 or 384 or 521 bits for the NIST curves.

In all of those cases except P521, the bias introduced by reducing a 512-bit number mod q is negligible. But in the case of P521, where q has 521 bits (i.e. more than 512), reducing a 512-bit number mod q has no effect at all – you get a value of k whose top 9 bits are always zero.

This bias is sufficient to allow a key recovery attack. It's less immediate than if an attacker knows all of k, but it turns out that if k has a biased distribution in this way, it's possible to aggregate information from multiple signatures and recover the private key eventually. Apparently the number of signatures required is around 60.

To fix this vulnerability, we've completely abandoned PuTTY's old system for generating k, and switched to the RFC 6979 technique, for all DSA and ECDSA key types. (EdDSA keys such as Ed25519 already used a different system, which has not changed.) However, this doesn't affect the fact that information about existing P521 private keys has already been leaked whenever a signature was generated using the old k generator.

If you want to comment on this web site, see the Feedback page.
Audit trail for this vulnerability.
(last revision of this bug record was at 2024-04-15 20:49:32 +0100)