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. 1 J. Fletcher, "An Arithmetic Checksum for Serial Transmissions,'' IEEE Trans. on Communication, Vol. 30, No. 1, January 1982, pp. 247-252.]]
2. 2 Z. Wang and J. Crowcroft, "SEAL Detects Cell Misordering," IEEE Network Magazine, Vol. 6, No. 4, July 1992, pp. 8-19.]]
3. 3 D. Greene and B. Lyles, "Reliability of Adaptation Layers," Protocols for High-Speed Networks, III (Proc. IFIP 6.1/6.4 Workshop), ed. B. Pehrson, P. Gunningberg, and S. Pink, 1992.]]
4. 4 J. Postel, '~Transmission Control Protocol," Internet Request for Comments No. 793, September 1981.]]
5. 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. 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. 7 William W. Plummer, "TCP Checksum Function Design," Internet Engineering Note No. 45, June 1978. Reprinted in reference {5}.]]
8. 8 Anastase Nakassis, "Fletcher's Error Detection Algorithm: How to implement it efficientlyy and how to avoid the most common pitfalls," ACM SIGCOMM Computer Communication Review, Vol. 18, No. 5, October 1988, pp. 63-88.]]
9. 9 Keith Sklower, "Improving the Efficiency of the OSI Checksum Calculation," ACM SIGCOMM Computer Communication Review, Vol. 19, No. 5, October 1989, pp. 44-55.]]

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Hardware

  • Communication hardware, interfaces and storage

• Mathematics of computing

  • Information theory

    • Coding theory

• Networks

  • Network performance evaluation

  • Network protocols

• Security and privacy

  • Cryptography

    • Mathematical foundations of cryptography