OSDev.org

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?

Solar wrote:

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

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

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

Yoda wrote: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).

turdus wrote:

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

turdus wrote:(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.

Solar wrote: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?

turdus wrote: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.

Yoda wrote: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.

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.

Solar wrote: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.

Solar wrote: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.

Solar wrote: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.

Solar wrote: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.

bluemoon wrote: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.

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

I've got to remember that.

</sarcasm>

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

Solar wrote: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.

Yoda wrote: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.

turdus wrote: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.

turdus wrote: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.

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

And are all values more or less likely.