crc32_clmul() computes wrong CRC for misaligned buffers with a non-zero initial value

[ThomasWaldmann]

Summary

crc32_clmul() returns wrong CRC32 values when all of the following hold:

• the initial value (value= argument) has any bit set above its low algn_diff bytes, and
• the buffer start address is congruent to 13, 14 or 15 modulo 16 (i.e. algn_diff is 1, 2 or 3), and
• the length is >= 16.

crc32_slice_by_8() and zlib.crc32() agree with each other; only crc32_clmul() is wrong.

Found while investigating #10149. It is a separate defect from the over-read reported there — it is present with and without that fix, and it is a correctness rather than a memory-safety problem.

Evidence

Sweeping a 4096 byte heap buffer, views at every start offset 0..31 and every length 0..47, comparing against zlib.crc32:

initial_crc=0x00000000 ->    0 mismatches
initial_crc=0x00000001 ->    0 mismatches
initial_crc=0x12345678 ->  192 mismatches
initial_crc=0xffffffff ->  192 mismatches

All 192 mismatches have algn_diff in {1, 2, 3} and length >= 16. crc32_slice_by_8 matches zlib.crc32 for every one of those inputs.

The dependence on the initial value rather than on the data is the tell: initial_crc=0 is always correct, and initial_crc=1 is correct too, because its only set bit lives in byte 0, which survives even when just one byte is folded.

Cause

In the alignment prologue:

    algn_diff = (0 - (uintptr_t)src) & 0xF;
    if (algn_diff) {
        xmm_crc_part = _mm_loadu_si128((__m128i *)src);
        XOR_INITIAL(xmm_crc_part);

        src += algn_diff;
        len -= algn_diff;

        partial_fold(algn_diff, &xmm_crc0, &xmm_crc1, &xmm_crc2, &xmm_crc3, &xmm_crc_part);
    }

XOR_INITIAL() xors the 32-bit initial CRC into the low 4 bytes of xmm_crc_part. partial_fold() then folds only algn_diff bytes into the accumulator and discards the rest of the register. When algn_diff < 4, the bytes of the initial value above byte algn_diff - 1 are silently thrown away, and the result is wrong.

The initial-value support is borg's own extension to the Intel code (see the Copyright (c) 2016 Marian Beermann (add support for initial value, restructuring) line in the file header). The upstream routine is a deflate fold-and-copy with no initial value at all, so this one is not an upstream bug either — see #10149 for upstream links.

Why the tests do not catch it

test_crc32 slices a single os.urandom(300) bytes object at start in range(0, 4). CPython's bytes payloads are 16-byte aligned, so those four starts produce addresses congruent to 0, 1, 2, 3 mod 16, i.e. algn_diff in {0, 15, 14, 13} — precisely the complement of the broken set {1, 2, 3}. The test can never reach the failing path.

Covering start in range(0, 16) would expose it immediately.

Impact

Borg 1.x itself appears not to be affected in practice. The two hot call sites in repository.py _read() are:

call	address	algn_diff
crc32(memoryview(header)[4:])	bytes payload + 4	12
crc32(data, ...)	bytes payload	0

Both are constant across 2000 samples, because CPython bytes payloads are 16-byte aligned, so neither reaches algn_diff 1..3.

But the function is a public, general-purpose checksum primitive, and the result is silently wrong rather than an error. If any call site ever passes a buffer at an odd alignment (a memoryview into an mmap, a slice at an arbitrary offset, a bytearray from a C extension), borg on a PCLMULQDQ CPU would compute a different CRC than borg on a CPU without it — which surfaces as spurious Segment entry checksum mismatch integrity errors when a repository is written on one machine and read on another.

Suggested fix

Fold the initial value in a way that does not depend on algn_diff. Options:

1. XOR the initial value into the accumulator after the prologue rather than into xmm_crc_part before it, or
2. handle the whole algn_diff prologue through the same zero-padded staging buffer used for the short-input path, positioning the initial value where partial_fold() will keep it, or
3. simplest and safest: route any input with algn_diff != 0 through the scalar path for the first algn_diff bytes, as zlib-ng does with crc32_copy_small().

Whichever is chosen, the regression test should sweep start in range(0, 16) with a non-zero initial value.

Not affected: master / borg 2

src/borg/algorithms/ was removed entirely in master, so there is no crc32_clmul there any more.

[ThomasWaldmann]

Existing repositories are not affected: no wrongly computed CRCs were ever written

Since this is a "silently wrong checksum" bug, the obvious worry is whether repositories out there contain bad CRC32 values. They do not. Reasoning and measurements below.

First, the other bug cannot corrupt anything

For completeness, #10149 (the 16 byte over-read) never produces a wrong value: partial_fold() discards the bytes that were read past the end, so the returned CRC is always correct. The only possible outcomes are "correct result" or SIGSEGV. In a full test suite run that path is taken 58039 times, all correct. So the bug that actually hurt users is integrity-neutral.

This bug needs three conditions at once

algn_diff in {1, 2, 3} (buffer address congruent to 13, 14 or 15 mod 16) and len >= 16 and a non-zero initial value. Borg never produces that combination at any of its call sites:

call site	buffer	algn_diff	initial value
crc32(header)	bytes from struct.pack	0	0
crc32(id, crc32(header))	bytes	0	non-zero
crc32(data, crc32(id, crc32(header)))	bytes	0	non-zero
crc32(data, crc32(memoryview(header)[4:]))	bytes / memoryview at offset 4	0 / 12	non-zero
crc32(d[4:size]) in recover_segment()	memoryview over an mmap, arbitrary offset	any	0

Two things make this work out:

1. CPython's bytes payload lives at object base + 32, and allocators return blocks aligned to at least 16 bytes, so every whole-bytes argument is 16 byte aligned - algn_diff 0. memoryview(header)[4:] is offset 4, so algn_diff 12. None of these are in the broken set.

2. There is one call site that walks arbitrary alignments: recover_segment() scans a memoryview over an mmap and does d = d[1:] on mismatch, so d[4:size] lands on every alignment in turn. But it passes no initial value, and with an initial value of 0 the bug provably cannot trigger - the upper bytes that get discarded are all zero. That is visible in the sweep in the issue description: initial_crc=0x00000000 -> 0 mismatches.

So the one place with dangerous alignment has a harmless initial value, and every place with a non-zero initial value has harmless alignment.

Measured, not just argued

I built an instrumented crc32_clmul that counts every input the unpatched code would have computed wrongly (len >= 16 && algn_diff in 1..3 && initial_crc != 0), and ran real workloads on a NetBSD 11.0 amd64 box with CLMUL:

workload	crc32_clmul calls	would have been wrong	alignments observed
init + create x2 + check + extract + delete + compact	912	0	0, 8, 12
full test suite, incl. the check/repair/recover paths	172153	0	0, 4, 7, 8, 12

Alignments 1, 2 and 3 were never reached by borg code at all.

Worth noting as a sanity check on the method: the first full-suite run reported 102 rather than 0. Those all came from the widened alignment sweep in test_crc32 added in #10151 - 3 broken alignments x 34 lengths >= 16 = exactly 102. Which is precisely what that test is for. Excluding the checksum tests themselves, borg's own code paths give 0.

This holds back to borg 1.1

1.1-maint, 1.2-maint and 1.4-maint all have the same six crc32() call sites in repository.py with identical argument shapes, unchanged since the vendored implementation was added in 9afebea.

Conclusion: no borg check campaign is needed, and no existing repository needs re-verification.

This is a latent bug in a general purpose primitive, worth fixing because the next caller might not be so lucky.

[ThomasWaldmann]

@enkore ^