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

[Matt Mackall]

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 systemic
patterns in the returned hash by xoring the first half of the hash
with the second half of the hash. While this might seem like a good
technique intuitively, it's mathematically flawed.

Let's assume the simplest case of a two bit hash xy. "Patterns" here
are going to translate into a correlation between otherwise
well-distributed x and y. A perfectly uncorrelated system xy is going
to have two bits of entropy. A perfectly correlated (or
anti-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 the
uncorrelated case we end up with a well-distributed z. In the
correlated case, we end up with 0 or 1, that is z=x^x=0 or z=x^-x, and
we've eliminated any entropy we once had. If correlation is less than
100%, then we get somewhere between 0 and 1 bits of entropy, but
always less than if we just returned z=x or z=y. This argument
naturally scales up to larger variables x and y.

Ok, so that explains taking out the xor. But I also return xy and not
just 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 lots
of feedback to foil backtracking attacks. In the latter, every output
bit is going through SHA four times, which is just overkill. If we
don't trust our hash to generate uniform, non-self-correlating output,
running additional rounds does not guarantee that we aren't magnifying
the 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" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/