OSDev.org

brain wrote:I've heard that there are some government/military systems that use a geiger counter in a secret location as a seed, measuring background radiation.

Not needed since you have p-n barrier noise generator. Much cheaper, much simpler, much more true random data could be collected per unit of time.

Yoda wrote:For example if you type one key on keyboard, it may be approximately one of the 100 values. For two keys if the second key pressed does not depend on previous key, the resulting range will be 100*100 = 10000 different values

It only increase the sample size, but the probability is not distributed and most likely the zero is dominant (in this case, no one ever press any key).
By introducing non-random factor in the seed you enlarge the bit, at the same time lost half the total randomness, even worst it may generate sensible patterns (loosely speaking, the top bits always zero, you got the idea), if that seed is used for encryption it may effectively using a constant value for the encrypting process.

Yoda wrote:But in the absence of true random source you need to collect as much sources as possible.

You collect as much entropy as possible. Either it's entropy or it is not, either it is enough or it is not. Adding sources only makes sense in as far as it gets you more entropy. (But not everything you get from these sources is entropy.)

- You can save the seed in a safe place for future use.

Use entropy (for generating a random seed, or for generating a random key pair), then toss it - because it is your randomness. Using it again simply makes no sense. (I know where you are coming from with your mentioning of a seed, but we're not talking pseudo-randomn sequences here.)

For example if you type one key on keyboard, it may be approximately one of the 100 values.

With a bell curve of probability, keys like "h" being orders of magnitude more likely than Numpad "8". Bad choice.

For two keys if the second key pressed does not depend on previous key, the resulting range will be 100*100 = 10000 different values...

...but the second key does depend on the previous, because the person doing the typing is human, and humans are incapable of consciously producing a random result.

Practical implementations may include the following:
- Prompt user to input a large amount of random mouse and keyboard events at startup.

Mouse input... you mean where the chance of repeated zig-zag or circular movements heavily outweights any other possibility?

- Collect data during the system activity (mouse/keyboard/disk/network events).

Now we're talking. But even those have patterns, and you have to make sure you only catch the random part, not the pattern part. That's why it should be done through algorithms created by experts, only. So many "random" things aren't.

bluemoon wrote:It only increase the sample size, but the probability is not distributed and most likely the zero is dominant (in this case, no one ever press any key).

I meant the imaginary experiment when user is forced to type something. For example to type in the password.

bluemoon wrote:By introducing non-random factor in the seed you enlarge the bit, at the same time lost half the total randomness

Introducing non-random factor means nothing in the case that you have a random part for sure. The correct combination process discounts non-random part and reveals random. Of course, you must take into account the total amount of different random values.

Yoda wrote:I meant the imaginary experiment when user is forced to type something. For example to type in the password.

As Solar mentioned, I expect significant number of user just type 1234, 12345, 123456 1qaz..., qwer... or password

Yoda wrote:Introducing non-random factor means nothing in the case that you have a random part for sure.

If you can filter out something that is not random, you should patent your method to identify if something is random.

Solar wrote:You collect as much entropy as possible. Either it's entropy or it is not, either it is enough or it is not. Adding sources only makes sense in as far as it gets you more entropy. (But not everything you get from these sources is entropy.)

Yes, that's right!

Solar wrote:Use entropy (for generating a random seed, or for generating a random key pair), then toss it - because it is your randomness. Using it again simply makes no sense.

Of course! The saved seed must have more entropy collected during the session.

Solar wrote:With a bell curve of probability, keys like "h" being orders of magnitude more likely than Numpad "8"...
...but the second key does depend on the previous, because the person doing the typing is human, and humans are incapable of consciously producing a random result.

Of course! The digits that I wrote is just for an imaginary experiment in ideal circumstances. For the real case you must have a large overhead to collect enough entropy.

Solar wrote:Mouse input... you mean where the chance of repeated zig-zag or circular movements heavily outweights any other possibility?

Not only figures, but clicks and precise timings of that events. You think that one zig-zag is quite same than other, but in reality it will never pass through the same pixels with the same time even if you train to do so.

Solar wrote:But even those have patterns, and you have to make sure you only catch the random part, not the pattern part. That's why it should be done through algorithms created by experts, only.

Quite so! That's why I object against XORing that data together and even against calculating CRC over them. The only correct combination of them together will be the cryptographic hash of all those collected data.

bluemoon wrote:As Solar mentioned, I expect significant number of user just type 1234, 12345, 123456 1qaz..., qwer... or password

That's why I warn: never rely on one source!

bluemoon wrote:If you can filter out something that is not random, you should patent your method to identify if something is random.

That doesn't require patenting since it is well known for every cryptographer.

Yoda wrote:

bluemoon wrote:As Solar mentioned, I expect significant number of user just type 1234, 12345, 123456 1qaz..., qwer... or password

That's why I warn: never rely on one source!

Better yet, exclude unreliable sources. They might seem to increase your amount of randomness, while in reality they reduce its strength.

Simplified: You want to collect 128 bits of entropy for a crypto key. 40 bits are actually not random - see bluemoon's comment above. You stop when you reached 128 bits of data, but actually you got only 88 bits of entropy. Your key looks secure, but isn't - about the worst-case scenario you could find yourself to be in.

In reality things are more complex than that - both in the positive and the negative. Any source considered for entropy input must be researched if you are aiming for cryptographic security. You might think the least significant bit of your CPU fan RPM value might be a good source for entropy, and it might even work on your desktop - but the next person's BIOS always has the lower 4 bits at zero...

I disagree. Determining a system is random is impossible(and illogical) until you got enough sample, and then you can tell if such sequence provide good strength, judged by a few factors)

