draft-ietf-tsvwg-sctpcsum-01.txt   draft-ietf-tsvwg-sctpcsum-02.txt 
Network Working Group R. Stewart Network Working Group R. Stewart
Request for Comments: 2960 C. Sharp
Category: Internet Draft Cisco Systems Category: Internet Draft Cisco Systems
J. Stone J. Stone
Stanford Stanford
D. Otis D. Otis
SANlight SANlight
January 05, 2002 January 18, 2002
SCTP Checksum Change SCTP Checksum Change
draft-ietf-tsvwg-sctpcsum-01.txt draft-ietf-tsvwg-sctpcsum-02.txt
Status of this Memo Status of this Memo
This document is an internet-draft and is in full conformance with all This document is an internet-draft and is in full conformance with all
provisions of Section 10 of RFC2026. provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Task Internet-Drafts are working documents of the Internet Engineering Task
Force (IETF), its areas, and its working groups. Note that other groups Force (IETF), its areas, and its working groups. Note that other groups
may also distribute working documents as Internet-Drafts. Internet- may also distribute working documents as Internet-Drafts. Internet-
Drafts are draft documents valid for a maximum of six months and may be Drafts are draft documents valid for a maximum of six months and may be
updated, replaced, or obsoleted by other documents at any time. It is updated, replaced, or obsoleted by other documents at any time. It is
inappropriate to use Internet- Drafts as reference material or to cite inappropriate to use Internet- Drafts as reference material or to cite
them other than as "work in progress." them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Abstract Abstract
SCTP [RFC2960] currently uses an Adler-32 checksum. For small packets, SCTP [RFC2960] currently uses an Adler-32 checksum. For small packets
this provides weak protection against the detection of errors. This Adler-32 provides weak detection of errors. This document changes that
document changes that checksum and updates SCTP to use a 32 bit CRC checksum and updates SCTP to use a 32 bit CRC checksum.
checksum.
Table of Contents Table of Contents
1 Introduction ................................................ 1 1 Introduction ................................................ 1
2 Checksum Procedures ......................................... 2 2 Checksum Procedures ......................................... 2
3 Acknowledgments ............................................. 4 3 Security Considerations...................................... 4
4 Authors' Addresses .......................................... 4 4 IANA Considerations.......................................... 4
5 References .................................................. 5 5 Acknowledgments ............................................. 4
6 Appendix .................................................... 5 6 Authors' Addresses .......................................... 4
7 References .................................................. 5
8 Appendix .................................................... 5
1 Introduction 1 Introduction
A fundamental weakness has been detected in SCTP's current Adler-32 A fundamental weakness has been detected in SCTP's current Adler-32
checksum algorithm [STONE]. One requirement of an effective checksum is checksum algorithm [STONE]. One requirement of an effective checksum is
that it evenly and smoothly spreads its input packets over the available that it evenly and smoothly spreads its input packets over the available
check bits. check bits.
From an email from Jonathan Stone, who analyzed the Adler-32 as part From an email from Jonathan Stone, who analyzed the Adler-32 as part
of his doctoral thesis: of his doctoral thesis:
skipping to change at page 2, line 16 skipping to change at page 2, line 16
"Briefly, the problem is that, for very short packets, Adler32 is "Briefly, the problem is that, for very short packets, Adler32 is
guaranteed to give poor coverage of the available bits. Don't take my guaranteed to give poor coverage of the available bits. Don't take my
word for it, ask Mark Adler. :-). word for it, ask Mark Adler. :-).
Adler-32 uses two 16-bit counters, s1 and s2. s1 is the sum of the Adler-32 uses two 16-bit counters, s1 and s2. s1 is the sum of the
input, taken as 8-bit bytes. s2 is a running sum of each value of s1. input, taken as 8-bit bytes. s2 is a running sum of each value of s1.
Both s1 and s2 are computed mod-65521 (the largest prime less than 2^16). Both s1 and s2 are computed mod-65521 (the largest prime less than 2^16).
Consider a packet of 128 bytes. The *most* that each byte can be is 255. Consider a packet of 128 bytes. The *most* that each byte can be is 255.
There are only 128 bytes of input, so the greatest value which the s1 There are only 128 bytes of input, so the greatest value which the s1
accumulator can have is 255 * 128 = 32640. So for 128-byte packets, s1 accumulator can have is 255 * 128 = 32640. So for 128-byte packets, s1
never_ wraps. That is critical. Why? never wraps. That is critical. Why?
The key is to consider the distribution of the s1 values, over some The key is to consider the distribution of the s1 values, over some
distribution of the values of the individual input bytes in each packet. distribution of the values of the individual input bytes in each packet.
Because s1 never wraps, s1 is simply the sum of the individual input Because s1 never wraps, s1 is simply the sum of the individual input
bytes. (even Doug's trick of adding 0x5555 doesn't help here, and an even bytes. (even Doug's trick of adding 0x5555 doesn't help here, and an even
larger value doesn't really help: we can get at most one mod-565521 larger value doesn't really help: we can get at most one mod-65521
reduction). reduction).
Given the further assumption that the input bytes are drawn independently Given the further assumption that the input bytes are drawn independently
from some distribution (they probably aren't: for file system data, it's from some distribution (they probably aren't: for file system data, it's
even worse than that!), the Central Limit Theorem tells us that that s1 even worse than that!), the Central Limit Theorem tells us that that s1
will tend to have a normal distribution. That's bad: it tells us that will tend to have a normal distribution. That's bad: it tells us that
the value of s1 will have hot-spots at around 128 times the mean of the the value of s1 will have hot-spots at around 128 times the mean of the
input distribution: around 16k, assuming a uniform distribution. That's input distribution: around 16k, assuming a uniform distribution. That's
bad. We want the accumulator to wrap as many times as possible, so that bad. We want the accumulator to wrap as many times as possible, so that
the resulting sum has as close to a uniform distribution as possible. (I the resulting sum has as close to a uniform distribution as possible. (I
skipping to change at page 3, line 17 skipping to change at page 3, line 17
2.1 Checksum Calculation 2.1 Checksum Calculation
When sending an SCTP packet, the endpoint MUST include in the checksum When sending an SCTP packet, the endpoint MUST include in the checksum
field the CRC-32c value calculated on the packet, as described below. field the CRC-32c value calculated on the packet, as described below.
After the packet is constructed (containing the SCTP common header and After the packet is constructed (containing the SCTP common header and
one or more control or DATA chunks), the transmitter MUST do the one or more control or DATA chunks), the transmitter MUST do the
following: following:
1) Fill in the proper Verification Tag in the SCTP common header and 1) Fill in the proper Verification Tag in the SCTP common header and
initialize the checksum field to 0's. initialize the Checksum field to 0's.
2) Calculate the CRC-32c of the whole packet, including the SCTP common 2) Calculate the CRC-32c of the whole packet, including the SCTP common
header and all the chunks. header and all the chunks.
3) Put the resultant value into the checksum field in the common header, 3) Put the resultant value into the Checksum field in the common header,
and leave the rest of the bits unchanged. and leave the rest of the bits unchanged.
When an SCTP packet is received, the receiver MUST first perform the When an SCTP packet is received, the receiver MUST first perform the
following: following:
1) Store the received CRC-32c value, 1) Store the received CRC-32c value,
2) Replace the 32 bits of the checksum field in the received SCTP packet 2) Replace the 32 bits of the Checksum field in the received SCTP packet
with all '0's and calculate a CRC-32c value of the whole received with all '0's and calculate a CRC-32c value of the whole received
packet. And, packet. And,
3) Verify that the calculated CRC-32c value is the same as the received 3) Verify that the calculated CRC-32c value is the same as the received
CRC-32c value. If not, the receiver MUST treat the packet as an CRC-32c value. If not, the receiver MUST treat the packet as an
invalid SCTP packet. invalid SCTP packet.
The default procedure for handling invalid SCTP packets is to silently The default procedure for handling invalid SCTP packets is to silently
discard them. discard them.
The 32 bit CRC is calculated as described for CRC-32c and uses the We define a 'reflected value' as one that is the opposite of the
polynomial code 0x11EDC6F41 (Castagnoli93) or x^32+x^28+x^27+x^26+x^25 normal bit order of the machine. The 32 bit CRC is
calculated as described for CRC-32c and uses the polynomial code
0x11EDC6F41 (Castagnoli93) or x^32+x^28+x^27+x^26+x^25
+x^23+x^22+x^20+x^19+x^18+x^14+x^13+x^11+x^10+x^9+x^8+x^6+x^0 with +x^23+x^22+x^20+x^19+x^18+x^14+x^13+x^11+x^10+x^9+x^8+x^6+x^0 with
(reflected) placement. With most serial media, the bits within each byte reflected placement. With most serial media, the bits within each
are shifted out least significant bit first whereas CRC is calculated byte are shifted out least significant bit first. CRCs are
from most significant to least. To accommodate the serial bit order, a calculated from most significant to least. To accommodate the
reflected table is used. Reflected means bit 31 becomes bit 0, bit 30 serial bit order, a reflected table is used. This reflected technique
becomes bit 1, etc. This reflected technique also reduces the number of also reduces the number of instructions needed for each lookup.
instructions needed for each lookup. Background information on reflected and non-reflected CRC tables
can be found in [Williams93]. A byte based lookup table would
use the same shifting algorithm (not the same table) as that
used by the ETHERNET CRC [ITU32] since the ethernet CRC is also
built with reflected placment.
It becomes a minor problem dealing with this unusual reflected value in To improve leading zero detection, the working accumulator holding
that both bit and byte order is reversed from that of the CPU. As the the CRC value is initialized to all one's prior to the packet
bits within each byte are to remain reflected as that is how they are calculation but is not inverted before being placed in the SCTP
sent out, then ideally only the byte order is adjusted to provide most to Checksum field [McKee75]. Placement in the SCTP common header and jumbo
least serial presentation. To utilize existing byte placement routines frames cause variances from the Ethernet CRC algorithm. The
defined for various architectures however, the CRC-32c value will be [Castagnoli93] polynomial offers error detection enhancements for
placed as reflected in network order. This incorrect byte order jumbo frames at the expense of gates. The software table
placement with respect to the serial sequence eliminates new byte order implementations for any 32 bit polynomial has the same overhead
placement definitions. however.
To improve leading zero detection, the CRC value is initialized to all 3 Security Considerations
one's prior to the packet calculation but is not inverted before being
placed. Placement in the SCTP common header and jumbo frames cause
variances from the Ethernet CRC algorithm. The [Castagnoli93] polynomial
offers error detection enhancements for jumbo frames at the expense of
gates. The software table implementations for any 32 bit polynomial has
the same overhead however.
3 Acknowledgments There may be a computational advantage in validating the Association
against the Verification Tag prior to performing a checksum as
invalid tags will result in the same action as a bad checksum in
most cases. The exceptions for this technique would be INIT and some
SHUTDOWN-COMPLETE exchanges as well as a stale COOKIE-ECHO. These
special case exchanges must represent small packets and will
minimize the effect of the checksum calculation. In general,
the security considerations of RFC2960 apply to the protocol
with the new checksum as well.
4 IANA Considerations
There are no IANA considerations required in this document.
5 Acknowledgments
The authors would like to thank the following people that have The authors would like to thank the following people that have
provided comments and input on the checksum issue: provided comments and input on the checksum issue:
Ran Atkinson, Stephen Bailey, David Black, Scott Bradner, Mikael Mark Adler, Ran Atkinson, Stephen Bailey, David Black, Scott
Degermark, Laurent Glaude, Klaus Gradischnig, Alf Heidermark, Jacob Bradner, Mikael Degermark, Laurent Glaude, Klaus Gradischnig, Alf
Heitz, Gareth Kiely, David Lehmann, Allision Mankin, Lyndon Ong, Craig Heidermark, Jacob Heitz, Gareth Kiely, David Lehmann, Allision
Partridge, Vern Paxson, Kacheong Poon, Michael Ramalho, David Reed, Ian Mankin, Lyndon Ong, Craig Partridge, Vern Paxson, Kacheong Poon,
Rytina, Hanns Juergen Schwarzbauer, Bill Sommerfeld, Michael Tuxen, Jim Michael Ramalho, David Reed, Ian Rytina, Hanns Juergen Schwarzbauer,
Williams, Jim Wendt, Michael Welzl, Jonathan Wood, Lloyd Wood, Qiaobing Chip Sharp, Bill Sommerfeld, Michael Tuxen, Jim Williams, Jim Wendt,
Xie, La Monte Yarroll, Dafna Sheinwald, and Julian Satran, Pat Thaler, Michael Welzl, Jonathan Wood, Lloyd Wood, Qiaobing Xie, La Monte
Vince Cavanna, Matt Wakeley. Yarroll, Dafna Sheinwald, and Julian Satran, Pat Thaler, Vince
Cavanna, Matt Wakeley.
4 Authors' Addresses Special thanks to Mr. Ross William's and his informative document
[Williams93] which helped further the authors understanding of
both CRC's and bit reflection.
6 Authors' Addresses
Randall R. Stewart Randall R. Stewart
24 Burning Bush Trail. 24 Burning Bush Trail.
Crystal Lake, IL 60012 Crystal Lake, IL 60012
USA USA
EMail: rrs@cisco.com EMail: rrs@cisco.com
Chip Sharp
Cisco Systems Inc.
7025 Kit Creek Road
Research Triangle Park, NC 27709
USA
EMail: chsharp@cisco.com
Jonathan Stone Jonathan Stone
Room 446, Mail code 9040 Room 446, Mail code 9040
Gates building 4A Gates building 4A
Stanford, Ca 94305 Stanford, Ca 94305
EMail: jonathan@dsg.stanford.edu EMail: jonathan@dsg.stanford.edu
Douglas Otis Douglas Otis
800 E. Middlefield 800 E. Middlefield
Mountain View, CA 94043 Mountain View, CA 94043
USA USA
Email dotis@sanlight.net Email dotis@sanlight.net
5 References 7 References
[Castagnoli93] Guy Castagnoli, Stefan Braeuer and Martin Herrman [Castagnoli93] G. Castagnoli, S. Braeuer and M. Herrman,
"Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity "Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity
Bits", IEEE Transactions on Communications, Vol. 41, No. 6, June 1993 Bits", IEEE Transactions on Communications, Vol. 41, No. 6, June 1993
5.1 Informative References [McKee75] H. McKee, "Improved {CRC} techniques detects erroneous
leading and trailing 0's in transmitted data blocks",
Computer Design Volume 14 Number 10 Pages 102-4,106,
October 1975
[STONE] Jonathan Stone "Checksums in the Internet", Doctoral [RFC2026] Bradner, S., "The Internet Standards Process -- Revision
3", BCP 9, RFC 2026, October 1996.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2960] R. R. Stewart, Q. Xie, K. Morneault, C. Sharp,
H. J. Schwarzbauer, T. Taylor, I. Rytina, M. Kalla, L. Zhang,
and, V. Paxson, "Stream Control Transmission Protocol," RFC
2960, October 2000.
[ITU32] ITU-T Recommendation V.42, "Error-correcting
procedures for DCEs using asynchronous-to-synchronous
conversion", section 8.1.1.6.2, October 1996.
7.1 Informative References
[STONE] Stone, J., "Checksums in the Internet", Doctoral
dissertation - August 2001 dissertation - August 2001
6 Appendix [Williams93] Williams, R., "A PAINLESS GUIDE TO CRC ERROR DETECTION
ALGORITHMS" - Internet publication, August 1993,
http://www.geocities.com/SiliconValley/Pines/8659/crc.htm.
Example code using 256 word lookup table. 8 Appendix
This appendix is for information only and is NOT part of the
standard. The following code is based on the Castagnoli's
CRC-32c polynomial 0x11EDC6F41 as in [Castagnoli93] and is
not intended to represent an optimal implementation.
/*************************************************************/
/* Note Definition for Ross Williams table generatator would */
/* be: TB_WIDTH=4, TB_POLLY=0x1EDC6F41, TB_REVER=TRUE */
/* For Mr. Williams direct calculation code use the settings */
/* cm_width=32, cm_poly=0x1EDC6F41, cm_init=0xFFFFFFFF, */
/* cm_refin=TRUE, cm_refot=TRUE, cm_xorort=0x00000000 */
/*************************************************************/
/* Example of the crc table file */ /* Example of the crc table file */
#ifndef __crc32cr_table_h__ #ifndef __crc32cr_table_h__
#define __crc32cr_table_h__ #define __crc32cr_table_h__
#define CRC32C_POLY 0x1EDC6F41 #define CRC32C_POLY 0x1EDC6F41
#define CRC32C(c,d) (c=(c>>8)^crc_c[(c^(d))&0xFF]) #define CRC32C(c,d) (c=(c>>8)^crc_c[(c^(d))&0xFF])
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* Copyright 2001, D. Otis. Use this program, code or tables */
/* extracted from it, as desired without restriction. */
/* */
/* 32 Bit Reflected CRC table generation for SCTP. */
/* To accommodate serial byte data being shifted out least */
/* significant bit first, the table's 32 bit words are reflected */
/* which flips both byte and bit MS and LS positions. The CRC */
/* is calculated MS bits first from the perspective of the serial*/
/* stream. The x^32 term is implied and the x^0 term may also */
/* be shown as +1. The polynomial code used is 0x1EDC6F41. */
/* Castagnoli93 */
/* x^32+x^28+x^27+x^26+x^25+x^23+x^22+x^20+x^19+x^18+x^14+x^13+ */
/* x^11+x^10+x^9+x^8+x^6+x^0 */
/* Guy Castagnoli Stefan Braeuer and Martin Herrman */
/* "Optimization of Cyclic Redundancy-Check Codes */
/* with 24 and 32 Parity Bits", */
/* IEEE Transactions on Communications, Vol.41, No.6, June 1993 */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
unsigned long crc_c[256] = unsigned long crc_c[256] =
{ {
0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L, 0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL, 0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL, 0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL,
0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L, 0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL, 0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L, 0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L, 0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L,
skipping to change at page 7, line 21 skipping to change at page 7, line 46
#endif #endif
/* Example of table build routine */ /* Example of table build routine */
#include <stdio.h> #include <stdio.h>
#include <stdlib.h> #include <stdlib.h>
#define OUTPUT_FILE "crc32cr.h" #define OUTPUT_FILE "crc32cr.h"
#define CRC32C_POLY 0x1EDC6F41L #define CRC32C_POLY 0x1EDC6F41L
#define CRC_TYPE "\
/* Castagnoli93 */\n\
/* x^32+x^28+x^27+x^26+x^25+x^23+x^22+x^20+x^19+x^18+x^14+x^13+ */\n\
/* x^11+x^10+x^9+x^8+x^6+x^0 */\n\
/* Guy Castagnoli Stefan Braeuer and Martin Herrman */\n\
/* \"Optimization of Cyclic Redundancy-Check Codes */\n\
/* with 24 and 32 Parity Bits\", */\n\
/* IEEE Transactions on Communications, Vol.41, No.6, June 1993 */\n"
FILE *tf; FILE *tf;
unsigned long unsigned long
reflect_32 (unsigned long b) reflect_32 (unsigned long b)
{ {
int i; int i;
unsigned long rw = 0L; unsigned long rw = 0L;
for (i = 0; i < 32; i++) for (i = 0; i < 32; i++)
{ {
skipping to change at page 8, line 25 skipping to change at page 8, line 41
printf ("\nGenerating CRC-32c table file <%s>\n", OUTPUT_FILE); printf ("\nGenerating CRC-32c table file <%s>\n", OUTPUT_FILE);
if ((tf = fopen (OUTPUT_FILE, "w")) == NULL) if ((tf = fopen (OUTPUT_FILE, "w")) == NULL)
{ {
printf ("Unable to open %s\n", OUTPUT_FILE); printf ("Unable to open %s\n", OUTPUT_FILE);
exit (1); exit (1);
} }
fprintf (tf, "#ifndef __crc32cr_table_h__\n"); fprintf (tf, "#ifndef __crc32cr_table_h__\n");
fprintf (tf, "#define __crc32cr_table_h__\n\n"); fprintf (tf, "#define __crc32cr_table_h__\n\n");
fprintf (tf, "#define CRC32C_POLY 0x%08lX\n", CRC32C_POLY); fprintf (tf, "#define CRC32C_POLY 0x%08lX\n", CRC32C_POLY);
fprintf (tf, "#define CRC32C(c,d) (c=(c>>8)^crc_c[(c^(d))&0xFF])\n"); fprintf (tf, "#define CRC32C(c,d) (c=(c>>8)^crc_c[(c^(d))&0xFF])\n");
fprintf (tf, "\
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */\n\
/* Copyright 2001, D. Otis. Use this program, code or tables */\n\
/* extracted from it, as desired without restriction. */\n\
/* */\n\
/* 32 Bit Reflected CRC table generation for SCTP. */\n\
/* To accommodate serial byte data being shifted out least */\n\
/* significant bit first, the table's 32 bit words are reflected */\n\
/* which flips both byte and bit MS and LS positions. The CRC */\n\
/* is calculated MS bits first from the perspective of the serial*/\n\
/* stream. The x^32 term is implied and the x^0 term may also */\n\
/* be shown as +1. The polynomial code used is 0x%08lX. */\n%s\
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */\n"
, CRC32C_POLY, CRC_TYPE);
fprintf (tf, "\nunsigned long crc_c[256] =\n{\n"); fprintf (tf, "\nunsigned long crc_c[256] =\n{\n");
for (i = 0; i < 256; i++) for (i = 0; i < 256; i++)
{ {
fprintf (tf, "0x%08lXL, ", build_crc_table (i)); fprintf (tf, "0x%08lXL, ", build_crc_table (i));
if ((i & 3) == 3) if ((i & 3) == 3)
fprintf (tf, "\n"); fprintf (tf, "\n");
} }
fprintf (tf, "};\n\n#endif\n"); fprintf (tf, "};\n\n#endif\n");
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/