WorksComputer Science
Deterministic ECDSA on secp256k1: the RFC 6979 assumption, a counterexample, and the state of deployed implementations
Abstract
RFC 6979 derives the ECDSA nonce as , with HMAC_DRBG keyed by the signing key x. We isolate the assumption its security rests on, A*: at known public key , the signing transcript under nonces is indistinguishable from the transcript under uniform nonces. A* suffices, and it is neither PRF security of HMAC nor auxiliary-input PRF security (AI-PRF) of . A function is a PRF under standard assumptions yet leaks x from one signature; the same holds for unmodified RFC 6979 over a compression function that keeps the PRF and dual-PRF properties used in proofs of HMAC, given a collision-resistance premise. A* and AI-PRF are separated in both directions. A* does not imply AI-PRF if the one-bit hidden number problem is hard. Conversely, in the standard model: any AI-PRF can be modified so that it stays one while two chosen-digest signing queries reveal x; under DDH with one public random point, or decisional square Diffie-Hellman without it, there is an AI-PRF whose key is recovered from signatures on two ordinary hashed messages; and a third function, under PRF security and DLP, violates A* while the scheme stays unforgeable. With an ideal compression function, A* follows tightly from DLP in the presence of a randomized-ECDSA signing oracle, and a nonce key independent of x removes the assumption. The secret HMAC message block is from uniform on secp256k1, on P-256 and 0.336 on brainpoolP256r1. An audit of 31 secp256k1 implementations finds that 28 sign deterministically without added entropy and that the raw-message deviation from bits2octets of libsecp256k1 before 0.2.0 survives in NBitcoin, dcrd and btcec v2. Low-R grinding needs no assumption beyond A*, and every nonzero Fourier coefficient of the low-R nonce set is below unconditionally. We give test vectors for the untested branch
Introduction
ECDSA leaks the signing key when the per-signature nonce is repeated, biased, or partially known. Deterministic nonce derivation (RFC 6979 [1]) removes the dependence on a run-time random number generator by computing from the signing key and the message hash with HMAC_DRBG. The construction is the de facto standard in the Bitcoin and Ethereum ecosystems: of the 31 secp256k1 implementations we audited, 28 sign ECDSA deterministically by default, and the dominant library, libsecp256k1, offers no other default.
The security argument that accompanies RFC 6979 is informal. Section 4 of the RFC states that HMAC_DRBG “is secure in that role as long as HMAC behaves as a PRF” and that the construction “requires HMAC_DRBG to keep on being a random oracle even when the public key is also known”. These two sentences describe two different assumptions, and we show that neither is the one actually needed.
Contributions.
We formulate the assumption under which deterministic ECDSA is exactly as secure as randomized ECDSA (Theorem 3.1), and show that the auxiliary-input PRF assumption AI-PRF on does not support such a reduction (§ 3).
We give a counterexample: , where is any PRF and Ext extracts bits from the public key, is a PRF under the PRF security of and a standard randomness-extraction lemma, yet deterministic ECDSA with reveals from one signature (Theorem 4.5). Hence “PRF + DLP + randomized ECDSA is secure” does not imply that RFC 6979 is secure, and is a genuinely additional assumption. We lift the counterexample to the compression function: there is with the PRF and dual-PRF properties used in proofs of HMAC (given a collision-resistance premise) for which the unmodified RFC 6979 state machine is a PRF in and Det-ECDSA is broken with one signature (Theorem 4.8).
We prove that and AI-PRF are not equivalent. AI-PRF holds conditionally on the hardness of the one-bit hidden number problem (§ 5). For AI-PRF , the natural candidate—rejecting nonces unless —does not separate the two notions for any number of signing queries and any filter width (Theorems 5.1 and 5.4), but two other constructions do, in the standard model. A planted nonce collision turns any AI-PRF into an AI-PRF under which two chosen-digest signing queries reveal (Theorem 5.7). Under the decisional square Diffie–Hellman assumption there is a single-key AI-PRF under which signatures on two ordinary SHA-256 messages reveal , so that a third message is forged (Theorem 5.9). Ordinary DDH suffices given one public random point, or, without any setup, given an AI-PRF and about signatures; with a second secret scalar the existence of an AI-PRF alone suffices (Theorem 5.13, Table 3). An ordering bit hidden in a signature scalar violates with advantage on three fixed hashed messages, under PRF security and DLP, and survives low- normalization (Theorem 5.11); that scheme remains unforgeable, so is sufficient but not necessary.
| Construction | Assumption | Setup and secrets | Signing queries |
| (Thm. 5.7) | an AI-PRF exists | none; | 2, chosen digests |
| (Thm. 5.9) | DSDH, PRF | none; | 2, hashed messages |
| Thm. 5.13(a) | DDH, PRF | one public random point; | 2, hashed messages |
| Thm. 5.13(b) | DDH, an AI-PRF exists | none; | , hashed messages |
| Thm. 5.13(c) | an AI-PRF exists | none; and a second scalar | 2, hashed messages |
Table 3. Key-recovery separations AI-PRF A*. In every row the nonce adversary queries arbitrary digests; the column “queries” restricts the signing attacker.
We record what is provable: with an ideal compression function, follows from DLP in the presence of a randomized-ECDSA signing oracle, with no factor (Theorem 6.1); a nonce key independent of makes it unnecessary (§ 6). We quantify the curve dependence of the standard part of the assumption (§ 7).
We audit 31 implementations (§ 8): nonce defaults,
bits2octetscompliance, the retry and grinding logic, and test coverage. We prove that low- grinding, as deployed in Bitcoin Core, reduces to on an extended input domain plus randomized ECDSA (Theorem 8.1), we bound every nonzero Fourier coefficient of the low- nonce set unconditionally (Proposition 8.2), and we supply test vectors for the branch, which no implementation we examined tests.
We place the one-bit nonce-bias attack in context (§ 9): a modelled data threshold of signatures for one error-free leaked bit on a 256-bit curve, with an honest uncertainty envelope of –, and the observation that GLV decomposition of a uniform nonce creates no such bias.
All claims are tagged in the text as proved here [T], taken from the literature [L], established by inspection of source code [S], or estimates and interpretations [O].
Preliminaries
Curve and notation. secp256k1 is the curve over , , with prime group order
and generator . We write . The signing key is , the public key is . For a message with hash we write . An ECDSA signature on with nonce is with , , .
RFC 6979. The nonce is where
and candidates outside are rejected by advancing the DRBG (step H.3). Section 3.6 of the RFC optionally appends additional data to the seed.
Three schemes. Rand-ECDSA: uniformly. Det-ECDSA: . Det′-ECDSA: for a PRF with key independent of .
Two assumptions. Let be a probabilistic polynomial-time distinguisher and a random function.
Assumption 2.1 (AI-PRF). is an auxiliary-input PRF at the public key if for every
Assumption 2.2 (). satisfies if for every
where is the signing oracle using nonces and the oracle using independent uniform nonces (with the same rejection rule).
Both assumptions are falsifiable in the sense of Naor [4]: an efficient distinguisher is a verifiable witness of failure.
Chosen digests and hashed messages. In both assumptions the distinguisher submits digests directly; we call this the chosen-digest game. It is the interface of libsecp256k1 and of most libraries of Section 8, which sign a caller-supplied 32-byte digest. In the hashed-message game queries are restricted to for messages . An assumption stated for chosen digests implies its hashed-message version, whereas an attack that needs particular digests may not transfer. Forgery games are always played with hashed messages, because ECDSA is forgeable on chosen digests (see (3)).
What the reduction needs
Theorem 3.1 ( suffices). For every forger against Det-ECDSA there is a forger against Rand-ECDSA and a distinguisher with
Proof. Game 0 is the Det-ECDSA forgery game; Game 1 replaces the nonces by independent uniform values. Any whose success differs between the games is a distinguisher for : receives , forwards signing queries to its oracle, and outputs 1 iff forges. Game 1 is the Rand-ECDSA game. [T]
Proposition 3.2 (AI-PRF does not support the reduction). A distinguisher for AI-PRF receives . To simulate the signing oracle for a Det-ECDSA forger it must produce , which requires . No generic reduction from AI-PRF to the security of Det-ECDSA can simulate signatures in the standard model. [T]
The proposition says only that the obvious reduction fails. The next section shows that no reduction that uses purely as a PRF can succeed, and Theorems 5.7 and 5.9 that the same is true of AI-PRF: there are nonce functions satisfying it under which two signatures reveal the key, on chosen digests if any AI-PRF exists at all, and on ordinary hashed messages under decisional square Diffie–Hellman, or under DDH with a public random point.
A counterexample
Let be an injective encoding of the points of , including , as strings of at most 258 bits, and let be a universal family of functions . For a seed fixed below put . Let be any PRF with a uniform -bit key, . Define
The key enters only through , which is a function of the public key.
Lemma 4.1 (extraction). For uniform on ,
which is for . Hence there is a seed with ; we fix such an . [T]
Proof. is uniform on points and is injective, so . Apply the leftover hash lemma [11] and average over .
Remark 4.2 (deterministic truncation). A seedless alternative is to truncate the abscissa, but the available bounds are for the least significant bits: Chevalier, Fouque, Pointcheval and Zimmer [10 Thm. 14] prove for uniform on and , i.e. on secp256k1 and for . The work of Fouque, Pointcheval, Stern and Zimmer [9] concerns subgroups of only. We use the seeded extractor throughout because § 4.1 needs extraction from a non-uniform subset of the group, where the leftover hash lemma applies verbatim.
Lemma 4.3 (PRF security). . [T]
Proof. Replace by a uniform key (loss by Lemma 4.1); forwards 's queries to its oracle. No circular-security assumption is needed because is used only as PRF key material.
Lemma 4.4 (key recovery). Given and one Det-ECDSA signature on with , anyone computes , and . [T]
Theorem 4.5 (counterexample). Assume is a PRF, DLP is hard on secp256k1 and Rand-ECDSA is EUF-CMA-secure. Then is a PRF (Lemma 4.3), all three premises hold, and Det-ECDSA with is totally broken (Lemma 4.4). Consequently no reduction that treats the nonce function only as a PRF—in particular none that uses only the PRF security of HMAC—can prove RFC 6979 secure. also violates AI-PRF: anyone holding recomputes all its outputs. [T]
Remark 4.6. A variant would require adding to oracle answers in the PRF reduction and therefore a circular-key assumption; the variant (1) avoids this entirely.
Opening the box: the SHA-256 compression function
Theorem 4.5 treats as a black box. HMAC_DRBG is not an arbitrary PRF: proofs of HMAC rest on properties of the SHA-256 compression function , and one might hope that these properties, together with the specific state machine of RFC 6979 §3.2, imply . They do not, given a collision-resistance premise.
Block layout. With and , step d computes
The inner hash first compresses the public block , giving a public chaining value , and then the 97-byte message; the total length is 161 bytes, bits. The two message blocks are
where is the -th byte of . Step f has the same layout with , and the secret chaining value derived from . Write for the 31-byte SHA-256 padding tails. In every other block of the computation—HMAC key setup, outer hashes, steps e, g, h, and the retry step H.3—either byte 32 is not in or bytes 33–63 lie in . Writing with and , we have .
[T]
Properties of
We use three properties.
(A1) PRF in the chaining value: is a PRF for uniform secret .
(A2) Dual PRF with a key in the first half of the block: for uniform secret , the map is a PRF. This is the property used for HMAC with 256-bit keys and for the outer hash [5, 6].
(A2′) Tail-keyed pseudorandomness: for public , a public 264-bit prefix and uniform , the value is pseudorandom. A standard-model proof that RFC 6979 is a PRF in needs with and (§ 7).
Construction. Let , let be as in § 4 and read as an integer. Define
with and . Let denote the advantage of an efficient algorithm that, given , outputs in with , and put .
Lemma 4.7 ( inherits the properties). , , and satisfies whenever satisfies and , with additional loss .
[T]
Proof. for a public map . The two branches never collide under : on the first branch the last bits are zero, whereas every element of ends in a non-zero length field, and for the byte already differs. Hence is injective on any set of queries that contains no collision of the composite map, and a distinguisher for (A1) or (A2) of is one for unless it finds such a collision. For with prefix byte and uniform : with probability ; the map is injective on because is invertible modulo and , so and the leftover hash lemma gives distance for all but a small fraction of seeds; choose good for this and for Lemma 4.1 simultaneously. Then apply . For other prefix bytes .
Theorem 4.8 (white-box counterexample). Assume satisfies , and and that the composite map above is collision resistant. Let be the unmodified RFC 6979 §3.2 nonce derivation with the SHA-256 compression function replaced by . Then:
satisfies , and (Lemma 4.7);
is a PRF in : for queries, ;
given and one Det-ECDSA signature under , is recovered with at most 256 runs of the nonce derivation, so Det-ECDSA with is totally broken and fails.
Consequently for HMAC_DRBG does not follow from , and of the compression function together with DLP and the EUF-CMA security of Rand-ECDSA, provided a collision-resistant map of this form exists. [T]
Proof. (2) The pair is within of independent uniform values on its range. enters the computation only in block 1 of steps d and f, and there only through , except when . Replace by a uniform (loss ); then disappears from the game. Now is pseudorandom by . Block 2 of step d is , a random function of by ; distinct queries give distinct inputs. The outer hash and the key setup of are keyed in the first half of the block by ; step e is ; block 1 of step f is under ; the remaining evaluations of steps f–h and the retries are evaluations of handled by and . The final nonces are independent and uniform for distinct .
(3) For each compute . Every evaluation of in the derivation depends on only through , hence through when , and on directly. Run the derivation with and , obtain , and test against . For this returns , unless (probability ).
Remark 4.9 (on the collision premise). alone is not collision resistant once is known: a linear universal family has collisions in a known kernel. Exploiting a kernel element, however, requires a with prescribed point , i.e. a discrete logarithm. In the generic group model [7] encodings are random and collisions of the composite cost (Table 1). We know no reduction to DLP, so the premise is non-standard and is stated explicitly. [O]
| collision, generic group | ||
| 128 | ||
| 160 | ||
| 184 |
Table 1. Parameters of : extraction loss and generic cost of a collision. [T][O]
Remark 4.10 (why the collision term is there). A proof of item (2) by statistical extraction must replace all information about that enters by a uniform string, which the leftover hash lemma allows only for strings shorter than bits. The first branch of is then not injective in , and for needs collision resistance. A two-call variant that feeds in clear into a second compression call restores injectivity but breaks item (2): after is replaced by , the point still appears in the second call of steps d and f, and the hybrid argument cannot proceed. Computational extraction could avoid the term at the price of another non-standard assumption. Theorem 4.8 does not exclude proofs of from other properties of , such as correlation intractability, or in the random-oracle model (Theorem 6.1). [O]
and AI-PRF are not equivalent
does not imply AI-PRF
Take with a one-bit leak: with its least significant bit replaced by a bit computable from and checkable from . AI-PRF is broken with queries. For an observer of signatures knows one bit of every ; this is the hidden number problem with one known bit per sample, equivalently a half-range nonce after the substitution . The best known attack is Bleichenbacher’s at (Aranha et al. [23]), about for 256 bits by scaling, by the model of § 9. A generic reduction AI-PRF-distinguisher -distinguisher would therefore yield a polynomial-time distinguisher for signatures with one-bit nonce bias. The separation holds conditionally on the one-bit HNP being hard, which is the same assumption the practical relevance of RFC 6979 rests on. [O]
AI-PRF does not imply : a natural candidate that fails
A separating predicate must (i) be computable by the signer, who knows ; (ii) not be computable from , else the AI-PRF distinguisher sees it; (iii) be efficiently detectable from the transcript , else is not violated. The natural candidate is . (Conditions on the point fail (ii): the AI-PRF distinguisher computes itself.)
Construction. Let be a PRF with an independent key and define
The expected number of trials is . The PRF key must not be itself, since the AI-PRF security of at known is the assumption under study.
Simulatability of a signature. For uniform and , the tuple has the same distribution as the tuple built without :
under which and ; the inverse map is , . This is the observation underlying Fersch, Kiltz and Poettering [12]. Consequently an observer of one signature solves “ from ” with uniform . [T]
Theorem 5.1 (one signature). A predictor of from with advantage over , for uniform and , yields a DLP solver running in time . [T]
Proof. By (3) the reduction constructs the tuple for any chosen and so obtains an oracle predicting . By Markov’s inequality there is for which predicts , , with advantage . Lemma 5.2 recovers .
| Regime | AI-PRF | Separation | |
| , | holds under PRF + DLP [T] | holds under PRF + DLP (Thm. 5.1) [T] | no |
| , | broken: 1D-HNP, lattice [T] | broken: 2D-HNP, lattice [T] | no |
| , | conditional on 1-bit 1D-HNP | conditional on 1-bit 2D-HNP | no |
Table 2. Status of the candidate by number of queries and filter width .
Lemma 5.2 (ACGS with an unknown shift). Let , let be unknown, and let satisfy . Then non-adaptive queries to and time recover with probability . [T]
Proof sketch. Follow Alexi, Chor, Goldreich and Schnorr [15] (in the form of Fischlin and Schnorr [16]). Query points for random , , . Then with and . The unknown shift enters only through , whose least significant bit and coarse approximation are enumerated exactly as ACGS enumerates them for ; the search space does not grow. The are pairwise independent in because is prime, so Chebyshev’s inequality bounds the error of the majority vote at each halving step; a union bound over the steps gives success probability with . The final candidate is checked against . Full details are in Appendix § 11. □
Corollary 5.3 (). With one signing query, with satisfies both AI-PRF (Yao’s lemma plus the hardcore property of the least significant bit of the discrete logarithm [17]; no hybrid is needed) and (Theorem 5.1), assuming is a PRF and DLP is hard. It does not separate the notions. For the simultaneous hardcore property of bits is needed. [T][L]
Theorem 5.4 (). For signing queries, neither side of reduces to DLP:
The hybrid argument fails for AI-PRF: Yao’s lemma over samples with a common secret requires the reduction to sample without knowing , which is the bit it is trying to predict. The AI-PRF game for is the one-dimensional HNP
On the side the hint eliminates : with , and the filter gives the two-dimensional HNP
For on a 256-bit curve both are solved by the Boneh–Venkatesan lattice [18], the AI-PRF side in lower dimension and with half the samples. For both are conditional on the hardness of one-bit HNP, in one and two dimensions respectively. A separation would require “1D-HNP hard, 2D-HNP easy”, for which there is no evidence. [T]
Remark 5.5 (oracle separation). does separate the notions relative to an oracle. Let be a random oracle and let return when , and , and otherwise. An observer of one such break has with advantage , while AI-PRF at holds up to the probability of a key-only forgery under , which reduces to DLP in the bijective random-oracle model of [12]: the reduction answers throughout, and the hash-free forgery does not qualify because . The oracle must be bound to ; one that accepts arbitrary keys admits a rogue-key attack . Section 5.3 makes the oracle unnecessary. [T]
Remark 5.6. Candidates of the type of fail for a simple reason: a relation between the nonce and that the signature equation exposes is exposed more directly by the public pair in the AI-PRF game. [O]
AI-PRF does not imply A*: standard-model separations
places the relation between the nonce and in the output of the nonce function, where the AI-PRF adversary reads it off. The three constructions below hide it elsewhere: in an input that only a signature reveals, in a PRF key derived from a point that only a signature reveals, and in one bit of a signature scalar, which a nonce observer knows only in the exponent. Write . Since , at most two field elements reduce to a given and each is the abscissa of at most two points, so at most four scalars share a value .
Theorem 5.7 (planted collision: one key, two chosen digests). Let be a nonce function with outputs in that satisfies AI-PRF at . Put and
For every distinguisher there are and , running in the time of plus one scalar multiplication per query, with
There is no factor in the number of queries.
There is a distinguisher making two signing queries with
also against a signer that normalizes to low . The two signatures reveal .
[T]
Proof. (1) receives and an oracle , asks , and answers a query of with if and with otherwise. For this is exactly . For a random function the answers are those of unless submits an exceptional ; runs the same simulation with a lazily sampled and, at the first exceptional query, outputs or according to which point matched. The simulator recognizes the hit itself, so no query index is guessed.
(2) queries the digest , receives and computes . The raw signature scalar is , so , the sign depending on normalization; this is why both signs are exceptional. picks with , which holds for at least one sign because , queries , and outputs 1 iff . In the real game , so the nonce is again and ; the choice of sign makes , so there is no retry. The real game fails only if , an event that is publicly testable from and therefore has probability at most . In the ideal game is fresh and the nonce is uniform among the at least valid candidates, of which at most four give .
For key recovery, the raw scalars satisfy and , hence and ; under low- normalization the four sign combinations are tried and tested against .
Remark 5.8 (scope of Theorem 5.7). A discrete-logarithm solver distinguishes from a random function at known , so ; the theorem assumes only that some AI-PRF exists, and turns it into one under which signing leaks the key. The secret is the only key; no independent seed is used. The attack needs digests of the adversary’s choice, namely and . The anchor can be replaced by any fixed digest by planting the collision at , that is at , which is tested publicly by . The second digest still depends on the first signature, so the attack does not pass through a
hash function without computing preimages; Theorem 5.9 removes this restriction at the price of a stronger assumption. No comparable attack on Rand-ECDSA is known: key recovery with a chosen-digest signing oracle is the assumption DLP-Sign of Theorem 6.1. [T]
Theorem 5.9 (hidden seed: one key, two hashed messages). Let and , let be a PRF with -bit keys and outputs in , and let be a fixed public message with digest . Fix a representation of the field and write for its multiplication, applied to abscissas read as -bit strings (the point at infinity is encoded by ). For a signing key with let
with if , let , and define
Candidates rejected by the signer are replaced by including a retry counter in the PRF input. On secp256k1, where :
for every distinguisher , making any number of adaptive queries,
where is the advantage of in distinguishing from with a uniform point independent of ;
an adversary that sees and the signatures on and on one further message of its choice recovers , except with probability at most , and then signs any message. This holds in the hashed-message game and against a signer that normalizes to low .
[T]
Proof. (1) The whole nonce oracle is a function of the two points : computes , , , and from them without knowing and answers every query. For this is , so replacing by an independent uniform point costs , for adaptive queries on arbitrary digests. In that hybrid two statistical facts suffice.
is close to uniform. The value corresponds to an interval of abscissas of length . The character-sum estimate in the proof of Proposition 8.2 applies to every interval, so the number of points in the -th bucket differs from by at most with , and the statistical distance of from uniform is at most .
is close to uniform given and . Condition on . Then and are fixed, is uniform on points and is a bijection, so is uniform on points. An abscissa has at most two preimages, so the collision probability of is at most , and on average over at most . For a uniform multiplier the family is universal, and the average-case leftover hash lemma [21] bounds the distance of from uniform by . The actual multiplier is independent of and takes each value with probability at most , which is at most times the uniform probability; the bound becomes .
Hence is within of for independent uniform keys, and two PRF steps, on the disjoint domains and its complement, turn the oracle into a random function.
(2) The raw scalar of the first signature is with , so
Everything on the left is public once the signature is seen, since . Low- normalization may replace by and by , which has the same abscissa. One signature therefore yields , the key of every non-anchor nonce. The adversary computes , reproducing retries because the validity of a candidate is publicly testable from , and obtains , testing both signs against . The attack fails only if the first anchor candidate is rejected, that is if or ; both events are publicly testable from and , so their probability is bounded by part (1). □
Remark 5.10 (scope of Theorem 5.9). The decisional square Diffie–Hellman assumption [20] is at least as strong as DDH, since a DDH oracle decides it, and it holds in the generic group model. It enters because the reduction must evaluate the oracle from ; Theorem 5.13 replaces it by ordinary DDH at a price listed in Table 3. Compare of § 4: there the PRF key is a function of alone, so AI-PRF fails; here the key depends in addition on the point , which is hidden behind and which one signature reveals. With the instance has a exhaustive-search ceiling on its AI-PRF security (search for from ); the separation is asymptotic, with , while the key recovery is concrete. We ran it on 16 secp256k1 keys with the messages 0, 1 and a forgery on 2: an independent ECDSA verifier accepted all 16 forgeries, covering the four combinations of low- sign changes, and the oracle computed from alone agreed with the signer on every tested key. [T][S]
Theorem 5.11 (ordering bit: hashed messages). Let be a PRF with outputs in and a key independent of , and fix three public messages with distinct digests ; for SHA-256 the one-byte messages 0, 1, 2 qualify. Let , , , and
Define ; let be or , whichever makes equivalent to , with ties in broken by the scalar and the pair left as if or ; and for every other . On secp256k1:
for every distinguisher , making any number of adaptive queries,
where is the advantage over of in predicting from for uniform ; a predictor with advantage yields a DLP solver running in time ;
the distinguisher that requests signatures on and outputs 1 iff has , in the hashed-message game and against a signer that normalizes to low .
[T]
Proof. (1) Replace by a random function; the PRF distinguisher samples itself. The view of is now determined by , , the unordered pair , the bit and independent uniform values. If is replaced by an independent fair bit, the pair is exactly uniform, because arranging two independent uniform draws in an order chosen by a fair coin restores their joint distribution. One bit is involved, so a distinguisher yields a predictor
of from with half the advantage, and no hybrid over a shared secret is needed (compare Theorem 5.4).
Given a challenge with uniform , sample uniformly with and set . For fixed the map is an affine bijection of , so is distributed as in the game up to the event , and exactly; fixing the digest in advance is what makes this embedding possible. A predictor of from therefore predicts from .
Finally, on secp256k1, and . For a uniform point put ; then . Applying the predictor to for chosen gives an oracle for that is correct with probability over uniform , and Lemma 5.2 with recovers .
(2) and normalization does not change , so the test is unaffected by it. In the real game the relation holds by construction unless a candidate is rejected, probability . In the ideal game the nonces at and are independent, uniform, and independent of the first signature, so is a fair coin up to ties, which have probability at most . □
Remark 5.12 (A* is not necessary). Det-ECDSA with is as unforgeable as Rand-ECDSA, although it violates A*. After the PRF step, a forger against Rand-ECDSA simulates the signer by resampling, as in Theorem 8.1: whenever a signature on one of is requested, it draws fresh signatures on that message until the relation is consistent with those already issued (when is known and is asked before , it keeps the smaller or larger of two draws). The expected number of extra queries is constant and all of them are on messages the adversary asked for, so its forgery stays fresh. Theorems 5.7 and 5.9, in contrast, destroy the scheme. [T]
Trading the assumption against setup, secrets and queries. Theorem 5.9 uses the square because the hidden point must be computable from and from nothing else. Each of the three variants below gives up one feature of that theorem and weakens the assumption in return. Write with , and if , otherwise.
Theorem 5.13 (variants of the hidden seed). With the notation of Theorem 5.9, on secp256k1, each nonce function below satisfies AI-PRF against any number of adaptive queries on arbitrary digests, and its key is recovered from signatures on ordinary hashed messages, also against a signer that normalizes to low .
(a) A public point; DDH; two signatures. Let be a uniform non-identity point, sampled independently of and published. Put , , , and ; the nonce is at and elsewhere. With the probability taken also over ,
and , so the signatures on and on one further message reveal as in Theorem 5.9.
(b) No setup, one key; DDH and an AI-PRF; about signatures. Let be a nonce function with outputs in satisfying AI-PRF at . From outputs of at reserved inputs derive scalars and , coin bits (the parities of fresh outputs) and further scalars. Put and . Fix public carrier messages with distinct digests, different from , arranged in blocks of pairs. Arrange the coins in words of bits and replace the first word that is the abscissa of a curve point by . The nonce is at ; on the -th pair of block it is the two scalars reserved for that pair, in increasing order of if bit of word is and in decreasing order otherwise; and at every other digest, the reserved inputs included. Then
An adversary reads from the order of the values on the carrier messages, block by block up to the first valid word, and continues as in (a) with . It asks for signatures in expectation, where , and for at most .
(c) Two secrets; an AI-PRF alone; two signatures. Let the signer hold, besides , an independent uniform , and let satisfy AI-PRF at . Put ; the nonce is at and elsewhere (with a fixed fallback if or $s = 0). Then , and the first signature reveals , the key of every later nonce.
[T]
Proof. (a) The oracle is a function of the three points , and ordinary DDH [19] replaces by a uniform point independent of and ; this is where the independent point removes the square. Given and the map is an affine bijection, because , and the statistical argument of Theorem 5.9 applies unchanged. For a valid anchor, , so , and its abscissa is unaffected by the sign of . The bound is an average over : for a point whose discrete logarithm the adversary knows, and the function is not an AI-PRF.
(b) First replace by a random function. The reduction to the AI-PRF security of learns , , the coins and the reserved scalars from its oracle and computes from , so it answers every query without . Next, with uniform, and apart from this point is used only through ; a DDH challenge therefore replaces by a uniform . The hidden point is then uniform and independent of , its bucket is within of uniform, and a PRF step makes all outputs outside and the carriers random. Finally, every abscissa is that of exactly two points, so is uniform on the set of valid words, which is the conditional distribution of the word it replaces given its position and all other words: the replacement preserves the joint distribution of the words, the no-valid-word case included. The bits are exactly fair, since is even, and independent of the reserved scalars, and ordering two independent uniform scalars by a fair bit restores their joint distribution, as in the proof of Theorem 5.11. For the attack, the bit of a pair is for its two signatures; either point with the recovered abscissa serves as , because depends on the abscissa only. A valid word fails to appear with probability , and ties or rejected candidates on the carriers have probability .
(c) Given an AI-PRF challenge for , sample and present , as in the proof of Theorem 5.11: is uniform up to and exactly. Answer with and every other digest with . This is the construction if and a random function if is one. The embedding uses the independence of from ; with the key would be related to , and that step is not proved. □
Remark 5.14 (what remains). A pseudorandom function exists if DDH is hard, so (a) rests on DDH alone. We checked the variants on secp256k1 with HMAC-SHA-256 as a functional stand-in for and : 16 two-signature key recoveries for (a) and 16 for (c), covering the four combinations of low- sign changes, and 10 for (b), which needed 514, 1026 or 2050 signatures; every forgery on a fresh message was accepted by an independent verifier. Such runs test the constructions and say nothing about HMAC. No row of Table 3 achieves everything at once: two hashed-message signatures, the original parameters, as the only secret, and no assumption beyond DLP or the existence of an AI-PRF. [T][S]
Summary. and AI-PRF are incomparable. AI-PRF is not sufficient: under the AI-PRF function two chosen-digest signatures reveal the key, and under , given DSDH, so do signatures on two ordinary hashed messages; Table 3 lists the variants under DDH. It is not necessary either, if one-bit HNP is hard (§ 5.1). is sufficient (Theorem 3.1) and not necessary (Remark 5.12). All of these separations concern constructed nonce functions; whether HMAC_DRBG satisfies is untouched by them.
What is provable
Theorem 6.1 (ideal compression function). Model the SHA-256 compression function as a random oracle . For every distinguisher for that makes signing queries and queries to there is an algorithm , running in time group operations, with
where is the probability that computes from given a Rand-ECDSA signing oracle . Moreover , and if for a programmable random oracle , can be replaced by . [T]
Proof. Without loss of generality never repeats , since both oracles in Assumption 2.2 are functions of ; rejections in step H.3 are handled identically in all games. Each signing query costs at most 15 compression evaluations plus block 1 of step d, which is shared. Let Ask be the event that queries at an input whose last 31 bytes equal (§ 4.1). Game 0 is the real game; Game 1 aborts on Ask. Conditioned on Ask, block 1 of steps d and f is evaluated at points never queries, so the chaining values they produce are uniform and hidden, and every later evaluation is at a fresh point unless an internal collision occurs or queries a hidden chaining value; this has probability at most . In Game 2 the nonces are therefore independent and uniform, which is the oracle. The games are identical until Ask or a collision, so it remains to bound in Game 2. There receives and the signing oracle, answers signing queries with it and -queries by lazy sampling, and keeps the table . For every -query with tail it checks whether , at the cost of one scalar multiplication, and on a hit outputs . No query index is guessed, so there is no factor . runs and forges with the recovered . If is programmable, the simulation (3) answers signing queries without .
Remark 6.2. The distinguisher in Assumption 2.2 chooses itself. Without a programmable message hash, a DLP reduction cannot answer its signing queries (Proposition 3.2), so the ideal-compression-function argument yields from DLP in the presence of a signing oracle, not from plain DLP. Combined with Theorem 3.1, up to the running-time overhead of .
Theorem 6.3 (independent nonce key). For -ECDSA with and independent of (or ),
in the standard model. [T]
Proof. The PRF distinguisher knows (it is not the PRF key) and simulates signatures with the nonces returned by its oracle.
This is precisely the construction that RFC 6979 §3.6 describes as “additional secret data . . . may help in formally proving the security”. EdDSA [2] obtains it by splitting . BIP-340 [3] does not: , still needs an -type assumption, discharged in the ROM. Table 4 summarizes.
| Scheme | Assumption | Model | Status |
| , RFC 6979 | standard | open; no attack; falsifiable | |
| same | DLP with a Rand-ECDSA signing oracle; plain DLP if programmable | ideal compression function | proved, no factor |
| , RFC 6979 §3.6 | for any ; nothing extra if uniform and secret | ROM | as above |
| BIP-340 Schnorr | -analogue for tagged SHA-256 | ROM | proved in ROM |
| , independent | PRF security of | standard | proved |
| EdDSA prefix | PRF security of with prefix as key | standard (ROM in [30]) | proved in ROM |
| — | standard | PRF, but key revealed by one signature | |
| RFC 6979 over (Section 4.1) | — | standard; has (A1), (A2), () given CR | PRF in , key revealed by one signature |
| , planted collision (Theorem 5.7) | — | standard | AI-PRF, key revealed by two chosen-digest signatures |
| , hidden seed (Theorem 5.9) | — | standard | AI-PRF under DSDH + PRF; key revealed by signatures on two hashed messages |
| Variants of (Theorem 5.13) | — | standard | AI-PRF under DDH with a public point, or DDH and an AI-PRF, or an AI-PRF and a second secret; key revealed through hashed messages |
| , ordering bit (Theorem 5.11) | — | standard | AI-PRF under PRF + DLP; fails with advantage 1/2; unforgeable |
Table 4. Assumptions beyond the security of Rand-ECDSA.
Curve dependence of the standard part
itself is curve-independent. What depends on the curve is the standard part of a proof that HMAC_DRBG is a PRF in . In step d of RFC 6979 §3.2 the HMAC key is the public , and enters the message: bytes 0–30 fill the tail of block 1 and byte 31 opens block 2 (§ 4.1). Bellare’s PRF theorem for HMAC [5], which assumes a uniform secret key, therefore does not apply to step d. What step d needs is property (A2′): is pseudorandom. Once is pseudorandom, Bellare’s theorem applies to in the later steps. For uniform on , the secret tail is at statistical distance from uniform on .
The same number governs every place in the secp256k1 stack where a 256-bit value is reduced modulo without rejection. For uniform on and , the statistical distance from uniform, the Fourier coefficient relevant to Bleichenbacher’s attack, and all equal to three digits [T]. A data threshold of order signatures makes the bias irrelevant in practice; transplanted verbatim to P-256 the same operation gives (threshold ) and on brainpoolP256r1 (lattice attacks with hundreds of signatures). RFC 9591 (FROST) requires to skip the range check; secp256k1 misses this criterion by 0.35 bit, which changes nothing in practice. [T]
Deployed implementations
We reviewed the source of 31 secp256k1 implementations (18 libraries, 7 wallets and nodes, 6 hardware wallets) at their default branches on 2026-10-18, and libsecp256k1 at commit 04b91ce (2026-10-19). Line numbers refer to those snapshots. [S]
Nonce defaults
28 of 31 implementations (90%) sign ECDSA deterministically without additional entropy; none of the 18 libraries hedges by default although 9 expose an API for it. The exceptions are python-ecdsa (sign() draws a uniform ), LDK (hedges its own commitment and sweep transactions) and BitBox02 (anti-klepto with host entropy). For BIP-340, 15 of 26 implementations sign with zero auxiliary randomness; Bitcoin Core’s source reads “Use uint256{} as aux_rnd for now”. The RFC 6979 §3.6 construction with an independent nonce key, which would discharge by Theorem 6.3, is used nowhere in the sample. [S]
Among general-purpose libraries the default differs: OpenSSL 3.x hedges (ossl_bn_gen_dsa_nonce_fixed_top, SHA-512 over priv || dgst || random; RFC 6979 only with nonce_type=1); wolfSSL, Crypto+++, libgcrypt, Botan (current head), Bouncy Castle’s stock ECDSA signer and python-ecdsa draw random nonces, with RFC 6979 as an opt-in; fastecdsa is deterministic by default; MIRACL Core has no RFC 6979 at all. None of these produces a biased nonce out of the box: the random paths use either rejection sampling or at least 64 extra bits before reduction. [S]
Compliance: bits2octets
RFC 6979 feeds bits2octets() = int2octets(bits2int() mod ) to the DRBG. libsecp256k1 reduced the message only from version 0.2.0 (2022-12-12); the changelog reads “now reduces the message hash modulo the group order to match the specification”. Ports made earlier retain the raw hash: NBitcoin (msg32.CopyTo(keydata)), dcrd (copy(keyBuf[offset:], hash)) and btcec v2, which delegates to dcrd; through them LND, btcd and go-ethereum in its non-cgo build. go-ethereum’s cgo build uses a vendored libsecp256k1 that reduces, so the two builds of the same program produce different signatures when . On secp256k1 with SHA-256 the discrepancy is observable only when , probability , and it has no security consequence: is public and is stated for any injective encoding of . It is a compatibility bug. [S][T]
elliptic and Bouncy Castle truncate to bits before a single subtraction of ; since the truncated value is below , one subtraction is exactly bits2octets for every hash length and every curve. The Ledger SDK’s open implementation (lib_cxng/src/cx_rng_rfc6979.c) has two -probability deviations: it leaves bits2int() unreduced when it equals exactly, and it does not reject the candidate . [S][T]
Retry and grinding
All implementations with an advance the DRBG on rejection as in step H.3. Trezor and the Ledger SDK apply the update eagerly after every output, libsecp256k1 lazily at the start of the next generate; the output sequences coincide. [S]
Bitcoin Core (default since 0.17), libwally (EC_FLAG_GRIND_R, used by Core Lightning), rustsecp256k1 (sign_ecdsa_low_r, used by BDK), Jade and Coldcard grind for a low : they pass a counter as the §3.6 additional data (no data for the first attempt, then the 32-byte little-endian counter) and keep the first signature whose fits in 32 DER bytes. This selects with for the public predicate .
Theorem 8.1 (grinding). Let be any public predicate on points with . For every forger against grinding Det-ECDSA there are and with
where is for on the extended input domain and makes signing queries in expectation. [T]
Proof. By the candidates are independent and uniform, so the selected nonce is uniform on . simulates this signer with the Rand oracle: on query it requests signatures on until one satisfies , returns it, and discards the rest. The distribution is identical (first success in a sequence of independent uniform nonces). Every extra query of is on a message queried, so ’s forgery is fresh for . The number of attempts is geometric with parameter ; for low , . The attempt count , observable through timing, adds nothing: reproduces its distribution. □
is the assumption already required by the rejection loop, which also selects a non-first output. Under it the selected nonce is uniform on the low- set, whose Fourier coefficients—the bias a Bleichenbacher-type attack would use—can be bounded without any model.
Proposition 8.2 (the low- set). Let , , and , the set selected by grinding. On secp256k1, with its standard generator,
and the same holds for with and . Both sets are symmetric under , so all coefficients are real. [T][L]
Proof. Expand the indicator of in additive characters, . Then , and for gives . The group is cyclic of prime order , so its characters are , and the function has degree 2 with a single pole, at infinity. The bound of Kohel and Shparlinski [22] for functions whose polar divisor is supported at one point gives, for every and every ,
Put . The term contributes for and for , so
and . For the set of abscissas is , since : two intervals, hence the error , around the density . □
An attack driven by this bias would need more than signatures. The bound is unconditional and holds for the actual curve and generator; it is within a factor of about of the typical of a random subset of density , which is what the bijective random-oracle model of [12] would predict, and the difference is the logarithmic loss of the completion argument. On a toy prime-order curve with the largest coefficient we measured is before normalization, against the bound . [T] The cost of grinding is an extra loop in the signer (a fault-injection surface) and twice the evaluations.
Testability
The branch is unreachable with natural inputs. libsecp256k1 tests it with nonce_function_test_retry (tests.c:6721–6744), which returns 0, , , and before a valid candidate and checks that the result equals the untampered RFC 6979 output. The branch is tested by no implementation we examined; Appendix B gives vectors that distinguish the conformant and raw-hash variants. Deterministic and hedged signatures are indistinguishable on chain, so the deployed share of each cannot be measured. [S]
Nonce bias in context
A single error-free leaked most-significant bit of on a 256-bit curve has not been attacked. Aranha et al. [23] broke a one-bit bias on a 160-bit curve with signatures and estimated signatures, time, memory for 256 bits by the scaling . LadderLeak [24] broke one-bit leakage on P-192 with about signatures and left P-256 with one-bit leakage open; its P-256 estimate ( signatures) is for two-bit leakage. Lattice methods reach one-bit leakage on 160-bit curves [26] and two-bit leakage on 256-bit curves with 146 signatures [25].
Our model of the sort-and-difference/FFT attack (five reduction rounds, 24-bit FFT) gives signatures for one error-free bit on 256 bits. A toy calibration on curves for reproduces the model within 1.3 bits (mean absolute gap 0.3 bit), and calibration against the LadderLeak P-192 experiment gives –. The honest envelope is –; the figure is the published scaling. [O] These are to be contrasted with for the naive-reduction bias of § 7: the two regimes differ by 127 bits in and are not continuations of each other.
GLV decomposition in the signing path (noble-secp256k1 1.7.1, dcrd under the tinygo tag, k256 without precomputed-tables, elliptic’s fallback) decomposes a uniform into and leaves the distribution of unchanged; the dangerous pattern is recomposition from short random halves, which no reviewed implementation does, and which on secp256k1 () yields a short-vector bias of 0.112 rather than the GLS value (exact computation; Monte Carlo 0.113). The real GLV-specific risk is the decomposition side channel of [23], a lattice attack with tens of signatures. [S][T]
Conclusion and open problems
The security of RFC 6979 on secp256k1 is equivalent, up to the security of randomized ECDSA, to the assumption on HMAC_DRBG at known public key. does not follow from the PRF security of HMAC and the hardness of DLP, nor, given a collision-resistance premise, from the PRF and dual-PRF properties of the SHA-256 compression function. It is not implied by auxiliary-input PRF security either: in the standard model there are nonce functions with that property under which two signatures reveal the key—on chosen digests if any such function exists, on ordinary hashed messages under decisional square Diffie–Hellman, or under DDH with one public random point—or under which three signatures on fixed messages distinguish the transcript of a scheme that stays unforgeable. follows, with an ideal compression function, from DLP in the presence of a randomized-ECDSA signing oracle; for HMAC_DRBG itself it is violated by no known attack, and it is falsifiable. It is probably the most widely deployed unproven assumption in ECDSA practice. Separating the nonce key from the signing key, as RFC 6979 §3.6 and EdDSA do, makes it unnecessary, but is incompatible with existing keys and is used by none of the 31 implementations audited.
Open: a standard-model proof or refutation of for HMAC_DRBG; removing the collision-resistance premise from Theorem 4.8; a two-signature key-recovery separation through ordinary message hashing with the original parameters and as the only secret, from DLP or from the bare existence of an AI-PRF (Table 3 lists what each relaxation costs); closing the factor between the proved and the heuristic Fourier bound for the low- set; and a measured, rather than modelled, cost for one-bit nonce leakage on a 256-bit curve.
Lemma 5.2: details
Write for the residue of in , an odd prime. Let , , , . Fix random and query at for , . Then
Enumerate , , an approximation with , an approximation with , and an initial approximation with ; in total branches, and the query set does not depend on .
In the correct branch maintain . For and one has , hence whenever , and then, being odd,
whenever answers correctly. The event “ correct and ” depends only on , has probability , and the indicators over are pairwise independent. because are pairwise independent and uniform ( prime, ). Chebyshev bounds the majority-vote error at step by ; a union bound over steps gives success probability . With the bit known, , so preserves the invariant and halves the error; after steps the error is below and (the ceiling, since the invariant is one-sided), whence , verified against .
Test vectors for the branch
secp256k1, SHA-256, HMAC_DRBG as in RFC 6979 §3.2; the implementation used to produce these values reproduces the RFC’s own P-256/SHA-256 vector for the message “sample” ( A6E3C57D . . . 8AAD60). “RFC” seeds the DRBG with int2octets() bits2octets(); “raw” seeds it with unreduced (libsecp256k1 before 0.2.0, NBitcoin, dcrd, btcec v2).
, ():
9a409dab05968059da3efb323dc67c96f234571b965fd39810ca0643fbb795ac
daf2c4e18d51a5918522bc9ab5856ed4682208ed35315c9365b86e90dae8e3e3
, ():
71139aac71b52f7d5961915af1b30f94baf35e39b0043c33d41a57d476a8905c
1a3bf84f9a0fd1fff4655ba0ec976b542621fd87b88c3ca6770d4183cbc0e741
Expected behaviour: libsecp256k1 , secp256k1-zkp, elliptic, Bouncy Castle, Trezor, the Ledger SDK, OpenSSL, libgcrypt and fastecdsa return ; NBitcoin, dcrd, btcec v2, LND and go-ethereum (non-cgo) return . Signatures must verify in both cases, since the signature equation uses .
Declaration of Generative AI Use
During the preparation of this work, the authors used Claude Fable 5.2 and ChatGPT Astra to prove mathematical correctness, improve readability, check grammar, and refine phrasing. After using this tool, the authors manually reviewed and edited all text and take full responsibility for the content of the publication.
References
| Curve | Distance | Consequence |
| secp256k1 | () applies with loss | |
| P-256 | () applies with loss | |
| brainpoolP256r1 | extra assumption: () for keys from a density-0.664 subset |
Table 5. Distance of the secret tail of block 1 from uniform. [T]
References
- [1]T. Pornin. Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). RFC 6979, 2013. https://datatracker.ietf.org/doc/html/rfc6979DOI
- [2]S. Josefsson, I. Liusvaara. Edwards-Curve Digital Signature Algorithm (EdDSA). RFC 8032, 2017.DOI
- [3]P. Wuille, J. Nick, T. Ruffing. Schnorr Signatures for secp256k1. BIP-340. https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
- [4]M. Naor. On Cryptographic Assumptions and Challenges. CRYPTO 2003.
- [5]M. Bellare. New Proofs for NMAC and HMAC: Security without Collision-Resistance. CRYPTO 2006; ePrint 2006/043.
- [6]M. Backendal, M. Bellare, F. Günther, M. Scarlata. When Messages are Keys: Is HMAC a dual-PRF? CRYPTO 2023; ePrint 2023/861.DOI
- [7]V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. EUROCRYPT 1997.DOI
- [9]P.-A. Fouque, D. Pointcheval, J. Stern, S. Zimmer. Hardness of Distinguishing the MSB or LSB of Secret Keys in Diffie–Hellman Schemes. ICALP 2006.DOI
- [10]C. Chevalier, P.-A. Fouque, D. Pointcheval, S. Zimmer. Optimal Randomness Extraction from a Diffie–Hellman Element. EUROCRYPT 2009, LNCS 5479, pp. 572–589.DOI
- [11]R. Impagliazzo, L. Levin, M. Luby. Pseudo-random Generation from One-way Functions. STOC 1989.
- [12]M. Fersch, E. Kiltz, B. Poettering. On the Provable Security of (EC)DSA Signatures. CCS 2016.DOI
- [15]W. Alexi, B. Chor, O. Goldreich, C.-P. Schnorr. RSA and Rabin Functions: Certain Parts are as Hard as the Whole. SIAM J. Comput. 17(2), 1988.
- [16]R. Fischlin, C.-P. Schnorr. Stronger Security Proofs for RSA and Rabin Bits. J. Cryptology 13, 2000.
- [17]J. Håstad, M. Näslund. The Security of all RSA and Discrete Log Bits. J. ACM 51(2), 2004.
- [18]D. Boneh, R. Venkatesan. Hardness of Computing the Most Significant Bits of Secret Keys in Diffie–Hellman and Related Schemes. CRYPTO 1996.
- [19]D. Boneh. The Decision Diffie–Hellman Problem. ANTS-III, LNCS 1423, pp. 48–63, 1998.
- [20]F. Bao, R. H. Deng, H. Zhu. Variations of Diffie–Hellman Problem. ICICS 2003, LNCS 2836, pp. 301–312.DOI
- [21]Y. Dodis, R. Ostrovsky, L. Reyzin, A. Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM J. Comput. 38(1), 2008.
- [22]D. R. Kohel, I. E. Shparlinski. On Exponential Sums and Group Generators for Elliptic Curves over Finite Fields. ANTS-IV, LNCS 1838, pp. 395–404, 2000.
- [23]D. F. Aranha, P.-A. Fouque, B. Gérard, J.-G. Kammerer, M. Tibouchi, J.-C. Zapalowicz. GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures with Single-Bit Nonce Bias. ASIACRYPT 2014, LNCS 8873, pp. 262–281.
- [24]D. F. Aranha, F. R. Novaes, A. Takahashi, M. Tibouchi, Y. Yarom. LadderLeak: Breaking ECDSA with Less than One Bit of Nonce Leakage. CCS 2020; ePrint 2020/615.
- [25]L. Xu, Z. Dai, B. Wu, D. Lin. Improved Attacks on (EC)DSA with Nonce Leakage by Lattice Sieving with Predicate. TCHES 2023(2).
- [26]J. Gao, Y. Wang, L. Hu, J. He. Lattice sieving with predicate for one-bit nonce leakage. ASIACRYPT 2024; ePrint 2024/296.
- [30]J. Brendel, C. Cremers, D. Jackson, M. Zhao. The Provable Security of Ed25519: Theory and Practice. IEEE S&P 2021.