Re: building a true RNG (was: Quantum Computing ...)
On Tue, 23 Jul 2002, John S. Denker wrote: > -- I am told (but don't understand) that there might exist > a weaker hash that somehow does require whitening. This > is the point of the conversation. Please address this > point if you can. Perhaps they were refering to something like what is done in the /dev/random driver, where inputs are mixed in using a simple polynomial scheme whose exact details (or name) escapes me at the moment. This is basically because it's called during interupts, and you might not want to be calling out to something expensive like SHA-1 right then. Then when someone reads from the device the output is derived from the internal pool using SHA-1. Regards, Jack - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: building a true RNG (was: Quantum Computing ...)
On Mon, 22 Jul 2002, John S. Denker wrote: >David Honig wrote yet another nice note: >I'm not trying to be dense, but I'm totally not >understanding the distinction here. The following >block diagram is excellent for focussing the discussion, >(thanks): > >> Source --> Digitizer --> Simple hash --> Whitener (e.g., DES) > >OK, we have DES as an example of a whitener. >-- Can somebody give me an example of a "simple hash" >that performs "irreversible compression" of the required >kind? Depends on the data and how much entropy you suppose it has, really. An irreversible compression function that I use when extracting entropy from text (for other purposes) is to have a counter. Each time you process a character, you add the character code to the counter, then multiply the counter by 2.4 rounding down. This is based on estimates of 1.33 bits of entropy per character in english text, and requires an "initialization vector" (in this case an initialization value) twice as long as the character code to prevent you from taking too many bits from the first few characters alone. For something like a lava-lamp picture, your compression function might be first converting it into a 4-color image, editing out the constant parts (eg, the lamp base and edges), compressing that using PNG format, and then taking some similarly counter-based function of those bits. Using a time series of pictures of the same lava-lamp, you'd have to adjust for lower entropy per byte of processed PNG (by using a lower factor), because it could be redundant with other frames. >-- Isn't the anti-collision property required of even >the simplest hash? Isn't that tantamount to a very >strong "mixing" property? If there's strong mixing in >the simple hash function, why do we need more mixing >in the later "whitening" step? You are talking, specifically, about cryptographic hash functions. The diagram specifies a simple hash function. The distinction between cryptographic hashes and simple hashes is, a simple hash is supposed to produce evenly distributed output. A cryptographic hash is supposed to produce evenly distributed *and unpredictable* output. A simple hash, plus a whitener, is about what you're thinking of for a cryptographic hash function. >I assume digestion means the same as distillation? Roughly. People talk of "digestion" of a datastream, or "distillation" of entropy, or "irreversible compression", etc. It's roughly the same thing. >Gimme a break. In particular, gimme an example of a crypto >algorithm that will fail if it is fed with a random-symbol >generator that has "only" 159.98 bits in a 160 bit word. That's one bit per 8k. I guess it just depends on which 8k comes through and how much your opponent can make of one bit. >> >I see no point in "whitening" the output of such a >> >distiller. >> >> So the adversary can't look back into your logic. A 'distiller' >> which produces quality entropy (after digesting an arbitrary >> number of bits) needn't be as opaque as a crypto-secure hash is. > >I'm still needing an example of a distiller that has >the weakness being alleged here. In particular, > -- either it wastes entropy (due to excessive hash collisions) >in which case it isn't a good distiller, and whitening it won't >improve things (won't recover the lost entropy), or > -- it doesn't waste entropy, in which case the output has entropy >density of 159.98/160, in which case there is nothing to be gained >by so-called "whitening" or any other post-processing. I think you may be right about that -- whitening protects you from errors in an overly-simple distiller such as I described above, but if you've got a really fine-tuned one, it doesn't help much. >In particular, (proof by contradiction) consider the following >scenario: suppose she captures 100 bits of output, and wants >to use it to make some predictions about the next 60 bits of >output. She uses the 100 bits to "see back into" the >hypothetical simple-hash function, learn something about the >input thereof, and then pushes that forward again through the >simple-hash function to make the predictions. But this scenario >violates the most basic requirements of the hash function, even >the simplest of simple-hash functions. Again, it violates the requirements of a cryptographic hash function, not a simple hash function. Bear - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: building a true RNG
Eugen Leitl wrote: > > ... framegrabber with a 640x480 24 bit/pixel camera. It doesn't > compress, is rather noisy, and since self-adjusting I get the maximum > entropy at maximum darkness. OK. Evidently it's dominated by thermal noise, not to be confused with the Poisson noise recently featured in another thread. Not a problem. > Is there any point in compressing the video before running it through a > cryptohash? There might be a minor point, namely computational efficiency. A well-chosen compressor might eliminate low-entropy bytes rather quickly. Make sure it's a lossless compressor, perhaps GIF or PNG ... as opposed to a perceptual coder (e.g. JPEG) that would persumably throw away some of the entropy. Calling SHA-1 on low-entropy bytes doesn't waste entropy, but wastes CPU cycles. > How does e.g. SHA-1 fare with very sparse bitvectors? 1) In any good hash function, any input bit should have about as much effect on the output as any other input bit. SHA-1 has been analyzed by experts (of which I am not one :-) and I would imagine they checked this. 2) There are 5 one-bit shifts in the fivefold expansion, and lots of 5-bit shifts in the main loop, so it shouldn't matter that the sparse input bits are clustered in the bottom of the 32-bit words. 3) I performed an amateur kick-the-tires test, namely cobbling up some sparse input vectors, calling SHA-1, and applying "standard" statistical tests including Diehard and Maurer's "universal" statistical test. No nobody's surprise, the tests didn't detect anything. Arnold Reinhold wrote: > > ... with a portable TV set and a video digitizer > should be a good source of high bandwidth noise. In both cases you > are just using the receivers as high gain amplifiers of the thermal > noise at the antenna terminals. Thermal noise is good. Antennas are bad -- just an invitation to be attacked that way. Get rid of the antenna. Keep the high gain preamp. Better yet, do as Eugen has done: Use a framegrabber !!without!! the "portable TV set". No RF section at all. Plenty of entropy, lower cost, greater simplicity, and less vulnerability to attack. For that matter, an audio card (without microphone) produces more than enough entropy for most applications. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: building a true RNG (was: Quantum Computing ...)
Derek Atkins wrote: > > > OK, we have DES as an example of a whitener. > > -- Can somebody give me an example of a "simple hash" > > that performs "irreversible compression" of the required > > kind? > > I can give you a number of examples: MD5, SHA-1, Sorry, no, that doesn't answer the question. -- I already use SHA-1. -- It is considered a strong cryptologic hash that doesn't need whitening. -- I am told (but don't understand) that there might exist a weaker hash that somehow does require whitening. This is the point of the conversation. Please address this point if you can. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: building a true RNG (was: Quantum Computing ...)
"John S. Denker" <[EMAIL PROTECTED]> writes: > > Source --> Digitizer --> Simple hash --> Whitener (e.g., DES) > > OK, we have DES as an example of a whitener. > -- Can somebody give me an example of a "simple hash" > that performs "irreversible compression" of the required > kind? I can give you a number of examples: MD5, SHA-1, > -- Isn't the anti-collision property required of even > the simplest hash? Isn't that tantamount to a very > strong "mixing" property? If there's strong mixing in > the simple hash function, why do we need more mixing > in the later "whitening" step? More mixing is never bad in an RNG.. See RFC1750. > -- What is meant by "cryptologic strength"? Strength > against what kind of attack? If this means in particular > the one-way property, why do I need it? I can understand > why a !!pseudo!! random symbol generator needs the one-way > property, to protect its internal state, but since my > generator has no secret state to protect, why do I need > any cryptologic properties other than mixing? I think they probably meant cryptographic strength, but I don't know what was going through their minds. What do people mean by "authentification"? That's not even a real world but I see it all the time. To me, I think people just don't know the right term to use so they just put down something that sounds right to them, regardless of its correctness. -derek -- Derek Atkins Computer and Internet Security Consultant [EMAIL PROTECTED] www.ihtfp.com - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: building a true RNG (was: Quantum Computing ...)
At 3:39 PM -0700 7/22/02, David Honig wrote: >At 04:24 PM 7/22/02 -0400, John S. Denker wrote: >> > >... >>A detuned FM card is a bad idea, because it is just >>begging the opponent to sit next door with an FM >>transmitter. > >So work in a Faraday cage... > At 8:21 PM -0400 7/22/02, John S. Denker replied: > >Tee, hee. Have you ever worked in a Faraday cage? >Very expensive. Very inconvenient. > > You don't have to put yourself inside the cage, just the FM radio. several layers of aluminum foil should work. The radio can run on batteries. Getting the audio out without allowing FM signal in is a bit tricky. The bast answer is to use fiber optics to carry the audio, but a good low-pass filter should work. Instead of detuning the receiver, tune it to the strongest station in your area. You'll know the shielding is effective when the signal is no longer detectable. Of course if an attacker gets a high power transmitter close to you, all bets are off, but simply listening to another receiver nearby tuned to the same station would make such an attack obvious. The same technique with a portable TV set and a video digitizer should be a good source of high bandwidth noise. In both cases you are just using the receivers as high gain amplifiers of the thermal noise at the antenna terminals. Arnold Reinhold - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: building a true RNG (was: Quantum Computing ...)
On Mon, 22 Jul 2002, David Honig wrote: > Yes, it is a joke. However, it is also a viable if low-bandwidth > entropy source. I disagree that you need to be able to model I've got a framegrabber with a 640x480 24 bit/pixel camera. It doesn't compress, is rather noisy, and since self-adjusting I get the maximum entropy at maximum darkness. Is there any point in compressing the video before running it through a cryptohash? How does e.g. SHA-1 fare with very sparse bitvectors? - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: building a true RNG (was: Quantum Computing ...)
-- On 22 Jul 2002 at 15:39, David Honig wrote: > You should be able to use any source which you know is not a > PRNG as the entropy-source in a true RNG. You should be able to > use entropy (and stat tests) to measure the source entropy after > digitization. You cannot measure entropy retrospectively. You need to have a theory as to where the entropy is coming from, in order to reliably measure it. Thus hardware sources should be based on simple and well understood physical principles, such as Johnson noise or shot noise. Entropy is not quite a physical quantity -- rather it is on the slippery edge between being a physical thing and a philosophical thing. If you are not careful, you will slip into a deep epistemic bog and find yourself needing to ask "how do we know what is knowable, and what is the whichness of why?" To avoid such deep waters, know where your entropy is coming from. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG SMGOwg3qIP0/FsfmA7GzZGN/XYAabuqcE9Z9eiuB 2CBUwRUngy0VcmaR93NvqduyZBKgppbTUy49tSdEn - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
