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?
1Related? Evaluating the entropy gathering in a PRNG– JaccoJun 29, 2011 at 11:52
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.
Very thorough. Good work.– DKGasserJun 29, 2011 at 15:45
How is a pure software solution based on inter-keystroke timings, time of day, process id, current weather, current stock indexes, etc., inferior to a noisy diode? The key is really introducing enough hard-to-predict seed such that pseudo-random effectively becomes truly-random.– FixeeJun 29, 2011 at 22:41
2@Fixee Becase the events are bounded. Key strokes are quantized by the keyboard controller. Transfer protocol often group keystrokes together, erasing the timing data. If time of day is calculated when the user runs the application, then the user's activity patterns limit the range of values. Depending on how you define current weather it is predictable to an extent. Stock indexes are also limited, they rarely change more than some percentage each day. See "Software Generation of Practically Strong Numbers"(citeseerx.ist.psu.edu/viewdoc/…) Jun 29, 2011 at 23:26
@Fixee technically it's predictable, in practice the entropy pool used by Linux for example has so many different data types put into it that one has a hard time tracking them all. Then a PRNG is used to pull a subset out at random. It's just better seeding than time of day, it's still using a possibly predictable seed. Jun 30, 2011 at 11:58
1@Fixee, I did not understand that you meant combining a variety of different sources. I thought you were asking about single sources. In that case, I think a mix of pseudo-random sources is just as good as a hardware generator. After all entropy is entropy no matter where it comes from. However there is a danger of using a poor source as many programmers don't pick the best available source. Jun 30, 2011 at 16:59
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:
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.
1For the avoidance of doubt, the hardware mechanism described in the second half of this answer is not based directly on radioactive decay, but on the position of scattered radioactive particles on a CCD. This is stupendously hard to predict, but is really on a level with Brownian motion. From this point of view, the "quasi" sources of randomness - based on noise-level fluctuations and distilling bits out of unpredictable behaviour - are just as good. If you do need guaranteed randomness, make sure you use something designed for it.– MarkJun 29, 2011 at 22:55
@Mark thanks I will add that in to the answer. The smoke detector hack is not using the proven source of randomness: the timing between radiation particles, thus may not be truly random. It should be taken as an fun experiment rather than production use.– RakkhiJun 30, 2011 at 8:03
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.
Thanks for the reply, I am mostly concerned about the fact that if you are using a pseudo random number generator whether it is software or hardware based, given the same seed it will always produce the same series of numbers so in theory an attacker intimately familiar with the OS and hardware you are using could use that knowledge to better guess the keys. So I am wondering how likely is that to be an issue and what can be done to ameliorate it... Jun 28, 2011 at 23:37
3That is not much of an issue. The PRNG implementations themselves are usually public, as it is common practice for good crypto algorithms. Similar seeds will produce similar outputs, but your OS takes care to introduce as much randomness as possible from events such as network activity, mouse and keyboard movement, process start/stop. Also, the state is stored to disk at shutdown, so that sufficient entropy is available at next bootup. Lack of entropy is only a problem in very confined devices, such as your car keys.– pepeJun 29, 2011 at 0:55
or if generating very long random chains. Jun 30, 2011 at 12:00
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.
would point out the issue was a programming error in trying to remove a compiler warning in the debian openssl package. The questioned and believed the change was safe. Jun 30, 2011 at 12:04