search

jvdsn / crypto-attacks

Python implementations of cryptographic attacks and utilities.
MIT License
935 stars 121 forks source link

Short Nonces in ECDSA #3

Closed demining closed 2 years ago

demining commented 2 years ago

Hello @jvdsn I saw your work on GitHub and decided to write to you as I have questions.

When creating ECDSA, it happens that some devices generate short Nonce. Approximately 2 ^ 243 - 2 ^ 244

Accordingly, if Nonces is short, then it must contain null at the beginning. That is, the first 3 bits of the Nonce contain a beginning null.

Given the known signature values [R, S, H (e)], can we define and calculate if the Nonce is short?

Is there a way to find out information about the first 3 bits of Nonces?

jvdsn commented 2 years ago

1) If the nonces are not generated uniformly at random in the interval [1, n - 1], then you have a biased nonce attack 2) If the modulus n is k bits, and the nonces are only l bits, with l < k, then the first (k - l) bits will be 0, yes 3) So if your modulus is 247 bits (weird choice of modulus), then the first 3 bits would be 0, yes

demining commented 2 years ago

@jvdsn I'm interested in whether it is possible to determine that a specific signature contains short Nonce using the signature values [R, S, H (e)] for calculations? Is there a script or algorithm for these calculations?

jvdsn commented 2 years ago

In order to know if the nonce is biased, you need to know how it was generated. If you don't know that, like in your case where you only have the signature, then you can't know.