5
$\begingroup$

Regarding CVE-2024-31497 a German article "Nur NIST P-521 betroffen: PuTTY-Lücke kompromittiert private SSH-Schlüssel" wrote something about a vulnerability in PuTTY. The issue was claimed to be a weakness in a random generator used to create nonces:

So liegt der Fehler in einer Besonderheit des PuTTY-eigenen Zufallszahlengenerators begründet. Dieser enthielt eine mathematische Ungenauigkeit, welche die in ECC-Verfahren unverzichtbaren Nonces ("number used once", Einmal-Nummer) unter bestimmten Bedingungen leichter erratbar macht.

Translation of the German citation above: The error is due to a special feature of PuTTY's own random number generator. This contained a mathematical inaccuracy that made the nonces (“number used once”), which are indispensable in ECC procedures, easier to guess under certain conditions.

What I don't understand is this: The nonces that I know of must be unique (non-repeating), but they may be predictable.

Can someone explain what's behind this? I admit that I don't understand the details of NIST P-521, however.

  • Are there different types of "nonces"?
  • May nonces be predictable (while still being unique)?
$\endgroup$
1
  • 1
    $\begingroup$ I'm surprised that the question was closed with no further comments other than "This question needs details or clarity." on the reason. So what detail is missing, and what about the question is unclear? $\endgroup$
    – U. Windl
    Commented Apr 19 at 8:29

3 Answers 3

11
$\begingroup$

The nonces that I know of must be unique (non-repeating), but they may be predicable.

Not exactly. The definition of a nonce is that it must be non-repeating. Some schemes that use a nonce have additional requirements on the nonce, beyond being a nonce. Some schemes allow predictable nonces, others don't.

For example, modern AEAD schemes such as GCM and CCM allow predictable nonces (e.g. {0, 1, 2, 3, …} is a perfectly fine sequences of nonces), but many older symmetric schemes have strongr requirements. For example CBC additionally requires the nonce to be unpredictable and uniformly distributed. (CBC calls the nonce “IV” (initialization vector), but that's more because of terminological history than because an IV is fundamentally different from a nonce.) CTR (which calls the nonce “initial counter value”) allows the nonce to be predictable, but requires the counter value for each block to be unique, not just the initial counter value for each message. All symmetric schemes allow the nonce to be published with the ciphertext.

ECDSA has very stringent requirements on the nonce. It needs to be unpredictable and uniformly distributed, but also it needs to remain secret. If you have a message, an ECDSA signature and the nonce used to produce it, you can recover the private key. If you have partial information about the nonce for multiple signatures, that can also be enough to recover the private key. For example, with two signatures of different messages with the same key and nonce (i.e. you don't know the nonce value but you know it's the same for both), you can recover the nonce value and thus the private key. This makes the ECDSA nonce a choice target for side channel attacks on the signature process.

The ECDSA nonce is sometimes given other names such as “ephemeral key”. “Ephemeral key” is technically correct, but is confusing for practicioners since it's very different, for example, from a Diffie-Hellman ephemeral key: you'll never see this “key” as a parameter of a crypto API, it's only an internal detail of the ECDSA signature operation. It can also be called by other names such as “internal random value” (mostly correct, but as we'll see below “random” is actually too strong) or “intermediate secret” (correct but ambiguous). The notation is pretty well established, so it's sometimes called just “$k$”.

The bug in PuTTY was that it generated nonces in the range $[1, 2^{512}]$ rather than $[1, n-1]$ where $n \approx 2^{521}$ is the curve size. This means that every nonce has 9 known bits out of 521. That's known to be bad. It allows the key to be recovered from a little more than $512 / 9 \approx 56$ signatures (each signature with 9 bits known in the nonce contributes to almost 9 bits of independent information about the private key).

The bug was specific to P-521. P-521 implementations are tricky because they're the only popular curve whose size isn't almost a whole number of machine words. That makes P-521 more prone to coding mistakes and side channel leakage than P-256 and P-384. Several P-521 implementations have been vulnerable to side channels that allowed attackers to find out when the top machine word of the nonce is 0, which for P-521 happens with probability $\approx 2^{512}/2^{521} = 2^{-9}$, allowing key recovery from thousands of signatures. Such a side channel is not exploitable for other curves, since for other curves the attacker needs to collect about $2^{32}$ signatures (for 32-bit words, assuming perfect measurements) to get 32 bits of information. In the case of this PuTTY bug, every signature is suitable for the attack, making the recovery very quick.