Now, can you tell me if 4353 is a random number?
or 4353, 54118 is a random sequence, without look at the subsequence thousand numbers?

42.

XKCD.

Dilbert.

I think the points have been made. Let's bury this, and agree to disagree.

Solar wrote:Better yet, exclude unreliable sources. They might seem to increase your amount of randomness, while in reality they reduce its strength.

No. Excluding unreliable sources will not make system more random. Whilst including them may make.

Solar wrote:You want to collect 128 bits of entropy for a crypto key. ... but actually you got only 88 bits of entropy.

I said already: you must have overhead when collecting real data.

bluemoon wrote:Now, can you tell me if 4353 is a random number?

It depends on that will the attacker be able to predict your 4353 or not.

BTW, even when typing "111", just executing RDTSC for every hit makes the combined result to have a lot of randomness, since our goal is obtaining the random values rather than memorizing the password. In practice, the humans are very powerful source of entropy, the only thing is to implement the proper method of extracting that entropy from them .

Solar wrote:I think the points have been made. Let's bury this, and agree to disagree.

That's your opinion. No one forces you to boil in this topic.

bluemoon wrote:Now, can you tell me if 4353 is a random number?

It's not, you just posted it.

Yoda wrote:BTW, even when typing "111", just executing RDTSC for every hit makes the combined result to have a lot of randomness

The attacker may narrow down the range of numbers this can produce, effectively reducing "bit length".

Rudster816 wrote:Also, I don't think using AES to as an RNG is a very good idea. Since encryption by it nature is reversible, if one were to know the key, you could trivially work out the seed based on a random number given from the given RNG. A better method would be to use a good hash function (e.g. SHA256), but I think a proven PRNG algorithm would be the best choice.

Any cipher can trivially be transformed into a hash function, and every hash function can trivially be transformed into a cipher. That said, for this kind of application I'd pick a hash function (for speed), unless you have e.g. hardware AES but not hardware SHA-1.

Owen wrote:...every hash function can trivially be transformed into a cipher.

Which, unfortunately, is not true. (I'd like to see how you'd go about reconstructing a document from it's md5 hash.)