At 11:45 AM 7/25/02 -0400, John S. Denker wrote: >David Honig helped focus the discussion by advocating the >block diagram: > >> Source --> Digitizer --> Simple hash --> Whitener (e.g., DES) > >Let me slightly generalize this to: >! Source --> Digitizer --> hash --> Whitener (e.g., DES) > >i.e. we defer the question of whether the hash is "simple" or not. > >I continue to claim that > a) if the hash function happens to have a property I call "no >wasted entropy" then the whitening stage is superfluous (and >you may decide to classify the hash as "non-simple");
Not wasting entropy does not mean that a function's output is "white" ie uniformly distributed. E.g., a function which doubles every bit: 0->00, 1->11 preserves total entropy but does not produce uniformly distributed output. (It also reduces entropy/symbol.) The simple-hash's --lets call it a digest-- function is to increase the entropy/symbol by *reducing* the number of symbols while preserving *total* entropy. A function like xor(bit N, bit N+1) which halves the number of bits can do this. While its output is whiter than its input, its output will not be perfectly white unless its input was. The crypto-whitener produces perfectly uniform output. It also hides the analog source and digest's regularities. >Well, then, suppose that the raw data coming off my digitizer >consists of an endless sequences of even-parity words. The >words have lots of variability, lots of entropy, but the parity >is always even. Then the output of the simple-hash is an endless >sequence of zeros. I encrypt this with DES. Maybe triple-DES. >It's not going to help. The generator is defective and doesn't >even have satisfactory error-concealment. Yes, your bit-reducing function (parity-over-N-bits) is particularly ill-suited for your raw source (constrained parity-over-M bits) for M=N. Pick a different N. >I like my design a lot better: > >+ Source --> Digitizer --> good hash > >where I have chosen SHA-1 as my hash function. > >Finally, since SHA-1 is remarkably computationally efficient, >I don't understand the motivation to look for "simpler" hash >functions, especially if they are believed to require whitening >or other post-processing. This discussion has made things clearer on this end, too. I better understand what SHA does in RNGs that use it. Two scenarios where SHA is contraindicated came up: 1. hardware 2. interrupt handlers Sometimes a hardware RNG will feed raw data into a crypto-WEAK analogue of SHA, ie a LFSR which does the bit-reduction and mixing functions, but doesn't mix as well as SHA. (LFSR are hardware-friendly) Separating the bit-reduction from the mixing can be useful for analyzing what's really going on. dh --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
