[Search] [txt|pdf|bibtex] [Tracker] [WG] [Email] [Nits]

Versions: 00 01 02 03 04 05 06 07 rfc3309                               
Network Working Group                                         R. Stewart
Request for Comments: 2960                                      C. Sharp
Category: Internet Draft                                   Cisco Systems
                                                                J. Stone
                                                               Standford

                                                            June 29 2001


                     SCTP Checksum Change
                  draft-ietf-tsvwg-sctpcsum-00.txt

Status of this Memo

     This document is an Internet-Draft and is subject to all provisions
     of Section 10 of RFC2026.

     Internet-Drafts are working documents of the Internet Engineering
     Task Force (IETF), its areas, and its working groups.  Note that
     other groups may also distribute working documents as
     Internet-Drafts.

     Internet-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 inappropriate to use Internet- Drafts as
     reference material or to cite them other than as "work in progress."

     The list of current Internet-Drafts can be accessed at
     http://www.ietf.org/1id-abstracts.html

     The list of Internet-Draft Shadow Directories can be accessed at
     http://www.ietf.org/shadow.html


Copyright Notice

    Copyright (C) The Internet Society (2001).  All Rights Reserved.

Abstract

     SCTP [RFC2960] currently uses an Adler-32 checksum.  For small
     packets, this provides weak protection against the detection of
     errors. This document changes that checksum and updates SCTP to use
     the CRC-32 checksum.

Table of Contents

   1. Introduction................................................1
    1.1  Conventions..............................................2
   2. Checksum procedures.........................................3
    2.1 Checksum calculation......................................3
   3. Acknowledgments.............................................4
   4. Authors' Addresses..........................................4
   5. References..................................................4
    5.1 Normative References......................................4
    5.2 Informative References....................................4
   Appendix A Example CRC-32 code.................................5

1. Introduction

    A fundamental weakness has been detected in SCTP's current Adler-32
    checksum algorithm [STONE]. One requirement of an effective checksum
    is that it evenly and smoothly spreads its input packets over the
    available check bits.

Stewart et.al.                                                  [Page 1]


