draft-ietf-tsvwg-sctpcsum-07.txt | rfc3309.txt | |||
---|---|---|---|---|

Network Working Group J. Stone | Network Working Group J. Stone | |||

Category: Internet Draft Stanford | Request for Comments: 3309 Stanford | |||

R. Stewart | Updates: 2960 R. Stewart | |||

Cisco Systems | Category: Standards Cisco Systems | |||

D. Otis | D. Otis | |||

SANlight | SANlight | |||

September 2002 | ||||

May 6, 2002 | Stream Control Transmission Protocol (SCTP) Checksum Change | |||

Stream Control Transmission Protocol (SCTP) Checksum Change | Status of this Memo | |||

draft-ietf-tsvwg-sctpcsum-07.txt | ||||

Status of this Memo | This document specifies an Internet standards track protocol for the | |||

Internet community, and requests discussion and suggestions for | ||||

improvements. Please refer to the current edition of the "Internet | ||||

Official Protocol Standards" (STD 1) for the standardization state | ||||

and status of this protocol. Distribution of this memo is unlimited. | ||||

This document is an internet-draft and is in full conformance with all | Copyright Notice | |||

provisions of Section 10 of RFC2026. | ||||

Internet-Drafts are working documents of the Internet Engineering Task | Copyright (C) The Internet Society (2002). All Rights Reserved. | |||

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/ietf/1id-abstracts.txt | ||||

The list of Internet-Draft Shadow Directories can be accessed at | ||||

http://www.ietf.org/shadow.html. | ||||

Abstract | Abstract | |||

Stream Control Transmission Protocol [RFC2960] (SCTP) currently uses an | Stream Control Transmission Protocol (SCTP) currently uses an Adler- | |||

Adler-32 checksum. For small packets Adler-32 provides weak detection | 32 checksum. For small packets Adler-32 provides weak detection of | |||

of errors. This document changes that checksum and updates SCTP to | errors. This document changes that checksum and updates SCTP to use | |||

use a 32 bit CRC checksum. | a 32 bit CRC checksum. | |||

Table of Contents | Table of Contents | |||

1 Introduction ................................................1 | 1 Introduction ................................................... 2 | |||

2 Checksum Procedures .........................................1 | 2 Checksum Procedures ............................................ 3 | |||

3 Security Considerations......................................5 | 3 Security Considerations......................................... 6 | |||

4 IANA Considerations..........................................5 | 4 IANA Considerations............................................. 6 | |||

5 Acknowledgments .............................................5 | 5 Acknowledgments ................................................ 6 | |||

6 Authors' Addresses ..........................................7 | 6 References ..................................................... 7 | |||

7 References ..................................................7 | Appendix ......................................................... 9 | |||

8 Appendix ....................................................7 | Authors' Addresses ............................................... 16 | |||

Full Copyright Statement ......................................... 17 | ||||

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]. This document updates and replaces the | |||

that it evenly and smoothly spreads its input packets over the available | Adler-32 checksum definition in [RFC 2960]. Note that there is no | |||

check bits. | 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. | ||||

From an email from Jonathan Stone, who analyzed the Adler-32 as part | One requirement of an effective checksum is that it evenly and | |||

of his doctoral thesis: | smoothly spreads its input packets over the available check bits. | |||

"Briefly, the problem is that, for very short packets, Adler32 is | From an email from Jonathan Stone, who analyzed the Adler-32 as part | |||

guaranteed to give poor coverage of the available bits. Don't take my | of his doctoral thesis: | |||

word for it, ask Mark Adler. :-). | ||||

Adler-32 uses two 16-bit counters, s1 and s2. s1 is the sum of the | "Briefly, the problem is that, for very short packets, Adler32 is | |||

input, taken as 8-bit bytes. s2 is a running sum of each value of s1. | guaranteed to give poor coverage of the available bits. Don't take | |||

Both s1 and s2 are computed mod-65521 (the largest prime less than 2^16). | my word for it, ask Mark Adler. :-) | |||

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 | Adler-32 uses two 16-bit counters, s1 and s2. s1 is the sum of the | |||

distribution of the values of the individual input bytes in each packet. | input, taken as 8-bit bytes. s2 is a running sum of each value of | |||

Because s1 never wraps, s1 is simply the sum of the individual input | s1. Both s1 and s2 are computed mod-65521 (the largest prime less | |||

bytes. (even Doug's trick of adding 0x5555 doesn't help here, and an even | than 2^16). Consider a packet of 128 bytes. The *most* that each | |||

larger value doesn't really help: we can get at most one mod-65521 | byte can be is 255. There are only 128 bytes of input, so the | |||

reduction). | greatest value which the s1 accumulator can have is 255 * 128 = | |||

32640. So, for 128-byte packets, s1 never wraps. That is critical. | ||||

Why? | ||||

Given the further assumption that the input bytes are drawn independently | The key is to consider the distribution of the s1 values, over some | |||

from some distribution (they probably aren't: for file system data, it's | distribution of the values of the individual input bytes in each | |||

even worse than that!), the Central Limit Theorem tells us that that s1 | packet. Because s1 never wraps, s1 is simply the sum of the | |||

will tend to have a normal distribution. That's bad: it tells us that | individual input bytes. (Even Doug's trick of adding 0x5555 doesn't | |||

the value of s1 will have hot-spots at around 128 times the mean of the | help here, and an even larger value doesn't really help: we can get | |||

input distribution: around 16k, assuming a uniform distribution. That's | at most one mod-65521 reduction.) | |||

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

Why is that bad? It's bad because the space of valid packets-- input | independently from some distribution (they probably aren't: for file | |||

data, plus checksum values -- is also small. If all packets have | system data, it's even worse than that!), the Central Limit Theorem | |||

checksum values very close to 32640, then the likelihood of even a | tells us that that s1 will tend to have a normal distribution. | |||

'small' error leaving a damaged packet with a valid checksum is higher | That's bad: it tells us that the value of s1 will have hot-spots at | |||

than if all checksum values are equally likely." | 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 | Due to this inherent weakness, exacerbated by the fact that SCTP will | |||

first be used as a signaling transport protocol where signaling messages | first be used as a signaling transport protocol where signaling | |||

are usually less than 128 bytes, a new checksum algorithm is specified by | messages are usually less than 128 bytes, a new checksum algorithm is | |||

this document, replacing the current Adler-32 algorithm with CRC-32c. | specified by this document, replacing the current Adler-32 algorithm | |||

with CRC-32c. | ||||

1.1 Conventions | 1.1 Conventions | |||

The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD,SHOULD | The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, | |||

NOT, RECOMMENDED, NOT RECOMMENDED, MAY, and OPTIONAL, when they appear in | SHOULD,SHOULD NOT, RECOMMENDED, NOT RECOMMENDED, MAY, and OPTIONAL, | |||

this document, are to be interpreted as described in [RFC2119]. | when they appear in this document, are to be interpreted as described | |||

in [RFC2119]. | ||||

2 Checksum Procedures | Bit number order is defined in [RFC1700]. | |||

The procedures described in section 2.1 of this document MUST be | 2 Checksum Procedures | |||

followed, replacing the current checksum defined in [RFC2960]. | ||||

Furthermore any references within [RFC2960] to Adler-32 MUST be treated | The procedures described in section 2.1 of this document MUST be | |||

as a reference to CRC-32c. Section 2.1 of this document describes the | followed, replacing the current checksum defined in [RFC2960]. | |||

new calculation and verification procedures that MUST be followed. | ||||

2.1 Checksum Calculation | Furthermore any references within [RFC2960] to Adler-32 MUST be | |||

treated as a reference to CRC-32c. 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 strengthen the data | When sending an SCTP packet, the endpoint MUST strengthen the data | |||

integrity of the transmission by including the CRC-32c checksum | integrity of the transmission by including the CRC-32c checksum value | |||

value calculated on the packet, as described below. | calculated on the packet, as described below. | |||

After the packet is constructed (containing the SCTP common header | After the packet is constructed (containing the SCTP common header | |||

and one or more control or DATA chunks), the transmitter shall: | and one or more control or DATA chunks), the transmitter shall: | |||

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 | |||

header and all the chunks. | common header and all the chunks. | |||

3) Put the resultant value into the Checksum field in the common header, | 3) Put the resulting value into the Checksum field in the common | |||

and leave the rest of the bits unchanged. | header, and leave the rest of the bits unchanged. | |||

When an SCTP packet is received, the receiver MUST first check the | When an SCTP packet is received, the receiver MUST first check the | |||

CRC-32c checksum: | CRC-32c checksum: | |||

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 | ||||

with all '0's and calculate a CRC-32c value of the whole received | ||||

packet. And, | ||||

3) Verify that the calculated CRC-32c value is the same as the received | 2) Replace the 32 bits of the Checksum field in the received SCTP | |||

CRC-32c value. If not, the receiver MUST treat the packet as an | packet with all '0's and calculate a CRC-32c value of the whole | |||

invalid SCTP packet. | received packet. And, | |||

The default procedure for handling invalid SCTP packets is to silently | 3) Verify that the calculated CRC-32c value is the same as the | |||

discard them. | received CRC-32c value. If not, the receiver MUST treat the | |||

packet as an invalid SCTP packet. | ||||

Any hardware implementation SHOULD be done in a way that | The default procedure for handling invalid SCTP packets is to | |||

is verifiable by the sofware. | silently discard them. | |||

We define a 'reflected value' as one that is the opposite of the | Any hardware implementation SHOULD be done in a way that is | |||

normal bit order of the machine. The 32 bit CRC is | verifiable by the software. | |||

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. | ||||

The CRC is computed using a procedure similar to ETHERNET CRC [ITU32], | ||||

modified to reflect transport level usage. | ||||

CRC computation uses polynomial division. A message bit-string M | We define a 'reflected value' as one that is the opposite of the | |||

is transformed to a polynomial, M(X), and the CRC is calculated | normal bit order of the machine. The 32 bit CRC is calculated as | |||

from M(X) using polynomial arithmetic [Peterson 72]. | described for CRC-32c and uses the polynomial code 0x11EDC6F41 | |||

When CRCs are used at the link layer, the polynomial is derived from | (Castagnoli93) or x^32+x^28+x^27+x^26+x^25 | |||

on-the-wire bit ordering: the first bit `on the wire' is | +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. The | |||

the high-order coefficient. Since SCTP is a transport-level protocol, | CRC is computed using a procedure similar to ETHERNET CRC [ITU32], | |||

it cannot know the actual serial-media bit ordering. Moreover, | modified to reflect transport level usage. | |||

different links in the path between SCTP endpoints may use | ||||

different link-level bit orders) | ||||

A convention must therefore be established for mapping SCTP transport | ||||

messages to polynomials for purposes of CRC computation. | ||||

The bit-ordering for mapping SCTP messages to polynomials is | ||||

that bytes are taken most-significant first; but within each byte, | ||||

bits are taken least-significant first. The first byte of the | ||||

message provides the eight highest coefficients. | ||||

Within each byte, the least-significant SCTP bit gives the | ||||

most significant polynomial coefficient within that byte, and | ||||

the most-significant SCTP bit is the most significant polynomial | ||||

coefficient in that byte. (This bit ordering is sometimes | ||||

called `mirrored' or `reflected' [Williams93].) CRC polynomials | ||||

are to be transformed back into SCTP transport-level byte values | ||||

using a consistent mapping. | ||||

The SCTP transport-level CRC value should be calculated as follows: | CRC computation uses polynomial division. A message bit-string M is | |||

- CRC input data are assumed to a byte stream numbered from 0 | transformed to a polynomial, M(X), and the CRC is calculated from | |||

to N-1. | M(X) using polynomial arithmetic [Peterson 72]. | |||

- the transport-level byte-stream is mapped to a polynomial value. | ||||

An N-byte PDU with bytes 0 to N-1, is considered as | ||||

coefficients of a polynomial M(x) of order 8N-1, with | ||||

bit 0 of byte j being coefficient x^(8(N-j)-8), bit 7 of byte | ||||

j being coefficient x^(8(N-j)-1). | ||||

- the CRC remainder register is initialized with all 1s | ||||

and the CRC is computed with an algorithm that | ||||

simultaneously multiplies by x^32 and divides by the CRC | ||||

polynomial. | ||||

- the polynomial is multiplied by x^32 and divided by G(x), | ||||

the generator polynomial, producing a remainder R(x) of degree | ||||

less than or equal to 31. | ||||

- the coefficients of R(x) are considered a 32 bit sequence. | ||||

- the bit sequence is complemented. The resulting is the CRC | ||||

polynomial. | ||||

- The CRC polynomial is mapped back into SCTP transport-level | When CRCs are used at the link layer, the polynomial is derived from | |||

bytes. Coefficient of x^31 gives the value of bit 0 of | on-the-wire bit ordering: the first bit 'on the wire' is the high- | |||

SCTP byte 0, the coefficient of x^24 gives the value of | order coefficient. Since SCTP is a transport-level protocol, it | |||

bit 7 of byte 0. The coefficient of x^7 gives bit 0 of | cannot know the actual serial-media bit ordering. Moreover, | |||

byte 3 and the coefficient of x^0 gives bit 7 of byte 3. | different links in the path between SCTP endpoints may use different | |||

The resulting four-byte transport-level sequence is the | link-level bit orders. | |||

32-bit SCTP checksum value. | ||||

IMPLEMENTATION NOTE: Standards documents, textbooks, and vendor | A convention must therefore be established for mapping SCTP transport | |||

literature on CRCs often follow an alternative formulation, in which | messages to polynomials for purposes of CRC computation. The bit- | |||

the register used to hold the remainder of the long-division | ordering for mapping SCTP messages to polynomials is that bytes are | |||

algorithm is initialized to zero rather than all-1s, and instead the | taken most-significant first; but within each byte, bits are taken | |||

first 32 bits of the message are complemented. The long-division | least-significant first. The first byte of the message provides the | |||

algorithm used in our formulation is specified such that the the | eight highest coefficients. Within each byte, the least-significant | |||

initial multiplication by 2^32 and the long-division, into one | SCTP bit gives the most significant polynomial coefficient within | |||

simultaneous operation. For such algorithms, and for messages longer | that byte, and the most-significant SCTP bit is the least significant | |||

than 64 bits, the two specifications are precisely equivalent. That | polynomial coefficient in that byte. (This bit ordering is sometimes | |||

equivalence is the intent of this document. Implementors of SCTP are | called 'mirrored' or 'reflected' [Williams93].) CRC polynomials are | |||

warned that both specifications are to be found in the literature, | to be transformed back into SCTP transport-level byte values, using a | |||

sometimes with no restriction on the long-division algorithm. | consistent mapping. | |||

The choice of formulation in this document is to permit non-SCTP | ||||

usage, where the same CRC algorithm may be used to protect messages | ||||

shorter than 64 bits. | ||||

If SCTP could follow link level CRC use, the CRC would be computed | The SCTP transport-level CRC value should be calculated as follows: | |||

over the link-level bit-stream. The first bit on the link | ||||

mapping to the highest-order coefficient, and so on down to the | ||||

last link-level bit as the lowest-order coefficient. The CRC value | ||||

would be transmitted immediately after the input message as a link-level | ||||

`trailer'. The resulting link-level bit-stream would be | ||||

(M(X)x) * x^32) + (M(X)*x^32))/ G(x), which is divisible by G(X). | ||||

There would thus be a constant CRC remainder for `good' packets. | ||||

However, given that implementations of RFC2960 have already | ||||

proliferated, the IETF discussions considered that the benefit of | ||||

a `trailer' CRC did not outweigh the cost of making a very large | ||||

change in the protocol processing. Further, packets accepted by | ||||

the SCTP `header' CRC are in one-to-one correspondence with | ||||

