Cryptographically secure random number generation

[Yoda]

Times is an excellent source of seeds for PRNGs, but has no business as a seed for cryptography because it's guessed way too easily.

I don't state that times itself is a good source of seed. Of course, this is VERY bad source. But nevertheless, in combination with other sources it makes seed less predictable for remote attack, when the hacker has no direct physical access to your PC. Especially it concerns RDTSC since this counter changes very quickly. BIOS timer combined with reading the PIT counter snapshot may be used as substitution for an old systems without RDTSC instruction support (486/386).

So long as a computer is off for a sufficient amount of time, all DRAM will be zero'd out on power up, so junk in memory can easily be reproduced reliably.

Actually DRAM is not zeroed. It is filled with almost regular patterns (with some kind of physical fluctuations), but not with zeroes. The actual pattern and amount of fluctuations highly depends on memory ICs used. Also there are areas (interrupt vector table, BIOS data areas and the MB/VGA BIOSes itself) which are less predictable for remote attacker.

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.

I suspect that you don't comprehend the work of cryptographical mechanisms well enough. The strength of algorithm means much more that just strength against decrypting the output. One of the most valuable criterion of strength is the standing against the following attack...
Suppose that an attacker has an unlimited access both to source data and to encrypted ones. In this case attacker must not have possibily to reconstruct the key used for encryption. AES is strong enough against this attack.
So, the reversability of encryption process means nothing in terms of RNG quality.

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.

Probably SHA256 should work well enough, but you don't take into account the full set of features which the good source of random numbers must have. Full set means not only unpredictability. It must include linearity of distribution. As for the SHA and MD hashes, they provide irreversibility of the gained value, but not guarantee the distribtion linearity. That's why RNG based on SHA should be used with some care for scientific physical modelling. The AES due to it's reversability ensures distribution linearity for algorithm that I described. The only drawback of algorithm is that for full cycle on source counter you'll get exactly linear distribution, which is unfair for the true random numbers. But since you get large enough source counter (128 bit) you'll not be able to detect that pecularity.
The same argumentation is also suitable for quantum random generators. Even if the predictability of values is beyond doubts, the linearity is arguable.

Making anything secure from a sophisticated attack is very difficult even for experts (just look at WEP).

Actually not entirely. The difficulty is to mathematically prove the strength of basic algorithm against a known (very limited) set of possible attacks. But since you rely on strength of basic algorithm, you may provide theoretically strong derivative algorithms.

But nevertheless, SHA256 is good for generating session key for AES RNG. I forgot to mention it in RNG algorithm description. Add the following step:
0. Take seed and make SHA or MD hash of it. Use the result value as session key for the following AES algorithm.

[Yoda]

@Solar
Did I mention somewhere that timings alone are good seed source?
Pls read carefully the whole description of seed generation algorithm and what I treat to be a good source.

[Solar]

@ Yoda:

I didn't even mention the source of the seed. I was aiming at this:

You take seed. Then encrypt it by strong cryptographic algorithm, for example AES. The result is the random number.

The whole point of (thread title) "cryptographically secure random number generation" is to get a (your quote) "strong cryptographic algorithm".

Trying to create such a random number by using that algorithm - which did not yet receive its cryptographically secure random number to "be" strong - is a bit... well... reversing cause and effect?

[Yoda]

The goal should be cleanly divided into two different parts:
- obtaining unpredictable value.
- generating a sequence of values that could not be distinguished from true random values by any mathematical experiment.
These goals may seem to be similar, but in practice they aren't. I described both algorithms strong enough for cryptographic purposes.

[Solar]

I described both algorithms strong enough for cryptographic purposes.

Let's suffice to say I wouldn't bet money on that if I were you.

[Yoda]

That's sufficient to say that I'm not imposing you to use these algorithms.
On the other hand, your bet will worth something if you have publications on cryptography and RNG (or at least have extensive practice in this field) and have to say something theoretically argumented. Otherwise it won't.

[Solar]

*sigh*

That's too similar to "show your OS or don't post here" for comfort. I think I made a valid point, you disagree, and I don't feel like rolling it out to full length and breadth and references to "Applied Cryptography" and bringing this up with a friend of mine who's a professional in the field and generally trying to sound important etc. etc., because I have better things to do and think that anyone reading this thread could make up his / her own mind, because there's nothing more futile than trying to prove someone is wrong on the internet beyond a point, which I merely reached earlier in this thread than I did in others, and I still might be wrong but I don't think so but don't really care much about it either way.

Deal?

[Yoda]

That's OK.
My purpose was to help others to solve the task by sharing my knowledges about it. It's up to them to decide is it suitable for them.
I just prefer to discuss about advantages or vulnerabilities with good arguments on hands instead of stamping "that's bad" or "taht's good". That's all.

