Beyond Nonce Reuse: Partial Leakage and the Limits of Deterministic Signing

Most engineers know the cautionary tale: a signer that uses the same ECDSA nonce twice publishes its private key to anyone holding the two signatures. That story has a comforting implication, that as long as nonces never repeat, the key is safe. It is wrong. A nonce does not have to repeat to betray its key. It only has to be slightly predictable, or to leak a little of itself through how long it takes to process, and the leak has to happen across enough signatures. Each signature then becomes a weak, noisy hint about the private key, and a mathematical technique built on lattices can combine thousands of weak hints into one strong answer. This has happened to real systems, from smart cards to Trusted Platform Modules to widely used cryptographic libraries. Deterministic signing, which derives each nonce from the key and the message, is often presented as the cure. It removes one important cause, a faulty random number generator, and leaves the others exactly where they were, while adding a new exposure of its own. This article explains the mechanism, maps the leak sources, and states what each defence actually covers, with particular attention to AI agents, which sign at machine speed and volume.

Every signature is an equation with two unknowns

An ECDSA signature consists of two numbers. The first is derived from the point obtained by multiplying the curve's base point by a secret per-signature nonce. The second combines the nonce, the hash of the message, the first number and the long-term private key in a single modular linear equation. To an observer who sees the signature and the message, that equation contains exactly two unknowns: the private key and the nonce. Because a fresh nonce enters every signature, every signature adds a new unknown, and the private key stays hidden however many signatures are collected.

That bookkeeping explains all the failures that follow. If a nonce is reused, two equations share the same two unknowns, and simple algebra solves them. If a nonce is fully known, one equation with one unknown remains, and the private key falls out immediately. The more interesting case is in between: if some information about each nonce is known, part of its bits, or the fact that it is smaller than it should be, then each equation reduces the uncertainty about the private key slightly, and many equations together can reduce it to zero.

EdDSA, specified in RFC 8032, has a different equation and derives its nonce deterministically, but it shares the same structure: a per-signature secret that, if known or partly known across signatures, exposes the long-term key.

From partial knowledge to a recovered key

Boneh and Venkatesan introduced the hidden number problem in 1996 while studying how many bits of a Diffie-Hellman secret are hard to compute. In informal terms, it asks for a hidden number when an attacker is given many random multiples of it with only their most significant bits revealed. They showed that, given enough such samples, the hidden number can be recovered efficiently with lattice reduction, an algorithmic technique that finds unusually short vectors in a regular grid of points built from the samples.

Howgrave-Graham and Smart showed in 2001 that DSA-style signatures with partially known nonces map directly onto this problem. Each signature with a few known nonce bits becomes one sample in which the private key is the hidden number. When enough samples are combined, the private key corresponds to an unusually short vector in a lattice, and reduction algorithms find it. Later work extended the approach to biased nonces, where no bits are known exactly but the nonces are statistically skewed, for example always shorter than the full length.

The governing trade-off, in qualitative terms, is that the less each signature leaks, the more signatures and computation an attacker needs. Leaks of several bits per signature have been exploited with modest numbers of signatures; published work has since pushed the frontier below one bit per signature, at the cost of very large signature counts and heavy computation, as in the LadderLeak study by Aranha and colleagues (2020). For defenders, the important conclusion is that there is no safe small leak: a systematic bias of any size is a key-recovery risk whose cost depends only on how many signatures an attacker can collect.

Where partial nonce information comes from

Documented cases fall into four sources, which this article separates because each needs a different defence. The first is biased generation. A nonce should be uniform over the whole range up to the group order. Implementations that reduce a random number of the same length modulo the order, or that truncate a hash to a length slightly shorter than the order, produce small but systematic biases. Faulty or weakly seeded random number generators produce larger ones.