packets accepted by a modified procedure using a `trailer' | ||||

CRC value, and where the SCTP common checksum header is set to zero | ||||

on transmission and is received as zero. | ||||

There may be a computational advantage in validating the Association | - CRC input data are assigned to a byte stream, numbered from 0 | |||

against the Verification Tag prior to performing a checksum as | to N-1. | |||

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. | ||||

3 Security Considerations | - the transport-level byte-stream is mapped to a polynomial | |||

value. An N-byte PDU with j bytes numbered 0 to N-1, is | ||||

considered as coefficients of a polynomial M(x) of order 8N-1, | ||||

with bit 0 of byte j being coefficient x^(8(N-j)-8), bit 7 of | ||||

byte j being coefficient x^(8(N-j)-1). | ||||

In general, the security considerations of RFC2960 apply to | - the CRC remainder register is initialized with all 1s and the | |||

the protocol with the new checksum as well. | CRC is computed with an algorithm that simultaneously | |||

multiplies by x^32 and divides by the CRC polynomial. | ||||

4 IANA Considerations | - the polynomial is multiplied by x^32 and divided by G(x), the | |||

generator polynomial, producing a remainder R(x) of degree less | ||||

than or equal to 31. | ||||

There are no IANA considerations required in this document. | - the coefficients of R(x) are considered a 32 bit sequence. | |||

5 Acknowledgments | - the bit sequence is complemented. The result is the CRC | |||

polynomial. | ||||

The authors would like to thank the following people that have | - The CRC polynomial is mapped back into SCTP transport-level | |||

provided comments and input on the checksum issue: | bytes. Coefficient of x^31 gives the value of bit 7 of SCTP | |||

byte 0, the coefficient of x^24 gives the value of bit 0 of | ||||

byte 0. The coefficient of x^7 gives bit 7 of byte 3 and the | ||||

coefficient of x^0 gives bit 0 of byte 3. The resulting four- | ||||

byte transport-level sequence is the 32-bit SCTP checksum | ||||

value. | ||||

Mark Adler, Ran Atkinson, Stephen Bailey, David Black, Scott | IMPLEMENTATION NOTE: Standards documents, textbooks, and vendor | |||

Bradner, Mikael Degermark, Laurent Glaude, Klaus Gradischnig, Alf | literature on CRCs often follow an alternative formulation, in which | |||

Heidermark, Jacob Heitz, Gareth Kiely, David Lehmann, Allision | the register used to hold the remainder of the long-division | |||

Mankin, Lyndon Ong, Craig Partridge, Vern Paxson, Kacheong Poon, | algorithm is initialized to zero rather than all-1s, and instead the | |||

Michael Ramalho, David Reed, Ian Rytina, Hanns Juergen Schwarzbauer, | first 32 bits of the message are complemented. The long-division | |||

Chip Sharp, Bill Sommerfeld, Michael Tuexen, Jim Williams, Jim Wendt, | algorithm used in our formulation is specified, such that the the | |||

Michael Welzl, Jonathan Wood, Lloyd Wood, Qiaobing Xie, La Monte | initial multiplication by 2^32 and the long-division are combined | |||

Yarroll. | into one simultaneous operation. For such algorithms, and for | |||

messages longer than 64 bits, the two specifications are precisely | ||||

equivalent. That equivalence is the intent of this document. | ||||

Special thanks to Dafna Scheinwald, Julian Satran Pat Thaler, Matt | Implementors of SCTP are warned that both specifications are to be | |||

Wakeley, and Vince Cavanna, for selection criteria of polynomials and | found in the literature, sometimes with no restriction on the long- | |||

examination of CRC polynomials, particularly CRC-32c [Castagnoli93]. | division algorithm. The choice of formulation in this document is to | |||

permit non-SCTP usage, where the same CRC algorithm may be used to | ||||

protect messages shorter than 64 bits. | ||||

Special thanks to Mr. Ross Williams and his document [Williams93]. | If SCTP could follow link level CRC use, the CRC would be computed | |||

This non-formal perspective on software aspects of CRCs furthered | over the link-level bit-stream. The first bit on the link mapping to | |||

understanding of authors previously unfamiliar with CRC computation. | the highest-order coefficient, and so on, down to the last link-level | |||

More formal treatments of [Blahut 94] or [Peterson 72], was | bit as the lowest-order coefficient. The CRC value would be | |||

also essential. | transmitted immediately after the input message as a link-level | |||

'trailer'. The resulting link-level bit-stream would be (M(X)x) * | ||||

x^32) + (M(X)*x^32))/ G(x), which is divisible by G(X). There would | ||||

thus be a constant CRC remainder for 'good' packets. However, given | ||||

that implementations of RFC 2960 have already proliferated, the IETF | ||||

discussions considered that the benefit of a 'trailer' CRC did not | ||||

outweigh the cost of making a very large change in the protocol | ||||

processing. Further, packets accepted by the SCTP 'header' CRC are | ||||

in one-to-one correspondence with packets accepted by a modified | ||||

procedure using a 'trailer' CRC value, and where the SCTP common | ||||

checksum header is set to zero on transmission and is received as | ||||

zero. | ||||

6 Authors' Addresses | 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. | ||||

Jonathan Stone | 3 Security Considerations | |||

Room 446, Mail code 9040 | ||||

Gates building 4A | ||||

Stanford, Ca 94305 | ||||

EMail: jonathan@dsg.stanford.edu | In general, the security considerations of RFC 2960 apply to the | |||

protocol with the new checksum as well. | ||||

Randall R. Stewart | 4 IANA Considerations | |||

24 Burning Bush Trail. | ||||

Crystal Lake, IL 60012 | ||||

USA | ||||

EMail: rrs@cisco.com | There are no IANA considerations required in this document. | |||

Douglas Otis | 5 Acknowledgments | |||

800 E. Middlefield | ||||

Mountain View, CA 94043 | ||||

USA | ||||

Email dotis@sanlight.net | The authors would like to thank the following people that have | |||

provided comments and input on the checksum issue: | ||||

7 References | Mark Adler, 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, Craig Partridge, Vern Paxson, Kacheong Poon, Michael Ramalho, | ||||

David Reed, Ian Rytina, Hanns Juergen Schwarzbauer, Chip Sharp, Bill | ||||

Sommerfeld, Michael Tuexen, Jim Williams, Jim Wendt, Michael Welzl, | ||||

Jonathan Wood, Lloyd Wood, Qiaobing Xie, La Monte Yarroll. | ||||

[Castagnoli93] G. Castagnoli, S. Braeuer and M. Herrman, | Special thanks to Dafna Scheinwald, Julian Satran, Pat Thaler, Matt | |||

"Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity | Wakeley, and Vince Cavanna, for selection criteria of polynomials and | |||

Bits", IEEE Transactions on Communications, Vol. 41, No. 6, June 1993 | examination of CRC polynomials, particularly CRC-32c [Castagnoli93]. | |||

[McKee75] H. McKee, "Improved {CRC} techniques detects erroneous | Special thanks to Mr. Ross Williams and his document [Williams93]. | |||

leading and trailing 0's in transmitted data blocks", | This non-formal perspective on software aspects of CRCs furthered | |||

Computer Design Volume 14 Number 10 Pages 102-4,106, | understanding of authors previously unfamiliar with CRC computation. | |||

October 1975 | More formal treatments of [Blahut 94] or [Peterson 72], was also | |||

essential. | ||||

[RFC2026] Bradner, S., "The Internet Standards Process -- Revision | 6 References | |||

3", BCP 9, RFC 2026, October 1996. | ||||

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | [Castagnoli93] G. Castagnoli, S. Braeuer and M. Herrman, | |||

Requirement Levels", BCP 14, RFC 2119, March 1997. | "Optimization of Cyclic Redundancy-Check Codes with | |||

24 and 32 Parity Bits", IEEE Transactions on | ||||

Communications, Vol. 41, No. 6, June 1993 | ||||

[RFC2960] R. R. Stewart, Q. Xie, K. Morneault, C. Sharp, | [McKee75] H. McKee, "Improved {CRC} techniques detects | |||

H. J. Schwarzbauer, T. Taylor, I. Rytina, M. Kalla, L. Zhang, | erroneous leading and trailing 0's in transmitted | |||

and, V. Paxson, "Stream Control Transmission Protocol," RFC | data blocks", Computer Design Volume 14 Number 10 | |||

2960, October 2000. | Pages 102-4,106, October 1975 | |||

[ITU32] ITU-T Recommendation V.42, "Error-correcting | [RFC1700] Reynolds, J. and J. Postel, "ASSIGNED NUMBERS", RFC | |||

procedures for DCEs using asynchronous-to-synchronous | 1700, October 1994. | |||

conversion", section 8.1.1.6.2, October 1996. | ||||

7.1 Informative References | [RFC2026] Bradner, S., "The Internet Standards Process -- | |||

Revision 3", BCP 9, RFC 2026, October 1996. | ||||

[STONE] Stone, J., "Checksums in the Internet", Doctoral | [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | |||

dissertation - August 2001 | Requirement Levels", BCP 14, RFC 2119, March 1997. | |||

[Williams93] Williams, R., "A PAINLESS GUIDE TO CRC ERROR DETECTION | [RFC2960] Stewart, R., Xie, Q., Morneault, K., Sharp, C., | |||

ALGORITHMS" - Internet publication, August 1993, | Schwarzbauer, H., Taylor, T., Rytina, I., Kalla, M., | |||

http://www.geocities.com/SiliconValley/Pines/8659/crc.htm. | Zhang, L. and V. Paxson, "Stream Control Transmission | |||

Protocol," RFC 2960, October 2000. | ||||

[Blahut 1994], R.E. Blahut, Theory and Practice of Error Control | [ITU32] ITU-T Recommendation V.42, "Error-correcting | |||

Codes, Addison-Wesley, 1994. | procedures for DCEs using asynchronous-to-synchronous | |||

conversion", section 8.1.1.6.2, October 1996. | ||||

[Easics 2001]. http://www.easics.be/webtools/crctool. Online tools | 7.1 Informative References | |||

for synthesis of CRC Verilog and VHDL. | ||||

[Feldmeier 95], David C. Feldmeier, Fast software implementation of | [STONE] Stone, J., "Checksums in the Internet", Doctoral | |||

error detection codes, IEEE Transactions on Networking, vol 3 no 6, | dissertation - August 2001. | |||

pp 640-651, December, 1995. | ||||

[Glaise 1997] R. J. Glaise, A two-step computation of cyclic | [Williams93] Williams, R., "A PAINLESS GUIDE TO CRC ERROR | |||

redundancy code CRC-32 for ATM networks, IBM Journal of Research and | DETECTION ALGORITHMS" - Internet publication, August | |||

Development} vol 41 no 6, 1997. URL= | 1993, | |||

http://www.research.ibm.com/journal/rd/416/glaise.html. | http://www.geocities.com/SiliconValley/Pines/ | |||

8659/crc.htm. | ||||

[Prange 1957], E. Prange, Cyclic Error-Correcting codes in two | [Blahut 1994] R.E. Blahut, Theory and Practice of Error Control | |||

symbols, Technical report AFCRC-TN-57-103, Air Force Cambridge | Codes, Addison-Wesley, 1994. | |||

Research Center, Cambridge, Mass. 1957. | ||||

[Peterson 1972], W. W. Peterson and E.J Weldon, Error Correcting | [Easics 2001] http://www.easics.be/webtools/crctool. Online tools | |||

Codes, 2nd. edition, MIT Press, Cambridge, Massachusetts. | for synthesis of CRC Verilog and VHDL. | |||

[Shie2001] Ming-Der Shieh et. al, A Systematic Approach for Parallel | [Feldmeier 95] David C. Feldmeier, Fast software implementation of | |||

CRC Computations. Journal of Information Science and Engineering, | error detection codes, IEEE Transactions on | |||

Vol.17 No.3, pp.445-461 | Networking, vol 3 no 6, pp 640-651, December, 1995. | |||

[Sprachman2001] Michael Sprachman, Automatic Generation of Parallel | [Glaise 1997] R. J. Glaise, A two-step computation of cyclic | |||

CRC Circuits, IEEE Design & Test May-June 2001 | redundancy code CRC-32 for ATM networks, IBM Journal | |||

of Research and Development} vol 41 no 6, 1997. | ||||

http://www.research.ibm.com/journal/rd/416/ | ||||

glaise.html. | ||||

8 Appendix | [Prange 1957] E. Prange, Cyclic Error-Correcting codes in two | |||

symbols, Technical report AFCRC-TN-57-103, Air Force | ||||

Cambridge Research Center, Cambridge, Mass. 1957. | ||||

This appendix is for information only and is NOT part of the | [Peterson 1972] W. W. Peterson and E.J Weldon, Error Correcting | |||

standard. | Codes, 2nd. edition, MIT Press, Cambridge, | |||

Massachusetts. | ||||

The anticipated deployment of SCTP ranges over several orders of | [Shie2001] Ming-Der Shieh et. al, A Systematic Approach for | |||

magnitude of link speed: from cellular-power telephony devices at | Parallel CRC Computations. Journal of Information | |||

tens of kilobits, to local links at tens of gigabits. Implementors | Science and Engineering, Vol.17 No.3, pp.445-461 | |||

of SCTP should consider their link speed and choose, from the wide | ||||

range of CRC implementations, one which matches their own design | ||||

point for size, cost, and throughput. Many techniques for computing | ||||

CRCs are known. This Appendix surveys just a few, to give a feel for | ||||

the range of techniques available. | ||||

CRCs are derived from early work by Prange in the 1950s [Prange 57]. | [Sprachman2001] Michael Sprachman, Automatic Generation of Parallel | |||

The theory underlying CRCs and choice of generator polynomial can be | CRC Circuits, IEEE Design & Test May-June 2001 | |||

introduced by either via the theory of Galois fields [Blahut 94] | ||||

or as ideals of an algebra over cyclic codes [cite Peterson 72]. | ||||

One of the simplest techniques is direct bit-serial hardware | Appendix | |||

implementations, using the generator polynomial as the taps of a | ||||

linear feedback shift register (LSFR). LSFR computation follows | ||||

directly from the mathematics, and is generally attributed to Prange. | ||||

Tools exist which, a CRC generator polynomial, will produce | ||||

synthesizable Verilog code for CRC hardware [Easics 2001]. | ||||

Since LSFRs do not scale well in speed, a variety of other | This appendix is for information only and is NOT part of the | |||

techniques have been explored. One technique exploits the fact that | standard. | |||

the divisor of the polynomial long-division, G, is known in | ||||

advance. It is thus possible to pre-compute lookup tables giving the | ||||

polynomial remainder of multiple input bits --- typically 2, 4, or 8 | ||||

bits of input at a time. This technique can be used either in | ||||

software or in hardware. Software to compute lookup tables yielding | ||||

2, 4, or 8 bits of result is freely available. [Williams93] | ||||

For multi-gigabit links, the above techniques may still not be fast | The anticipated deployment of SCTP ranges over several orders of | |||

enough. One technique for computing CRCS at OC-48 rates is | magnitude of link speed: from cellular-power telephony devices at | |||

`two-stage' CRC computation [Glaise 1997]. Here, some multiple | tens of kilobits, to local links at tens of gigabits. Implementors | |||

