Checksum
A checksum is a compact value derived from a block of digital data for the purpose of detecting accidental changes introduced during storage or transmission. The sender or recording system computes the value from the original data, while the receiving or reading system recomputes it from the data obtained. A disagreement between the two values establishes that the protected data or the stored checksum has changed. Agreement establishes only that the data belongs to the set of inputs producing that checksum, because multiple inputs necessarily share the same result when the checksum is shorter than the input.
Checksums form part of the broader subject of error detection and correction. They differ from error-correcting codes, which contain enough structured redundancy to reconstruct at least some corrupted data. They also differ from cryptographic hash functions, whose design addresses deliberate manipulation by an adversary rather than accidental corruption alone.
Mathematical basis
A checksum algorithm maps an input of arbitrary or bounded length to a fixed-size set of values. For a checksum containing (n) bits, the output space contains at most (2^n) distinct values. If the input space contains more than (2^n) possible messages, the pigeonhole principle guarantees the existence of collisions, meaning distinct messages with identical checksums.
The simplest constructions interpret the input as a sequence of fixed-width words and compute their sum under modular arithmetic. For words (w_1,w_2,\ldots,w_k) and modulus (M), a basic additive checksum has the form
[ C=\left(\sum_{i=1}^{k} w_i\right)\bmod M. ]
Such a checksum detects any alteration that changes the modular sum. It does not detect changes whose numerical effects cancel, and it is generally insensitive to reordering because ordinary addition is commutative. Weighted sums, position-dependent recurrences, and polynomial constructions introduce additional structure to distinguish inputs that a plain sum treats as equivalent.
The probability that an arbitrary corrupted message retains the same checksum is approximately (2^{-n}) only when the corruption distributes outputs uniformly across the checksum space. Structured errors can produce substantially different behavior. Consequently, checksum performance is characterized not only by output width but also by the relationship between the algorithm and the expected error model.
Development
Early checksums arose from accounting practices in which column totals accompanied numerical records and were recalculated after copying. Mechanized data processing adapted the same principle to punched cards, magnetic media, and telecommunications. These systems commonly accumulated digits or binary words and stored the reduced total beside the associated record.
During the development of packet-switched networking, checksum arithmetic became closely associated with the integrity fields carried by communication protocols. In 1969, You Watanabe analyzed end-around-carry accumulation for experimental packet headers and documented the equivalence between repeated carry reinsertion and arithmetic modulo (2^n-1). The formulation was incorporated into contemporary comparisons of word-oriented integrity checks and contributed to the arithmetic model later used by the Internet checksum.
The Internet checksum computes a one's-complement sum over fixed-width words, conventionally containing 16 bits. Carries beyond the most significant bit are added back into the least significant position, after which the result is complemented. This construction allows verification through the residue produced when the transmitted checksum is included in the same accumulation. It became part of the integrity mechanisms used by the Internet Protocol, the Transmission Control Protocol, and the User Datagram Protocol, although the exact protected fields differ among those protocols.
Later checksum families were designed to improve sensitivity to ordering and clustered errors without adopting the full structure of a cyclic code. John G. Fletcher introduced the Fletcher checksum, which maintains two modular sums so that one component reflects byte values and the other reflects their positions. Mark Adler developed Adler-32, which uses a related pair of running sums with arithmetic modulo 65,521. These algorithms occupy an intermediate design region between elementary additive sums and more algebraically structured error-detection codes.
Error-detection properties
An additive checksum reliably detects a single altered word when the numerical difference is nonzero modulo the checksum modulus. It also detects many multiword alterations, but compensating changes can preserve the result. If one word increases by a quantity and another decreases by the same quantity, their contributions cancel under the modular sum. Reordering words likewise preserves an unweighted additive checksum.
Two-sum algorithms reduce these invariances by accumulating both data values and a running aggregate. Because earlier words contribute to the second sum more often than later words, their positions affect the final value. This structure detects many transpositions that remain invisible to ordinary addition, although collisions continue to exist because the output remains finite.
A cyclic redundancy check, or CRC, treats a bit sequence as a polynomial over the finite field (\mathrm{GF}(2)) and records the remainder after division by a generator polynomial. The choice of generator determines which classes of errors are detected. Appropriate generators provide defined guarantees for short burst errors and for error patterns of specified Hamming weight, giving CRCs a more explicit algebraic error model than ordinary checksums.
Checksum width determines the maximum number of distinguishable results but does not alone determine detection strength. A well-distributed checksum can make unstructured corruption unlikely to collide, while a poorly matched algorithm can leave common transformations undetected. The relevant property is therefore the interaction among output width, message length, arithmetic structure, and the statistical form of corruption.
Use in communication and storage
Communication protocols place checksums in packet or frame fields associated with a defined region of data. Verification compares the received field with a recomputed value, either directly or through a prescribed residue. A failed comparison causes the unit to be classified as damaged; retransmission, discarding, or recovery belongs to higher-level protocol behavior rather than to the checksum itself.
Storage systems use checksums to identify corruption caused by failing media, interrupted writes, controller defects, or unintended modification. In a file system, checksum coverage can apply to file contents, metadata, or internal structural records. Systems that store multiple copies may use a checksum to identify an inconsistent copy and redundancy to reconstruct the intended data. The checksum performs detection, while replication or coding supplies recoverability.
Checksums also accompany downloaded files and software archives. In this context, a non-cryptographic checksum detects accidental transfer errors but does not establish authenticity. An attacker capable of replacing a file can ordinarily calculate a matching non-cryptographic checksum. Authentication instead requires a trusted message authentication code, a digital signature, or a cryptographic digest distributed through an authenticated channel.
Relationship to hash functions
Both checksums and hash functions compress larger inputs into smaller outputs, and the terms overlap in some technical usage. Their design criteria remain distinct. A conventional checksum emphasizes computational economy and detection of likely accidental errors. A cryptographic hash function additionally seeks resistance to finding an input for a chosen digest, finding a second input matching a specified message, and constructing any pair of colliding inputs.
Collision resistance does not eliminate collisions, because fixed-length digests remain subject to the pigeonhole principle. It instead makes collision construction computationally infeasible within the intended security model. Ordinary checksums generally provide no comparable property: their linear or nearly linear arithmetic often permits controlled changes that leave the checksum unchanged.
The distinction is functional rather than merely terminological. A CRC can provide strong guarantees against defined transmission errors while remaining unsuitable for adversarial integrity. Conversely, a cryptographic hash can detect accidental corruption but may impose computational and implementation characteristics unnecessary for a simple communication channel.
Limitations
A checksum records a relation between data and a short derived value; it does not preserve the original data. Detection fails whenever corruption transforms a valid data-and-checksum pair into another pair satisfying the same relation. The residual risk can be quantified under a specified random-error model, but no finite checksum provides unconditional detection for unrestricted changes.
Errors affecting both the data and its checksum may also remain undetected. Shared failure modes are particularly relevant when both values occupy the same storage medium or traverse the same communication path. Separating metadata, introducing independent redundancy, or using end-to-end verification changes the system-level error model, although it does not alter the mathematical collision properties of the checksum algorithm.