Checksum Strength: What CRC32C and SHA-256 Each Guarantee

A block checksum is a bet about which errors will occur. Choosing the function means choosing which error patterns are guaranteed to be caught and which are merely unlikely to be caught, and those two kinds of assurance behave very differently when a fault is adversarial rather than random. CRC32C and SHA-256 sit at opposite ends of that trade, and the reason filesystems use both — sometimes in the same product — is that they are answering different questions.

What a CRC guarantees, stated precisely

A CRC is the remainder of a polynomial division. The message bits are treated as coefficients of a polynomial over GF(2), multiplied by x raised to the width of the check value, and divided by a fixed generator polynomial; the remainder is the checksum. Verification is the same division applied to message-plus-checksum, which yields zero when nothing has changed.

Because the structure is algebraic, the detection properties are provable rather than probabilistic. For a generator of degree n with a nonzero constant term, every burst error of length at most n bits is detected. For CRC-32 that means any error confined to a span of 32 consecutive bits is caught with certainty. If the generator has a factor of (x + 1), every error pattern with an odd number of flipped bits is detected, because such a polynomial cannot be divisible by (x + 1). The Castagnoli polynomial used by CRC32C has that factor; the older IEEE 802.3 polynomial does not, which is among the reasons CRC32C was adopted for storage and internet checksums.

The probabilistic statement covers everything else. For a message longer than the guarantee extends to, a random error pattern is caught with probability 1 − 2^−n: 1 − 2^−32 for CRC-32, which is about one in four billion. That is a fine number for random media faults, and it is exactly the number that matters when the error is not random.

CRC32C is the Castagnoli polynomial, chosen because its algebraic properties give better minimum distance for the message lengths that matter in networking and storage than the older IEEE polynomial. It is the checksum of iSCSI data digests, of ext4 metadata blocks, of btrfs data and metadata, and of the metadata checksums in several other Linux filesystems. On processors with the SSE4.2 crc32 instruction or the ARMv8 CRC extension, computing it over a block costs roughly one cycle per byte or less.

The property CRC does not have

A CRC is linear over GF(2). Formally, for two messages of equal length, CRC(a XOR b) equals CRC(a) XOR CRC(b) XOR a constant that depends only on the lengths. That linearity is what makes the implementation cheap and the guarantees provable, and it is also what makes the checksum forgeable.

An adversary who can choose the contents of a block and knows the checksum function can compute a modification that leaves the CRC unchanged, and can do so with simple arithmetic rather than search. This is not a theoretical concern in a system where an untrusted party supplies file contents: a virtual machine image, a container layer, a backup target, or a peer in a replicated store. In those settings the question is not “will a random bit flip be caught” but “can a deliberate edit be made to look untouched”, and a CRC answers the second question badly.

A cryptographic hash answers it well. SHA-256, specified in FIPS 180-4, is a Merkle–Damgård construction over 512-bit blocks with a 256-bit chaining value. Its security claim is that finding two inputs with the same digest requires on the order of 2^128 work — the birthday bound for a 256-bit output — and that finding any input matching a given digest requires on the order of 2^256 work. Neither claim is a proof; both are backed by decades of cryptanalysis without a practical break of the full function. For the purpose of detecting tampering, the relevant consequence is that no shortcut exists: the only way to produce a colliding block is to search.

The width also changes the accidental-collision arithmetic. A random corruption surviving a CRC-32 check has probability 2^−32; surviving a 128-bit hash has probability 2^−128. Both are small enough that the difference is not what decides the design. The linearity is what decides it.

Where the cost lands

Speed is the axis where CRC wins outright, and the margin is large enough to constrain architecture.

A portable table-driven CRC32C implementation processes roughly a byte per cycle; the dedicated instruction advances the CRC over wider chunks per step, several times faster again. A 4 KiB block therefore costs on the order of a few thousand cycles, small compared with the cost of the I/O that fetched it. Verification on every read is affordable, and filesystems that use CRC32C generally do verify on every read.

SHA-256 is a different budget. Portable implementations cost on the order of ten cycles per byte, roughly an order of magnitude more than a CRC. Processors with SHA extensions narrow the gap to a few cycles per byte, but the instructions are not universal, and where they are absent the gap stands. A 128 KiB block verified with SHA-256 on every read consumes a noticeable fraction of the time the read itself takes.

This is why the choice is usually made per object class rather than globally. Metadata is small, read less often than data in a streaming workload, and expensive to lose: hashing it cryptographically costs little in aggregate. Bulk data is large, read constantly, and usually protected by a fast checksum, with the cryptographic option reserved for cases where tampering is in the threat model. Systems that support both typically let the function be selected per dataset or per file rather than fixing one for the whole volume.

ZFS is the instructive example of a third position. Its native checksum is Fletcher-4, which keeps four independent running sums rather than one, producing a 256-bit stored value from arithmetic that is cheaper than a CRC on the processors of its design era. Fletcher checksums are weaker than CRCs in their guaranteed burst detection for a given width, but the four-accumulator structure raises the effective width enough to compensate for random faults. For deduplication, where a false match causes two different blocks to be treated as identical and one of them to be discarded, ZFS requires a cryptographic hash instead — the failure mode there is not “damage went unnoticed” but “data was destroyed by a wrong equality decision”, and only a collision-resistant function makes that decision safe.

/* CRC32C, bitwise form. The table-driven and instruction forms
   compute the same value with the same polynomial. */
#include <stddef.h>
#include <stdint.h>

uint32_t crc32c_bitwise(const uint8_t *p, size_t n)
{
    uint32_t crc = 0xFFFFFFFFu;
    for (size_t i = 0; i < n; i++) {
        crc ^= p[i];
        for (int k = 0; k < 8; k++)
            crc = (crc >> 1) ^ (0x82F63B78u & (0u - (crc & 1u)));
    }
    return ~crc;
}

The constant 0x82F63B78 is the Castagnoli polynomial in reflected form: 0x1EDC6F41 with its bits reversed. The final complement and the initial all-ones value are conventions that distinguish the CRC32C used in storage from a raw polynomial remainder; getting either wrong produces a checksum that validates nothing.

Choosing when the threat model is unclear

The decision reduces to a single question: can an attacker influence the bytes being protected? If not, CRC32C is the correct default, because its guarantees cover exactly the fault classes that occur — bursts from media, torn sectors, transport glitches — at a cost that permits verification on every access. If an attacker can, a CRC is not a weak checksum but an absent one, since the forgery cost is a few dozen arithmetic operations.

Intermediate positions exist and are worth naming. Truncated cryptographic hashes, 64 or 128 bits of a SHA-256 digest, keep collision resistance against random faults and reduce collision resistance against a searching adversary in proportion to the truncation, while cutting the storage cost of the checksum. Keyed functions such as HMAC-SHA-256 remove even the offline forgery route, at the cost of key management the filesystem is poorly placed to provide. A filesystem that stores the checksum in metadata it also protects with its own checksum is layering detection rather than strengthening the function, which helps against misdirected writes but not against a determined forger.

The choice also interacts with placement and granularity. A checksum stored in a block pointer is protected by the tree structure above it; one stored in the payload competes with data for space. Both arrangements are covered in checksum placement across pointers, trees, and payloads, and the granularity question — how large a region one checksum should cover — changes the cost calculus in ways that a faster function does not fix, as checksum granularity and the read-modify-write penalty describes. Function strength sets the floor on what detection is possible; those two decisions set what it costs to achieve.