Generating the ECDSA nonce k samples a random number r...
Moderate severity
Unreviewed
Published
Aug 27, 2024
to the GitHub Advisory Database
•
Updated Aug 27, 2024
Description
Published by the National Vulnerability Database
Aug 27, 2024
Published to the GitHub Advisory Database
Aug 27, 2024
Last updated
Aug 27, 2024
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.
References