The second is timing that depends on the nonce. Scalar multiplication implementations that skip leading zero bits run measurably faster for nonces that happen to be short, so signing time leaks the nonce's bit length. The Minerva study by Jančár and colleagues (2020) found this class of leak in several cryptographic libraries and smart cards, and the TPM-Fail study by Moghimi and colleagues (2020) found it in Trusted Platform Modules, including recovery of keys from timing measurements taken over a network in one case.

The third is microarchitectural and physical side channels, such as cache access patterns, power consumption or electromagnetic emanations, which can reveal individual nonce bits during scalar multiplication. The fourth is faults: deliberately induced computational errors that, combined with correct outputs, reveal nonce or key information. These sources are not mutually exclusive, and an implementation can suffer from several at once.

What deterministic signing removes, and what it does not

RFC 6979 specifies deterministic ECDSA: the nonce is derived from the private key and the message hash using an HMAC-based deterministic random bit generator. RFC 8032 builds a similar derivation into EdDSA. Both remove the dependence on a random number generator at signing time, which eliminates the failures caused by broken, unseeded or biased generators, historically some of the most damaging. RFC 6979's derivation also produces nonces that are uniform over the correct range, removing simple reduction bias.

Determinism does nothing for implementation leakage. A deterministic nonce processed by a scalar multiplication whose timing depends on bit length leaks exactly as a random one does; several of the cases cited above affected implementations regardless of how their nonces were chosen. Cache and power leakage are likewise unaffected.

Determinism also adds an exposure. Because the same message under the same key always yields the same nonce, an attacker who can request two signatures on the same message, and cause a computational fault during one of them, obtains a correct and a faulty signature sharing one nonce, a configuration that can expose the private key. Poddebniak and colleagues (2018) demonstrated practical fault attacks of this kind against deterministic signature implementations. A separate class of API misuse, in EdDSA libraries that accept a public key as a separate input to signing without checking it against the private key, can likewise produce two signatures with the same nonce and different challenges. Determinism is therefore a strong defence against one source and neutral or adverse for the others.

A layered defence model for signing implementations

Because the four sources are independent, defences must be layered, and this article proposes a model with five layers, from nonce derivation outward. First, derivation: nonces should be uniform and independent of the random number generator's health, which means deterministic derivation or, better, hedged derivation that mixes fresh randomness into a deterministic construction, so that both a broken generator and an induced fault on repeated signing must occur before the nonce is exposed. RFC 6979 explicitly permits additional input for this purpose.

Second, arithmetic: scalar multiplication must be constant time with respect to the full nonce, including its bit length, typically by always processing a fixed number of bits through a ladder or fixed window with masked selection. Third, physical and microarchitectural resistance: blinding of the nonce or private key, and hardware evaluated against power and electromagnetic analysis where attackers may have physical access. Fourth, fault resistance: verify every signature with the public key before release, and detect computational inconsistencies. Fifth, operational limits: rotate keys that sign at very high volume, and monitor signing behaviour and collected signatures for anomalies such as repeated first components.

No single layer is sufficient, and the absence of any one reopens a known attack class. The model's value is that it turns a vague instruction, 'handle nonces carefully', into separate, testable obligations.

Exposure in AI agent platforms

Leak-based attacks are limited mainly by the number of signatures an attacker can collect and observe. AI agents remove that limit. An agent may sign every request it sends to a tool server, every token it presents, every entry it writes to an audit log, and every approval it records, potentially many thousands of times a day under a single key. Many of those signatures are stored and exposed to other systems, and signing latency is often observable to the services the agent calls. In this article's analysis, an agent platform that signs with a software implementation susceptible to timing leakage of nonce length is therefore a far more attractive target than a human user of the same implementation would be.

A second agent-specific concern is code generation. Signing glue code written quickly, sometimes by code assistants, may generate nonces with a general-purpose random function, reduce random values naively, or call low-level arithmetic routines that are not constant time. Each of those reproduces one of the documented leak sources.

