begin Wednesday 11 February 2004 17:24, wayne quote:
In
<MHEGIFHMACFNNIMMBACAIEPAHGAA(_dot_)sethg(_at_)GoodmanAssociates(_dot_)com>
"Seth Goodman"
<sethg(_at_)GoodmanAssociates(_dot_)com> writes:
Since people are talking about something shorter and lighter weight than
SHA1 or MD5, and we are not trying to build a crypto system but merely
have an efficient hash that is not easily guessed, how about something
like CRC-16 or CRC-32 but with a random seed? Even if the CRC algorithm
is fixed and known, it's still very hard to invert and crack the random
seed, as long as you run more than a few non-zero bytes through it.
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.
As a result, I think the Chinese Remainder Theorem can be used to
crack CRCs.
You don't even need to go that far. Just notice that crc commutes with
xor. Let's ^ be the bytewise xor operator, and . concatenation.
crc(m1^m2) = crc(m1) ^ crc(m2)
Assuming that m1 = secret1 . known_plaintext1 . secret2
And crc(m1) = hash1
we can calculate
crc(secret1 . known_plaintext2 . secret2)
trivially as
hash1 ^ crc(0 . know_plaintext1^known_plaintext2 . 0)
where the 0's are sequences of zeroes matching the lengths of both
secrets.
===> To "break" this CRC hash, you only need to have one valid hash
with matching input (receiver, recipient, time), and from that you can
make up hashes matching any (receiver, recipient, time) triples.
CRC is WEAK for crypto purposes!
Regards,
Alain