Deterministic Nonce (RFC 6979) Failures — when 'no more RNG risk' still leaks the key

A DSA/ECDSA implementation that claims to derive the nonce k deterministically (RFC 6979 or a home-rolled equivalent) but drops the private key or the message from that derivation reintroduces the exact nonce-reuse class RFC 6979 exists to prevent.

The signal that betrays it

RFC 6979 done correctly seeds an HMAC-DRBG with both the private key x (as int2octets(x)) and the message hash H(m) (as bits2octets(H(m))) — that's the whole point: k is unique per (key, message) pair without needing an RNG. The tell in a challenge is when the source (or the observable behavior) shows k derived from less than that pair:

- k = H(m) alone — key-independent. Anyone can compute k from a public message. - k = H(seed || m) where seed is a fixed, hardcoded, or otherwise recoverable constant instead of the actual private key. - A custom "deterministic" scheme that documents itself as RFC-6979-inspired but the code path skips folding in the private key. - k derived from a low-entropy counter or a timestamp instead of a proper HMAC chain — deterministic in the sense of "predictable," not in the RFC 6979 sense.

Behaviorally, the giveaway is identical r across signatures that shouldn't share a nonce: the same message signed under different keys produces the same r (because k never depended on the key), even though a correct RFC 6979 implementation would never do that.

How to exploit it

First establish *why* k is guessable — that decides the recovery path:

1. `k` is directly computable (e.g., k = H(m), key-independent, and you can compute the hash yourself): recover the private key d in one shot from a single signature, since you now have two equations reduced to one unknown:

``python # ECDSA/DSA core identity: s*k = h + d*r (mod n) # If k is known (recomputed from the leaked/deterministic derivation): def d_from_known_k(r, s, h, k, n): return ((s * k - h) * pow(r, -1, n)) % n ``

2. `k` is the same across two different messages under one key (the derivation forgot to fold in m, or used a fixed low-entropy seed): this collapses to the standard nonce-reuse case — treat it exactly like ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra: two signatures (r,s1) on h1 and (r,s2) on h2 give a closed-form solve for both k and d.

3. **Only the *structure* of the weak derivation is known, not k itself (e.g., a seed of small/bounded entropy, or a counter you can bound the range of): brute-force the seed or counter space, deriving a candidate `k` for each guess, computing a candidate `d`, and verifying it against the public key** (d*G == Q for ECDSA, or g^d mod p == y for DSA) before trusting it. This is the only way to be sure — a wrong k guess can still produce *a* number, so always validate against the public key, never just against one signature.

4. Same key-independent `k` reused across different keys on the same message: identical r appears, but the *s* values differ per key — this does not hand you either private key from the pair alone (see below), but it is strong confirmation you found the right vulnerability class before you go hunting the per-key second relation (a second message from the same key, or a leaked/brute-forceable seed).

What does NOT work

- Assuming any "RFC 6979" label means you can skip auditing it. The name in a comment or a doc string is not proof of correct implementation — the recognizable failure mode is specifically an implementation that *claims* determinism-for-security but silently drops the private key from the HMAC chain. Read the actual derivation code, not the docstring. - Trying to recover a private key directly from two signatures (same `r`, different keys) that both used a key-independent `k`. Different s values under different d with the same k is *not* the same closed-form system as classic same-key nonce reuse — you get one equation with two unknowns (k still unknown to you, d unknown) per signature, and the two equations don't share a key to eliminate. This looks like a jackpot (identical r!) but it isn't one on its own; it only tells you the derivation is broken. You still need a *second* relation on one specific key (another message from that key, or the recoverable seed) to actually solve for d. - Proper RFC 6979 (private key + message hash both folded into the HMAC-DRBG chain) is not vulnerable to this class at all. Don't waste time trying to attack a genuinely correct implementation — verify first that the derivation is actually missing an input before investing in brute force or algebra. If both x and H(m) demonstrably feed the HMAC chain, this attack does not apply; look elsewhere (fault injection, side channel, bias in the underlying hash).

Related

ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra — the closed-form recovery once two signatures share a nonce. Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula — generalizes to nonces related by a *known* linear formula (counters, LCGs) rather than exact reuse. ECDSA Fundamentals — the s*k = h + d*r identity that routes every nonce attack and DSA Fundamentals — the linear signing equation every DSA attack exploits — the s*k = h + d*r identity this attack exploits. DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery — the sibling technique when the nonce leak is partial (some bits) rather than a full derivation break. Cryptanalysis Methodology — classify the family before you reach for an attack — where this fits in the overall triage of a signature challenge.