RFC 3309 (rfc3309) - Page 2 of 17

Stream Control Transmission Protocol (SCTP) Checksum Change

RFC 3309                  SCTP Checksum Change            September 2002


1 Introduction

   A fundamental weakness has been detected in SCTP's current Adler-32
   checksum algorithm [STONE].  This document updates and replaces the
   Adler-32 checksum definition in [RFC 2960].  Note that there is no
   graceful transition mechanism for migrating to the new checksum.
   Implementations are expected to immediately switch to the new
   algorithm; use of the old algorithm is deprecated.

   One requirement of an effective checksum is that it evenly and
   smoothly spreads its input packets over the available check bits.

   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-65521 reduction.)

   Given the further assumption that the input bytes are drawn
   independently 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 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".)






Stone, et. al.              Standards Track