[e2e] Re: [Tsvwg] Really End-to-end or CRC vs everything
David P. Reed
dpreed at reed.com
Mon Jun 11 10:00:39 PDT 2001
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.
WWW Page: http://www.reed.com/dpr.html
More information about the end2end-interest