Internet Draft              SCTP Checksum Change               June 2001


    From an email from Jonathan Stone, who analyzed the Adler-32 as part
    of his doctoral thesis:

    "Briefly, the problem is that, for very short packets, Adler32 is
    guaranteed to give poor coverage of the available bits.  Don't take
    my word for it, ask Mark Adler. :-).

    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. 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.  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 _never_ wraps.  That is
    critical. Why?

    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.  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 larger value doesn't really help: we can get
    at most one mod-565521 reduction).

    Given the further assumption that the input bytes are drawn
    independently from some distribution (they probably aren't: for
    filesystem data, it's 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 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
    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 call this "fairness").

    So, for short packets, the Adler-32 s1 sum is guaranteed to be
    unfair.  why is that bad? it's bad because the space of valid
    packets-- input data, plus checksum values -- is also small. If all
    packets have checksum values very close to 32640, then the
    likelihood of even a `small' error leaving a damaged packet with a
    valid checksum is higher than if all checksum values are equally
    likely."

    Due to this inherent weakness, exacerbated by the fact that SCTP will
    first be used as a signaling transport protocol where signaling
    messages are usually less than 128 bytes, a new checksum algorithm
    is specified by this document, replacing the current Adler-32
    algorithm with CRC-32.

1.1  Conventions

    The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD,
    SHOULD NOT, RECOMMENDED, NOT RECOMMENDED, MAY, and OPTIONAL, when
    they appear in this document, are to be interpreted as described in
    [RFC2119].

Stewart et.al.                                                  [Page 2]


Internet Draft              SCTP Checksum Change               June 2001


2. Checksum procedures

    The procedures described in section 2.1 of this document MUST be
    followed, replacing the current checksum defined in
    [RFC2960]. Furthermore any references within [RFC2960] to Adler-32
    MUST be treated as a reference to CRC-32.  Section 2.1 of this
    document describes the new calculation and verification procedures
    that MUST be followed.

2.1 Checksum calculation

    When sending an SCTP packet, the endpoint MUST include in the
    checksum field the CRC-32 [CRC-32] value calculated on the packet, as
    described below.

    After the packet is constructed (containing the SCTP common header
    and one or more control or DATA chunks), the transmitter MUST
    do the following:

    1) Fill in the proper Verification Tag in the SCTP common header and
       initialize the checksum field to 0's.

    2) Calculate the CRC-32 of the whole packet, including the
       SCTP common header and all the chunks.

    3) Put the resultant value into the checksum field in the common
       header, and leave the rest of the bits unchanged.

    When an SCTP packet is received, the receiver MUST first perform the
    following:

    1) Store the received CRC-32 value,

    2) Replace the 32 bits of the checksum field in the received SCTP
       packet with all '0's and calculate a CRC-32 value of
       the whole received packet.  And,

    3) Verify that the calculated CRC-32 value is the same as the
       received CRC-32 value.  If not, the receiver MUST treat the
       packet as an invalid SCTP packet.

    The default procedure for handling invalid SCTP packets is to
    silently discard them.

    The CRC-32 is calulated as described in [CRC-32] and uses
    the polynominal polynomial is (X^32 + X^26 + X^23 + X^22 + X^16 +
    X^12 + X^11 +X^10 + X^8 + X^7 + X^5 + X^4 + X^2 + X^1 + X^0).
    Appendix A includes example code that uses a 256 word lookup
    table.



Stewart et.al.                                                  [Page 3]


Internet Draft              SCTP Checksum Change               June 2001

3. Acknowledgments

    The authors would like to thank the following people that have
    provided comments and input on the checksum issue:

    Ran Atkinson, Stephen Bailey, David Black, Scott Bradner, Mikael
    Degermark, Laurent Glaude, Klaus Gradischnig, Alf Heidermark, Jacob
    Heitz, Gareth Kiely, David Lehmann, Allision Mankin, Lyndon Ong,
    Douglas Otis, Craig Partridge, Vern Paxson, Kacheong Poon, Michael
    Ramalho, David Reed, Ian Rytina, Hanns Juergen Schwarzbauer, Bill
    Sommerfeld, Michael Tuxen, Jim Williams, Jim Wendt,
    Michael Welzl, Jonathan Wood, Lloyd Wood, Qiaobing Xie, La Monte
    Yarroll.


4.  Authors' Addresses

    Randall R. Stewart
    24 Burning Bush Trail.
    Crystal Lake, IL 60012
    USA

    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
    Room 446, Mail code 9040
    Gates building 4A
    Stanford, Ca 94305

    EMail: jonathan@dsg.stanford.edu


5. References

5.1 Normative References
     [CRC-32]  ITU-T Recommendation V.41, "Code-independent
                error-control system," November 1989.

5.2 Informative References

     [STONE]  Doctoral Thesis


Appendix A   Example CRC-32 code.


Stewart et.al.                                                  [Page 4]


Internet Draft              SCTP Checksum Change               June 2001


/*
 *  COPYRIGHT (C) 1986 Gary S. Brown.  You may use this program, or
 *  code or tables extracted from it, as desired without restriction.
 *
 *  First, the polynomial itself and its table of feedback terms.  The
 *  polynomial is
 *  X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0
 *
 *  Note that we take it "backwards" and put the highest-order term in
 *  the lowest-order bit.  The X^32 term is "implied"; the LSB is the
 *  X^31 term, etc.  The X^0 term (usually shown as "+1") results in
 *  the MSB being 1
 *
 *  Note that the usual hardware shift register implementation, which
 *  is what we're using (we're merely optimizing it by doing eight-bit
 *  chunks at a time) shifts bits into the lowest-order term.  In our
 *  implementation, that means shifting towards the right.  Why do we
 *  do it this way?  Because the calculated CRC must be transmitted in
 *  order from highest-order term to lowest-order term.  UARTs transmit
 *  characters in order from LSB to MSB.  By storing the CRC this way
 *  we hand it to the UART in the order low-byte to high-byte; the UART
 *  sends each low-bit to hight-bit; and the result is transmission bit
 *  by bit from highest- to lowest-order term without requiring any bit
 *  shuffling on our part.  Reception works similarly
 *
 *  The feedback terms table consists of 256, 32-bit entries.  Notes
 *
 *      The table can be generated at runtime if desired; code to do so
 *      is shown later.  It might not be obvious, but the feedback
 *      terms simply represent the results of eight shift/xor opera
 *      tions for all combinations of data and CRC register values
 *
 *      The values must be right-shifted by eight bits by the "updcrc
 *      logic; the shift must be unsigned (bring in zeroes).  On some
 *      hardware you could probably optimize the shift in assembler by
 *      using byte-swap instructions
 *      polynomial $edb88320
 */

static unsigned int crc32_tab[] = {
        0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
        0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
        0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
        0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
        0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
        0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
        0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
        0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
        0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
        0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
        0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
        0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
        0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,

Stewart et.al.                                                  [Page 5]


Internet Draft              SCTP Checksum Change               June 2001

        0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
        0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
        0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
        0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
        0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
        0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
        0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
        0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
        0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
        0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
        0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
        0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
        0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
        0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
        0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
        0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
        0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
        0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
        0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
        0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
        0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
        0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
        0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
        0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
        0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
        0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
        0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
        0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
        0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
        0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
        0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
        0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
        0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
        0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
        0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
        0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
        0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
        0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
        0x2d02ef8dL
};

/* Return a 32-bit CRC of the contents of the buffer. */

unsigned int
ssh_crc32(const unsigned char *s, unsigned int len)
{
        unsigned int i;
        unsigned int crc32val;

        crc32val = 0;
        for (i = 0;  i < len;  i ++) {
                crc32val = crc32_tab[(crc32val ^ s[i]) & 0xff] ^ (crc32val >> 8);
        }
        return crc32val;

Stewart et.al.                                                  [Page 6]


Internet Draft              SCTP Checksum Change               June 2001

}




Full Copyright Statement

    Copyright (C) The Internet Society (2001).  All Rights Reserved.

    This document and translations of it may be copied and furnished to
    others, and derivative works that comment on or otherwise explain it
    or assist in its implementation may be prepared, copied, published
    and distributed, in whole or in part, without restriction of any
    kind, provided that the above copyright notice and this paragraph are
    included on all such copies and derivative works.  However, this
    document itself may not be modified in any way, such as by removing
    the copyright notice or references to the Internet Society or other
    Internet organizations, except as needed for the purpose of
    developing Internet standards in which case the procedures for
    copyrights defined in the Internet Standards process must be
    followed, or as required to translate it into languages other than
    English.

    The limited permissions granted above are perpetual and will not be
    revoked by the Internet Society or its successors or assigns.

    This document and the information contained herein is provided on an
    "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
    TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
    BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
    HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
    MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Acknowledgment

    Funding for the RFC Editor function is currently provided by the
    Internet Society.


















Stewart et.al.                                                  [Page 7]