Subject: RE: [Tsvwg] SCTP and Checksums

From: "WENDT,JIM (HP-Roseville,ex1)" <[email-masked]>
Date: Mon, 14 May 2001 10:18:09 -0600

Doug,

> Burst errors should already be guarded by media CRC.

What do you mean by "media CRC"?  Is this the link level CRC on Ethernet (or
other) frames?
My impression from Jonathan and Craig's paper is that a variety of software
and hardware errors can (and do) occur within routers and end nodes that
appear as large burst errors. What is the performance of the various
checksum and CRC algorithms when errors with large hamming distances (1000
or 2000 bits) are involved?

Jim

-----
Doug Otis writes:
> > > All,
> > >
> > > I made a quick simulation of a stuck bit error and the ability of
either
> > > Fletcher and Alder-Fletcher to detect this problem.  Think of this as
a
> > > memory cell within a router with a defective driver.  The results were
> > > surprising so perhaps I made a mistake.
> > >
> > > See: Errchk.c and Errchk.exe  (Windows compatible)
> > > ftp://ftp.sanlight.net/pub/
> > >
> > > The results indicated this significant error could not be
> > > detected 2% of the
> > > time using Fletcher and yet the Adler-Fletcher algorithm failed
detectio
> n
> > > .1% of the time for a 20 times improvement.  The simulation code
> > > plays a few
> > > tricks.  The SCTP header ensures any stuck bit induces an error.
> > >
> > > The method of ensuring the Adler modulo used an integer with the
> > > C code but
> > > this could be done using a 16 bit register if written in assembly to
tak
> e
> > > advantage of the carry flag.  This would avoid the modulo
> > > comparison in most
> > > cases and would actually be faster.  The modulo technique should not
be
> > > viewed as more instructions to that of the traditional technique.
> > >  A 16 bit
> > > add can exceed the modulo, the addition technique with a 16 bit
register
> > > ensures the upper sum remains within a Adler modulo.
> > >
> > > I'll play around with other error techniques, but I thought this was
> > > significant to provide this information sooner than later.
> > >
> > > Doug
> > >
> > > _______________________________________________

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

---

From: "Douglas Otis" <[email-masked]>
Date: Mon, 14 May 2001 12:41:23 -0700

Jim,

I hope that Craig and Jonathan don't mind, here is the following excerpt
from:

"When The CRC and TCP Checksum Disagree
 Jonathan Stone
 Stanford Distributed Systems Group
 [email-masked]

 Craig Partridge
 BBN Technologies
 [email-masked]

4.3.4 Router memory errors

Table 3 shows that single-bit errors are relatively common. For each
single-bit error, our analysis tools report the offset of the bit and
whether the error set or cleared the bit. If we examine occurrences of bit
offsets modulo 8 (to track bit offsets within bytes) and sort the
occurrences by source IP addresses, we can find a set of hosts which may
share a common bad bit. If we know the topology and the paths to each of the
sources, and assuming a single bad bit, we can infer the probable location.

            7   6   5   4   3   2   1   0
          +---+---+---+---+---+---+---+---+
Stuck On  |  4|  0|  0|  6| 45|142|  8| 70|
          +---+---+---+---+---+---+---+---+
Stuck Off |  0| 12|  0|  0|  0|162|336| 31|
          +---+---+---+---+---+---+---+---+
Table 4: Frequency of single-bit errors in DOE-Trace, by bit position.

For the DoE-LAB trace, we managed to obtain traceroute paths between the
trace-collection point, to each recorded
source of single-bit errors. (Note that the traceroute data is slightly
later than the trace, and gives the reverse route to the source of the
inbound erroneous packets.) Table 4 shows the frequency of each of the bit
offsets. The most frequent error is bit 1 forced off. The only packets with
that error came from 5 distinct hosts; all but a single occurrence (335 out
of 336) came from just 4 hosts with addresses on 207.115.200.0/24. The
traceroute data shows route flapping to these hosts. As illustrated in
figure 5, the routes to each host diverge at the fifth hop router and
converge again at twelfth hop router.

Figure 5: Paths for a Bit Error Pattern.

The fifth hop router in figure 5 regularly showed up in trace-routes for
packets with errors, but the single-bit errors only occurred in the packets
from net 207. The logical inference, therefore, is that the bit errors are
occurring past the fifth hop, and (assuming a single source of errors),
after the paths converge again at the twelfth hop. As further confirmation,
we also observe that of these 336 errors, all 335 from the four
207.115.120.0/24 hosts are at a byte offset of 0 (mod 4), whereas the sole
remaining bit-1-off error occurred at a
different byte offset.

The next-most-frequent error, bit 2 off, shows a similar pattern: three
hosts, 210.157.0.13 210.157.0.16, 210.157.0.48, are the only sources showing
that error. The error seems to be a router between the sixth and last hop in
the path."

Although it is possible that communication errors may appear as a burst
error and it is clear this router failure appears as a single memory bit,
within parallel data paths found in routers and computers, there is also a
likelihood of errors happening at a byte modulo four due to a weak or
defective signal driver with a growing number of no-parity devices.  In
their paper, many errors were sorted as "unclassified" or as "most bytes
bad."  To be fair, extreme cases are likely hard to classify.  This could be
happening at any memory chip such that of dozens of banks of memory, only
those packets unfortunate to be placed within a defective device would
experience a large number of bit corruptions.  I could adjust the simulation
to make this a soft rather than a hard failure, but that would miss the
point.  This error may happen more than once per packet and thus burst error
calculations tend to be less applicable.

Burst errors will be seen on the serial links and most of these serial links
are well protected using CRC.  Although there are cosmic rays and RF pulses
zapping signals, there are also hardware related errors that can extend
beyond the few bits protected by algorithms suitable for a few adjacent
bits.  In the case of a high number of bits in error, the randomness of the
algorithm provides significant protection.  Fletcher offers little such
protection.  Fletcher depends on the error appearing to be random, but
hardware tends to have distinct patterns.  It is that reason, focus on burst
errors or noise may be misplaced.  It would appear that CRC is the ideal
solution, if this algorithm can be handled by software within a reasonable
time frame.

Doug

---

From: Jonathan Stone <[email-masked]>
Date: Mon, 14 May 2001 23:04:50 -0700

Doug,

Ouch. I should have written that more carefully.
In context, the "most frequent" and "next-most-frequent" errors were
referring only to the single-bit errors.

It may help you guys to know that i am nearly done re-analyzing the
error "twins" from the SIGCOMM '00 paper, as error polynomials.

If you will forgive me bandying  preliminary numbers about...

The errors in our datasets break down like this:

			DORM   CAMPUS    DOE   WEBCRAWL 
total `twins'		6617	7381	9194  3066
---------------------------------------------------
single-bit errors	236	2022	 866   622
mean bit length    	6195  	3662 	4672  3951
mean byte length      	 772 	 456 	 583   493
mean weight             2779    1576    1927  1526

median byte length  	 834      66     536   302
median bit length  	6683     541    4301  2428
median weight     	2902     138    1916   867

Cleary, long errors are very common in our datasets.

One interesting number here, error polynomials with weight
33 or greater (i.e., which flipped more than 32 bits):

weight >= 32		6341	3860	6692 	2242
weight >= 33		6340	3855	6687	2240

The latter are long that a 32-bit CRC will only catch the errors
probabalistically. (I could compute the CRC of the acutal error
polynomials, but its not very interesting.)

I have plots of the data broken down in various interesting ways.
I dont want to spam you all with huge .ps files, though.

Give me 24 hours, and I'll be able to tell you exactly what fraction
of the errors in our datasets are of a Hamming distance short enough,
and in packets short enough [*] , that they are guaranteed to be
caught by the Ethernet CRC; and the fraction which are long and heavy
enough to be caught statistically (a rate of 1 in 2^32 or better;).

(see the table in Fujiwara's et. al's paper, or Raj Jain's
paper on FDDI errors.)

Please dont forward this to tsvwg just yet; i want to be sure
the data is really accurate, first.

That said: my current breakdown of our data is this: very roughyl
 1/3 of the errors are short enough that both a CRC32 or a
32-bit 1's complement checksum should catch all of them.

Some fraction are long bursts of low weight, which a CRC wil always
catch; but a checksum will catch probabalistically.
*If* the checksum does a good job of stirring the data, then a
checksum should be just as good for these errors as a CRC.

Then there's a majority of errors -- one-half to two-thirds, varying
across the traces -- which are so long that neither CRCs nor sums do a
really good job of catching errors.

Of these, **very** roughly, one-half has the entire TCP payload
trashed; and the other half has the packet trashed from part-way
through, all the way to the end. these `tail bad' or `most tail bad'
show up in the SIGCOMM '00 paper; but here, we're also catching
a lot of the ``unknowns'' as `middle-to-end bad' as well.

I claim that it's pretty darn obvious that these "middle-to-end bad"
errors are due to causes which are non-memoryless: something like a
FIFO getting an underrun in the midle of a packet, or a DMA-pointer
screwup.   I also awknowledge that i have no way to test that conjecture.

If you fallow the argument in our ToN 98 paper (and its tricky!), this
suggests that moving a checksum to the end of the packet should help
all those cases. If we move the checksum to the end,  we will:
	* interpret a checksum as data, if there is a FIFO underrun;
  	* interpett data as a checksum, if there is a FIFO overrun;
	*interpret previous contents of the packet buffer as a checksum,
	 if the packet is not delivered to its buffer space.
	* interpret some random junk as a checksum, if the  error
	  substituted some other stream for the packet contents.

I am actively writing this up, so if that description
is confusing, please let me know.

Last: The stuck-bit simulation code showing that the checksum does
badly at stuck-bit errors sounds interesting, but i have not looked at
it yet.  I am curious what distribution of checksum values looks like.

--Jonathan

---

From: "Douglas Otis" <[email-masked]>
Date: Mon, 14 May 2001 23:54:35 -0700

Jonathan,

If you replace the #define PRINTF(a,b,c) printf(".") with PRINTF(a,b,c)
printf(a,b,c) then you will get a breakdown of the stuck bit positions in
error.  You would then run this program from the root of your drive or some
directory with a large number of files.  (Be sure to set the structure
alignment to 4.)  I use files as test patterns.  It seemed better than
attempting to create data.  The command line may look something like
errchk_all >errchk_all.txt.  Be prepared to wait a few hours.  I noticed
that Fletcher failed on bit 31 and 15 a high number of times although I did
not attempt to create a statistical database.  The errchk.exe which compares
just Fletcher and Fletcher-Adler presently prints the bit positions and this
was reduced to a dot in errchk_all.exe.

Doug

---

From: "Randall R. Stewart" <[email-masked]>
Date: Tue, 15 May 2001 19:54:17 -0500

Jim:

I think this is an excellent point... From the papers I gather
that packets in the "Wild" tend to exhibit this type of huge
numbers of bits 1000-2000 bits at a time... to the end of the
packet per chance... :)

Doug, can you re-run your tests with this type of results i.e.
the packet gets corrupted from the middle all the way to the
end with a complete copy error... say the last part of the
packet is mutilated...

R

-- 
Randall R. Stewart
[email-masked] or [email-masked]
815-342-5222 (cell) 815-477-2127 (work)

---

From: "Douglas Otis" <[email-masked]>
Date: Tue, 15 May 2001 19:20:11 -0700

Randall,

I'll run the test tonight when I get home.  I will need to check if a
modification gets made, but that is a small matter.  Jonathan had already
recommended some modifications for both a Modified Adler (where a modulo is
placed on the s1 summation and for the Fletcher algorithm for a 65535
modulo.  Both of these modifications create blind codes which weakens the
burst error integrity of the algorithm.  I can include the whole lot but a
log file becomes very large.  Perhaps a zip version will be much smaller.
If just the tail end of a packet is sitting within a defective memory
device, then the header would still allow delivery but the back end would be
heavily corrupted.  It would not be surprising to see these types of packets
captured in the wild.

Doug

---

From: "Randall R. Stewart" <[email-masked]>
Date: Wed, 16 May 2001 06:21:34 -0500

Great

---

From: "Douglas Otis" <[email-masked]>
Date: Wed, 16 May 2001 07:35:18 -0700

All,

I have completed the half packet tests that now include a modified Adler
with a 16 bit add and a modified Fletcher that uses a 65535 modulo.

See errchk_half.c and errchk_half.exe at:
ftp://ftp.sanlight.net/pub/

The Modified Adler as recommended by Jonathan, has the blind codes of:

s1+testbuf[i] = 65535 or 14
s1+testbuf[i] = 65534 or 13
s1+testbuf[i] = 65533 or 12
s1+testbuf[i] = 65532 or 11
s1+testbuf[i] = 65531 or 10
s1+testbuf[i] = 65530 or 9
s1+testbuf[i] = 65529 or 8
s1+testbuf[i] = 65528 or 7
s1+testbuf[i] = 65527 or 6
s1+testbuf[i] = 65526 or 5
s1+testbuf[i] = 65525 or 4
s1+testbuf[i] = 65524 or 3
s1+testbuf[i] = 65523 or 2
s1+testbuf[i] = 65522 or 1
s1+testbuf[i] = 65521 or 0

As well as some additional blind codes due to the partial pipeline of the
Adler modulo.

for (i = 0; i < TBUFSIZ; i++)
  {
  s1 += testbuf[i];
  if (s1 >= ADLER_MODULO)
    {
    s1 += 15;
    s1 &= 0xffff;
    }
  s2 += s1;
  if (s2 >= ADLER_MODULO)
    {
    s2 += 15;
    s2 &= 0xffff;
    }

The modified Fletcher as recommended by Jonathan, but not as described in
RFC1146, has the blind codes of:

s1+testbuf[i] = 65535 or 0

for (i = 0; i < TBUFSIZ; i++)
  {
  s1 += testbuf[i];
  if (s1 >= 0xffff)
    {
    s1++;
    s1 &= 0xffff;
    }
  s2 += s1;
  }

Perhaps to be expected, the Fletcher code had a 1.3% failure rate instead of
2%.  The Adler-32, Modified Adler, and Modified Fletcher had zero failures
to detect in the same number of passes as before or around 28 million.  To
get relative error rate information, defects will need to be made in a more
aggressive manner or shorter packets will need to be investigated.  Note,
none of these algorithms, with their bind codes or byte adds, are robust
with respect to burst errors.  Moving off of the binary modulo offers a
significant advantage with respect to stuck bit errors however.  I also
found an error in the prior Adler-32 routine in that I used short rather
than int reducing the application of the modulo.

Doug

---

From: Jonathan Stone <[email-masked]>
Date: Wed, 16 May 2001 10:43:34 -0700

[...]

Doug, all,

A few words about the choice of modulus and "blind" codes,
and thechoice of error patterns...

There are three choices on the table for a modulus:
mod-65536, mod-65535, and mod-65521.

Computing a sum mod 2^n discards any carry out of the high-order
bits of the accumulator. That causes a "blindness" of its own: two words
of 0x8000 anywhere in a packet sum to 0x0000, mod 65536.
So replacing both with zeros will go undetected.

The paper by myself, Michael Greenwald, Jim Hughes and Craig Partridge
looked at 8-bit Fletcher sums (total check 16 bits).  We found that
except for some rare cases, the mod-255 fletcher consistently did
better than the mod-256. A good intuition is that the mod-(2^n-1)
Fletcher gives a smoother "mix" of the input into the available
checksum bits, because instead of leaking out information due to carry
out of the high-order bits, those carries are added back into the
low-orer bit.  The exceptional case was one specific directory
containing 8-bit-deep bitmaps where every pixel was 0x00 or 0xff.  So,
whether mod-65536 or mod-65535 is better depends whether on how
commonly files contain runs of alternating 0x0000/0xffff.  Without
better data, this one is a hard call. If I had to guess, I'd say that
as 0x0000/0xFFFF are less likely than 0x00/0xff pairs (since the
former are a special case of the latter, but not vice-versa), the
mod-65535 is *probably* better overall. But that's just a guess.

The mod-65521 creates more congruent values ("blind" code pairs,
as Doug calls them) but it has the upside of, _in theory_, giving a
much smoother "mix" of the input data. Whether this is a net win in
practice depends on both the likelihood of errors which smash one
value from a congruent pair into another, versus still-smoother
"mixing".  Which is better depends on what kinds of errors occur.

Last: the simulation code uses sums which initialize the 's1'
accumulator to 0x5555.  what is that supposed to buy?

The issue I and Craig raised is how evenly and smoothly the checksum
function spreads its input packets over the available check bits.  If
the checksum function does poorly -- that is, a histogram of the
computed values shows hotspots -- then adding 0x5555 gives exactly the
same distribution -- hotspots just as hot -- only with all the hot and
cold values shifted up by 0x5555.  Adding 0x5555 may give a more even
ratio of 0 and 1 bits in the computed checksum fields; but it doesn't
change the shape of the distribution, whichy is what really matters here.
(The s2 accumulator increases by (*0x5555 * packet-length) mod M,
which for streams of maximal-frame-length packets, again doesn't
change the shape of the distribution, which is the important thing
here.)  Is there some subtle point behind the 0x5555 which I' missing?

One final question with simulating errors at the packet level is:
just what errors should be simulated?  obviusly we should simulate the
errors which actually occur at the packet level.  (I'm still crunching
my datasets into a model where that may be feasible.)

I think the always-stuck-bit goes a little bit too far: a bit stuck at
1 or 0 which affects every 32-bit word in a packet is going to be
damaging MAC addresses and IP addresses too.  Half the destination
addresses would be unreachable. Really stuck bits will get caught
pretty quickly (during manufacturing QA, I'd hope.)

To construct "more aggresive" errors, i'd suggest over-writing part of
a packet with data from some previous packet, so as to simulate an
intermittently bad bit in a DMA pointer register.  Filesystem data
tends to be locally correlated, which makes this an aggressive test.

>than int reducing the application of the modulo.

With respect to burst errors.. what kind of burst errors?  Is this the
example of adding values to three consecutive words (or bytes) which
cancel out, or somethihg else?  Is there something about a mod-65536
which makes it stronger against certain burst errors?

---

From: "Douglas Otis" <[email-masked]>
Date: Wed, 16 May 2001 15:36:41 -0700

Jonathan,

As I have time, I'll attempt to run shorter packet sizes.  The concept
behind the 0x5555 start point rather than 0 or 1 is to spread the checksum
over more bits for smaller packets with the concept that errors may be
prevalent on specific bits.  There are many places within the network data
path where this could be true.  Not all of this equipment has been subjected
to four corner temperature and shake table testing and even then time may
provide a cold solder joint the opportunity to play havoc even after
exhaustive testing.  If such a failure can be caught in a power-on memory
check in lieu of parity, then even these cycle events may not happen with a
great deal of frequency unless in the state of California. :) Adders do not
involve higher order bits until the count arrives at that magnitude.  In
addition, the modulo 'stirring' does not happen until these values have
wrapped.  Moving the start point closer to this magic moment is intuitive
for smaller packets of mostly zero to break out of a purely binary modulo
which may otherwise catch as few as 1 in 50 stuck bit error events and to
involve more bits in the algorithm even when the packet is not helping.

I have also heard anecdotally DSLAM is injecting errors dependent on data
patterns.  I would be interested in more details on this type of failure.
It is also my understanding this DSLAM interface is not protected with an
error check.  For a protocol that provides protection from this type of
equipment failure, an error check algorithm with 'blind' codes opens the
possibility of two bad bytes allowing undetected errors.  I do not agree
that a 65536 modulo wrap allows the same 'short' undetected error patterns
whereas 'blind' codes obviously allows patterns the size of the blind code
itself to slip through undetected.  Alas, Adler-32, summing a byte at a
time, has even more 8 bit undetectable error pairs.

There is an understanding that errors are prevalent and that a simple 16
checksum is not adequate, but to ascertain all prevalent error patterns is
sizable task.  I was simply conjecturing about a possible stuck bit error
scenario and, yes, this would be extreme.  In real life, such an error would
likely be pattern sensitive and fail softly. The manufacturer that elected
not to use parity may also choose not to find these errors dynamically.  It
would leave the customer the sizable task of understanding the source of the
error.  If not wanting to negotiate an error check, then ensuring an error
check is suitable for all applications would be preferable to an error check
adequate from some but not all.  The IPS group has elected to incorporate
CRC and has dubbed Adler-32 unacceptable.  I doubt that a modified Fletcher
will be received well in IPS or in the same storage market place. :(

As the network becomes more mission critical, and as SCTP has made
significant strides to improve the reliability of the connection, it would
be sad to see complex application level error handling added on top of SCTP.
Of all the IETF protocols, SCTP is the most suitable for hardware
implementations at high speeds where some consideration regarding the
performance of a hardware check may bear consideration.  I have proposed an
Integrity-Authentication Digest Chunk that could also include a CRC check at
the end of the packet.  The checking hardware would be required to parse all
intervening chunk headers with the benefit of ensuring the packet was not
truncated and allow the IP header to be handled independently of the SCTP
packet again depending on the robust SCTP validation.  I understand the
balance trying to be achieved among small slow devices and big fast ones.
One has not had to work very long in the industry to know electronics is
following Gordon Moore's law first stated in '65 however.

Doug

> and the choice of error patterns...
>

---

From: Jonathan Stone <[email-masked]>
Date: Wed, 16 May 2001 17:02:12 -0700

Doug,

At the high level i think we are in violent agreement.  And yes,
trying to model all errors *is* a huge undertaking, even for
the small datasets I and Craig have.

For iniializing the Fletcehr "A" accumulator (Adler "s1") to 0x5555:
the distribution over filesystem data is still non-uniform, and adding
0x5555 does not change the nonuniformity in any way.  Is the purpose
of padding in 0x5555 to detect errors in the adder itself,
or something else?

There are a few speciifc points which I'll try and address one by one.

> [...] For a protocol that provides protection from this type of
>itself to slip through undetected.  

Here'an example.  Consider some hardware device with some component
wiht a 16-bit datapath, where the high-order bit sometimes goes to 0
when it should be 1.

Give this device the pattern 0x80008000.  If this data gets smashed to
0x00000000, then a mod-65536 sum will not detect the error, since

	(0x8000 + 0x8000 ) % 65536 = (0x0000 + 0x0000 ) % 65536 = 0

whereas a mod-65535 sum will detect the error, since
	(0x8000 + 0x8000 ) % 65535 = 1
	(0x0000 + 0x0000 ) % 65535 = 0

The is a very real trade-off here, between dropping `carry' bits out
of the checksum, versus the extra exposure to errors due to having two
distinct but congruent data values. All I'm saying is that it *is* a
trade-off.

I believe we put some words in our ToN paper about the issue.
For 16-bit check in toto) came down for the mod-2^n, just as you have
here.  I think the issue is worth revisiting when the check algorithim
uses 6-bit accumulators rather than 8-bit.

>Alas, Adler-32, summing a byte at a
>time, has even more 8 bit undetectable error pairs

I think you mean the modified Alder sum Values in the range 0 to 255
cannot up congruent, mod 65521.  It's the modified 16-bit-at-a-time
sum which is subject to this problem -- but, alas, does poorly on
128-byte packets.  Telephony signalling packets are so short that the
sum never gets anywhere near the modulus. A conventional central limit
theorem implies the resulting sum will be normally distributed, rather
than uniformly distributed over the available check bits; very bad juju.

>>Note,

>> which makes it stronger against certain burst errors?

The mod-65536 issue has been done to death, but I still don't
understand the reference to "burst errors".

---

From: "Douglas Otis" <[email-masked]>
Date: Wed, 16 May 2001 21:53:20 -0700

Jonathan,

See comments interspersed.

> of padding in 0x5555 to detect errors in the adder itself,

Two points, if the packet is mostly zero, then getting an Adler modulo wrap
to even occur is helped by starting with a larger offset.  I was not
concerned about the data distribution in the file, but rather the bit
distribution in the checksum.  Again, by starting at a larger offset, more
bits are in play and this could be significant for small packets that
contain mostly zero as you do not enjoy Adler modulo protections until the
code wraps.  The tests on unmodified Fletcher bears out the significance of
that protection.

