crc32_clmul() reads up to 12 bytes past the end of short buffers (SIGSEGV)

[ThomasWaldmann]

Summary

crc32_clmul() reads up to 12 bytes past the end of the input buffer for inputs of 4..15 bytes. When those bytes fall in an unmapped page the process dies with SIGSEGV.

This is a memory-safety bug in code borg vendored and then modified; the upstream it was taken from does not have it. It has been present since the code was first added in 2016, so every borg release from 1.1 on is affected on any x86-64 CPU with PCLMULQDQ (i.e. essentially all of them).

It is the root cause of the long-standing intermittent NetBSD CI segfaults in #5922.

The bug

borg/src/borg/algorithms/crc32_clmul.c

Lines 357 to 375 in 04d1a53

	if (len < 16) {
	if (len == 0)
	return initial_crc;
	if (len < 4) {
	/*
	* no idea how to do this for <4 bytes, delegate to classic impl.
	*/
	uint32_t crc = ~initial_crc;
	switch (len) {
	case 3: crc = (crc >> 8) ^ Crc32Lookup[0][(crc & 0xFF) ^ *src++]; // fallthrough
	case 2: crc = (crc >> 8) ^ Crc32Lookup[0][(crc & 0xFF) ^ *src++]; // fallthrough
	case 1: crc = (crc >> 8) ^ Crc32Lookup[0][(crc & 0xFF) ^ *src++];
	}
	return ~crc;
	}
	xmm_crc_part = _mm_loadu_si128((__m128i *)src);
	XOR_INITIAL(xmm_crc_part);
	goto partial;
	}

    if (len < 16) {
        if (len == 0)
            return initial_crc;
        if (len < 4) {
            /* ... delegates to the table-driven implementation ... */
        }
        xmm_crc_part = _mm_loadu_si128((__m128i *)src);   /* <-- reads 16 bytes */
        XOR_INITIAL(xmm_crc_part);
        goto partial;
    }

For 4 <= len < 16 this loads a full 16 bytes starting at src, i.e. it reads up to 12 bytes that are not part of the buffer. partial_fold() later discards them, so the result is correct — but the load has already happened.

The len >= 16 paths are fine: after the alignment prologue they use aligned _mm_load_si128(), and an aligned 16-byte load can never straddle a page boundary. Only the short-buffer branch can fault.

repository.py _read() calls crc32(memoryview(header)[4:]), which is a 5 byte view for header_fmt, so this branch is on the hot path for every segment entry read.

Reproducer

Place a short buffer flush against the end of a mapped page and make the next page PROT_NONE:

buffer length	crc32_slice_by_8	crc32_clmul
5	ok	SIGSEGV
12	ok	SIGSEGV
40	ok	ok

len=40 surviving is exactly what the code predicts — it takes the aligned path.

This is also why it looks like a platform bug: whether it faults depends purely on where the allocator happened to place the buffer. Linux/glibc rarely puts a small object within 12 bytes of the end of the last mapped page; NetBSD does it often enough that our CI has been failing for years. On a NetBSD 11.0 amd64 KVM guest the 1.4-maint suite (pytest -n auto, py3.11.15) crashed in 4 of 5 full runs, every core dump faulting at the same instruction in crc32_clmul.

The existing test_crc32 does not catch this: it slices a single 300-byte os.urandom() buffer, which never sits near a page boundary.

Which changeset introduced it

9afebea — "two fast CRC implementations" (2016-12-20), where the file was added as src/borg/_crc32/clmul.c. The buggy load is present in that very first version and has never been touched since; later commits only renamed/moved the file.

The upstream this was adapted from is Intel's PCLMULQDQ CRC-folding code, which is a fold-and-copy routine for deflate. Upstream stages short inputs through a zero-padded 16-byte buffer:

char zalign(16) partial_buf[16] = { 0 };
...
if (len < 16) {
    if (len == 0)
        return;
    memcpy(partial_buf, src, len);
    xmm_crc_part = _mm_loadu_si128((const __m128i *)partial_buf);
    memcpy(dst, partial_buf, len);
    goto partial;
}

In upstream, partial_buf does double duty: it bounds the load and is the source of the memcpy(dst, ...). Borg's port dropped the copy-to-dst (we only want a checksum, not a copy), and partial_buf went with it — but it was also the thing keeping the load in bounds.

Upstream

The actively maintained descendant of this code is zlib-ng:

• https://github.com/zlib-ng/zlib-ng/blob/develop/arch/x86/crc32_pclmulqdq_tpl.h

zlib-ng is not affected: it has been restructured so that short inputs and the pre-alignment remainder are handled by a scalar crc32_copy_small() path, and the vector loads only ever run on full 16-byte-aligned blocks.

The original (now unmaintained) source the header credits is Jim Kukunas's zlib fork carrying the Intel patch:

• https://github.com/jtkukunas/zlib/blob/master/crc_folding.c

Nothing needs to be reported upstream — both are clean. This defect is ours.

Fix

Stage through a zero-padded 16-byte buffer, as upstream does. partial_fold() shifts the padding out again, so results are bit-identical — verified against both crc32_slice_by_8 and zlib.crc32 for lengths 0..199 x 20 random inputs x 3 initial values, 0 mismatches. With the fix, the NetBSD runs that previously crashed 4 out of 5 times went 5 out of 5 clean.

A regression test should place the buffer at the end of a mapped page; the current test cannot detect the over-read.

Not affected: master / borg 2

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

[ThomasWaldmann]

@enkore ^