David Honig wrote: > The thread here has split into "QM & True Randomness" and > "what do you need to build a true RNG"...
Yup. > >Specifically: The "executive summary" of the > >principles of operation of my generator is: > > -- use SHA-1, which is believed to be resistant > > to collisions, even under chosen-input attack. > > -- use it under conditions where the adversary > > cannot choose the input. > > -- the rest is just physics and statistics. > > Sure. There are many examples of this kind of generator, > using physical sources from video'd lava lamps to radioactive decay > (incl. semiconductor junctions, resistors, microphone, > detuned FM radio cards). For the humor-impaired, let me point out that the lava lamp is a joke. What it conspicuously lacks is a proof of correctness -- that is, a nonzero lower bound on the entropy rate of the raw data. The "lava" could turn out to have a not-very-complicated periodic pattern. Secondarily, the pattern changes so slowly that there must be rather strict upper bounds on the entropy rate, small out of all proportion to the cost of the contraption. A detuned FM card is a bad idea, because it is just begging the opponent to sit next door with an FM transmitter. A microphone causes users to worry about privacy, and in any case doesn't add much beyond what you'd get with the same input circuitry open-circuited, i.e. everything except the microphone itself. Radioactive decay has a poor price/performance ratio, and isn't nearly as random as neophytes might think, when the data-acquisition hardware is taken into account. > >2) Vetting a generator by trying to "detect" patterns > >in the output is like kicking the tires on a used car > >... go ahead and do it if you want, but it is far from > >sufficient for establishing any reasonable standard of > >correctness. > > You can't vet a RNG by looking at its output, We agree. > which is likely whitened anyway, Depending on what "whitening" means; see below. > but you can gain confidence by looking at its design Yes! > and measuring the entropy in the raw-physical-source derived bitstream. That's the point where I would like some more detail. If "measuring" means applying statistical tests, then I've never seen such measurements done in a way that is really convincing. Constructive examples would be welcome. Just saying "Joe Schmoe applied all the tests he could think of and couldn't compress it more than XY%" isn't going to convince me. I recommend _calculating_ the entropy from physics principles, rather than trying to "measure" the entropy using statistical tests. The calculation is based on a handful of macroscopic physical parameters, such as temperature, gain, and bandwidth. > If the raw source has < 1 bits/symbol (and it will), Commonly but not necessarily < 1 bit/symbol. Depending on what you mean by "symbol", a 24-bit audio card provides a low-cost counterexample. > it'd be nice if a later stage > distilled this to near 1 bit/symbol, before whitening. We need to be more specific about what the symbol alphabet is. If the symbols are ASCII characters, 1 bit per symbol is not nearly good enough. More importantly, I don't know what whitening means in this case. The output of a good distiller has virtually 100% entropy density, i.e. 8 bits per byte. I say "virtually" because perfection is impossible, but 159.98 bits in a 160 bit word ought to be good enough for most applications :-). I see no point in "whitening" the output of such a distiller. If whitening means encrypting the output of the distiller, I consider that just a more-complicated hash function ... just another few rounds. > Of course, no one > outside the box will know, since you're whitening, but it yields resistance > to (albeit difficult) attacks (e.g., your hash turns out to be attackable). I assume that means "know [that I'm using a distiller]" Well, in principle nobody outside the box knows _anything_ about the mechanism (unless they read the documentation). One random symbol stream looks a lot like another :-). Attackers can always check to see whether the generator is broken or not. But if it's not broken, all they can do (from outside) is measure the output-rate. > I also fail to see harm in measuring/monitoring entropy > as the RNG operates. Certainly there's no harm. It's like kicking the tires on the used car. It gives some people a warm fuzzy, but it's far from sufficient for establishing any reasonable level of confidence. I recommend monitoring the aforementioned macroscopic (non-statistical) physical parameters, both to detect gross hardware failure and to detect attempted jamming. But that's very different from the traditional (and hereby deprecated) procedure of "measuring" the entropy using statistical tests. For lots more detail, see http://www.monmouth.com/~jsd/turbid/ --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]