Messages in this thread | | | Date | Sun, 10 Aug 2003 12:45:28 -0500 | From | Matt Mackall <> | Subject | Re: [RFC][PATCH] Make cryptoapi non-optional? |
| |
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@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |