ALLES! CTF 2020 - crccalc1,2 (Crypto)

multicrc_solve.py

from sage.all import *
from crccheck.crc import *

def tobin(v, n):
    assert 0 <= v < 2**n
    return tuple(ZZ(v).digits(2, padto=n))[::-1]

def frombin(v):
    return sum(int(c)*2**i for i, c in enumerate(v[::-1]))

for chall in range(2):
    if chall == 0:  # crccalc1
        N = 12
        data = [
            (Crc32,      0x8A7B9617),  # CRC-32        
            (Crc32Bzip2, 0x58653D65),  # CRC-32/BZIP2  
            (Crc32c,     0x822681C1),  # CRC-32C     
            (Crc32d,     0xB6608BDC),  # CRC-32D     
            (Crc32Mpeg2, 0xA79AC29A),  # CRC-32/MPEG-2 
            (Crc32Posix, 0x51F96944),  # CRC-32/POSIX  
            (Crc32q,     0x28D0D4AD),  # CRC-32Q       
            (CrcJamcrc,  0x758469E8),  # CRC-32/JAMCRC
            (CrcXfer,    0x6DEE8406),  # CRC-32/XFER   
        ]
    else:  # crccalc2
        N = 24
        data = [
            (Crc32,      0xB60C1196), # CRC-32        
            (Crc32Bzip2, 0x540FB6E5), # CRC-32/BZIP2  
            (Crc32c,     0x0472FC19), # CRC-32C
            (Crc32d,     0xCD3BFFA5), # CRC-32D     
            (Crc32Mpeg2, 0xABF0491A), # CRC-32/MPEG-2 
            (Crc32Posix, 0xAFA3CADF), # CRC-32/POSIX  
            (Crc32q,     0xC4B409AD), # CRC-32Q       
            (CrcJamcrc,  0x49F3EE69), # CRC-32/JAMCRC
            (CrcXfer,    0x0B91E517), # CRC-32/XFER   
        ]

    target = ()
    m = matrix(GF(2), 0, N*8)

    for func, h in data:
        f0 = func.calc(b"\x00" * N)
        target += tobin(int(h) ^ int(f0), 32)
        
        sub = []
        for i in range(N):
            for j in range(8):
                s = [0] * N
                s[i] = 1 << (7 - j)
                res = func.calc(bytes(s)) ^ f0
                sub.append(tobin(res, 32))

        sub = matrix(GF(2), sub).transpose()
        m = m.stack(sub)

    print(m.ncols(), m.nrows(), m.rank())
    sol = m.solve_right(vector(target))
    for z in m.right_kernel():
        solz = sol + z
        res = []
        for i in range(0, len(solz), 8):
            res.append(frombin(solz[i:i+8]))

        print(bytes(res))