> wiht a 16-bit datapath, where the high-order bit sometimes goes to 0

Now you are describing a 32 bit error pattern versus a 16 bit error pattern.
I view this as a difference and that was the point that I was making by
saying 'small'.  You are pointing out the reason to avoid a purely binary
modulo to detect stuck bits.  On that I agree, but again the error pattern
here is larger.  You may view that as a minor point but it depends on error
patterns as seen across two versus four bytes.  Fletcher-16 does so poorly,
it is not even a candidate I would hope, but now we are back into making
blind code trade-offs to get it working?

> distinct but congruent data values. All I'm saying is that it *is* a

This is a trade-off not being made with CRC or Adler-32.  If the packet is
mostly zero, two all one's bytes goes unnoticed or conversely the same would
be true.  The question to then be answered, will this be a possible error?

> uses 6-bit accumulators rather than 8-bit.

You must mean 16 bit.

> than uniformly distributed over the available check bits; very bad juju.

Excerpt from draft-sheinwald-iSCSI-CRC-00.txt:
"Also, suppose that at that point the original data stream continues with
bytes of values 4,2,1. <snip> Now, suppose that a 24 burst occurred on these
three bytes, which modified them to 5,0,2."

s2=s1=0; (a+1, b-2, c+1) (6,3,11 -> 7,1,12)

