Sign the same message twice.

8 min read

SIGNATURE NONCES

A one-line test that reveals part of what a signing device does internally, and a fleet-wide scan for nonce-reuse compromises and anomalies.

The earlier article observed that a secure element may implement deterministic, randomized or hedged nonce generation without revealing which, and that conformance to the external signature format says nothing about what happens inside the boundary.

That is true, and it is also not the end of the story. The choice is partially observable from outside, at no cost, and the observation is worth making before the procurement conversation rather than after.

The test

Sign the same message, with the same key, twice. Compare the raw signature bytes.

Identical output is consistent with deterministic signing. It can also result from a repeated random nonce, a cached signature, or an API that does not perform a fresh signing operation. Repeat the test across several messages and verify the API semantics before drawing a conclusion. The observation is useful, but it does not by itself prove an RFC 6979 implementation.

Different output means something varies. This is where the test stops being conclusive, and the distinction matters more than it first appears.

A fully randomized nonce and a hedged nonce both produce varying signatures. Their failure profiles differ. If the random source degrades because of cloned VM state, an embedded device signing before entropy is available, or a hardware generator that has quietly stopped, a fully randomized implementation may repeat or bias a nonce and disclose the private key. A correctly constructed hedged implementation retains a deterministic contribution and is designed to remain secure when the random contribution fails.

The test therefore does not answer the question. It tells you which question to ask, and it converts a vague procurement conversation into a specific one: your device produces varying signatures; is that randomized or hedged, and under which construction?

That is a question a vendor can answer in one sentence or decline to answer, and both responses are informative.

The scan

The single-device test extends into something considerably more useful across a population.

In ECDSA, the value r in a signature is derived from the x-coordinate of the ephemeral point kG. Two signatures sharing the same r have reused that x-coordinate. The usual cause is nonce reuse, although k and its group inverse also share an x-coordinate and must be considered in the analysis.

If those two signatures are under the same private key, the key falls out with arithmetic that fits on one line: the nonce is recoverable from the two message hashes and the two s values, and the private key follows from the nonce.

If the two signatures are under different keys, a repeated r does not by itself recover either private key. It is still an anomaly worth investigating, especially across devices that should have independent random state. It may indicate shared or repeated nonce material, deterministic seeding across a manufacturing batch, or another implementation defect, but the collision must be analysed in context.

The scan follows directly:

Collect ECDSA signatures produced by the device population. Signatures are public by construction; no device access is required.
Extract r from each.
Sort and look for duplicates.
Cluster any collision by key, firmware version and manufacturing batch.

This is a compromise and implementation-anomaly detector that can operate on public signatures. A repeated r under the same key and different message hashes is a key-recovery condition. A repeat under the same key and same message may be expected from deterministic signing. A repeat across different keys is an anomaly, not proof of compromise. The grouping step is therefore part of the cryptographic analysis, not merely reporting.

Partial bias is harder to detect but has been exploited in published work. Breitner and Heninger recovered private keys from cryptocurrency signatures with only a few bits of nonce bias, using lattice techniques. A generator does not have to repeat to be fatal; a sufficiently exploitable bias can be enough.

The devices that failed this way were certified

Two results from 2019 make the parent article’s point concretely.

Minerva demonstrated recovery of ECDSA private keys from timing variation correlated with the bit length of the nonce, on smartcards and cryptographic libraries, including evaluated devices.

TPM-Fail demonstrated the same class of recovery against TPM implementations from major vendors, including a firmware TPM in widely deployed processors.

In both cases the signature format was correct, the algorithm was correct, the certification was genuine, and the nonce leaked through a channel the specification does not describe. The signatures those devices produced would have passed every functional test, every test vector and every interoperability suite.

This is the same lesson that applies to PKCS #11 attributes: certification evaluates the module against its security target, and the security target may not include the property you are relying on.

The retry problem, which has money attached

There is an operational consequence of nonce choice that rarely reaches the security discussion, and it moves in the opposite direction from everything above.

Deterministic signing can create accidental idempotency.

A payment authorisation, transaction instruction or settlement message signed deterministically produces byte-identical output every time, provided the complete signing input and encoding remain identical. A downstream system that incorrectly uses signature bytes as a deduplication key may therefore appear to handle retries safely.

Adopting randomized or hedged signing removes that accidental property. The retried operation produces a different signature over the same message, and a deduplication mechanism built on signature bytes silently stops working. It may accept the second copy as a distinct instruction.

The parent article raises the retry question in terms of trace alignment. The practical version is sharper: a change made by the cryptography team can break a duplicate-detection mechanism owned by the payments team, and the failure will not appear in any test that signs one message once.

The resolution is that transaction identity must be established by an explicit identifier carried in the signed message, not inferred from signature bytes. That is the correct design regardless of nonce policy. Most systems that need it do not have it, and the discovery usually happens during the migration rather than before.

The procurement questions

Six questions, to be answered in writing, per device or library:

Which nonce generation does the signing operation use: deterministic per RFC 6979, randomized, or hedged?
If hedged, which construction, which pseudorandom function, and how are the deterministic and random contributions combined? An unanalysed XOR of random bytes into a deterministic nonce is not a hedge; it can introduce bias or cancel.
If the API accepts caller-supplied additional randomness, does the implementation actually use it, and how is it incorporated?
Is the nonce derived from a prehash or from raw message bytes, and does that match what the layer above supplies? A mismatch here binds the nonce to less context than the protocol assumes.
What side-channel and fault evaluation has been performed, to what level, by whom, and is the report obtainable under NDA?
On a retry after transport failure, does the device reproduce the previous signature or generate a new one?

Question six is the one that surprises people, and it belongs in the same document as the other five.

The test matrix

For a hedged implementation, functional testing should cover the failure modes the construction is supposed to survive:

Random input	Expected behaviour
High-quality entropy	Valid signature; varies across runs
All zeros	Behaviour defined by the selected hedged construction; never use uninitialised state
Constant non-zero value	Behaviour remains valid and repeatable under the construction’s specified test procedure
Repeated previous value	Valid signature; must not repeat the nonce under a different message
Random source returns an error	Defined behaviour: either refuse or use a specified fallback, never proceed with uninitialised memory
Same message, many repetitions	All signatures valid; nonces distinct when entropy is present

Every case must produce a signature that verifies. The specification permits the deterministic fallback; an implementation that fails closed when entropy is unavailable is making a different, defensible choice, but it must be a documented choice rather than an accident.

Side-channel and fault resistance cannot be established this way. Those require physical measurement, and no functional test vector substitutes for it.

Open work

The high-value project here is the same shape as the PKCS #11 one, and it is cheaper.

Nobody has published a table of what commercially available secure elements, HSMs and TPMs actually do internally. The test is: sign the same message twice, compare the bytes, record the result. Per device, it is minutes. Across a representative sample of the devices currently sold for identity, payment and IoT applications, it would be a weekend and a small hardware budget.

The resulting table, listing device, firmware version, deterministic or varying output, and the vendor’s written answer to question one, does not appear to exist in public. It would be useful to procurement and evaluation work, and the methodology is transparent enough that others could verify or extend it.

Two adjacent questions worth the same treatment:

How many production systems depend on signature-byte idempotency without knowing it? Detectable by searching for deduplication logic keyed on signature values rather than transaction identifiers.
What fraction of suitable signature corpora contain repeated r values? Cryptocurrency ledgers have been scanned. Other public protocol traces, attestation collections and device test corpora may offer additional populations, provided they expose ECDSA signatures with enough context to group keys and message hashes correctly.

The second is a query, not a research programme. It has produced findings every time anyone has run it.