4 ms·

That makes no sense, how can you get the private key from knowing 1 bit of the nonce?

tptacek 5y ago
See, cryptography engineering is sinking in! Here you go: https://toadstyle.org/cryptopals/62.txt https://toadstyle.org/cryptopals/62.txt What's especially great about this is that it's very easy to accidentally have a biased nonce; in most other areas of cryptography, all you care about when generating random parameters is that they be sufficiently (ie, "128 bit security worth") random. But with ECDSA, you need the entire domain of the k value to be random.
- drexlspivey 5y ago
  Ok but for this scheme you need a large amount of signatures from the same biased RNG which makes sense. I thought that the GP was suggesting that you can recover the key from one signature with just a few bits.
  - cbhl 5y ago
    "same biased RNG" largely reduces to "I use the same computer to generate all my signatures"; for example see the Debian RNG bug from 2008 and "large amount of signatures" could be "I sign every email I send to a mailing list" or "I use this key to sign some widely distributed software every two weeks"
  - tptacek 5y ago
    When these bugs first came into fashion, the "bias" of the RNG was an implementation artifact, not some bug in /dev/random: it was the code you used to fill a bignum uniformly in the size of the nonce. So mentally substitute "same biased RNG" for "same implementation, with same keys". Yes, the attacks require many signatures. Like the infamous Bleichenbacher RSA attack, which was originally dubbed "The Million Message Attack", in part as a jab at how impractical they were presumed to be, collecting thousands of signatures is often a very realistic attack; for instance, any system that generates signed messages automatically.
na85 5y ago
I guess like so: https://cryptopals.com/sets/8/challenges/62.txt https://cryptopals.com/sets/8/challenges/62.txt E: Thomas beat me to it

See, cryptography engineering is sinking in! Here you go: https://toadstyle.org/cryptopals/62.txt https://toadstyle.org/cryptopals/62.txt What's especially great about this is that it's very easy to accidentally have a biased nonce; in most other areas of cryptography, all you care about when generating random parameters is that they be sufficiently (ie, "128 bit security worth") random. But with ECDSA, you need the entire domain of the k value to be random.

drexlspivey 5y ago
Ok but for this scheme you need a large amount of signatures from the same biased RNG which makes sense. I thought that the GP was suggesting that you can recover the key from one signature with just a few bits.
- cbhl 5y ago
  "same biased RNG" largely reduces to "I use the same computer to generate all my signatures"; for example see the Debian RNG bug from 2008 and "large amount of signatures" could be "I sign every email I send to a mailing list" or "I use this key to sign some widely distributed software every two weeks"
- tptacek 5y ago
  When these bugs first came into fashion, the "bias" of the RNG was an implementation artifact, not some bug in /dev/random: it was the code you used to fill a bignum uniformly in the size of the nonce. So mentally substitute "same biased RNG" for "same implementation, with same keys". Yes, the attacks require many signatures. Like the infamous Bleichenbacher RSA attack, which was originally dubbed "The Million Message Attack", in part as a jab at how impractical they were presumed to be, collecting thousands of signatures is often a very realistic attack; for instance, any system that generates signed messages automatically.

na85 5y ago

I guess like so: https://cryptopals.com/sets/8/challenges/62.txt https://cryptopals.com/sets/8/challenges/62.txt E: Thomas beat me to it