A research paper. The subject of this study is RFC 6979 (T. Pornin, August 2013), an RFC document defining a deterministic procedure for generating a one-time secret scalar k for DSA and ECDSA.
Annotation
In DSA and ECDSA, the cryptographic strength of a signature is determined not only by the difficulty of the discrete logarithm problem but also by the correctness of the one-time scalar lifecycle k. RFC 6979 replaces the external random number generator during signing with a deterministic HMAC procedure dependent on the private key x and the message hash H(m). This eliminates a whole class of practical disasters: nonce repetition, predictability, and statistical bias due to a faulty entropy source. The signature format and verification algorithm remain unchanged.
Keywords: RFC 6979, DSA, ECDSA, nonce, ephemeral scalar, HMAC, HMAC-DRBG, secp256k1, cryptanalysis, reuse k, side-channel attacks.
Statement of the problem
Classical DSA/ECDSA requires a new secret value for each signature k from an interval [1, q-1], which is practically uniform and inaccessible to an observer. This requirement is operational, not cosmetic: leakage, replay, or partial predictability k could turn a published signature into a linear equation with respect to the private key.
RFC 6979 constructs k a private key-message pair as a pseudo-random but completely reproducible function. Therefore, the signature of the same message with the same key is repeated bitwise, and nonces differ for different messages in the absence of input hash collisions. Determinism applies only to the signing operation: the generation of the private key itself must still use high-quality entropy.
Mathematical model
Parameters and keys
| Scheme | Group and public key | One-time secret |
|---|---|---|
| DSA | Subgroup of order q in Z_p*; y = g^x mod p | k ∈ [1, q-1] |
| ECDSA | Order point q; U = xG | k ∈ [1, q-1] |
Here x is a closed scalar, and G is the base point of the elliptic curve. The security of the schemes implies that recovery x from is computationally undecidable U = xG; however, a bug in the nonce circumvents this difficulty and is not a solution to ECDLP.
Signature formation
\[ h = \operatorname{bits2int}(H(m)) mod q \]
For ECDSA, calculate R = kG and take r = x_R mod q; then:
\[ s = k^{-1}(h + xr) mod q \]
Signature is a pair (r, s). If r = 0 or s = 0, the candidate is rejected, since the standard algorithm requires repeating the procedure with another valid k.
Cryptanalytic fact
Let two different messages be signed with the same nonce k, that is, published by (r, s₁) and (r, s₂); a match r is a practical indicator of duplication k in typical ECDSA analysis. From the signature equalities it follows:
\[ s_1 = k^{-1}(h_1+xr) mod q, \qquad s_2 = k^{-1}(h_2+xr) mod q \]
Subtraction eliminates the private key in the first step:
\[ k = (h_1-h_2)(s_1-s_2)^{-1} mod q \]
Once found, k the private key is restored directly:
\[ x = (s_1k-h_1)r^{-1} mod q \]
This is the central cryptanalytic fact: compromise is possible using publicly observable signatures, without breaking the hash function, brute-forcing the key, or solving the discrete logarithm problem.
Historical incidents
| Event | Mechanism | Cryptanalytic investigation |
|---|---|---|
| PlayStation 3, 2010 | Sony’s code signature implementation used a repeating ECDSA nonce. | The private portion of the root of trust was reconstructed using update signatures; the example demonstrated that a strong algorithm does not compensate for the violation of the one-time requirement. |
| Android Bitcoin Wallets, 2013 | SecureRandom initialization issues resulted in predictable or repeatable values in ECDSA transaction signatures. | A blockchain observer could find collisions r, infer private keys, and spend funds from the corresponding addresses. |
Both cases are not “ECDSA cracks” in the mathematical sense, but rather exploitation of a violation of the algorithm’s preconditions. It is precisely this failure of external randomness that RFC 6979 addresses.
Normalization of representations
Implementation compatibility requires that RFC 6979 transformations be literally reproduced. Let be qlen the bit length of q, and rolen = ceil(qlen/8).
| Operation | Purpose | Risk of incorrect implementation |
|---|---|---|
bits2int(b) | Leaves the left qlen bits (or pads them with zeros on the left), interpreting them big-endian. | Incorrect shift direction and byte order produce a different nonce and break test vectors. |
int2octets(x) | Encodes a fixed-length rolen byte scalar in big-endian. | Removing leading zeros changes the HMAC input and breaks inter-implementation compatibility. |
bits2octets(h1) | Calculates int2octets(bits2int(h1) mod q). | Substitution with “raw” H(m) creates a variant that does not coincide with the specification and its vectors. |
It’s important to note that when selecting a candidate, k one cannot simply calculate k mod q. If the value is out of range, the generation must be repeated: modular reduction with an uneven number of preimages introduces a bias into the distribution.
RFC 6979 algorithm
HMAC is used on the same hash function Hthat is used to hash the message. With SHA-256, the initial K and V are 32 bytes long: all zeros and all , respectively 0x01.
Вход: закрытый ключ x, сообщение m, порядок группы q, хэш H
h1 = H(m)
bx = int2octets(x)
bh = bits2octets(h1)
V = 0x01 повторённое hlen/8 раз
K = 0x00 повторённое hlen/8 раз
K = HMAC(K, V || 0x00 || bx || bh)
V = HMAC(K, V)
K = HMAC(K, V || 0x01 || bx || bh)
V = HMAC(K, V)
цикл:
T = пустая строка
пока длина(T) < qlen:
V = HMAC(K, V)
T = T || V
k = bits2int(T)
если 1 <= k < q и r(k) != 0:
вернуть k
K = HMAC(K, V || 0x00)
V = HMAC(K, V)Structurally, this is a specialized use of HMAC_DRBG: int2octets(x) it acts as an entropy input, and bits2octets(H(m)) the nonce is used to initialize a separate state for each signature. Actual randomness at the time of signature is not required.
Practical example
Bitcoin uses ECDSA over secp256k1 and typically SHA-256 from the serialized transaction (the exact sighash scheme depends on the input type). RFC 6979 does not change the public key, the DER encoding of the pair (r,s), or the network verification rules: only the internal method for obtaining [signer] is modified k. Therefore, a deterministic signer can interoperate with existing verifiers without a protocol fork.
Why HMAC eliminates risk
The private key is included in the initial state of the HMAC, and the message hash associates the nonce with the specific entity being signed. For a person without x [a] signature, the candidate sequence must be computationally indistinguishable from pseudorandom under the standard assumption of the HMAC as a PRF.
| The failure of the traditional approach | RFC 6979 in effect | Border of protection |
|---|---|---|
| Uninitialized or faulty CSPRNG | Excludes CSPRNG from the nonce generation path. | Does not fix a weak private key created with low entropy. |
| Repeat nonce after device restart | Nonce is tied to x and H(m), not to the PRNG state. | Identical messages are deliberately given the same signature. |
| Unverifiable randomness quality by tests | Provides fixed test vectors and reproducible results. | Does not prove the absence of errors in curve arithmetic and memory protection. |
| Offset when converting to a range | Uses rejection sampling rather than unconditional sampling mod q. | Requires correct implementation of the rejection cycle. |
Limitations and side channels
RFC 6979 is not a replacement for a full-fledged key protection model. It does not protect against memory reading, device compromise, weak key pair generators, pre-signature hashing, timing, electromagnetic radiation, or power consumption attacks.
Determinism can make some side-channel measurements more convenient for an attacker, since the same secret scalar is repeated for a fixed message. A practical implementation should employ constant-time scalar arithmetic, blinding when necessary, memory protection, and hardware/software measures against key leakage.
Options and compatibility
The RFC allows for theoretical variations: additional non-repeatable input, a separate secret for the HMAC, or different hash functions for the message and the HMAC. However, such schemes are no longer strictly RFC 6979 procedures and do not match its published test vectors.
In a production system, a literal implementation of RFC 6979 should be chosen if predictable compatibility is required. Changes are permitted only as explicitly specified parts of the upper protocol with independent test vectors, threat assessment, and migration plan.
Audit recommendations
- Check that
kit is not imported from a shared or unsafe PRNG when deterministic-signing is enabled. - Check the implementation against the RFC 6979 test vectors for the applied curve and hash function.
- Audit fixed-length
int2octets, big-endian encoding, and correctnessbits2int/bits2octets. - Check rejection loop: the candidate must be comparable to
q, not unconditionally reduced modulo . - Monitor published ECDSA signatures for duplicates
r; this is a strong signal of immediate key compromise. - Don’t extend the “RFC 6979 is everything” conclusion to key generation, HSM protection, backups, side-channel resistance, and supply chain security.
Conclusion
The primary significance of RFC 6979 is engineering: it transforms ECDSA/DSA’s fragile reliance on correct randomness during each signature into a deterministic, testable HMAC procedure. Historical cases of PS3 and Android Bitcoin wallets demonstrate that a nonce error breaks the cryptosystem at the key level, even though the underlying mathematical assumptions of ECDSA remain intact.
Sources
RFC 6979: deterministic nonce in DSA and ECDSA: https://ctxc.ru/rfc-6979-deterministic-nonce-in-dsa-and-ecdsa/
- T. Pornin. RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) , August 2013. Official RFC text .
- H. Krawczyk, M. Bellare, R. Canetti. RFC 2104: HMAC: Keyed-Hashing for Message Authentication , February 1997.
- NIST. SP 800-90A: Recommendation for Random Number Generation Using Deterministic Random Bit Generators .
- Public incident reviews: fail0verflow/PlayStation 3 (2010); Android SecureRandom and Bitcoin wallet vulnerability (2013).