Using computer random number generators to produce keys, it is secure?

Question

Does generating an encryption key using the random number generator on one's computer present a security risk? If so how might that risk be mitigated, specifically when generating RSA key pairs in .Net?

Answer 1

Using computer random number generators to produce keys, it is secure?

It depends on your threat environment, exposure, and overall system security. Given the difficulty in implementing robust secure systems, and assuming that the thing you are protecting is not of high value (to others), using your own computer to generate random numbers is likely ok. However, if the threat to your system is high, your exposure is great, and or the thing you are protecting is high value, then no, using computer generated random numbers is insecure.

Does generating an encryption key using the random number generator on one's computer present a security risk?

Yes, but it may not be a significant enough risk to do anything about it. See the next part of the answer.

If so how might that risk be mitigated, specifically when generating RSA key pairs in .Net?

In RSA encryption the private key and the public key are mathematically related. Random numbers are needed in order to generate the private-public key pair. If an attacker had the random numbers used to generate the key pair and the public key, they could easily find the private key.

Microsoft's .Net framework provides RNGCryptoServiceProvide for random number generation. All software based random number generators are actually pseudo-random number generators. Meaning that they are not truly random, but they produce output in a way that makes the output appear random.

All software is deterministic. Meaning that for a given set of inputs the output can be determined exactly. This is bad for prng (pseudo-random number generators), because they would produce predictible output. i.e. The output would not even be pseudo-random. To get past this limitation, prng need seed random data to get them started.

By giving the prng function a little random data to start with it can generate lots of pseudo-random numbers. There are many methods to generate random seed data: using the time the function was called, reading a block of uninitialized memory, using the time average time between keyboard presses, the position of your mouse, etc. Generally the data used to generate the random seed it not perfectly random either.

If an attacker knew the algorithm used to produce the random numbers, and the seed data, they may be able to reduce the possible outputs of the prng and used the reduced set out output to easily find your private key.

I do not know what rpng algorithm is used by RNGCryptoServiceProvide, so I can not speak to it's effectiveness.

To mitigate risk due to random number generation, you can use true hardware based random number generators. Hardware based random number generators do not require a seed, becausee instead of an algorithm they use a physical process to generate their data. Certain physical processes have random or near-random characteristics: decay of a radio active particle, therman noise, race conditions in transistors, etc. The output of the hardware based random number generators will be statistically more random then the numbers generated by your computer. Additionally, no value available on your computer is used to generate the output. However, many hardware random number generators are expensive, and slow.

So, would the cost in money and speed be worth the investment?

It depends on what you are protecting, and how sophisticated and determined your attackers may be.

Note: some computer chipsets now include hardware random number generators.

Answer 2

If you are in London you really should have come to dc4420.org monthly meetup's this year! Three talks on random number generators and we are only in June!

One of the talks was from IDQ and anther from a consultant that looks at random number generators for on-line Casino's and Poker sites (guys that really care about randomness). This is what I learnt:

• Once you have a good source of randomness, leave the data alone" the data streams that we tampered with the least had the best randomness performance
• "Don't hash entropy". If it made your entropy any longer we'd call it Viagra, not a hash function

When it comes to random number generators there's no need to look further than the Quantis . It's relatively inexpensive and it's fast and reliable. It's from IDQ, who say it is use by the Geneva government.

Second best is hardware based mechanism. For a bit of fun with a the radioactive source from a smoke detector, a web-cam and some python (for less than £20) check this out: http://www.aperturelabs.com/smoke-rng/

Note: this is fun hack is not using the proven source of randomness being the timing between radiation particles, thus may not be truly random (although probably more so than software). It should be taken as an fun experiment rather than production use.

Assessing the quality of random number generators:

• http://warmcat.com/_wp/2007/11/07/adding-entropy-to-devrandom/
• http://warmcat.com/_wp/2007/11/12/ring-oscillator-rng-performance/
• http://warmcat.com/_wp/2007/11/14/diehard-validation-vs-ring-rng/
• http://warmcat.com/_wp/2007/11/15/fips-140-2-and-ent-validation-vs-ring-rng/
• http://warmcat.com/_wp/2007/11/24/whirlygig-gpld-hwrng/
• http://warmcat.com/_wp/whirlygig-rng/

The worst is software based pseudo random number generators which use quasi sources of "randomness" like CPU current and worse time. Use these only if the asset you are protecting and threats you are facing are ok with e.g. Java Dev random.

Answer 3

For this sort of application (generating fairly small keys), the biggest worry is that the PRNG may not be seeded with enough entropy -- if the input(s) to the PRNG are predictable, so are the outputs. Probably the most famous recent example of this was in the Debian version of OpenSSL (between September 2006 and May 13th, 2008): the only entropy source it used was the process ID of the generating program, so there were only 32,768 possible keys (and some were more likely than others). (Refs: Debian Security Advisory DSA-1571-1 and discussion here.)

This was not an isolated incident. This bibliography lists 4 examples in its 'Serious flaws in PRNGs used in "real world" applications' section (and doesn't appear to have been updated in a decade). Another example: Samy Kamkar showed how to discover enough of the entropy sources for a PHP (before version 5.3.2) session key to make it brute-forceable.

Overall, I think the best approach is to use a random number generator intended for key generation (esp. one that takes care of entropy collection for you), from a developer you trust to have paid attention.

Answer 4

I assume you mean the HW PRNGs available in some chipsets.

In general, you should use the OS's PRNG facility. They try to produce good randomness. I have once seen a talk on the FreeBSD PRNG design, and they integrated the hardware PRNG of the chipset such that it will, in the worst case, add no randomness but also not weaken the system's PRNG. However, I would also appreciate some more resources/confirmation/generalization on this issue.

Note that the TPM also provides a HW PRNG. Google can tell you how to use it. "Analysis of the Linux Random Number Generator" may have some interesting pointers as well.

If you don't trust your PRNG, you can try running some PRNG test suites. However, none of these can tell you if your PRNG is, indeed, random or only pseudo-random.