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

[Russ Allbery]

Ken McCall via cryptography <cryptography at metzdowd.com> writes:

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

There are various ways bad RNGs can hurt (I'm sure other people will add
more), but possibly the easiest one to explain is in key pair generation.

This is not specific to Bitcoin; it applies to any public and private key
pair (SSH, X.509, PGP, whatever).

Generating a key pair involves picking two numbers with certain
mathematical properties.  The exact details of how that's done varies by
the type of public key algorithm, but it involves using an RNG at some
step to make up a new pair of numbers that, other than their required
properties, should be effectively unguessable.  Specifically, even with
possession of the public key or the output from some cryptographic
operation with the private key (such as a signature), it should be
impossible to guess the corresponding private key.

The most obvious attack on any form of public key signature is to repeat
or reverse-engineer this key generation process to figure out someone
else's private key.  The primary defense against that attack is a large
and randomly distributed key space: ideally you have to try every possible
private key to see if it's the right one for a given public key,
signature, or whatever you're attacking, and this takes infeasibly long.

The most obvious way that a bad RNG hurts is that a bad RNG may mean that
the private key is *not* chosen from the full key space.  Instead, due to
properties of the RNG, the key is effectively chosen from a tiny fraction
of the key space.  Now, all the attacker has to do is search that entire
key space for the private key, which because it is so much smaller becomes
computationally feasible to do.

One in possession of someone's private key, in most public-key systems you
are now them and can impersonate them freely, with all the obvious
consequences.

-- 
Russ Allbery (eagle at eyrie.org)             <https://www.eyrie.org/~eagle/>