encrypted FM radio hiss
On the subject of RNGs. Thinking about conditioning. Suppose you have a "poor" random number stream, e.g., FM hiss digitized at say 8 Ksamples/sec. Can you get a crypto-secure random-number stream by "whitening" the stream with a good block cipher? This scheme uses the RNG to "kick" the cipher out of the deterministic cycle its in, which is determined by the cipher key and initialialization vector. Poor RNG ----> XOR ----> BlockCipher ----> improved RNG? ^ | |____________________| The output of a good block cipher in feedback mode will pass Diehard tests, though it is not crypto-secure.
From an information theoretic perspective, in the above scheme, you are slowly adding entropy to the output stream, at a rate determined by the actual number of bits/iteration and the bits/symbol of your poor random numbers.
If you fed 64 bits of pure random values into a 64 bit cipher you would have a true RNG, filtered by the xor/ciphering, but still crypto-secure. With fewer true bits, you have a 'smooth' way to introduce variable amounts of true entropy. If your RNG is 'stuck at' a constant value you are back to a deterministic PRNG. How do you cryptanalze the mix of a keyed PRNG and a true entropy source here? Is there any mathematical literature on this? Thanks honig@alum.mit.edu "Speech is not protected simply because it is written in a language" Federal Misjudge Gwin on the Bernstein Case
David Honig wrote:
The output of a good block cipher in feedback mode will pass Diehard tests, though it is not crypto-secure.
I often see the phrase 'pass Diehard test' though I don't see from the documents of Diehard how to evaluate the volumenous printout of Diehard to say exactly whether the test is passed or not. Furthermore the component asc2bin.exe of Diehard is buggy. M. K. Shen
At 10:40 AM 7/28/98 +0100, Mok-Kong Shen wrote:
David Honig wrote:
The output of a good block cipher in feedback mode will pass Diehard tests, though it is not crypto-secure.
I often see the phrase 'pass Diehard test' though I don't see from the documents of Diehard how to evaluate the volumenous printout of Diehard to say exactly whether the test is passed or not. Furthermore the component asc2bin.exe of Diehard is buggy.
M. K. Shen
My rough understanding: the 'P' value is a measure on the hypothesis that the test sample is a truly random sample, where truly random is defined by the expected statistical properties being measured. Eg in 100 bits you expect to find 50 1's; if you count 48, is your 100-bit sample consistant with it being unpredictable? If you get values near 1.0 your sample is not likely taken from a random pool. Try this: generate 10Meg from a block cipher feeding back on itself. Diehard will pass these. (Diehard needs 10M samples) Now run FM hiss into your soundcard. Sample this at 8Khz (to avoid temporal correlation) and save to a file til you have 10Meg. Diehard will reject this. Make a larger file, and then gzip it down to 10Meg. (That it shrinks indicates its symbols don't carry a full bit.) Run Diehard on this. It will pass more tests but not all. Take the FM hiss, feed it into a stream cipher, and start burning those OTPs. Do this with a detuned *video* tuner for more bandwidth. honig@alum.mit.edu "Speech is not protected simply because it is written in a language" Federal Misjudge Gwin on the Bernstein Case
David Honig wrote:
At 10:40 AM 7/28/98 +0100, Mok-Kong Shen wrote:
David Honig wrote:
The output of a good block cipher in feedback mode will pass Diehard tests, though it is not crypto-secure.
I often see the phrase 'pass Diehard test' though I don't see from the documents of Diehard how to evaluate the volumenous printout of Diehard to say exactly whether the test is passed or not. Furthermore the component asc2bin.exe of Diehard is buggy.
My rough understanding: the 'P' value is a measure on the hypothesis that the test sample is a truly random sample, where truly random is defined by the expected statistical properties being measured. Eg in 100 bits you expect to find 50 1's; if you count 48, is your 100-bit sample consistant with it being unpredictable?
My concrete problem is: With the bunch of p-values how does one (in accordance with the intention of the designer of the package) go about to determine that the test is passed at a certain confidence level. I don't see anything in the documents instructing the user to do this. Maybe I indeed missed something. Please point that out in this case. M. K. Shen
At 10:01 AM 7/29/98 +0100, Mok-Kong Shen wrote:
My concrete problem is: With the bunch of p-values how does one (in accordance with the intention of the designer of the package) go about to determine that the test is passed at a certain confidence level. I don't see anything in the documents instructing the user to do this. Maybe I indeed missed something. Please point that out in this case.
M. K. Shen
I don't believe the depth of info you want is in Marsaglia's distribution notes. You want to talk to a real statistician... honig@alum.mit.edu "Speech is not protected simply because it is written in a language" Federal Misjudge Gwin on the Bernstein Case
At 11:04 AM 7/27/98 -0700, David Honig wrote, about (Real, not Pseudo) RNGs:
Poor RNG ----> XOR ----> BlockCipher ----> improved RNG? ^ | |____________________| The output of a good block cipher in feedback mode will pass Diehard tests, though it is not crypto-secure. From an information theoretic perspective, in the above scheme, you are slowly adding entropy to the output stream, at a rate determined by the actual number of bits/iteration and the bits/symbol of your poor random numbers.
It's an interesting problem, and I doubt there's a consensus on strength, in particular, on how much randomness is left after you take a random sample out of the system. I'd feel much better if you also ran the output through a keyed hash before giving it to anyone (e.g. run pairs or triples of 64-bit blocks plus a private salt through MD5.) With a perfectly strong RNG, the output should also be perfectly strong, though with a weak RNG, the block cypher does add some correlation. You definitely should trash the initial outputs, until you've added enough bits of real randomness that the block chaining step has probably accumulated a whole block's worth of randomness. Otherwise, the first round of block cypher is an ECB on a small set of input data (e.g. 64 possible values of one 1 and 63 0s fed into a DES cracker.) Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
David Honig wrote:
I don't believe the depth of info you want is in Marsaglia's distribution notes. You want to talk to a real statistician...
It may be of some interest for you to know that the designer of Diehard has the rather uncommon habit of never answering mails with questions on his package. A bug report of mine was without answer. Later I learned that others have had the same experience. M. K. Shen
At 02:11 PM 7/30/98 +0100, Mok-Kong Shen wrote:
David Honig wrote:
I don't believe the depth of info you want is in Marsaglia's distribution notes. You want to talk to a real statistician...
It may be of some interest for you to know that the designer of Diehard has the rather uncommon habit of never answering mails with questions on his package. A bug report of mine was without answer. Later I learned that others have had the same experience.
M. K. Shen
Hmm. What packages or tests do any experimentalists out there use for entropy measurements? I've used Diehard. Also I look at compressability (gzip). I've found spectrogramming utilities. I think Walker has a utility, not yet looked at. honig@alum.mit.edu "Speech is not protected simply because it is written in a language" Federal Misjudge Gwin on the Bernstein Case
participants (3)
-
Bill Stewart -
David Honig -
Mok-Kong Shen