Bugs like this, where some output is random but not random enough, are very hard to detect by testing. That's why many modern ECDSA implementations use a deterministic variant codified in RFC 6979. The ECDSA nonce doesn't actually need to be a nonce (but it's still called “nonce”), in the sense that it can be repeated for multiple signature operations, it only needs to be unique for a given (key, message) pair. Deterministic ECDSA uses a PRNG seeded by the key and message to create the nonce, instead of random generation. Deterministic ECDSA is less prone to implementation bugs because implementers can test that they get the sole permitted output for a given input. (Deterministic ECDSA doesn't particularly help againt side channel attacks, however; it makes some attacks easier and others harder.)

PuTTY actually used a deterministic variant of ECDSA, but it was older than RFC 6979 and proprietary to PuTTY. The design of this variant was overly fragile: a simple hash of the PRNG inputs, limited to 512 bits. This is insecure for curves larger than 512 bits, and the only curve that's so large is P-521.

$\endgroup$
2
  • 1
    $\begingroup$ I always found it really wrong to call it "nonce". It needs secrecy and uniform distribution, that is never the case for a nonce. This is really is an ephemeral key. $\endgroup$
    – Ruggero
    Commented Apr 18 at 8:26
  • $\begingroup$ @Ruggero “Ephemeral key” is a better term for theoretists, but confusing for practicioners: a “key” is something that you store at least in memory and pass as a parameter to a crypto API, not something used internally in the implementation of a mechanism. “Nonce” isn't a perfect fit because it doesn't actually have to be a nonce (you can repeat it if the key and message are the same), but it's taken on, I guess, because it's shorter than the accurate “per-key-and-message-secret”. $\endgroup$ Commented Apr 18 at 8:43
4
$\begingroup$

The issue is not specifically with P-521; instead it is the use of ECDSA with a biased random number generator.

ECDSA is a signature system (based on an elliptic curve; in this case, P-521; however the same would apply to any good elliptic curve) where the 'signer' holds a private key' and a message, and uses that to generate a 'signature', that is, a proof that anyone with the public key can use to verify that the message was precisely what the signer (the holder of the private key) actually saw.

Now, ECDSA also takes a random number (they refer to it as a nonce, however we need to make stronger assumptions on it than just uniqueness) as an input when generating the signature. If the random number was selected uniformly randomly (and independently of other random numbers and secret), all is well. However, with ECDSA, if the random number selection is biased, someone listening into the signatures (and the signed messages) can learn the ECDSA private key by listening into a number of signatures (which means that they can then also sign anything they want, and make it look like it came from the valid PuTTY system).

The number of signatures needed for an attacker to do this depends on the strength of the bias - it would appear that the random number generator used in PuTTY is pretty strongly biased, as it appears that about 60 signatures are sufficient for an attacker to recover the private key.

$\endgroup$
5
  • 1
    $\begingroup$ Addition: From hearsay, the issue is in the principle of the generation of the secret $k$ in ECDSA by Putty (version 0.80 and before), which takes a 512-bit uniformly random $h$ and uses $k=h\bmod n$ [or is it $k=(h\bmod(n-1))+1$ ] where $n$ is the curve's order. When $n$ approaches or worse exceeds the 512-bit threshold (as is the case for P-521 which $n$ is 521-bit), $k$ becomes awfully biased towards low values and ECDSA becomes vulnerable. It's recommendable to regenerate P-521 keys that have been used by the old Putty, for logs of past sessions may allow attack. $\endgroup$
    – fgrieu
    Commented Apr 17 at 15:05
  • 1
    $\begingroup$ So if I understood the answer and comment correctly, the problem is not "guessing the nonce", but "knowing some fixed bits" (@fgrieu suggests the highest 9 bits are always zero)? In that case it means that "nonce" is not the correct phrase for the number the algorithm actually requires. $\endgroup$
    – U. Windl
    Commented Apr 17 at 20:16
  • $\begingroup$ @U.Windl Guessing the nonce is bad. Even partially guessing the nonce is bad. With this PuTTY bug, for P-521, you could guess “the top 9 bits of the nonce are 0” and be correct every time. The nonce in ECDSA must remain secret. $\endgroup$ Commented Apr 17 at 23:17
  • $\begingroup$ "The issue is not specifically with P-521", I'd rather say "the issue is specific with the implementation quirks of P-521". At algorithm level, it's nothing special, but on implementations, it is. $\endgroup$
    – DannyNiu
    Commented Apr 23 at 2:37
  • $\begingroup$ @DannyNiu: fair enough - it appears that implementation quirks around P-521 caused the biases that were the real problem. $\endgroup$
    – poncho
    Commented Apr 23 at 2:41