of G(x), G(x)H(x), is chosen so as to minimize the number of nonzero | of SCTP should consider their link speed and choose, from the wide | |||

coefficients, or weight, of the product G(x)H(x). The low weight of | range of CRC implementations, one which matches their own design | |||

the product polynomial makes it susceptible to efficient hardware | point for size, cost, and throughput. Many techniques for computing | |||

divide-by-constant implementations. This first stage gives M(x) / | CRCs are known. This Appendix surveys just a few, to give a feel for | |||

(G(x)H(x)) as its result. The second stage then divides the result | the range of techniques available. | |||

of the first stage by H(x), yielding (M(x) / (G(x)H(x))) / H(x). If | ||||

H(x) is also relatively prime to G(x), this gives M(x)/G(x). | ||||

Further developments on this approach can be found in [Shie2001] and | ||||

[Sprachman2001]. | ||||

The literature also includes a variety of software CRC | CRCs are derived from early work by Prange in the 1950s [Prange 57]. | |||

implementations. One approach is to use carefully-tuned assembly | The theory underlying CRCs and choice of generator polynomial can be | |||

code for direct polynomial division. [Feldmeier 95] reports that for | introduced by either the theory of Galois fields [Blahut 94] or as | |||

low-weight polynomials, tuned polynomial arithmetic gives higher | ideals of an algebra over cyclic codes [cite Peterson 72]. | |||

throughput than table-lookup algorithms. Even within table-lookup | ||||

algorithms, the size of the table can be tuned, either for total | ||||

cache footprint, or (for space-restricted environments) to minimize | ||||

total size. | ||||

Implementors should keep in mind the bit ordering described in | One of the simplest techniques is direct bit-serial hardware | |||

Section 2: the ordering of bits within bytes for computing CRCs in | implementations, using the generator polynomial as the taps of a | |||

SCTP is the least significant bit of each byte is the | linear feedback shift register (LSFR). LSFR computation follows | |||

most-significant polynomial coefficient(and vice-versa). This | directly from the mathematics, and is generally attributed to Prange. | |||

