CRC

本文主要介绍CRC的定义，以及CRC的相关变种。

CRC

循环冗余校验（英语：Cyclic redundancy check，通称“CRC”）是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。

CRC的一个重要性质是仿射函数。确切的说，$\mathrm{CRC}(x\oplus y)=\mathrm{CRC}(x)\oplus\mathrm{CRC}(y)\oplus c$ ，$c$ 取决于 $x,y$ 的长度。也有另一种表达方式，对于等长的 $x,y,z$，有 $\mathrm{CRC}(x\oplus y\oplus z)=\mathrm{CRC}(x)\oplus\mathrm{CRC}(y)\oplus\mathrm{CRC}(z)$ 。

CRC 求逆

参考：hackergame2022-writeups/official/不可加密的异世界 at db7b525937fb68e0ba3941ce0ec8d532eb159af8 · SuperSodaSea/hackergame2022-writeups (github.com)

现在如果知道 $\mathrm{CRC}(x)$，要怎么求 $x$ 呢。首先定义 $\_\mathrm{CRC}(x)=\mathrm{CRC}(x)\oplus \mathrm{CRC}(0^l)$ ，其中 $0^l$ 代表与 $x$ 等长的 b'\x00 字节流。那么对于等长的输入 $a,b$ 有：

$\begin{aligned}\_\mathrm{CRC}(\Delta\oplus a)\oplus\_\mathrm{CRC}(\Delta\oplus b)&=\_\mathrm{CRC}(a\oplus b)\\ \text{Generally }\Longrightarrow\forall x_i,n\quad\oplus_1^n\_\mathrm{CRC}(x_i)&=\_\mathrm{CRC}(\oplus_1^nx_i)\end{aligned}$

$\_\mathrm{CRC}(x)$ 可以理解为一个同态。

有了这个性质，我们只要选取一个基底 $v_i$，例如 $v_i=(0,\ldots,1,\ldots,0)\quad i\in1,2,3,\ldots,128$ ，记这一组标准正交基的 $\_\mathrm{CRC}$ 哈希值的对应的向量为 $V_i=\_\mathrm{CRC}(v_i)$ ，用 $V_i$ 构建一个在 $GF(2)$ 上的矩阵：

$\text{let}\quad M^T=\begin{bmatrix}V_1 \\V_2 \\ \vdots\\V_{128}\end{bmatrix},\forall\vec{x}=(x_1,\ldots,x_n)\in GF(2)^{128} \\$

则 $x=\sum\limits_{i=1}^{128} x_iv_i$ ，从而：

$xM^T = \sum\limits_{i=0}^{128} x_iV_i = \_\mathrm{CRC}(\sum\limits_{i=0}^{128} x_iv_i) = \_\mathrm{CRC}(x) = \mathrm{CRC}(x) + \mathrm{CRC}(0^{128}) \in GF(2)^{128}$

进而可以求出 $x^T=M^{-1}*(\mathrm{CRC}(x)^T+C) \quad \textrm{where} \ C = \mathrm{CRC}(0^{128})^T$。

CRC128

ACTF2023出过一道CRC128的题：

from base64 import *

def crc128(data, poly = 0x883ddfe55bba9af41f47bd6e0b0d8f8f):
    crc = (1 << 128) - 1
    for b in data:
        crc ^= b
        for _ in range(8):
            crc = (crc >> 1) ^ (poly & -(crc & 1))
    return crc ^ ((1 << 128) - 1)

with open('./flag.txt','r') as f:
    flag = f.readline()

YourInput = input().encode()
YourDecode = b64decode(YourInput, validate=True)

print(len(YourDecode))

assert len(YourDecode) <= 127 and YourDecode.startswith(b'Dear guest, welcome to CRCRC Magic House, If you input ') and YourDecode.endswith(b", you will get 0x9c6a11fbc0e97b1fff5844fa88b1ee2d")

YourCRC = crc128(YourInput)
print(hex(YourCRC))

if(YourCRC) == 0x9c6a11fbc0e97b1fff5844fa88b1ee2d:
    print(flag)

大概就是找到一个输入 $x$ 使得 $x$ 在 pad 之后进行crc128等于一个定值，即0x9c6a11fbc0e97b1fff5844fa88b1ee2d。并且 $x$ 是可见字符，长度不能超过30.

我的做法是对于 $x$ 的每个字节，固定其前两个比特为 0,1，这样极大可能得到A-Za-z。然后算出基本解系，再搜索进行组合，可以找出符合条件的解。

var_bytes = 26
ans_bytes = 16
start = len(b'RGVhciBndWVzdCwgd2VsY29tZSB0byBDUkNSQyBNYWdpYyBIb3VzZSwgSWYgeW91IGlucHV0IC') * 8
s = b'RGVhciBndWVzdCwgd2VsY29tZSB0byBDUkNSQyBNYWdpYyBIb3VzZSwgSWYgeW91IGlucHV0IC' + b'\x40'*var_bytes + b'LCB5b3Ugd2lsbCBnZXQgMHg5YzZhMTFmYmMwZTk3YjFmZmY1ODQ0ZmE4OGIxZWUyZA=='
target_bytes = len(s)
D = crc128(s) ## 作为常数向量
zero_crc = crc128(target_bytes*b"\x00")
target_bits = 8 * target_bytes
var_bits = 8 * var_bytes
ans_bits = 8 * ans_bytes
v2n = lambda v: int(''.join(map(str, v)), 2)
n2v = lambda n: vector(GF(2), bin(n)[2:].zfill(ans_bits))
crc_value = 0x9c6a11fbc0e97b1fff5844fa88b1ee2d

Affine_Matrix = []
for i in range(var_bits):
    if i % 8 in [0, 1]:
        continue
    v = [0] * target_bits
    v[start+i] = 1
    v = vector(GF(2), v)
    value = crc128(long_to_bytes(v2n(v),target_bytes)) ^ zero_crc
    Affine_Matrix.append(n2v(value))
# crc affine function: crc_128(x) = M*x+ C
M, D = matrix(GF(2),Affine_Matrix).transpose(), n2v(D)
# crc affine function: crc_128(x) = M*x+ C
v2n = lambda v: int(''.join(map(str, v)), 2)
n2v = lambda n: vector(GF(2), bin(n)[2:].zfill(128))
res = M.solve_right(n2v(crc_value)+D)
dv = vector([i % 8 == 1 for i in range(var_bits)])
res_ = [0] * var_bits
for i in range(len(res) // 6):
    # res_[8*i] = 0
    # res_[8*i+1] = 1
    for j in range(6):
        res_[8*i+j+2] = res[6*i+j]
        
res_ = vector(GF(2), res_)
print(long_to_bytes(v2n(res_+dv), var_bytes))
basis = M.right_kernel().basis()


import itertools


def convert(res, var_bits):
    res_ = [0] * var_bits
    for i in range(len(res) // 6):
        # res_[8*i] = 0
        # res_[8*i+1] = 1
        for j in range(6):
            res_[8*i+j+2] = res[6*i+j]

    res_ = vector(GF(2), res_)
    return res_ + dv
        
for num in range(len(basis)):
    for i in itertools.combinations(basis,num+1):
        tmp = res
        for j in i:
            tmp += j
        s = long_to_bytes(v2n(convert(tmp, var_bits)),var_bytes)
        if re.fullmatch(b'[A-Za-z0-9+/]*', s):
            print('success')
            print(f'i:{i}')
            print('s:', s)
						break