3
$\begingroup$

Are there different types of "nonces"?

Yes.

  1. Those which only required security attribute is being a number used once. Examples include initialization vector in AES-CTR.
  2. Those which additionally require being unpredictable. Example include initialization vector in AES-CBC.
  3. Those which additionally require being kept secret after generation. This includes ephemeral secrets for some protocols.
  4. Those which additionally require near uniform distribution on some interval. This includes the ephemeral secret for ECDSA, which is very sensitive to some kinds of bias in it's ephemeral secret.

The issue considered in the question is that the $k$ in the ECDSA Signing Operation as generated by PuTTY version [0.68 to 0.80] is (mostlya) of kind 3, but not of type 4 in the case of elliptic curve groups of size approaching or higher than 512-bit, including P-521 aka secp521r1. Specifically, the high-order 9 bits of $k$ are always zero. This bias allows recovery of a private key from public key and about $521/9\approx58$ message/signature pairs (and I think this can be lowered significantly with additional effort). It's recommendable to regenerate P-521 keys that have been used by the old PuTTY, for transcripts of enough past sessions allow attack.


a Except the same $k$ is reused if a message is resigned, since in PuTTY $k$ a deterministic secret function of the message. Such deterministic choice of $k$ is believed secure, arguably more secure (if done properly) than random choice of $k$.

$\endgroup$
8
  • 2
    $\begingroup$ Password hashing doesn't really require an unpredictable salt. Sure, it can allow the search to start before the database leak, but an attacker who does that also won't know when to stop, so it's a doubtful trade-off. A predictable but unique salt still serves its primary purpose of preventing efficient multi-target attacks. A better example for unpredictability is the CBC IV. $\endgroup$ Commented Apr 22 at 9:43
  • 1
    $\begingroup$ “I think this can be lowered, perhaps about halved, with additional effort” I'm intrigued: how does that work? I don't know the math, but my intuition was that 1 bit of information about $k$ translates to 1 bit of information about the key, which gives the $\approx 521/9$ signature count. $\endgroup$ Commented Apr 22 at 9:45
  • $\begingroup$ @Gilles'SO-stopbeingevil' : Yes IV in AES-CBC is a better example, changed. Yes 1 bit of information about $k$ gives at best to 1 bit of information about the private key. But we can find a private key with knowledge of some bits of the private key, and the others $b$ found by Pollard's rho, at cost $\mathcal O(2^{b/2})$. If it's possible to combine the two, and if $\mathcal O(2^{80})$ effort is feasible, we need about $(521-2×80)/9≈58$ message/signature pairs. That's not quite "about halved" as I wrote, changed that. $\endgroup$
    – fgrieu
    Commented Apr 22 at 11:41
  • $\begingroup$ So the four type are?: (1) nonce (be unique), (2) "larger random number", (3) "shared (random) secret", (4) "uniformly distributed random secret) -- if that's true all but (1) aren't really nonces IMHO. $\endgroup$
    – U. Windl
    Commented Apr 23 at 7:43
  • $\begingroup$ @U.Windl: (2) is about unpredicatability, not size or randomness. True randomness and large size imply unpredictability, but not the other way around. In my view, an incremental counter starting at zero and large enough to never repeat is a (predictable) nonce ("Number used ONCE"), and is perfectly fine in some applications (AES-CTR), but not others (AES-CBC). Hence my distinction between (1) and (2). $\endgroup$
    – fgrieu
    Commented Apr 23 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.