On March 6, 2023, Kudelski Security published groundbreaking research revealing a novel attack against the Elliptic Curve Digital Signature Algorithm (ECDSA), the cryptographic foundation securing Bitcoin and Ethereum transactions. The attack, dubbed “Polynonce,” represents a significant advancement in the theoretical understanding of how private keys can be extracted from poorly implemented wallet software.
The Threat Landscape
The ECDSA algorithm underpins the security of virtually every major cryptocurrency, including Bitcoin, which was trading at approximately $22,430 at the time of the research, and Ethereum, valued around $1,567. The algorithm relies on the generation of a random nonce — a unique number used exactly once — for each digital signature. If these nonces follow predictable patterns, the private key can be mathematically derived from the signatures alone.
The Polynonce attack takes this concept significantly further than previous nonce-based attacks. While earlier methods like lattice attacks required specific linear relationships between nonces, the Kudelski Security team discovered that polynomial relationships of arbitrary degree can also be exploited. This dramatically expands the attack surface for wallets with flawed random number generators.
The timing of this disclosure is particularly relevant as the cryptocurrency industry continues to grapple with an ongoing wave of wallet exploits and exchange breaches, with losses from hacks exceeding $3.8 billion in 2022 alone according to various industry reports.
Core Principles
The mathematical foundation of the Polynonce attack operates on the principle that ECDSA nonces, when generated by a flawed implementation, may follow a polynomial recurrence relation rather than being truly random. If an attacker can observe multiple signatures from the same private key where the nonces follow this pattern, the private key becomes recoverable.
Specifically, the attack requires a minimum of four signatures generated by the same private key, along with the associated public key and message hash for each signature. The researchers demonstrated that if the nonces obey a recurrence relation of degree D, and the attacker has access to at least D+3 signatures, key recovery becomes computationally feasible.
The attack works by exploiting the ECDSA signature equation to rewrite the polynomial in terms of the private key and the recurrence unknown coefficients. The breakthrough insight was that these unknown coefficients can be eliminated from the polynomial, which always has the signer’s private key among its roots. Finding roots of a polynomial with known coefficients over a finite field is a computationally tractable problem.
Tooling & Setup
The Kudelski Security team validated their attack against real-world datasets from both the Bitcoin and Ethereum networks. While they did not recover any previously unknown private keys — evidence suggested that vulnerable wallets had already been drained using a different exploit — the proof of concept confirmed the attack’s viability.
The researchers released their findings through an academic paper published on the International Association for Cryptologic Research (IACR) ePrint archive, along with open-source proof-of-concept code on GitHub. This responsible disclosure approach allows wallet developers and security auditors to test their implementations for vulnerability to the Polynonce attack before malicious actors can exploit it.
For security practitioners, the attack underscores the critical importance of using cryptographically secure random number generators (CSPRNGs) in all wallet implementations. Hardware wallets, which typically use dedicated secure elements for nonce generation, remain the gold standard for protecting against this class of attacks.
Ongoing Vigilance
The Polynonce discovery highlights an uncomfortable truth about cryptographic security: vulnerabilities can lurk in well-studied algorithms for years before being discovered. ECDSA has been the standard for cryptocurrency signatures since Bitcoin’s inception in 2009, yet novel attack vectors continue to emerge.
The research also raises questions about the long-term security of older Bitcoin transactions. Signatures generated by early wallet software with potentially weak random number generators may be vulnerable to retrospective analysis using this new technique. However, the Bitcoin network’s transition to Schnorr signatures through the Taproot upgrade in November 2021 provides an alternative that is not susceptible to this particular class of nonce attacks.
Users should also consider the broader implications for multisig wallets and hardware security modules (HSMs) used by exchanges and custodial services. Any system that generates ECDSA signatures should be audited against the Polynonce criteria to ensure nonce generation is truly random and free from polynomial relationships.
Final Takeaway
The Polynonce attack represents a meaningful advancement in the cryptanalysis of ECDSA. While it does not pose an immediate threat to well-implemented wallets using modern cryptographic libraries, it serves as a powerful reminder that the security of cryptocurrency systems depends not just on the mathematical soundness of their algorithms, but on the quality of their implementations. Developers, auditors, and users must remain vigilant against both known and emerging attack vectors in the rapidly evolving landscape of digital asset security.
Disclaimer: This article is for informational purposes only and does not constitute financial or investment advice. Always conduct your own research before making any financial decisions.
polynomial relationships between nonces leaking private keys is terrifying. this is why hardware wallets generate randomness securely
Karl V. hardware wallets help but the Polynonce paper showed the vulnerability is in implementation not just RNG quality. even some HSMs had biased nonces
Kudelski finding polynomial nonce bias in 2023 and most wallet devs still havent patched. classic security research that gets ignored until funds disappear
BTC at 22430 when this dropped and the real risk was wallet RNG bugs not price action
hardware wallets with proper TRNGs are fine but the real danger is mobile wallet apps using OS entropy. most people dont even know which randomness source their wallet uses
Kudelski finding polynomial nonce bias means every wallet using OS-level RNG at $22k BTC was theoretically exposed. the scary part is how long this could have been known before publication
nonce_entropy_ three letter agencies absolutely had this catalogued before Kudelski. polynomial relationships in ECDSA nonces is exactly the kind of math NSA hires for
nonce_entropy_ three letter agencies had polynomial nonce bias catalogued years before Kudelski. this is exactly the kind of math the NSA quietly weaponizes
polynomial relationships in nonces is a step beyond lattice attacks. kudelski found something genuinely new here
polynomial nonces is genuinely new research. lattice attacks needed linear bias, this works with much weaker assumptions about the RNG
polynomial bias surviving across multiple degrees means the attacker doesnt need a perfect nonce correlation anymore. this is a much weaker assumption than lattice attacks needed
polynomial bias is way harder to detect than linear. the fact that kudelski found this means someone else probably already knew
nonce_hunter_ if kudelski published it you can bet three letter agencies already knew. polynomial nonce bias is exactly the kind of thing NSA mathematicians would catalog quietly
the NSA angle is real. if Kudelski found this in 2023, intelligence agencies with dedicated math teams probably had it cataloged years before
this only affects wallets with bad RNG implementations right? hardware wallets with proper TRNGs should be fine
^ theoretically yes but you’d be surprised how many software wallets roll their own crypto. always verify the implementation
too many wallets use OS-level randomness instead of dedicated TRNG hardware. software RNG is the weakest link in most implementations
OS-level randomness is a ticking time bomb on mobile wallets especially. most android devices have terrible entropy sources
Katya B. android entropy was genuinely bad pre-2018 on certain devices. old broadcom chips had predictable TRNG output. who knows how many keys generated on those phones are theoretically vulnerable
polynomial relationships between nonces leaking private keys is terrifying. wallet devs cutting corners on RNG is the oldest vuln in crypto
Kudelski finding polynomial nonce bias means every wallet using OS RNG was exposed. scary implications
BTC at $22k when this dropped and everyone was worried about price. the real risk was always in wallet implementation bugs like this
android wallets from pre-2018 devices using broadcom TRNG are a ticking bomb. anyone who generated keys on a 2016 samsung is theoretically exposed to this
polynomial relationships in nonce generation is actually insane. most wallet devs think random means random but Kudelski showed even tiny biases in the RNG lead to full key recovery. if you ran a wallet from 2013-2020 your keys might be at risk
the fact that this works across BOTH bitcoin and ethereum because they share the same curve (secp256k1) makes it way worse. this isnt a one-chain problem