The defensive response follows the layered model: route agent signing through a key management service or hardware security module whose implementation has been evaluated against side channels and faults, use deterministic or hedged nonces, cap the signing volume per key with rotation, and monitor stored agent signatures for anomalies.

Testing for leakage, and limitations

Organisations can test their own signing implementations without implementing any recovery algorithm. With a test key in a test environment, the team can instrument the signer to record each nonce's bit length alongside the measured signing time, then check statistically whether time depends on length or on other nonce properties; any significant dependence is a defect. A second test checks the nonce distribution itself under the test key for uniformity. A third, for fault resistance, confirms that the implementation verifies signatures before release. These tests use internal access that an attacker would not have, which is exactly why they are effective at finding problems early.

This article's limitations are deliberate. It describes the lattice method qualitatively and omits construction details. Statements about signature counts are qualitative because the published figures depend heavily on leak size, noise and computational budget. The agent-platform analysis extrapolates from the documented mechanisms and the signing volumes agents can generate; it does not report a measured incident. Finally, the layered model is a review aid, not a substitute for formal side-channel evaluation of high-assurance implementations.

SETUP  test environment, test-only signing key, instrumented signer
REPEAT N times:
    msg   = random_test_message()
    t0    = clock(); sig = sign(test_key, msg); t1 = clock()
    k_len = instrumented_nonce_bit_length()      # available only in the test build
    record(k_len, t1 - t0)
TEST  correlation(k_len, elapsed)      -> any significant dependence is a DEFECT
TEST  uniformity(nonce_samples)        -> any detectable bias is a DEFECT
TEST  verify_before_release_enabled    -> must be TRUE

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

samples = []
for i in range(N):
    t, sig, k_len = timed_sign_with_instrumentation(test_key, test_msg(i))
    samples.append((k_len, t))
assert not significant_correlation(samples)
assert nonce_distribution_uniform(test_build_nonces())
assert verify_before_release(test_signer)

agent_signing:
  location: evaluated_kms_or_hsm      # never in agent memory
  nonce: deterministic_or_hedged
  verify_before_release: required
  rotation: { max_signatures: per_policy, max_age: per_policy }
  application_nonce_generation: forbidden
  monitoring: [repeated_r_values, signing_latency_anomalies]

Glossary

Nonce

The secret per-signature value used in ECDSA and EdDSA, which must be uniform, secret and unique.

Hidden number problem

Recovering a secret number from many random multiples of it with only partial information about each.

Lattice reduction

Algorithms that find short vectors in a lattice, used to combine many weak hints into a recovered key.

Nonce bias

A systematic deviation of nonces from the uniform distribution, such as being shorter than full length.

Deterministic signing

Deriving each nonce from the private key and message rather than from a random generator.

Hedged signing

Deterministic nonce derivation with added fresh randomness, so two independent failures are needed to expose the nonce.

Fault attack

Inducing a computational error and comparing faulty and correct outputs to extract secrets.

Constant-time implementation

Code whose timing and memory access patterns do not depend on secret values.

References

1. D. Boneh, R. Venkatesan, Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes, CRYPTO 1996
2. N. A. Howgrave-Graham, N. P. Smart, Lattice Attacks on Digital Signature Schemes, Designs, Codes and Cryptography, 2001
3. RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) (IETF)
4. RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA) (IETF)
5. D. Moghimi, B. Sunar, T. Eisenbarth, N. Heninger, TPM-FAIL: TPM meets Timing and Lattice Attacks, USENIX Security 2020
6. J. Jančár, V. Sedláček, P. Švenda, M. Sýs, Minerva: The curse of ECDSA nonces, IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020
7. D. F. Aranha et al., LadderLeak: Breaking ECDSA with Less than One Bit of Nonce Leakage, ACM CCS 2020
8. D. Poddebniak, J. Somorovsky, S. Schinzel, M. Lochter, P. Rösler, Attacking Deterministic Signature Schemes Using Fault Attacks, IEEE EuroS&P 2018