DEF CON Quals 2022- sameold

solve.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


tint = crc32(b"the")
target = vector(GF(2), i2v(tint, 32))

n_digits = 16
data = b"Balsn.217@TSJ.tw" + b"\0" * n_digits
m = len(data) * 8
A, C = crcmat(crc32, 32, m)
# A*(base+delta)+C=t
# A*delta=t-C-A*base
delta = A.solve_right(target - C - A * vector(b2v(data)))
dd = v2b(vector(GF(2), b2v(data)) + delta)
print(dd, crc32(dd), tint)

# basis: some vectors that could becomes the ascii digits 0~7
# k: another constant ensures
# delta + right_kernel = k + basis
# right_kernel - basis = k - delta
def gen_at(i):
    v = [0] * m
    v[i] = 1
    return vector(GF(2), v)


basis = []
k = [0] * m
for i in range(0, m, 8):
    if i >= m - n_digits * 8:
        # do not modify the prefix
        continue
    # f'{ord("7"):08b}' == '00110111'
    # the lowest three bits belongs to basis
    # and the higher two bits are for k
    # the bits are reversed
    k[i + 4] = 1
    k[i + 5] = 1
    basis.append(gen_at(i))
    basis.append(gen_at(i + 1))
    basis.append(gen_at(i + 2))
rhs = vector(k) - delta
nk = len(A.right_kernel().basis())
lhs = list(A.right_kernel().basis()) + basis
sol = matrix(lhs).solve_left(rhs)
delta2 = sol[:nk] * A.right_kernel_matrix() + delta
print(delta2)
dd = v2b(vector(GF(2), b2v(data)) + delta2)
print(dd, crc32(dd), tint)
assert crc32(dd) == crc32(b'the')