Checksum

Fletcher’s checksum

Proposed by John G. Fletcher (Lawrence Livermore, 1982). Two running sums (one of the data, one of the first sum’s history) combined into a single output. Catches all single-bit, all double-bit, and all burst errors of short length , while running far faster than CRC. Widely deployed in network protocols where speed matters.

The three sizes

How it works

Maintain two accumulators a, b initialized to 0 (or to a non-zero starting state per the variant). For each input word w: a = (a + w) mod M; b = (b + a) mod M. Output (b << bits) | a where bits is half the output width. Compared with Adler-32, the modulus is the Mersenne-like 2^k−1 rather than a prime , making the modular reduction cheaper at the cost of slightly weaker distribution.

Where it shows up

• OSPF , Fletcher-16 over the routing-protocol packet header (RFC 1008 / 2328).
• ISO TP4 / X.224 , Fletcher-16 as the transport-layer checksum.
• SCTP (legacy) , Fletcher-32 in early drafts before the switch to CRC-32C (RFC 4960).
• UBIFS (Linux) , metadata integrity.
• ZFS (older versions) , one option for block-level checksums.

Limitations

Like every checksum on this list, Fletcher is non-cryptographic. Adversaries can construct collisions trivially. It also has a well-known limitation: a block of all-zero bytes followed by a single non-zero byte at the right position can mask error patterns.

References

• J. G. Fletcher, “An arithmetic checksum for serial transmissions,” IEEE Transactions on Communications, 1982.
• RFC 1008 , Implementation guide for the ISO Transport Protocol
• Adler-32 · Internet checksum