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

From: "David P. Reed" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:03 -0700

At 04:48 PM 6/11/01 -0400, Craig Partridge wrote:
>I think you've missed the point.  In a prior note, you suggested a line of
>thinking of assume an adversary.  Implicitly, that's an error model.

You're right, it's a model.  But there are advantages in not forcing the
model to be statistical.  Instead you can bound, say, the adversary's
computational complexity - which is what you do when thinking about a
cryptographic adversary, since inversion of one-way functions is blocked by
computational complexity considerations.

When you are trying to think through what kinds of errors software and
hardware design flaws might introduce, it helps to classify them by
computational complexity - it takes resources to screw stuff up in a
complicated way.

The computational complexity needed to screw up cryptographic hash is known
to be high, whereas there are computationally simple functions that can
screw up  simple checksums.

_______________________________________________
tsvwg mailing list
[email-masked]
http://www1.ietf.org/mailman/listinfo/tsvwg

---

From: "Craig Partridge" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:02 -0700

In message <[email-masked]>, "David P. Reed"
writes:

>>Third, is that I wonder if you took in the result from my dissertation
>>which Craig reported a couple of days ago?  Over the space of all
>>possible errors, md5 detects the exact same fraction of errors as MD4,
>>or as a 128-bit CRC, or a 128-bit sum, or even a 128-bit constant.
>>Given that, what is the *error-detection* rationale for using MD5--
>>as opposed (per the earlier disscussion) chooisng a cheaper function,
>>which gives us the same Shannon information?
>
>I did, but it does not make sense.  Detecting the same fraction is not the
>same as having a good probability of detecting the errors that happen in
>fact.  The constant function is particularly bad on this front.  But by
>using a keyed class of cryptographically based functions, you increase the
>potential set of errors that will be detected eventually if they are repeated.

So what if traffic doesn't match that error model -- that is to say, errors
are not ones an adversary would pick -- then the checksum chosen is the
wrong one.

Craig

---

From: "David P. Reed" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:03 -0700

At 01:00 PM 6/11/01 -0700, Jonathan Stone wrote:
>But outboard checksumming is source of additional uncaught errors:
>errors which would be caught by a software implementation of
>a checksum but not by an outboard implementation of the same checksum,
>because the actual cause of the error was between the hardware checksum
>and the in-memory buffer..
>
>You and Vern seem to be assuming that is a rare case. The data I have
>indicates that, amonsgt the end-hosts we could directly monitor and
>caught sending errored packets, it is a common case.

I think I was being too subtle.  Of course outboard checksumming is not a
good design for detecting errors.  But in today's market for network
hardware, reliability has very little effect on purchasing
decisions.  Price and performance matter more.  So outboard checksumming,
or no checksumming at all, is going to happen if it boosts performance for
a small price.  (The first part of this paraagraph may not agree with
Vernon's point of view, but I've always  viewed the checksum as a check
from the point that the source process creates the data to the point that
the target process receives it.  What I was agreeing with was his statement
that outboard checksumming is the certain result, driven by market forces).

If you could accelerate checksumming with inboard or outboard hardware
assist on the data as presented at the application-protocol interface, that
would be a better design than outboard checksum insertion into datagrams in
a NIC card.  Thus it isn't whether the checksum is done in hardware or
software, but when the checksum is calculated and checked relative to the
steps involved in processing the packets in the protocol.

We can talk offline about blind vs. malicious adversaries and error
models.  I would point out that there are many kinds of blind adversaries.

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

---

From: "Jonathan Stone" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:05 -0700

In message <[email-masked]>
"David P. Reed" writes:

>At 11:22 AM 6/11/01 -0700, Jonathan Stone wrote:

[...]

>I think I side with Vernon Schryver (as I understand his
>point).  Checksumming is going to be done in outboard boxes even if it is
>cheap,

Yes, it will be done there. Yes, it is a cheap hardware speedup.

For the end-hosts we could directly observe, the conditonal
probabillity of an error damaging a packet between the end-host's
computation of IP checksum and CRC computation, given that an error
happens at all, was significant.

Whether that is an artifact of the local environement or a general
observation, I can't say.

>fact.  The constant function is particularly bad on this front.

Then I failed to get the point across.  The proof Craig mentioned is
*not* saying that all functions are equvalent in practice.  It says
that if we have no information about the acutal, empirical
distribution of errors, we have no basis at all for saying that some
function is stronger than another. How, then, can we rank or compare
checksums, given we dont know a lot about the acutal distribution of
errors (and that the link-level models are clearly inapplicable?)

The approach I took was that, in the absence of information about what
kinds of errors happen now, (or in the future seeing as the Internet
is not statistically stationary), we should use error-check functions
which minimise the worst-case damage which a blind, uninformed
adversary can do.  The constant function is weak on that score,
because the adversary might choose never to hit the constant check
bits. (Even though, across all possible errors, the constant function
is just as good as any other).

That' a minimax argument: assume there's some error process, with some
distribution of acutal errors; but the error process is not smart
enough to damage bits and recompute a valid checksum.  Under those
conditions, how do we minimize the worst-case or expected rate of
undetected errors?

That's where I argue for maxmizing the Shannon information content of
the error-check bits. That minimizes the likelihood that a `blind'
error process will manage to stumble into doing errors which manage to
duplicate the error-check function we are acutally using.

Unless we know a lot more about the distribution of acutal,
in-the-wild errors, I dont think any better metric of error-check
functions is possible.  The good news for you is that cryptographic
functions do well on that metric.

>But by

I dont follow this at all. From what think I understand, I beleive I
can construct a counter-example, if you let me count the key size
as part of the check bits. Can we maybe take this one off-line?

>>Last, a question. I've suggested an adversary models with `blind'
>>adversaries which can't exploit the structure of an error-check
>>function. You proposed informed, intelligent, malicious adversaries --
>>an intruder model which suggests cryptographic approaches.
>>We already have protocols which address those latter models.
>
>But they aren't standard.  If they were standardly used, we wouldn't need
>checksums.

But are they standardly needed, enough so to force the cost onto all
packets, from all hosts?

[...]