AI & ML
Deterministic ECDSA on secp256k1: the RFC 6979 assumption, a counterexample, and the state of deployed implementations
arXiv cs.CR0 views
arXiv:2611.18449v1 Announce Type: new Abstract: RFC 6979 derives the ECDSA nonce as $k = F_x(h)$, with $F_x$ HMAC_DRBG keyed by the signing key x. We isolate the assumption its security rests on, A*: at known public key $Q = xG$, the signing transcript under nonces $F_x()$ 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 $F_x$. A function $F'(x, h) = P_{Ext(xG)}(h)$ 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 $2^{-127.65}$ from uniform on secp256k1, $2^{-32}$ 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 $2^{-116.9}$ unconditionally. We give test vectors for the untested $h >= n$ branch
Source:https://arxiv.org/abs/2611.18449PreviousCANTraj: Recovering Vehicle Trajectories from CAN Signals in Naturalistic DrivingNextVellSSLH: Sound Type-Guided Selective Speculative Load Hardening for LLVM IR
Related posts
evgmrf: An R Package For Gaussian Markov Random Field Extreme Value Models
0arXiv stat.CO
Limitations of nonreversible lifts for subgeometric diffusions
0arXiv stat.CO
Audition Every AI Cut Before You Publish the Episode
0dev.to Productivity
AI Lead Generation: How to Automate Capture, Qualification and Follow-Up
0dev.to Productivity
AI Automation for Small Business: How to Scale Without the Stress
0dev.to Productivity
Four local-first Edge extensions I'm building: one live, three in review
0dev.to Productivity