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

[Matt Mackall]

On Tue, Aug 12, 2003 at 11:20:38PM -0400, Theodore Ts'o wrote:
> On Sun, Aug 10, 2003 at 12:45:28PM -0500, Matt Mackall wrote:
> > 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.
> 
> No, that's not why the folding was done.  You could have asked me
> first....

Didn't think you were terribly interested, considering your lack of
response to the accounting problems.

> First of all, I wasn't worried about simple correlations.  There are
> enough statistical tests done that we don't need to worry about xor
> causing problems.

The argument applies to any and all structure. If X and Y are n-bit
words and some pairs (X,Y) are more likely than others even though X
and Y are perfectly distributed when looked at normally, the
distribution (and hence the entropy) of X^Y will be less ideal than X
or Y taken alone. No statistical tests will catch the case of
X=hash(a) and Y=hash(~a).

> The real issue is discarding information.  By folding, we hide
> information about the output of the SHA hash that will hopefully deny
> information that a Very Sophisticated Attacker (say, at the level of a
> certain agency that designed the SHA algorithm) that might make it
> easier for them to attack the SHA algorithm.

I'll buy that. However simply dropping the data would serve this
purpose better. As would hashing less than the entire pool on each
read. 

Currently we have: 
  hash (1024 or 4096) bits down to 160, mix back in (16 or 64), return 80

The patch I'm fiddling with for cryptoapi comparitive benchmarking does:
  hash 512 to 160, mix back in 160, return 160

More ideal would be something like:
  hash 512 to 160, mix back in 32, return other 128

Actually, I can simply set a return/mix-back ratio per pool, now that
I've added a third one for urandom and then we can raise the tinfoil
factor on /dev/random. Seem reasonable?

> > 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. 
> 
> Speed really doesn't matter here.  /dev/random is supposed to produce
> somethign which is close to true randomness, not crypto
> psuedo-randomness.  So overkill is a good thing.  It should only be
> used for generating long-term keys, so speed is really not a concern. 

Mostly agreed. But I would also like to:

a) cat /dev/urandom > /dev/hda and not have it take all day
b) enable syncookies with less of a performance penalty
c) generate other short-term keys, cookies, and UUIDs rapidly
d) not disable preemption for long stretches while hashing (a
   limitation of cryptoapi)

-- 
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/