[Cryptography] How can poor/bad/compromised random number generators manifest themselves in Bitcoin?

[John-Mark Gurney]

Ken McCall via cryptography wrote this message on Mon, Nov 18, 2019 at 22:09 +0000:
> Folks,
> 
> Excuse my ignorance, but I'm trying to understand, from a realistic/practical standpoint, how a "poor" (Bad? Less than optimal?) random number generator can create a problem in the Bitcoin network (blockchain, transactions, nodes, exchanges, wherever.).
> 
> My initial thoughts were that good (true?) random numbers were integral to everything. That everything could be compromised somehow. But when I think it through, how in actuality can a less than optimal number end up creating a problem? I don't understand how the bitcoin network could be compromised by a poor RNG anywhere?
> 
> Here's where I get stonewalled:
> 
> Transactions:
> 
> - A transaction output already has been signed by someone's private key. Even if you could insert your own, that would accomplish nothing but making you the signer on the next transaction.
> - A transaction consists of a UTXO being digitally signed over to an address using ECDSA. The random number (private key) used to generate signature is never exposed, also the recipient address (really a pubic key that's been hashed repeatedly) is also never exposed, so I don't see how knowing that they had a faulty RNG could gain an attacker any benefit?
> 
> Wallets / blocks:
> 
> - The Bitcoin wallet generates the keys internally. So, it would seem the only attack vector would be to know what RNG the wallet was using, and what weakness it possessed. However, even with this knowledge I don't understand how any bad actor could benefit from it? I.e, the transaction's been signed. The block has been confirmed, etc. It's all a done deal.
> 
> In other words, all the random numbers are generated on the fly, as needed, they aren't preconceived in some list or database. Where in the network could bad RNGs be used to wreak havoc, and how? Please keep in mind I'm not a mathematician or cryptographer, just a curious techie.
> 
> In need of enlightenment.

An example of this is the Debian ssh key issue:
https://en.wikipedia.org/wiki/OpenSSL#Predictable_private_keys_(Debian-specific)

They had a buggy RNG that would only generate a possibly 32,768 different
private keys.  This means it would be trivial to generate all the possible
different private keys (there is a list of the private keys for this).

Now this is an overtly bad RNG, and doubtful to be a problem, but even
a weak RNG that can only produce 2^64 different outputs is not good,
as a rainbow table can be generated to be able to lookup a private key
that matches w/ a public key allowing an attacker to easily and quickly
steal another person's bitcoins.

https://en.wikipedia.org/wiki/Rainbow_table

-- 
  John-Mark Gurney				Voice: +1 415 225 5579

     "All that I will do, has been done, All that I have, has not."