recover the matrix from a crc function by blackbox

crcmat.sage

from zlib import crc32


def v2b(v):
    v = v[::-1]
    return bytes([int("".join(map(str, v[i : i + 8])), 2) for i in range(0, len(v), 8)])


def b2v(b):
    v = []
    for x in b:
        v.extend(list(map(int, f"{x:08b}")))
    return v[::-1]


def i2v(i, n):
    return list(map(int, f"{i:0{n}b}"))[::-1]


def v2i(v):
    return int("".join(map(str, v[::-1])), 2)


def crcmat(crc, n, m):
    """
    Recover matrix of crc by black box
    crc: crc function, bytes->int
    n: crc output bits
    m: crc input bits

    crc(x) = Ax+C
    x is n bits
    crc(x) is m bits
    A is m by n matrix
    Assuming bits reversed crc
    """
    C = vector(GF(2), i2v(crc(v2b([0] * m)), n))
    right = []
    # left = []
    for i in range(m):
        v = [0] * m
        v[i] = 1
        # left.append(v)
        right.append(vector(i2v(crc(v2b(v)), n)) - C)
    # L = matrix(GF(2), left).T
    R = matrix(GF(2), right).T
    # A = R * L.inverse()
    # Note: L is identity matrix
    A = R
    return A, C


if __name__ == "__main__":
    # matrix recover test
    A, C = crcmat(crc32, 32, 128)
    msg = bytearray(b"x" * (128 // 8))
    msg[-8:] = b"pekomiko"
    x = v2i(A * vector(b2v(msg)) + C)
    assert x == crc32(msg)

    # find crc(x) == x for 32 bits x
    # A*x+C=x
    # (A-I)*x=-C
    A, C = crcmat(crc32, 32, 32)
    x = v2b((A - matrix.identity(32)).solve_right(-C))
    assert v2i(b2v(x)) == crc32(x)

crcmat_optimized.sage

from zlib import crc32
from tqdm import tqdm


def v2b(v):
    v = v[::-1]
    return bytes([int("".join(map(str, v[i : i + 8])), 2) for i in range(0, len(v), 8)])


def b2v(b):
    v = []
    for x in b:
        v.extend(list(map(int, f"{x:08b}")))
    return v[::-1]


def i2v(i, n):
    return list(map(int, f"{i:0{n}b}"))[::-1]


def v2i(v):
    return int("".join(map(str, v[::-1])), 2)


def crcmat(crc, n, m):
    """
    Recover matrix of crc by black box
    crc: crc function, bytes->int
    n: crc output bits
    m: crc input bits

    crc(x) = Ax+C
    x is n bits
    crc(x) is m bits
    A is m by n matrix
    Assuming bits reversed crc
    """
    C = vector(GF(2), i2v(crc(v2b([0] * m)), n))
    right = [None] * m
    vb = bytearray(b"\x00" * (m // 8))
    for i in tqdm(range(m)):
        vb[(m - i - 1) // 8] |= 1 << (i % 8)
        v = [0] * m
        v[i] = 1
        right[i] = vector(i2v(crc(vb), n)) - C
        vb[(m - i - 1) // 8] = 0
    R = matrix(GF(2), right).T
    A = R
    return A, C


if __name__ == "__main__":
    # matrix recover test
    A, C = crcmat(crc32, 32, 128)
    msg = bytearray(b"x" * (128 // 8))
    msg[-8:] = b"pekomiko"
    x = v2i(A * vector(b2v(msg)) + C)
    assert x == crc32(msg)

    # find crc(x) == x for 32 bits x
    # A*x+C=x
    # (A-I)*x=-C
    A, C = crcmat(crc32, 32, 32)
    x = v2b((A - matrix.identity(32)).solve_right(-C))
    assert v2i(b2v(x)) == crc32(x)