Re: [RFC][PATCH] Make cryptoapi non-optional?

Theodore Ts'o
2003-08-15T22:34:44Z

On Thu, Aug 14, 2003 at 06:17:13PM -0600, Val Henson wrote:
> There is no way in which folding is better than
> halving, and folding is demonstrably worse if SHA-1's output is
> correlated across the two halves in any way (which is almost certainly
> true).

If there any kind of correlation between any two individual bits, such
that XOR'ing them together resulted in a pattern which was not
statistically random, it would be a significant weakness in the SHA
algorithm.

Consider that a requirement of a secure cryptographic hash is one
where for any (x,y) pair where y=H(x), finding another x' where
y=H(x') is no easier than brute force search. If two bits in the
output of the hash have any kind of statistically detectable
correlation, then it effectively reduces the size of the output space
of the hash, and so it would take less effort than a brute force
search of (on average) 2**80 random inputs before finding a hash
collision.

- Ted