Cryptographically secure random number generation

[Yoda]

Well, I see a certain degree of misunderstanding of some cryptographic and RNG mechanisms.
Lets walk together through the solution step by step, since it is very difficult to argue with a crowd over the whole description. Actually there is no any kind of "black magic" behind cryptography once you comprehend what's going on.

As a first step, let's formulate a task clearly:
1. For cryptographic applications we need a series of big and random values.
Every emphasized word in this formulation is valuable, isn't it? Does anyone want to correct formula or to clear out something?

[turdus]

...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.)

Solar is right. Ciphers must be bijective (injective and surjective at the same time), while hash functions are non-injective by nature. Therefore it's not "trivial" to transform one to another, instead it's mathematically impossible.
For more detailed explanation: http://en.wikipedia.org/wiki/Bijection, ... surjection

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 exactly, they use it for precise timing, see iridium oscillators. For random it's much much cheaper to use plain radio noise (also scrambled by background radiation).

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

True. Also true that more source the better (each new source increase the difficulty to guess the seed).

[Solar]

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 exactly, they use it for precise timing, see iridium oscillators. For random it's much much cheaper to use plain radio noise (also scrambled by background radiation).

The decay of radioactive isotopes is also an excellent source for randomness, since it is based on quantum effects ("true" randomness).

(each new source increase the difficulty to guess the seed).

The line between "added entropy" and "security through obscurity" is a fine one, here. The former is good, the latter is disastrous.

[Yoda]

The line between "added entropy" and "security through obscurity" is a fine one, here. The former is good, the latter is disastrous.

Don't mix up "obscurity of algorithm" and "absence of knowledge about certain value". Wi'll return to this question at the certain step and will see it closer.

So, if no one objects against first step, let's proceed to the following. Consider the term "random".
2. The only source of true random value may be only the physical process. No random value can be generated by any kind of [black box] mathematical algorithm.
Any objections? Comments? Uncertainty?

[bluemoon]

For random it's much much cheaper to use plain radio noise (also scrambled by background radiation).

If the site of your sensor is known, and also the exact mechanism to generate seed, it is possible to intercept such radio nose and reproduce your seed, since the noise would not vary much within a town-size region.

[Solar]

So, if no one objects against first step, let's proceed to the following.

Absence of objection does not mean acceptance of content. If you want to make a tutorial about cryptography, do so, and perhaps post a link here, but please don't make it like we're some first-class pupils obliged to listen to Mr. Teacher and nod our heads.

Your point 1), for example, depends on the cryptographic system used, and your definition of "series" and "big", while the thread itself is about something different entirely - not cryptographic algorithms, but the generation / collection of randomness.

Since I don't know where you're going with your miniseries, I don't know if it's worth arguing the point.

[bluemoon]

Let's call it an end.

The OP seems not interested in the topic anymore. And we are not proposing any practical solution to him but just argue on crypto theories for our own entertainment.

[Yoda]

If you want to make a tutorial about cryptography, do so, and perhaps post a link here

I'll consider it. Only the lack of time prevents me to do it.

but please don't make it like we're some first-class pupils obliged to listen to Mr. Teacher and nod our heads.

I'm sorry if my posts look so. I never minded to hurt anybody. The only thing is that it is much easier to discuss each point separately building up the whole system and not messing all into the one big pile.

Your point 1), for example, depends on the cryptographic system used, and your definition of "series" and "big"

That terms obviously wil be considered too at their time. I just started from nature of randomness.

while the thread itself is about something different entirely - not cryptographic algorithms, but the generation / collection of randomness.

Cryptography and generation/collection of randomness are VERY closely bound together. They can't be easily separated.

[turdus]

If the site of your sensor is known,

It's not. "in a secret location", remember?

and also the exact mechanism to generate seed, it is possible to intercept such radio nose and reproduce your seed, since the noise would not vary much within a town-size region.

Wrong. Propably you have never set up a TV satellite receiver. I'm not talking about home radio antennas, but a parabolic one that receives waves from only a fraction of the sky. What's more, that antenna is constantly moving around, and you also have to know it rotation speed and angle, besides you need to be excatly at the same position to receive the same signals (which is impossible). Even if you know:
1. the location
2. rotation speed
3. angle
and you set up a similar device a few meters away, there's no guarantee that you won't miss a signal, never get more signals (or echoes not sooner or later), and receive with the same intensity as the original antenna. The smallest difference in input can lead to a big difference in the generated seed (that's called hash distance). Calculate sha1("abcdefghijklmnop0") and sha1("abcdefghijklmnop1") for example (or md5, or any other hashing algorithm), in which input differs in only one bit, yet the results are totally different.

[Solar]

Ah, so you get additional bits of entropy if you feed it through a hash function?

I've got to remember that.

</sarcasm>

[Yoda]

Why organize complicated receiving, secret locations and so on? I said already: noise generators based on quantum effects in p-n junction (zener diode) are most cheap, safe and productive.
http://pdfserv.maxim-ic.com/en/an/AN3469.pdf

[turdus]

Ah, so you get additional bits of entropy if you feed it through a hash function?

I've got to remember that.

</sarcasm>

Could be. Read: http://people.seas.harvard.edu/~salil/r ... -Jun10.pdf

In practice, however, it is commonly observed that simple hash functions, including 2-universal hash functions, perform as predicted by the idealized analysis for truly random hash functions.
...
As long as the (Renyi) entropy per data item is sufficiently large, it turns out that the performance when choosing a hash function from a 2-universal family is essentially the same as for a truly random hash function.

But what I wrote was it's more difficult to reproduce the same seed if hashing used. It was not about entropy of hashing, but about predicting the original input to get the same result.

Why organize complicated receiving, secret locations and so on?

Because military locators are already installed. It's very cheap and easy to use an existing secure data source.

[Solar]

But what I wrote was it's more difficult to reproduce the same seed if hashing used. It was not about entropy of hashing, but about predicting the original input to get the same result.

You generate a 128bit seed by capturing radio noise. Assuming I know your exact setup and algorithm (Shannon's maxim), if I capture almost the same radio noise, that significantly reduces the amount of tries I have to go through, effectively reducing the security of your system.

Whether you feed your seed through a hash or not becomes insignificant.

Maxim #1 of any cryptologist: Paranoia, paranoia, paranoia.

Aragorn: Are you frightened?
Frodo: Yes.
Aragorn: Not nearly frightened enough. I know what hunts you.

[Yoda]

It's very cheap and easy to use an existing secure data source.

To use it you need to build radio receiver, which is by nature far more complicated than just two amplifiers and zener diode. And indeed I suspect that radio beam from locator is not as random as supposed. Moreover it can turn out completely predictable if I direct my own strong modulated radio beam onto this receiver.

Solar is right. The randomness doesn't depend on how large is you hash and how random it looks. The only thing that matters is how large is the set of it's possible values.

[qw]

The only thing that matters is how large is the set of it's possible values.

And are all values more or less likely.