Tome of Finite Knowledge

Spoofing CRC32 checksums

4 min read

CRC32 is a very weak checksum mechanism and can be spoofed (or collided) with ease.

See also

I got this info from this page: https://www.nayuki.io/page/forcing-a-files-crc-to-any-value. While it’s an excellent read and goes more into the math than I do, I’m writing down the essentials here in case that site ever goes down.

The Code

All credit to the author of the Nayuki page linked at the top. This is a copy-paste!

More accurately, this is a copy-paste of a section of the code. I left off the argument parsing and processing; this is more of a “library” snippet thinned down to what’s necessary to import & use as part of another program.

Polynomial value may differ

If you already have a polynomial value in mind that you intend to swap out for the 0x104C11DB7 value here, note that most polynomials are 32 bits. This one has a 33rd bit which must be 1.

I am not smart enough to do this level of math, but I think it’s something to do with the reversing of the polynomial bitstring.

# ---- Main function ----
 
# Public library function. offset is uint, and newcrc is uint32.
# May raise IOError, ValueError, AssertionError.
def modify_file_crc32(path: str, offset: int, newcrc: int, printstatus: bool = False) -> None:
	with open(path, "r+b") as raf:
		raf.seek(0, os.SEEK_END)
		length: int = raf.tell()
		if offset + 4 > length:
			raise ValueError("Byte offset plus 4 exceeds file length")
		
		# Read entire file and calculate original CRC-32 value
		crc: int = get_crc32(raf)
		if printstatus:
			print(f"Original CRC-32: {reverse32(crc):08X}")
		
		# Compute the change to make
		delta: int = crc ^ newcrc
		delta = multiply_mod(reciprocal_mod(pow_mod(2, (length - offset) * 8)), delta)
		
		# Patch 4 bytes in the file
		raf.seek(offset)
		bytes4: bytearray = bytearray(raf.read(4))
		if len(bytes4) != 4:
			raise IOError("Cannot read 4 bytes at offset")
		for i in range(4):
			bytes4[i] ^= (reverse32(delta) >> (i * 8)) & 0xFF
		raf.seek(offset)
		raf.write(bytes4)
		if printstatus:
			print("Computed and wrote patch")
		
		# Recheck entire file
		if get_crc32(raf) != newcrc:
			raise AssertionError("Failed to update CRC-32 to desired value")
		elif printstatus:
			print("New CRC-32 successfully verified")
 
 
# ---- Utilities ----
 
POLYNOMIAL: int = 0x104C11DB7  # Generator polynomial. Do not modify, because there are many dependencies
MASK: int = (1 << 32) - 1
 
 
def get_crc32(raf: BinaryIO) -> int:
	raf.seek(0)
	crc: int = 0
	while True:
		buffer: bytes = raf.read(128 * 1024)
		if len(buffer) == 0:
			return reverse32(crc)
		crc = zlib.crc32(buffer, crc)
 
 
def reverse32(x: int) -> int:
	y: int = 0
	for _ in range(32):
		y = (y << 1) | (x & 1)
		x >>= 1
	return y
 
 
# ---- Polynomial arithmetic ----
 
# Returns polynomial x multiplied by polynomial y modulo the generator polynomial.
def multiply_mod(x: int, y: int) -> int:
	# Russian peasant multiplication algorithm
	z: int = 0
	while y != 0:
		z ^= x * (y & 1)
		y >>= 1
		x <<= 1
		if (x >> 32) & 1 != 0:
			x ^= POLYNOMIAL
	return z
 
 
# Returns polynomial x to the power of natural number y modulo the generator polynomial.
def pow_mod(x: int, y: int) -> int:
	# Exponentiation by squaring
	z: int = 1
	while y != 0:
		if y & 1 != 0:
			z = multiply_mod(z, x)
		x = multiply_mod(x, x)
		y >>= 1
	return z
 
 
# Computes polynomial x divided by polynomial y, returning the quotient and remainder.
def divide_and_remainder(x: int, y: int) -> tuple[int,int]:
	if y == 0:
		raise ValueError("Division by zero")
	if x == 0:
		return (0, 0)
	
	ydeg: int = get_degree(y)
	z: int = 0
	for i in range(get_degree(x) - ydeg, -1, -1):
		if (x >> (i + ydeg)) & 1 != 0:
			x ^= y << i
			z |= 1 << i
	return (z, x)
 
 
# Returns the reciprocal of polynomial x with respect to the modulus polynomial m.
def reciprocal_mod(x: int) -> int:
	# Based on a simplification of the extended Euclidean algorithm
	y: int = x
	x = POLYNOMIAL
	a: int = 0
	b: int = 1
	while y != 0:
		q, r = divide_and_remainder(x, y)
		c = a ^ multiply_mod(q, b)
		x = y
		y = r
		a = b
		b = c
	if x == 1:
		return a
	else:
		raise ValueError("Reciprocal does not exist")
 
 
def get_degree(x: int) -> int:
	return x.bit_length() - 1

It might be worth nothing that the polynomial value in this example matches that used by ArduPilot for checksumming Lua scripts.

Graph View