`On Thu, Aug 14, 2003 at 07:40:25PM +0000, David Wagner wrote:> Val Henson  wrote:> >Throwing away 80 bits of the 160 bit output is much better> >than folding the two halves together.  In all the cases we've> >discussed where folding might improve matters, throwing away half the> >output would be even better.> > I don't see where you are getting this from.  Define>   F(x) = first80bits(SHA(x))>   G(x) = first80bits(SHA(x)) xor last80bits(SHA(x)).> What makes you think that F is a better (or worse) hash function than G?See Matt Mackall's earlier post on correlation, excerpted at the endof this message.  Basically, with two strings x and y, the entropy ofx alone or y alone is always greater than or equal to the entropy of xxored with y.entropy(x) >= entropy(x xor y)entropy(y) >= entropy(x xor y)If you have the goal of throwing away some information so that theattacker can't guess the state of the pool (which I'm not entirelysure I agree with), then it is better to throw away half the hash thanto xor the two halves together.> I think there is little basis for discriminating between them.> If SHA is cryptographically secure, both F and G are fine.> If SHA is insecure, then all bets are off, and both F and G might be weak.There's plenty of basis.  We have two goals:1. Return as much random data as possible (maximize entropy).2. Don't reveal the state of the entire pool.Throwing away half the result is at least as good or better thanfolding the result.  There is no way in which folding is better thanhalving, and folding is demonstrably worse if SHA-1's output iscorrelated across the two halves in any way (which is almost certainlytrue).-VALFrom Matt Mackall:Let's assume the simplest case of a two bit hash xy. "Patterns" hereare going to translate into a correlation between otherwisewell-distributed x and y. A perfectly uncorrelated system xy is goingto have two bits of entropy. A perfectly correlated (oranti-correlated) system xy is going to have only 1 bit of entropy.Now what happens when we fold these two bits together z=x^y? In theuncorrelated case we end up with a well-distributed z. In thecorrelated case, we end up with 0 or 1, that is z=x^x=0 or z=x^-x, andwe've eliminated any entropy we once had. If correlation is less than100%, then we get somewhere between 0 and 1 bits of entropy, butalways less than if we just returned z=x or z=y. This argumentnaturally scales up to larger variables x and y.-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`