----- Original Message ----- From: "John S. Denker" <[EMAIL PROTECTED]> To: "David Honig" <[EMAIL PROTECTED]> Cc: <[EMAIL PROTECTED]>; "'Hannes R. Boehm'" <[EMAIL PROTECTED]>; "'Ian Hill'" <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]> Sent: Saturday, July 27, 2002 10:52 AM Subject: Re: building a true RNG
> I wrote: > > > 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"); I disagree. The whitening stage can perform a very important step of allowing for stretching of the entropy. Ideally a true RNG would be fast enough to supply all our needs, but that typically doesn't happen. Instead we have to depend on stretching tricks, basically using a primitive in counter mode, to stretch the bits we have as far as is needed. This can be combined with the distillation stage itself by inserting a fixed string, copying the state, and finishing the calculation, but can conceptually be thought of as a seperate stage. > David Honig responded: > > 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.) > > That's a red-herring tangent. I'm not talking about any old > function that doesn't waste entropy; I'm talking about a > !!hash!! function that doesn't waste entropy. A construct that simply does not exist, more on this later. > And remember: in addition to having a non-entropy-wasting hash > function, we are also required to saturate its input. Then we can > conclude that the output is white to a very high degree, as > quantitatively discussed in the paper. > > > 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. I seperated this because I agree with teh statement completely, that is the one and only function of the distilling function, whether it is a hash, a cipher, or a miracle construct. > > Total entropy is preserved in the non-saturated regime. This is > documented in upper rows of the table: > http://www.monmouth.com/~jsd/turbid/paper/turbid.htm#tab-saturation I disagree. There are several ways of viewing the problem. Modelling the distillation function as a perfect entropy smoother over k bits (other than that I will be assuming a worst case). We see the following happen: When the first bit is inserted, each of the k bits receives 1/k entropy When the second bit of entropy is inserted one of those bits received 1 bit of entropy, the entire system now has 1 + (k-1)/k bits of entropy, already there is a small but measurable discrepancy Each bit now has (2k-1)/k bits of entropy The third bit results in 1 of the k bits having entropy 1 giving 1+ ((2k-1)/k)(k-1)/k bits of entropy in total While the system slowly loses entropy, it does lose entropy. It's also worth noting that this agrees with the presented analysis at 3 points, 0 has 0 entropy, 1 has 1-bit of entropy, and inf has k bits, but that for all useful lengths having k bits of entropy can never occur. > In the saturated regime, some entropy is necessarily lost. This is > documented in the lower rows of the table. This is only a small > percentage, but it is mandatory. I don't consider this to be "wasted" > entropy; I consider it entropy well spent. That is, these are > necessary hash collisions, as opposed to unnecessary ones. These don't even have to be hash collisions, it is possible for the hash function to discard entropy simply through its behavior, as in my example where entropy starts being discarded beginning with the second bit. From a theoretic standpoint, it is entirely possible that a function exists that discards entropy beginning with the first bit. > > 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. This statement is true of all deterministic algorithms. In fact it it one of the points where all presented models agree, you cannot reach a completely entropic state until you reach infinite lengths for the input. If the input if purely entropic there is some grey area surrounding this, but for a hash function to be secure the grey area disappears. > > 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. > > Well, I tend to agree that systems that separate the bit-reduction > from the mixing are easier to analyze, in the sense that it is > easier to find flaws in them. But that's because they're so flawed! Not necessarily. Take a two phase system, in hardware you have a hardware random bit generator feeding a perfect hash function, in software you have something collecting several of these inputs, and mixing them using a strong cipher (no stretching is occurring). This system is no easier to analyze than the bit generator->hash, but also no weaker. It is certainly the case that certain designs are more likely to be weak when encountered in the wild, but in general this is due simply to the frequency with which under-educated people design/implement them versus the rate at which properly educated people design/implement. Joe --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