[brain]

I would look at how freebsd does /dev/random and /dev/urandom, and then look at openssl. Openssl uses /dev/?random for its seed and has a cryptographically secure random generator built in. You could of course just use ssl. IMHO when it comes to cryptography, never do it yourself, find a reference implementation that is tested to death by cryptographers and mathematicians not software developers.

Just my $0.020000002 (2 cents plus rounding errors )

[brain]

That's OK.
My purpose was to help others to solve the task by sharing my knowledges about it. It's up to them to decide is it suitable for them.
I just prefer to discuss about advantages or vulnerabilities with good arguments on hands instead of stamping "that's bad" or "taht's good". That's all.

Cryptography is a field where many amateurs are bound to fail spectacularly. You're very generous in helping them to lay this trap for themselves. Very.

That is all.

I agree completely berkus, encryption and hashing is a job best left to cryptologists, it is a specialist field on the fringes of computer science and usually it is best that the uninitiated steer well clear to prevent people creating yet more pointless insecure 'killer encryption' algorithms that are just a bunch of xor instructions and shifts.

Proper encryption algorithms should be mathematically proven with lots of peer review to verify their security, e.g. FIPS compliant algorithms.

[Yoda]

That's true. Never try to invent something new in cryptography unless you are a specialist in cryptography and mathematics. That way may have a lot of hidden traps. Once you found some cryptographic algorithm, don't try to "improve" it, just implement it as is. Your improvement may easily make it vulnerable.

[Solar]

when it comes to cryptography, never do it yourself, find a reference implementation that is tested to death by cryptographers and mathematicians not software developers.

Correct.

And do keep up to date with recent findings...

tl;dr

A quite significant percentage of SSL certificates on the web offers next to no security due to insufficient randomness of the seed.

[bluemoon]

About the seed,

- thermal conditions does have patterns, server get hotter in peak hour
- clock, ticks are guessable (with a small range) if attacker know the reboot schedule
- mouse, keyboard events may not occur at all on server machines

if someone is going to crack you, he will do necessary research on the environment to get those data.

So, it turns out that, to improve security to a higher degree you need to physically make those seed information, or sensors, unreachable by anyone.

A piece of hardware with microscope that count how many bacteria grown inside a sealed box would be good.

[brain]

About the seed,

- thermal conditions does have patterns, server get hotter in peak hour
- clock, ticks are guessable (with a small range) if attacker know the reboot schedule
- mouse, keyboard events may not occur at all on server machines

if someone is going to crack you, he will do necessary research on the environment to get those data.

So, it turns out that, to improve security to a higher degree you need to physically make those seed information, or sensors, unreachable by anyone.

A piece of hardware with microscope that count how many bacteria grown inside a sealed box would be good.

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. This would be pretty random, unless you were able to find the equipment and expose it deliberately to radiation, which is most likely very difficult as i bet it isn't in any public place

EDIT: Looks like its not just the domain of governments and military these days. Fun stuff

[Yoda]

- thermal conditions does have patterns, server get hotter in peak hour
- clock, ticks are guessable (with a small range) if attacker know the reboot schedule
- mouse, keyboard events may not occur at all on server machines

That's why I say: "Never use these sources alone for seed".
Indeed, ONE good source is quite enough if it is based on quantum processes, that's why Intel implemented it in chipset. But in the absence of true random source you need to collect as much sources as possible. You just don't have another way. But even in the case of good prediction of each separate source their combination may give good seed in the following circumstances:
- You combine (see above what is the true "combination") as many sources as you can;
- You combine as musch amount of random data from each source as possible;
- You can save the seed in a safe place for future use.
About combining sources. Imagine that you have a set of not correlated random data. 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 (for timer snapshots that won't be true because two sequential snapshots are highly correlated). The range of result value is the production of the ranges of source values. This is exactly true for linear distribution of source values. In nonlinear distributions the formula is more complicated and it's usability depends on the shape of distribution.

Once the combined range of resulting value become more than size of your seed (128 bit) it may be treated as reliable.

Practical implementations may include the following:
- Prompt user to input a large amount of random mouse and keyboard events at startup.
- Collect data during the system activity (mouse/keyboard/disk/network events).

Once you get a seed that proved to be reliable you don't need to improve it futher. That means that there is no principal difference between 128 and 1000000000 true random bits. But it will good idea not to rely solely only on one method. For example, if you find the previously saved seed, you treat it as sufficiently strong and just use it alone without modifications. In this case, hacker that got physical access to disk and stolen that seed will predict all your sequence.