[463] in cryptography@c2.net mail archive
Re: How bad is this?
daemon@ATHENA.MIT.EDU (Colin Plumb)
Wed Apr 2 10:24:08 1997
Date: Wed, 2 Apr 97 05:40:51 MST
From: colin@nyx.net (Colin Plumb)
To: stewarts@ix.netcom.com
Cc: cryptography@c2.net
At 09:33 PM 4/1/97 MST, Colin Plumb wrote:
>I've been trying to come up with a very fast, and not necessarily
>very secure hash function for TCP initial sequence number selection.
And Bill Stewart replied:
> What's your threat model, and what're your requirements?
> Without those answers, yes, you're in pretty murky waters,
> though how dangerous they are depends on the undefined threats :-)
> How good a hash do you need? Does it need to be non-linear,
> or is something cheap and linear like a CRC good enough?
> Does it have to be non-invertible?
> Does it need to be a hash, or is a PRNG good enough?
> Do you need all this bit-shifting, or are byte or word
> operations good enough? Checksums?
What is actually needed is a (pseudo-)random function. An attacker
breaks it if, given access to a number of chosen function
outputs H(x1), H(x2), ..., he can find a pair (y,H(y)), for
a y never asked about. (Actually, the threat is only significant if
he can find many more y's than x's.)
If an attacker can do this, he can syn-flood the machine and tie up
resources. This is why the *number* of breaks is important.
Just one, or two, or even a hundred is not fatal. The reason for using
a cryptographic primitive is to generate a nonce challenge (a "cookie")
which can be echoed, and the echo verified, without taking up any
memory to store the nonce until a reply is received.
A pretty simple pseudo-random function implementation is a hash of the
input x and some random key material. That's the approach I'm taking.
Thus, something linear is undesirable. "Cryptographically strong"
is needed, but the attack is very low-value, so the strength needed
is limited. Also, it only protects against an attacker with
limited resources (i.e. can only inject messages, but not hear the
responses), so an attacker with significant resources is not likely
to bother trying to break the crypto. We're talking something like
40-bit security.
> Perry's question about how fast it needs to be is also good;
> fast is obviously nice for something you're doing often,
> but if a little latency is ok, do MD4 or SHA1 or whatever.
SHATransform is currently taking up 6% of the CPU time of a web server
that isn't saturated. This is 20% of the time required for the
connection establishment per se; the other time is spent doing the
connection and so on. That's a significant fraction, and the code
is being tuned for speed, so the fraction will go up. Reducing it
would be nice.
--
-Colin