s1+=4  (4)		s1+=6  (6)
s2+=s1 (4)		s2+=s1 (6)
s1+=2  (6)        s1+=3  (9)
s2+=s1 (10)       s2+=s1 (15)
s1+=1  (7)        s1+=11 (20)
s2+=s  (17)       s2+=s1 (35)

s1+=5  (5)        s1+=7  (7)
s2+=s1 (5)        s2+=s1 (7)
s1+=0  (5)        s1+=1  (8)
s2+=s1 (10)       s2+=s1 (15)
s1+=2  (7)        s1+=12 (20)
s2+=s1 (17)       s2+=s1 (35)

       v+      v--       v+
00000100 00000010 00000001
00000101 00000000 00000010

Sorry, Modified Adler.  For Adler-32, the undetected error pattern is 3
bytes (almost).  Again, starting Adler-32 at a larger offset should improve
performance for the smaller packet with respect to dispersing the checksum
bits.  I have no clue what your concern is to insist on starting at 1.  Not
wrapping makes very bad dudu. :) With respect to Modulo-65536 vs. 65535, the
smallest possible error pattern is reduced in size as a result of the 16 bit
'blind' codes.  The error pattern you gave was a 32-bit example.  I would
not want to go from Adler-32 to Fletcher-16 because of the problem you are
attempting to cure.  Perhaps some wording about silently ignoring a packet
with an invalid or unknown Integrity-Authentication Digest Chunk would be
equally good.  In which case, the SCTP checksum becomes a don't care in my
mind.  The proposed change was to Fletcher-16 and not your modified
Fletcher.  The Fletcher algorithm is simply broken in the face of
potentially real error conditions.

See:
ftp://ftp.ietf.org/internet-drafts/draft-otis-sctp-digest-00.txt

I was already admonished for calling this a digital signature in the
abstract.  That will be changed.

Doug

---

From: "La Monte Henry Piggy Yarroll" <[email-masked]>
Date: Thu, 17 May 2001 05:38:16 -0500

> is confusing, please let me know.

This recommendation seems to have generated no traffic.  Should we be
putting the checksum at the END of the packet?

---

From: "Randall R. Stewart" <[email-masked]>
Date: Thu, 17 May 2001 07:02:34 -0500

> putting the checksum at the END of the packet?

La Monte:

I actaully did make a proposal that no one responded to..
aka..

1) Change the 32 bit C-Sum field to a 16 bit one.
2) Use CRC-16 or TCP sum or fletcher-8.. your choice
3) Make the high order bit of the current C-Sum field be
   a CRC-32 follows bit. If 1, the last 4 bytes is a
   CRC-32... for those that can do it they check it, for
   those that can't they ignore the last 4 bytes.
   If 0, no CRC-32 is appended..

I am not sure if I made this in jest or for real :/ but 
it would be one way to attack this issue :>

Moving the C-sum to the end is a drastic change so I think
something like the above would be the way to go.. if we
were to take this course..

