Performance of checksums and CRCs over real data

ABSTRACT

Checksum and CRC algorithms have historically been studied under the assumption that the data fed to the algorithms was entirely random. This paper examines the behavior of checksums and CRCs over real data from various UNIX® file systems. We show that, when given real data in small to modest pieces (e.g., 48 bytes), all the checksum algorithms have skewed distributions. In one dramatic case, 0.01% of the check values appeared nearly 19% of the time. These results have implications for CRCs and checksums when applied to real data. They also cause a spectacular failure rate for the both TCP and Fletcher's checksums when trying to detect certain types of packet splices.

REFERENCES

• 1: J. Fletcher, "An Arithmetic Checksum for Serial Transmissions,'' IEEE Trans. on Communication, Vol. 30, No. 1, January 1982, pp. 247-252.
• 2: Z. Wang and J. Crowcroft, "SEAL Detects Cell Misordering," IEEE Network Magazine, Vol. 6, No. 4, July 1992, pp. 8-19.
• 3: Daniel H. Greene , Bryan Lyles, Reliability of Adaptation Layers, Proceedings of the IFIP WG6.1/WG6.4 Third International Workshop on Protocols for High-Speed Networks III, p.185-200, May 13-15, 1992
• 4: J. Postel, '~Transmission Control Protocol," Internet Request for Comments No. 793, September 1981.
• 5: R. Braden, D. Borman, and C. Partridge, "Computing the Internet Checksum", Internet Request for Comments No. 1071, September 1988. (Updated by RFCs 1141 and 1624).
• 6: Joseph L. Hammond, Jr, et al., "Development of a Transmission Error Model and an Error Control Model," Georgia Institute of Technology, prepared for Rome Air Development Center, May 1975.
• 7: William W. Plummer, "TCP Checksum Function Design," Internet Engineering Note No. 45, June 1978. Reprinted in reference {5}.
• 8: Anastase Nakassis, Fletcher's error detection algorithm: how to implement it efficiently and how toavoid the most common pitfalls, ACM SIGCOMM Computer Communication Review, v.18 n.5, p.63-88, October 1988 [doi>10.1145/53644.53648]
• 9: K. Sklower, Improving the efficiency of the OSI checksum calculation, ACM SIGCOMM Computer Communication Review, v.19 n.5, p.32-43, Oct. 1989 [doi>10.1145/74681.74684]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  E. Data

General Terms:
Algorithms, Experimentation, Performance