[e2e] Re: [Tsvwg] Really End-to-end or CRC vs everything else?

[Hilarie Orman]

It is believed that coming up with a matching message and hash
cannot be done with less effort than hashing the message.  That's
largely because of the avalanche affect of the algorithms.  So that
does make MD5, etc. good candidates in the war against outrageous
fortune at the hands of hardware.

A keyed hash, though, that's what you use against an adversary
who's as smart as you and very determined.  Not your average
piece of hardware (today).

Hilarie

>>> Jonathan Stone <jonathan at DSG.Stanford.EDU> 06/11/01 04:02PM >>>
In message <5.1.0.14.2.20010611172743.04607430 at mail.reed.com>,
"David P. Reed" writes:

>The computational complexity needed to screw up cryptographic hash is known 
>to be high,

Not quite. what's beleived to be computationally intractrable about
one-way hashes is coming up with a message which matches some
pre-specified hash; or a pair of inputs which collide on the same
hash. It doesn't say that coming up with M1:H1 such that H1 == H(M1)
is fiendishly hard; your argument about MD5 was, after all, that this
was not much worse than CRCs to compute in software, right?

We can extend this to shard-secret cryptographic systems, but it
seems to me that your motivation for doing so is not detectinge errors
(per se) at all.


> whereas there are computationally simple functions that can 
>screw up  simple checksums.

It really doesn't matter.  Over the space of all possible errors,
they both do as well, given equivalent numbers of `bits'.