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

[Matt Mackall <mpm@selenic.com>]

On Mon, Aug 11, 2003 at 06:20:35AM +0100, Jamie Lokier wrote:
> Matt Mackall wrote:
> > On Mon, Aug 11, 2003 at 05:59:47AM +0100, Jamie Lokier wrote:
> > > Matt Mackall wrote:
> > > > And we're safe here. The default pool size is 1024 bits, of which we
> > > > hash 512. I could hash even fewer, say, 480 (and this would deal with the
> > > > cryptoapi padding stuff nicely).
> > > 
> > > Where is the pool size set to 1024 bits?  I'm reading 2.5.75, and it
> > > looks to me like the hash is over the whole pool, of 512 bits for the
> > > primary and 128 bits for the secondary pool:
> > > 
> > > 	for (i = 0, x = 0; i < r->poolinfo.poolwords; i += 16, x+=2) {
> >                                                ^^^^
> > 
> > Unfortunately, there's an ugly mix of words, bytes, and bits here (and it
> > was actually broken for years because of it). The input pool is 4kbits
> > and the output pools are 1k.
> 
> You're right about the sizes.  But you said it hashes only half of the
> pool.  Where is that?

Hmmm, you may have something. I've been over this code in great depth
and I keep finding bits that didn't work quite the way I (or the
original author) thought they did.

The old version does:

 reset hash state
 for each 512 bit chunk in pool:
   hash 512 bit
   mix cumulative 160 bit result back in
 
 fold cumulative result
 return 80 bit result

..which is vulnerable to your (entirely theoretical) attack

The cryptoapi version I posted does:

 for each 512 bit chunk in pool:
   reset hash state
   hash 512 bits
   mix 160 bits back in

 return 160 bit result

..which is less vulnerable, but I won't say immune.

An ideal version would do:

 pick an offset into the pool
 hash somewhere in the neighborhood of 512 bits
 mix 160 bits back in
 update offset

 return 160 bit result

..which is not vulnerable and faster. I'll whip something up.

-- 
Matt Mackall : http://www.selenic.com : of or relating to the moon