[wayne]
I'm almost certain that CRCs can be "quickly" cracked with a
reasonable number of sample SRS strings.
It may not be obvious to those that have looked at CRC algorithms, but
the math behind CRCs is basically just taking the remainder from a
division operation. The "division" is done in a funny mathmatical
system (a "field"), and if I recall correctly that field is the
polynomials over Z/2.
Yes, a CRC is the remainder resulting from dividing the message polynomial
by a generator polynomial. Though the generator polynomial is known and
specified, you need to crack the initializer or the prepended salt.
However, you have two variables that set the level of security. You can
make the salt bit string any length you want and change it as frequently as
you want. Therefore, you can make the CRC engine required to crack the key
before it changes arbitrarily large and impractical. Pick the two constants
to suit (i.e. 256-bits and one minute) and you can make it secure enough.
For that matter, you could use a measly 16-bit initializer or salt and
change it with every message. Even if you knew the randomization algorithm
to predict future keys, you would need to inject your message in the correct
slot of the incoming message stream. If you simply changed the new
initializer after a random number of messages to destroy the sequence, you
can make this extremely secure. We're not trying to protect Fort Knox, just
prevent open relaying.
Why do I even suggest this? According to the paper that George cited,
CRC32b had a slightly better evenness of distribution than SHA1 (8 compared
to just under 7, so let's just call them equivalent) while it took about
half the time to compute. Though they didn't give a compute time for SHA1,
it looked similar on the graph to MD5, which took 4.64 microseconds compared
to 2.31 microseconds for CRC32b. Since the MD5 and SHA1 implementations
were tuned for the system they ran on while CRC32b was not, I suspect that
the real difference in compute time is somewhat larger than a factor of two.
This is significant. CRC's also lend themselves to hardware implementation
nicely.
[George Schlossnagle]
Lets not get into the crypto-weeds here until we have thunk through all
the implementation use cases.
OK.
--
Seth Goodman
Goodman Associates, LLC