R

---

From: Stephen Bailey <[email-masked]>
Date: Thu, 17 May 2001 10:04:15 -0400

> Should we be putting the checksum at the END of the packet?

It certainly IS helpful for hardware.  All other things being equal (I
can't assess if they are---that's for you), a trailing integrity check
is the way to go.

Steph

---

From: "Douglas Otis" <[email-masked]>
Date: Thu, 17 May 2001 08:12:21 -0700

Randall,

If you are using a multi-word digest, that should be even better than CRC
making CRC redundant.  This was the direction being taken by IPS.  The
robust nature of SCTP does make an integrity check at the SCTP packet very
attractive.  My feeling is this check can be anywhere but maintaining the
SCTP Chunk format makes sense in allowing more than just CRC.  The header
that I proposed would consume a Chunk code.  The IANA Designator could
include CRC as one of the options.  This could be placed either at the end
or beginning of the packet.  I see advantages for both.

  0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Type 15    |IANA Designator|        Digest Length          |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 \                                                               \
 /                          Digest Value                         /
 \                                                               \
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

This would then allow removal of the Checksum from the common header but
then add 32 bits of Chunk header.  If you wish to go with a 16 bit checksum
and a 16 bit flag field (messy to some extent when extending to other types
of checks), then I would hope this would include options to expand the
checksum field to include SHA-1 digests and others.  Five or six bits
declaring the type of checksum would be helpful.  The IANA designator could
also include 16 bit CRC (with a 16 bit pad).  Silently discard a packet if
an unknown or invalid Type 15 is contained.  This Chunk placed at the end
then provides confirmation of the end of the packet by this Chunk Type.
This may help justify the slight increase in overhead and make hardware
implementers happy.

Doug

---

From: "Randall R. Stewart" <[email-masked]>
Date: Thu, 17 May 2001 10:43:14 -0500

Doug:

If we go the digest route why not use AH? And the IPSEC
problem is being addressed (there is a draft in IPSEC
working on fixing the issues with multi-homing).

Besides a digest will be very expensive CPU wise. Think
of a poor hand-held computer with low memory and low
cpu power (of course I guess low is better than my
ole 8086 :>)..

Before I went with a digest I would be much more inclined
to go with a CRC-32 solution. Less costly than a digest
and you can always proceed with your digest draft and
have this be just another chunk.. auxilliary to the 
CRC/checksum.

Jonathan/Craig: I would really like your recommendations
on which checksum to use... right now we have defined
Fletcher-16... Doug's studies appear to state this is
weaker than the Adler-32.. which is interesting.. I frankly
don't really care which checksum/crc gets used... I just
don't want it swamping the CPU of a small device that may
want to implement SCTP.... 

Note for Doug: I realize we do already have SHA-1 or MD5 in SCTP but
this
is NOT required... a device can sign its cookie with whatever
it likes... maybe nothing...

R

---

From: RJ Atkinson <[email-masked]>
Date: Thu, 17 May 2001 12:19:11 -0400

