5 ms·

Could you use a similar idea to go after bitcoin keys? If so, you may not be able to crack any particular key, but you could steal the bitcoins from the ones yo

Could you use a similar idea to go after bitcoin keys? If so, you may not be able to crack any particular key, but you could steal the bitcoins from the ones you did crack.

sowbug 8y ago
With a tiny number of exceptions, Bitcoin private keys are just random sequences of 256 bits. They don't involve primality. So unless a shared CRNG is truly awful, there shouldn't be any reason why keys would cluster around certain values.
- tptacek 8y ago
  Which is basically the thesis of the underlying "Ron Was Wrong Whit Was Right" paper --- that discrete log systems are safer than RSA. Since then, there's been more work done on the pitfalls of prime generation, perhaps most notably the "Prime And Prejudice" paper, which is really excellent and more interesting technically than this article: https://eprint.iacr.org/2018/749.pdf https://eprint.iacr.org/2018/749.pdf New systems should generally avoid RSA, for this reason among several others.
  - pbsd 8y ago
    Isn't the point of "Prime and Prejudice" that primality tests that are perfectly adequate for RSA key generation are inadequate to verify the primality of adversarial inputs, in protocols like negotiated DHE or whatnot?
    - tptacek 8y ago
      Dammit. I just wanted a cool link to Prime and Prejudice! You're right, of course.
  - AlexCoventry 8y ago
    > generally avoid RSA, for this reason among several others. What are the others?
schoen 8y ago
As sowbug and tptacek mention, there are no common-factor attacks against Bitcoin keys. However, that doesn't mean that the PRNGs used in cryptocurrency implementations aren't a concern. The most famous incident was probably this https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-April/015873.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018... (you can find subsequent journalism about the effects of this if you're interested). There have also been other cryptocurrency PRNG attacks that weren't as high-profile as this issue.
- tptacek 8y ago
  Java SecureRandom: a userland CSPRNG!
  - pvg 8y ago
    This is JS. The (current-ish) Java ones use the OS-provided facility.
- schoen 8y ago
  I wish I had remembered the "Biased Nonce Sense" paper (which I heard about last week but didn't read!), which someone else mentions downthread at https://news.ycombinator.com/item?id=18917385 https://news.ycombinator.com/item?id=18917385 https://eprint.iacr.org/2019/023.pdf https://eprint.iacr.org/2019/023.pdf (This is a nonce reuse issue rather than a common-factor vulnerability, but one reason for nonce reuse can also be CSPRNG seeding problems.)
anoncrypto 8y ago
See: https://eprint.iacr.org/2019/023.pdf https://eprint.iacr.org/2019/023.pdf

Could you use a similar idea to go after bitcoin keys? If so, you may not be able to crack any particular key, but you could steal the bitcoins from the ones you did crack.

sowbug 8y ago

With a tiny number of exceptions, Bitcoin private keys are just random sequences of 256 bits. They don't involve primality. So unless a shared CRNG is truly awful, there shouldn't be any reason why keys would cluster around certain values.

tptacek 8y ago
Which is basically the thesis of the underlying "Ron Was Wrong Whit Was Right" paper --- that discrete log systems are safer than RSA. Since then, there's been more work done on the pitfalls of prime generation, perhaps most notably the "Prime And Prejudice" paper, which is really excellent and more interesting technically than this article: https://eprint.iacr.org/2018/749.pdf https://eprint.iacr.org/2018/749.pdf New systems should generally avoid RSA, for this reason among several others.
- pbsd 8y ago
  Isn't the point of "Prime and Prejudice" that primality tests that are perfectly adequate for RSA key generation are inadequate to verify the primality of adversarial inputs, in protocols like negotiated DHE or whatnot?
  - tptacek 8y ago
    Dammit. I just wanted a cool link to Prime and Prejudice! You're right, of course.
- AlexCoventry 8y ago
  > generally avoid RSA, for this reason among several others. What are the others?

schoen 8y ago

As sowbug and tptacek mention, there are no common-factor attacks against Bitcoin keys. However, that doesn't mean that the PRNGs used in cryptocurrency implementations aren't a concern. The most famous incident was probably this https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-April/015873.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018... (you can find subsequent journalism about the effects of this if you're interested). There have also been other cryptocurrency PRNG attacks that weren't as high-profile as this issue.

tptacek 8y ago
Java SecureRandom: a userland CSPRNG!
- pvg 8y ago
  This is JS. The (current-ish) Java ones use the OS-provided facility.
schoen 8y ago
I wish I had remembered the "Biased Nonce Sense" paper (which I heard about last week but didn't read!), which someone else mentions downthread at https://news.ycombinator.com/item?id=18917385 https://news.ycombinator.com/item?id=18917385 https://eprint.iacr.org/2019/023.pdf https://eprint.iacr.org/2019/023.pdf (This is a nonce reuse issue rather than a common-factor vulnerability, but one reason for nonce reuse can also be CSPRNG seeding problems.)

anoncrypto 8y ago

See: https://eprint.iacr.org/2019/023.pdf https://eprint.iacr.org/2019/023.pdf