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:

> 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

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