Checksum

A checksum is a value computed from a block of data (number, message, file) using a deterministic function. This value accompanies the data during storage or transmission to detect certain alterations, particularly accidental ones: a flipped bit, a misread digit, etc.

The principle is based on redundancy: adding to the data information computed from that same data.

Recomputing the checksum on arrival and comparing it with the received value makes it possible to detect certain errors.

A checksum algorithm transforms data into a value called a checksum according to a deterministic rule.

The methods used vary depending on the algorithm. They can be based on modular arithmetic, XOR (exclusive OR), or even polynomial algebra.

The parity bit is one of the simplest forms of error checking: applying XOR to all bits of a message makes it possible to determine an additional bit to transmit.

For even parity, the added bit is chosen so that the total number of bits set to 1 is even. For odd parity, it is chosen so that this number is odd.

Any modification affecting an odd number of bits flips the parity and is therefore detected. In contrast, a modification affecting an even number of bits can remain invisible, for example when two bits are flipped.

This mechanism illustrates the fundamental trade-off of error-detecting codes: adding very little redundancy makes it possible to detect some errors, but not all.

— The parity bit (1 bit) is used to detect certain errors in binary data.

— The Luhn formula (1 check digit) is used in particular for certain bank card numbers, SIREN/SIRET numbers and IMEIs. It is mainly used to detect common input or transmission errors.

— The Internet checksum (16 bits) is used in particular by IPv4, TCP and UDP. It is based on one's complement addition.

— Fletcher checksums use cumulative modular additions that take into account the position of the data.

— CRC-32 based on the polynomial used by IEEE 802.3 is notably used for error detection in Ethernet and in several file formats, including PNG and ZIP.

— CRC-32C, also called Castagnoli, uses a different polynomial and is notably used by iSCSI and in several modern systems and protocols.

— Adler-32, used in particular by zlib, is fast to compute but has less favorable detection properties than some CRCs, particularly for certain small data.

— CRC-8, CRC-16 and CRC-64 exist in many variants adapted to different protocols and formats.

A collision occurs when two different contents produce the same check value.

For an N-bit function, the probability that a random modification produces a given value is approximately 1/(2^N).

For a deliberate collision search in an ideal N-bit hash function, the birthday paradox reduces the generic complexity to about 2^(N/2).

A classic checksum is therefore not designed to resist an adversary actively searching for a collision. Cryptographic hash functions are designed to make such searches computationally difficult.

A checksum belongs primarily to error detection mechanisms: when corruption is detected, the system can request a retransmission or reread the data from another medium.

Error-correcting codes add more redundancy to allow reconstruction of damaged data without retransmission. Hamming codes can correct certain binary errors, Reed-Solomon codes are notably used in QR codes and some optical media, while LDPC codes are used in many modern communication systems.

The two approaches can be combined: a system can use an error-correcting code to repair certain errors and a checksum to detect residual corruption.

A hash function transforms variable-length data into a fixed-size value designed to resist intentional collisions (unlike checksums). To achieve this, hashing uses the avalanche effect, where a small change in the input causes a large change in the output.

A checksum published alongside the data does not protect against an attacker capable of modifying both the data and the checksum. To achieve authentication, secret information or a private key must be involved.

A first solution is HMAC (Hash-based Message Authentication Code), which combines a cryptographic hash function and a shared secret key. Only a holder of the key can normally produce a valid HMAC. HMAC thus provides message integrity and authentication, but not confidentiality.

A second solution is digital signature, for example with RSA, ECDSA or EdDSA. The sender signs with a private key and the recipient verifies with the corresponding public key. This approach is notably used to authenticate software, updates or digital documents.

To also obtain confidentiality, encryption is required. Authenticated encryption modes (AEAD) combine encryption and authentication to provide both confidentiality and data integrity.