Hacker News Reader

Comment by incompatible | Hacker News Reader

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.

View on HN

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...

(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.

Java SecureRandom: a userland CSPRNG!

This is JS. The (current-ish) Java ones use the OS-provided facility.

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://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.)

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.

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

New systems should generally avoid RSA, for this reason among several others.

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?

Dammit. I just wanted a cool link to Prime and Prejudice!

You're right, of course.

> generally avoid RSA, for this reason among several others.

What are the others?

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

Reply on news.ycombinator.com