ECDSA nonce bias caused by truncation
- Published
- Last modified
- Where the record stands: published, rejected by its publisher, or superseded by another id.What do these mean? →
- published
- Whether CISA lists it in its Known Exploited Vulnerabilities catalog: proof that attackers are using it.What do these mean? →
- Not listed in CISA KEV
- Whether working attack code is public (Exploit-DB, Metasploit, Nuclei or GitHub). Public code makes attacks easier.What do these mean? →
- None on Exploit-DB, Metasploit or GitHub
- Exploitation: none
- Automatable: no
- Technical impact: partial
Summary
Generating the ECDSA nonce k samples a random number r and then truncates this randomness with a modular reduction mod n where n is the order of the elliptic curve. Meaning k = r mod n. The division used during the reduction estimates a factor q_e by dividing the upper two digits (a digit having e.g. a size of 8 byte) of r by the upper digit of n and then decrements q_e in a loop until it has the correct size. Observing the number of times q_e is decremented through a control-flow revealing side-channel reveals a bias in the most significant bits of k. Depending on the curve this is either a negligible bias or a significant bias large enough to reconstruct k with lattice reduction methods. For SECP160R1, e.g., we find a bias of 15 bits.
Timeline
- CVE published
- CISA SSVC assessment
Exploitation: none · Automatable: no · Technical impact: partial
- Record last updated
Affected versions
- wolfSSL wolfSSL
through 5.6.4