>cpu power (of course I guess low is better than my

3 cents from the peanut gallery:
        - We don't need an awesome or perfect checksum.
          TCP's Fletcher checksum, while theoretically not
          optimal, has worked out just fine in practice.
        - We need a "normally good enough" checksum that
                is not too expensive to compute fast for
                lots of packets.  
        - any kind of cryptographic checksum (MD5, SHA-1,
          whatever) is too computationally expensive to
          be a reasonable choice for every SCTP packet.

 From where I sit, we are micro-optimising the checksum
part of SCTP in a way that might not be very clever in
the long-run, if it is clever in the short-run.

Ran
[email-masked]

---

From: Qiaobing Xie <[email-masked]>
Date: Thu, 17 May 2001 11:37:27 -0500

Doug,

This is indeed an interesting proposal... and structurally quite
elegant. But there is a flaw in your reasoning that this may make
hardware people happy if it is put to the end of the packet: they still
need to go to the end of the packet first to find out what the IANA
Designator is before they can do anything with the data!

Another touching issue would be, for the sake of interoperability, there
still must be a default digest type defined and made mandatory to all
implementations. What would that be?

Then, the mainstream implementations very likely will ONLY implement the
default.... :-(

regards,
-Qiaobing

---

From: "Douglas Otis" <[email-masked]>
Date: Thu, 17 May 2001 10:09:04 -0700

Qiaobing,

I had originally had proposed this chunk be placed at the beginning of the
packet for that reason.  It was those that wanted it at the end that
convinced me to move it to the end.  Yes, it will require that all chunk
headers be treaded before a check can be made and that is why I had it
placed at the beginning.  I still have 'at the beginning' wording in the
Record Delivery proposal.  That was indeed the drawback that I saw with
placing it at the end.  The advantage for placing it at the end was simply
as a truncation indication if I understood the reasoning.  If the checksum
is CRC or better, it should not matter.  In addition, having this chunk at
the beginning would allow a small FIFO to buffer the period of process
uncertainty.  At the end, it would require a wait for all data before
kicking off any process.  Move this to the beginning, where I had it, and I
am happy.  I was only responding to requests.

As far as defaults, it should be the preferred checksum method (Adler-32
perhaps), but if the application requires CRC-32, either the transport
supports this level of checking or it is silently discarded.  For those
processors unable to achieve CRC-32, this seems like the correct behavior.

Doug

---

From: "Douglas Otis" <[email-masked]>
Date: Thu, 17 May 2001 10:08:54 -0700

Randall,

I'll attempt to track the IPSEC efforts with SCTP, but there is not much
detail yet.  My proposal was an attempt to provide parity with the iSCSI
protocol.  I know this is a work in progress that may bend to the same
pressures that push toward IPSEC as a solution for SCTP but if iSCSI uses
its own form of security, an ability to track this effort would be a highly
desired feature.

As you would not want additional overhead with a processor, if there is an
ability to process SHA-1 digests, doing it a packet at a time would be
preferable over doing it a chunk at a time.  In addition, having to process
a checksum algorithm would be made redundant by this more extensive check.
In my view, for lightweight operations, Adler-32 (with a larger offset) or
CRC-32 would be the only checks made.  If that becomes the two options, then
sticking with the Chunk Header format gives you the standard flag field
defined for Chunks.  Placing this at the end of the packet gives the added
assurances against truncation.  If iSCSI does create their own world of
security, then defining a few of the flag bits in this Chunk allows the
ability to track this effort.  Again, I am only looking for functional
parity.  Life would be easier if iSCSI and SCTP could agree on things like
security and error checking.  If not, having a back-door seems like a
reasonable approach.  For those applications that would never use such high
intensity methods, then communication would not happen until a compatible
mode was found.  It is also be likely those lightweight applications would
not even need to hunt for the correct mode.

Doug

---

From: RJ Atkinson <[email-masked]>
Date: Thu, 17 May 2001 13:40:34 -0400

At 13:08 17/05/01, Douglas Otis wrote:
>Randall,
>
>I'll attempt to track the IPSEC efforts with SCTP, 
>but there is not much detail yet.  

Hmm.  What do you want to know ?  ESP/AH don't need
to change one iota to support SCTP just fine, in either
tunnel-mode or transport-mode, with AH, ESP, or both.

>My proposal was an attempt to provide parity with the iSCSI
>protocol.  I know this is a work in progress that may bend 
>to the same pressures that push toward IPSEC as a solution 
>for SCTP  but if iSCSI uses its own form of security, 
>an ability to track this effort would be a highly desired feature.

        Some few of us think the iSCSI WG has architectural issues,
not least of which seems to be a strong tendency to avoid
reusing existing IETF standards that reasonably fit their needs.
At least some of us will object strenuously at IETF Last Call 
to iSCSI inventing their own security, should it come to that.

>As you would not want additional overhead with a processor, 
>if there is an ability to process SHA-1 digests, doing it a 
>packet at a time would be preferable over doing it a chunk at a time.  

        Still too expensive in my embedded system.  The bottom
line is that SHA-1/MD5/MD4/etc are just too expensive computationally
for day-to-day mundane checksum use.  If we are using them for
security, we should just reuse ESP/AH and not reinvent any 
new wheels here with SCTP.

>In addition, having to process a checksum algorithm would be 
>made redundant by this more extensive check.

        True.

>In my view, for lightweight operations, Adler-32 (with a larger offset) or CRC-32 would be the only checks made.  

        Sounds better.  This is the only bit that ought to be
in the SCTP specification, IMHO.

Cheers,

Ran
[email-masked]

---

From: "Randall R. Stewart" <[email-masked]>
Date: Fri, 18 May 2001 07:11:36 -0500

La Monte Henry Piggy Yarroll wrote:
> 
> Hmm.  What I had in mind was MUCH simpler, and don't I think it need
> be as drastic:
> 
>    Simply remove the checksum (or CRC) from the header and move it to
>    the last four bytes of the packet.
> 
> I think we've already reached consensus that we are going for a
> flashcut, so compatability is not an issue.
> 
> Furthermore, I think we've already reached consensus that we want
> precisely one algorithm, not a plethora.
> 
> This proposal is also immune to the problem Qiaobing pointed out with
> Douglas' trailing chunk proposal.  You need not parse the whole packet
> to find the checksum--it is ALWAYS the last four bytes.

I think I could support this. It would also fix a lot of the issues
that Craig and Jonathan saw on packets in the wild :)

Of course there is still the lurking question.. which checksum :0

R

---

From: "La Monte Henry Piggy Yarroll" <[email-masked]>
Date: Fri, 18 May 2001 07:02:12 -0500