`reflected' SCTP CRC bit ordering matches on-the-wire bit order for | Tools exist which, a CRC generator polynomial, will produce | |||

Ethernet and other serial media, but is the reverse of traditional | synthesizable Verilog code for CRC hardware [Easics 2001]. | |||

Internet bit ordering. | ||||

One technique to accommodate this bit-reversal can be explained as | Since LSFRs do not scale well in speed, a variety of other techniques | |||

follows: sketch out a hardware implementation assuming the bits are | have been explored. One technique exploits the fact that the divisor | |||

in CRC bit order; then perform a left-to-right inversion (mirror | of the polynomial long-division, G, is known in advance. It is thus | |||

image) on the entire algorithm. (We defer for a moment the issue of | possible to pre-compute lookup tables giving the polynomial remainder | |||

byte order within words.) Then compute that "mirror image" in | of multiple input bits --- typically 2, 4, or 8 bits of input at a | |||

software. The CRC from the ``mirror image'' algorithm will be the | time. This technique can be used either in software or in hardware. | |||

bit-reversal of a correct hardware implementation. When the | Software to compute lookup tables yielding 2, 4, or 8 bits of result | |||

link-level media sends each byte, the byte is sent in the reverse of | is freely available. [Williams93] | |||

the host CPU bit-order. Serialization of each byte of the | ||||

``reflected'' CRC value re-reverses the bit order, so in the end, | ||||

each byte will be transmitted on-the-wire in the specified bit | ||||

order. | ||||

The following non-normative sample code is taken from an open-source | For multi-gigabit links, the above techniques may still not be fast | |||

CRC generator [Williams93] using the ``mirroring'' technique | enough. One technique for computing CRCS at OC-48 rates is 'two- | |||

and yielding a lookup table for SCTP CRC32-c with 256 entries, each | stage' CRC computation [Glaise 1997]. Here, some multiple of G(x), | |||

32 bits wide. While neither especially slow nor especially fast, as | G(x)H(x), is chosen so as to minimize the number of nonzero | |||

software table-lookup CRCs go, it has the advantage of working on | coefficients, or weight, of the product G(x)H(x). The low weight of | |||

both big-endian and little-endian CPUs, using the same (host-order) | the product polynomial makes it susceptible to efficient hardware | |||

lookup tables, and using only the pre-defined ntohl() and htonl() | divide-by-constant implementations. This first stage gives M(x)/ | |||

operations. The code is somewhat modified from [Williams93], to | (G(x)H(x)), as its result. The second stage then divides the result | |||

ensure portability between big-endian and little-endian | of the first stage by H(x), yielding (M(x)/(G(x)H(x)))/H(x). If H(x) | |||

architectures. (Note that if the byte endian-ness of the target | is also relatively prime to G(x), this gives M(x)/G(x). Further | |||

architecture is known to be little-endian the final bit-reversal and | developments on this approach can be found in [Shie2001] and | |||

byte-reversal steps can be folded into a single operation.) | [Sprachman2001]. | |||

/*************************************************************/ | The literature also includes a variety of software CRC | |||

/* Note Definition for Ross Williams table generator would */ | implementations. One approach is to use a carefully-tuned assembly | |||

/* be: TB_WIDTH=4, TB_POLLY=0x1EDC6F41, TB_REVER=TRUE */ | code for direct polynomial division. [Feldmeier 95] reports that for | |||

/* For Mr. Williams direct calculation code use the settings */ | low-weight polynomials, tuned polynomial arithmetic gives higher | |||

/* cm_width=32, cm_poly=0x1EDC6F41, cm_init=0xFFFFFFFF, */ | throughput than table-lookup algorithms. Even within table-lookup | |||

/* cm_refin=TRUE, cm_refot=TRUE, cm_xorort=0x00000000 */ | algorithms, the size of the table can be tuned, either for total | |||

/*************************************************************/ | cache footprint, or (for space-restricted environments) to minimize | |||

total size. | ||||

/* Example of the crc table file */ | Implementors should keep in mind, the bit ordering described in | |||

#ifndef __crc32cr_table_h__ | Section 2: the ordering of bits within bytes for computing CRCs in | |||

#define __crc32cr_table_h__ | SCTP is the least significant bit of each byte is the most- | |||

significant polynomial coefficient(and vice-versa). This 'reflected' | ||||

SCTP CRC bit ordering matches on-the-wire bit order for Ethernet and | ||||

other serial media, but is the reverse of traditional Internet bit | ||||

ordering. | ||||

#define CRC32C_POLY 0x1EDC6F41 | One technique to accommodate this bit-reversal can be explained as | |||

#define CRC32C(c,d) (c=(c>>8)^crc_c[(c^(d))&0xFF]) | follows: sketch out a hardware implementation, assuming the bits are | |||

in CRC bit order; then perform a left-to-right inversion (mirror | ||||

image) on the entire algorithm. (We defer, for a moment, the issue | ||||

of byte order within words.) Then compute that "mirror image" in | ||||

software. The CRC from the "mirror image" algorithm will be the | ||||

bit-reversal of a correct hardware implementation. When the link- | ||||

level media sends each byte, the byte is sent in the reverse of the | ||||

host CPU bit-order. Serialization of each byte of the "reflected" | ||||

CRC value re-reverses the bit order, so in the end, each byte will be | ||||

transmitted on-the-wire in the specified bit order. | ||||

unsigned long crc_c[256] = | The following non-normative sample code is taken from an open-source | |||

{ | CRC generator [Williams93], using the "mirroring" technique and | |||

0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L, | yielding a lookup table for SCTP CRC32-c with 256 entries, each 32 | |||

0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL, | bits wide. While neither especially slow nor especially fast, as | |||

0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL, | software table-lookup CRCs go, it has the advantage of working on | |||

0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L, | both big-endian and little-endian CPUs, using the same (host-order) | |||

0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL, | lookup tables, and using only the pre-defined ntohl() and htonl() | |||

0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L, | operations. The code is somewhat modified from [Williams93], to | |||

0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L, | ensure portability between big-endian and little-endian | |||

0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL, | architectures. (Note that if the byte endian-ness of the target | |||

0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL, | architecture is known to be little-endian the final bit-reversal and | |||

0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L, | byte-reversal steps can be folded into a single operation.) | |||

0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L, | ||||

0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL, | ||||

0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L, | ||||

0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL, | ||||

0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL, | ||||

0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L, | ||||

0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L, | ||||

0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L, | ||||

0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L, | ||||

0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L, | ||||

0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L, | ||||

0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L, | ||||

0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L, | ||||

0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L, | ||||

0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L, | ||||

0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L, | ||||

0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L, | ||||

0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L, | ||||

0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L, | ||||

0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L, | ||||

0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L, | ||||

0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L, | ||||

0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL, | ||||

0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L, | ||||

0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L, | ||||

0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL, | ||||

0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L, | ||||

0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL, | ||||

0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL, | ||||

0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L, | ||||

0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L, | ||||

0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL, | ||||

0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL, | ||||

0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L, | ||||

0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL, | ||||

0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L, | ||||

0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L, | ||||

0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL, | ||||

0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L, | ||||

0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL, | ||||

0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL, | ||||

0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L, | ||||

0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL, | ||||

0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L, | ||||

0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L, | ||||

0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL, | ||||

0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL, | ||||

0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L, | ||||

0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L, | ||||

0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL, | ||||

0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L, | ||||

0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL, | ||||

0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL, | ||||

0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L, | ||||

}; | ||||

#endif | /*************************************************************/ | |||

/* Note Definition for Ross Williams table generator 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 table build routine */ | /* Example of the crc table file */ | |||

#ifndef __crc32cr_table_h__ | ||||

#define __crc32cr_table_h__ | ||||

#include <stdio.h> | #define CRC32C_POLY 0x1EDC6F41 | |||

#include <stdlib.h> | #define CRC32C(c,d) (c=(c>>8)^crc_c[(c^(d))&0xFF]) | |||

#define OUTPUT_FILE "crc32cr.h" | unsigned long crc_c[256] = | |||

#define CRC32C_POLY 0x1EDC6F41L | { | |||

FILE *tf; | 0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L, | |||

0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL, | ||||

0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL, | ||||

0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L, | ||||

0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL, | ||||

0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L, | ||||

0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L, | ||||

0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL, | ||||

0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL, | ||||

0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L, | ||||

0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L, | ||||

0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL, | ||||

0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L, | ||||

0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL, | ||||

0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL, | ||||

0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L, | ||||

0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L, | ||||

0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L, | ||||

0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L, | ||||

0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L, | ||||

0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L, | ||||

0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L, | ||||

0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L, | ||||

0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L, | ||||

0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L, | ||||

0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L, | ||||

0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L, | ||||

0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L, | ||||

0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L, | ||||

0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L, | ||||

0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L, | ||||

0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L, | ||||

0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL, | ||||

0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L, | ||||

0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L, | ||||

0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL, | ||||

0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L, | ||||

0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL, | ||||

0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL, | ||||

0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L, | ||||

0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L, | ||||

0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL, | ||||

0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL, | ||||

0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L, | ||||

0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL, | ||||

0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L, | ||||

0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L, | ||||

0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL, | ||||

0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L, | ||||

0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL, | ||||

0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL, | ||||

0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L, | ||||

0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL, | ||||

0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L, | ||||

0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L, | ||||

0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL, | ||||

0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL, | ||||

0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L, | ||||

0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L, | ||||

0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL, | ||||

0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L, | ||||

0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL, | ||||

0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL, | ||||

0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L, | ||||

}; | ||||

unsigned long | #endif | |||

reflect_32 (unsigned long b) | ||||

{ | ||||

int i; | ||||

unsigned long rw = 0L; | ||||

for (i = 0; i < 32; i++){ | /* Example of table build routine */ | |||

if (b & 1) | ||||

rw |= 1 << (31 - i); | ||||

b >>= 1; | ||||

} | ||||

return (rw); | ||||

} | ||||

unsigned long | #include <stdio.h> | |||

build_crc_table (int index) | #include <stdlib.h> | |||

{ | ||||

int i; | ||||

unsigned long rb; | ||||

rb = reflect_32 (index); | #define OUTPUT_FILE "crc32cr.h" | |||

#define CRC32C_POLY 0x1EDC6F41L | ||||

FILE *tf; | ||||

unsigned long | ||||

reflect_32 (unsigned long b) | ||||

{ | ||||

int i; | ||||

unsigned long rw = 0L; | ||||

for (i = 0; i < 8; i++){ | for (i = 0; i < 32; i++){ | |||

if (rb & 0x80000000L) | if (b & 1) | |||

rb = (rb << 1) ^ CRC32C_POLY; | rw |= 1 << (31 - i); | |||

else | b >>= 1; | |||

rb <<= 1; | } | |||

} | return (rw); | |||

return (reflect_32 (rb)); | } | |||

} | ||||

main () | unsigned long | |||

{ | build_crc_table (int index) | |||

int i; | { | |||

int i; | ||||

unsigned long rb; | ||||

printf ("\nGenerating CRC-32c table file <%s>\n", OUTPUT_FILE); | rb = reflect_32 (index); | |||

if ((tf = fopen (OUTPUT_FILE, "w")) == NULL){ | ||||

printf ("Unable to open %s\n", OUTPUT_FILE); | ||||

exit (1); | ||||

} | ||||

fprintf (tf, "#ifndef __crc32cr_table_h__\n"); | ||||

fprintf (tf, "#define __crc32cr_table_h__\n\n"); | ||||

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, "\nunsigned long crc_c[256] =\n{\n"); | ||||

for (i = 0; i < 256; i++){ | ||||

fprintf (tf, "0x%08lXL, ", build_crc_table (i)); | ||||

if ((i & 3) == 3) | ||||

fprintf (tf, "\n"); | ||||

} | ||||

fprintf (tf, "};\n\n#endif\n"); | ||||

if (fclose (tf) != 0) | for (i = 0; i < 8; i++){ | |||

printf ("Unable to close <%s>." OUTPUT_FILE); | if (rb & 0x80000000L) | |||

rb = (rb << 1) ^ CRC32C_POLY; | ||||

else | else | |||

printf ("\nThe CRC-32c table has been written to <%s>.\n", | rb <<= 1; | |||

OUTPUT_FILE); | } | |||

} | return (reflect_32 (rb)); | |||

} | ||||

/* Example of crc insertion */ | main () | |||

{ | ||||

int i; | ||||

#include "crc32cr.h" | printf ("\nGenerating CRC-32c table file <%s>\n", OUTPUT_FILE); | |||

if ((tf = fopen (OUTPUT_FILE, "w")) == NULL){ | ||||

printf ("Unable to open %s\n", OUTPUT_FILE); | ||||

exit (1); | ||||

} | ||||

fprintf (tf, "#ifndef __crc32cr_table_h__\n"); | ||||

fprintf (tf, "#define __crc32cr_table_h__\n\n"); | ||||

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, "\nunsigned long crc_c[256] =\n{\n"); | ||||

for (i = 0; i < 256; i++){ | ||||

fprintf (tf, "0x%08lXL, ", build_crc_table (i)); | ||||

if ((i & 3) == 3) | ||||

fprintf (tf, "\n"); | ||||

} | ||||

fprintf (tf, "};\n\n#endif\n"); | ||||

unsigned long | if (fclose (tf) != 0) | |||

generate_crc32c(unsigned char *buffer, unsigned int length) | printf ("Unable to close <%s>." OUTPUT_FILE); | |||

{ | else | |||

unsigned int i; | printf ("\nThe CRC-32c table has been written to <%s>.\n", | |||

unsigned long crc32 = ~0L; | OUTPUT_FILE); | |||

unsigned long result; | } | |||

unsigned char byte0,byte1,byte2,byte3; | ||||

for (i = 0; i < length; i++){ | /* Example of crc insertion */ | |||

CRC32C(crc32, buffer[i]); | ||||

} | ||||

result = ~crc32; | ||||

/* result now holds the negated polynomial remainder; | #include "crc32cr.h" | |||

* since the table and algorithm is "reflected" [williams95]. | ||||

* That is, result has the same value as if we mapped the message | ||||

* to a polynomial, computed the host-bit-order polynomial | ||||

* remainder, performed final negation, then did an end-for-end | ||||

* bit-reversal. | ||||

* Note that a 32-bit bit-reversal is identical to four inplace | ||||

* 8-bit reversals followed by an end-for-end byteswap. | ||||

* In other words, the bytes of each bit are in the right order, | ||||

* but the bytes have been byteswapped. So we now do an explicit | ||||

* byteswap. On a little-endian machine, this byteswap and | ||||

* the final ntohl cancel out and could be elided. | ||||

*/ | ||||

byte0 = result & 0xff; | unsigned long | |||

byte1 = (result>>8) & 0xff; | generate_crc32c(unsigned char *buffer, unsigned int length) | |||

byte2 = (result>>16) & 0xff; | { | |||

byte3 = (result>>24) & 0xff; | unsigned int i; | |||

unsigned long crc32 = ~0L; | ||||

unsigned long result; | ||||

unsigned char byte0,byte1,byte2,byte3; | ||||

crc32 = ((byte0 << 24) | | for (i = 0; i < length; i++){ | |||

(byte1 << 16) | | CRC32C(crc32, buffer[i]); | |||

(byte2 << 8) | | } | |||

byte3); | result = ~crc32; | |||

return ( crc32 ); | ||||

} | ||||

int | /* result now holds the negated polynomial remainder; | |||

insert_crc32(unsigned char *buffer, unsigned int length) | * since the table and algorithm is "reflected" [williams95]. | |||

{ | * That is, result has the same value as if we mapped the message | |||

SCTP_message *message; | * to a polynomial, computed the host-bit-order polynomial | |||

unsigned long crc32; | * remainder, performed final negation, then did an end-for-end | |||

message = (SCTP_message *) buffer; | * bit-reversal. | |||

message->common_header.checksum = 0L; | * Note that a 32-bit bit-reversal is identical to four inplace | |||

crc32 = generate_crc32c(buffer,length); | * 8-bit reversals followed by an end-for-end byteswap. | |||

/* and insert it into the message */ | * In other words, the bytes of each bit are in the right order, | |||

message->common_header.checksum = htonl(crc32); | * but the bytes have been byteswapped. So we now do an explicit | |||

return 1; | * byteswap. On a little-endian machine, this byteswap and | |||

} | * the final ntohl cancel out and could be elided. | |||

*/ | ||||

int | byte0 = result & 0xff; | |||

validate_crc32(unsigned char *buffer, unsigned int length) | byte1 = (result>>8) & 0xff; | |||

{ | byte2 = (result>>16) & 0xff; | |||

SCTP_message *message; | byte3 = (result>>24) & 0xff; | |||

unsigned int i; | crc32 = ((byte0 << 24) | | |||

unsigned long original_crc32; | (byte1 << 16) | | |||

unsigned long crc32 = ~0L; | (byte2 << 8) | | |||

byte3); | ||||

return ( crc32 ); | ||||

} | ||||

/* save and zero checksum */ | int | |||

message = (SCTP_message *) buffer; | insert_crc32(unsigned char *buffer, unsigned int length) | |||

original_crc32 = ntohl(message->common_header.checksum); | { | |||

message->common_header.checksum = 0L; | SCTP_message *message; | |||

crc32 = generate_crc32c(buffer,length); | unsigned long crc32; | |||

return ((original_crc32 == crc32)? 1 : -1); | message = (SCTP_message *) buffer; | |||

} | message->common_header.checksum = 0L; | |||

crc32 = generate_crc32c(buffer,length); | ||||

/* and insert it into the message */ | ||||

message->common_header.checksum = htonl(crc32); | ||||

return 1; | ||||

} | ||||

Full Copyright Statement | int | |||

validate_crc32(unsigned char *buffer, unsigned int length) | ||||

{ | ||||

SCTP_message *message; | ||||

unsigned int i; | ||||

unsigned long original_crc32; | ||||

unsigned long crc32 = ~0L; | ||||

Copyright (C) The Internet Society (2001). All Rights Reserved. | /* save and zero checksum */ | |||

message = (SCTP_message *) buffer; | ||||

original_crc32 = ntohl(message->common_header.checksum); | ||||

message->common_header.checksum = 0L; | ||||

crc32 = generate_crc32c(buffer,length); | ||||

return ((original_crc32 == crc32)? 1 : -1); | ||||

} | ||||

Authors' Addresses | ||||

This document and translations of it may be copied and furnished to | Jonathan Stone | |||

others, and derivative works that comment on or otherwise explain it or | Room 446, Mail code 9040 | |||

assist in its implementation may be prepared, copied, published and | Gates building 4A | |||

distributed, in whole or in part, without restriction of any kind, | Stanford, Ca 94305 | |||

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 | EMail: jonathan@dsg.stanford.edu | |||

revoked by the Internet Society or its successors or assigns. | ||||

This document and the information contained herein is provided on an "AS | Randall R. Stewart | |||

IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK | 24 Burning Bush Trail. | |||

FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT | Crystal Lake, IL 60012 | |||

LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT | USA | |||

INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR | ||||

FITNESS FOR A PARTICULAR PURPOSE. | ||||

Funding for the RFC Editor function is currently provided by the | EMail: rrs@cisco.com | |||

Internet Society. | ||||

Douglas Otis | ||||

800 E. Middlefield | ||||

Mountain View, CA 94043 | ||||

USA | ||||

EMail: dotis@sanlight.net | ||||

Full Copyright Statement | ||||

Copyright (C) The Internet Society (2002). 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. | ||||

Acknowledgement | ||||

Funding for the RFC Editor function is currently provided by the | ||||

Internet Society. | ||||

End of changes. 118 change blocks. | ||||

588 lines changed or deleted | | 567 lines changed or added | ||

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ |