Polynonce Attack Exposes Novel ECDSA Vulnerability Threatening Bitcoin and Ethereum Wallets

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.