RNG vs PRNG for bip39 it's relation to Trezor

[baringforge]

I'm working on a bip32 wallet, and am using bip39 to generate a multi-word mnemonic for the bip32 wallet generation. 

The mnemonic is generated using a random number as a seed, which is sha256 hashed and manipulated to arrive at the mnemonic word list.  My question is, does the original random gain a real increased security from using a hardware-based RNG, or is a PRNG sufficient?  The initial Trezor source used a PRNG, but their updated firmware source is using a hardware-based RNG.  If hardware-based RNG is required, how do the PC-based clients using a PRNG, like bitcoind, manage?  I looked through the bitcoind source, and they add entropy to their pool periodically based of a performance counter, but is that the ideal way to do it?  How would one go about proving it's not susceptible to a bias?

I'm really new to crypto, so I'm trying to understand the process by which questions like this are evaluated.  I don't even really know where to start at this point, so guidance is appreciated.

[telepatheic]

Computers use a cryptographically secure pseudo-random number generator such as CryptGenRandom

Bitcoind uses OpenSSL's CSPRNG which is seeded from CryptGenRandom on windows and /dev/random on linux. Bitcoind adds in extra random data from the performance counter to increase security.

[baringforge]

Thanks telepatheic.  Is a CSPRNG considered as secure as, say, and ARM hardware-based RNG that is NIST certified?  On the one hand the CSPRNG is software that can be reviewed, but the hardware-based one is pretty black box, and difficult to evaluate other than through external black-box type testing. 

Also, if I use a CSPRNG seeded with a performance counter, similar to bitcoind, how do you establish "trust" that the product is cryptographically sound?  For example, maybe the performance counter is always read at a certain predictable cadence.  Do folks in the community just review the code, and if no one complains it's good to go?

[cp1]

Also, if I use a CSPRNG seeded with a performance counter, similar to bitcoind, how do you establish "trust" that the product is cryptographically sound?  For example, maybe the performance counter is always read at a certain predictable cadence.  Do folks in the community just review the code, and if no one complains it's good to go?

I wonder if there is some RNG verification software you can run.  But then how do you trust the verification software?  You might need to get a degree in cryptography to understand whether or not your data is sound.  Or you could just trust that there hasn't been a huge vulnerability for the last three years, that works out well

[telepatheic]

Is a CSPRNG considered as secure as, say, and ARM hardware-based RNG that is NIST certified?

Both should be equally secure, they use similar methods at a hardware level. You can evaluate the output using statistical tools to check it is producing random (enough) data.

Do folks in the community just review the code, and if no one complains it's good to go?

Yes, this is why I only use bitcoin at the moment. Most of the altcoins aren't reviewed and built by enough independent trusted people, so it would be easy for a developer to switch the randomness off or insert other malicious code.

If you are really paranoid, you should build the code from source files yourself.

[cwil]

It should be noted that the randomness of a CSPRNG depends on your entropy pool.  TRNG's exist to increase your entropy pool.  If you're planning on building a hardware solution like the Trezor, you will need an entropy source.

[baringforge]

I wonder if there is some RNG verification software you can run.  But then how do you trust the verification software?  You might need to get a degree in cryptography to understand whether or not your data is sound.  Or you could just trust that there hasn't been a huge vulnerability for the last three years, that works out well

The one ARM uses is from NIST ( http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html ).  I've never tried to run it, but it looks interesting.

[gmaxwell]

Private keys must _always_ be derived from attacker unknowable data. That data can pass through a CSPRNG on its way, but from the attacker's perspective it must be 'random'.

Just sticking in a PRNG would instantly cause users to be robbed, since an attacker would just run the same program and get the same results.  On a desktop the OS provides a cryptographically strong PRNG which operates over and an entropy pool and is constantly fed sources of true randomness. This is the primary source of key entropy in Bitcoin core (the actual implementation is under the hood of the library, which is why you did not see the /dev/urandom calls in the bitcoin codebase itself).

Perhaps you should reevaluate if you're prepared to be creating cryptographic software for third parties to use at this time? If you make a mistake here people will lose money but the mistake could be undiscovered for many months. Security failures are usually completely invisible until they aren't.

[baringforge]

Private keys must _always_ be deprived from attacker unknowable data. That data can pass through a CSPRNG on its way, but from the attacker's perspective it must be 'random'.

Just sticking in a PRNG would instantly cause users to be robbed, since an attacker would just run the same program and get the same results.  On a desktop the OS provides a cryptographically strong PRNG which operates over and an entropy pool and is constantly fed sources of true randomness. This is the primary source of key entropy in Bitcoin core (the actual implementation is under the hood of the library, which is why you did not see the /dev/urandom calls in the bitcoin codebase itself).

Perhaps you should reevaluate if you're prepared to be creating cryptographic software for third parties to use at this time? If you make a mistake here people will lose money but the mistake could be undiscovered for many months. Security failures are usually completely invisible until they aren't.

True enough, and security failure is a primary concern, and is why I'm posting here rather than just defaulting to a hardware RNG. What I am trying to establish is a strong rationale and deep understanding for why I should use a hardware RNG, rather than a CSPRNG seeded periodically by a timestamp of 'randomly' occurring events such as IO events.  My current understanding is that the primary value of an established hardware RNG is that there is sufficient available test data and third-party validation to prove it is cryptographically secure.  A homebrew CSPRNG seeded with random IO events may be as good or better (maybe due to some undiscovered bias in the hardware method), but a large amount of additional effort is required to acquire the assurance provided by the hardware validation efforts.

The other interesting point I noticed was the drama with "/dev/random" and Intels' rdrand (using their DRNG).  I've been casually assuming if the reason bitcoin does additional seeding is to guarantee an extra layer of protection against RNG bias.  However, it looked like the perf counter method was prone to manipulation, and it seemed like an attacker could easily override the call to QueryPerformanceCounter, and either return known values or predictable values.  The perf counter is just one source of many, but why doesn't a potential bias there reduce the overall assurance of the system?  Is there a point of diminishing returns when it comes to adding entropy from multiple sources?

[gmaxwell]

but why doesn't a potential bias there reduce the overall assurance of the system?

Because it is mixed into unknown state using a cryptographic function. Even if an attacker completely controls the additional inputs, without knowledge of the interior state and the ability to compromise a cryptographic assumption (e.g. the one-way-ness of SHA1) the system remains secure.

Hardware RNGs are mostly tricky because they can fail in difficult to detect ways. Good designs have several layers of checking and still whiten them using a CSPRNG just in case the entropy is lower than expected. E.g. the no-longer-available entropy key used two hw rngs and checked their individual entropy with an estimator, along with the entropy after debiasing and the entropy of their xors and xor of the debiased values... and then followed it with the FIPS rng test (though I thought their particular placement of the fips test was a bit ill advised).

rather than a CSPRNG seeded periodically by a timestamp of 'randomly' occurring events such as IO events.

Many apparently 'random' IO events are not really random or are less random than you might assume, so great care is required. A good CSPRNG design will substantially preserve any entropy which is provided, and so long as there is enough in total, no matter how much non-random bits dilute it, the output will be strong.

[baringforge]

Thanks gmaxwell, awesome answer.