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

[David P. Reed]

At 09:35 AM 6/11/01 -0400, Craig Partridge wrote:
>You just changed the problem from one of checksum (where checksum is defined
>as "a cost-effective error check") to cryptographic signature ("a check
>against adversaries").  I think that's redefining the problem :-).  It may
>turn out that the solution is to declare, OK checksums were a bad idea -- but
>I'm not there yet.

I think I am there.  It's not obvious that there is a significant 
difference in computational complexity between handling the adversary model 
and error detection that is tuned to a model of all possible kinds of 
corruption that can be introduced by computational elements.

Yes, I'd like to see faster end-to-end message hashes, but they really 
aren't inherently slow - at least I haven't seen a proof yet that shows 
that good check-functions are in a different computational complexity class 
from good message-authentication-functions.  (there's a theory thesis 
there, perhaps? though since both classes seem to be linear in message 
size, the problem seems to be one of bounding the constant factor).

In addition, it has become clear over the last few years that there is a 
rising propensity for introduction of middleboxes/services that try to do 
favors that supposedly don't "change the semantics" of the communication 
among applications.  The "radical" part of my position is that end-to-end 
protocols should be able to detect and reject these "favors".  That still 
leaves a lot of room for network optimizations - lossless compression, 
dynamic routing, congestion control, etc. all can be done without tinkering 
with the application messages.

>That list (of typical hardware and software malfunctions) is a small 
>fraction of the kinds of errors that a motivated adversary
>could cause.  And we could imagine designing checksums to be efficacious
>against such errors.

Agreed.  I stipulate that this paragraph is all true.   But as mentioned 
above, proving that the checksum will be significantly optimized by 
handling only this broad and fuzzy "small fraction" and not the more 
general "adversary-driven" class of corruptions seems to be of value only 
if the cryptographic approach is dramatically costly.  And it isn't 
anymore, since silicon and theory have both advanced over the last 25 years 
a great deal.






- David
--------------------------------------------
WWW Page: http://www.reed.com/dpr.html