IACR News item: 03 March 2023
Marco Macchetti
ePrint Report
We describe a new related nonce attack able to extract the
original signing key from a small collection of ECDSA signatures generated with weak PRNGs. Under suitable conditions on the modulo order
of the PRNG, we are able to attack linear, quadratic, cubic as well as
arbitrary degree recurrence relations (with unknown coefficients) with
few signatures and in negligible time. We also show that for any collection of randomly generated ECDSA nonces, there is one more nonce that
can be added following the implicit recurrence relation, and that would
allow retrieval of the private key; we exploit this fact to present a novel
rogue nonce attack against ECDSA. Up to our knowledge, this is the
first known attack exploiting generic and unknown high-degree algebraic
relations between nonces that do not require assumptions on the value
of single bits or bit sequences (e.g. prefixes and suffixes).
Additional news items may be found on the IACR news page.