`On Sun, Aug 10, 2003 at 11:18:43PM +1000, James Morris wrote:> On Sat, 9 Aug 2003, Matt Mackall wrote:> > > out. Another thing I failed to mention at 3am is that most of the> > speed increase actually comes from the following patch which wasn't in> > baseline and isn't cryptoapi-specific. So I expect the cryptoapi> > version is about 30% faster once you amortize the initialization> > stuff.> > > > >>>>> > Remove folding step and double throughput.> > Why did you remove this?I suppose the comment you deleted was a little light on details, sigh.The idea with the folding was that we can cover up any systemicpatterns in the returned hash by xoring the first half of the hashwith the second half of the hash. While this might seem like a goodtechnique intuitively, it's mathematically flawed.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.Ok, so that explains taking out the xor. But I also return xy and notjust x. With the former, every bit of input goes through SHA1 twice,once in the input pool, and once in the output pool, along with lotsof feedback to foil backtracking attacks. In the latter, every outputbit is going through SHA four times, which is just overkill. If wedon't trust our hash to generate uniform, non-self-correlating output,running additional rounds does not guarantee that we aren't magnifyingthe problem. And it is of course making everything twice as expensive.-- Matt Mackall : http://www.selenic.com : of or relating to the moon-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/`