逆向卷积型线性加密:把 des[i+j]+=flag[i]*key[j] 建模为 Toeplitz 方程组用最小二乘还原输入
code-analysis/reverse · draft
一句话结论
当加密循环写成 des[i+j] += flag[i] * key[j](外层明文、内层密钥、目标下标为两者之和)时,它就是一个离散卷积/线性映射;密文长度等于明文长度加密钥长度减一,把每个输出写成 A·x 的行,用已知密钥构造 Toeplitz 矩阵后解线性方程组(最小二乘或前代)即可唯一还原明文,无需爆破。
原理
des[i+j] += flag[i]*key[j]完全等价于多项式乘法:把flag的字节看作多项式系数、key的字节看作另一个多项式系数,des就是两者乘积的系数序列。长度关系len(des) = len(flag) + len(key) - 1是判断「这是卷积而不是普通逐字节加密」的第一特征。- 展开成矩阵形式:对每个输出下标
k,des[k] = Σ_i flag[i] * key[k-i](0 ≤ k-i < len(key))。把key按行平移填入矩阵,得到len(des) × len(flag)的 Toeplitz 矩阵A,整个加密就是A·x = b,x即明文向量。 - 该映射是线性的且
key[0] ≠ 0时矩阵首行对角非零,x可由前代法从des[0]开始逐个解出:flag[0] = des[0]/key[0],flag[1] = (des[1] - flag[0]*key[1])/key[0],依此类推。因此加密本身不提供任何混淆强度,只是把明文「摊开」到更长的输出里。 - 实战中更省事的是把矩阵直接丢给最小二乘:
x = (AᵀA)⁻¹Aᵀb。即使下标起点/长度判断有偏差,只要行数多于未知数,最小二乘仍能给出接近整数解的结果,四舍五入即为字节。之所以能这么做,是因为运算在整数(或浮点精确可表示的小整数)域内进行,没有模运算截断。 - 反例边界:若内层写成
des[i+j] = (des[i+j] + flag[i]*key[j]) & 0xffffffff,就是模 2³² 的卷积,普通最小二乘失效,需要按模运算处理(逐项取模前代或交给 z3)。
触发条件
- 逆向目标中存在双重循环,内层累加下标为
i+j(或i-j、(i+j)%n等固定线性偏移),且没有取模/非线性 S 盒; - 已知或可从二进制中提取密钥数组;
- 能拿到密文数组(静态数据段、比较常量或输入后的期望值);
- 分组长度较短、字节取值范围可枚举时也可用已知明文校验结果。
利用步骤
- 在反编译代码中确认累加形式与长度关系,记录
len(des)、len(key),推出len(flag) = len(des) - len(key) + 1。 - 从数据段/初始化代码中取出
key与des(注意des末尾常见补 0,需按长度裁掉)。 - 构造
A:对每个i(明文下标)、j(密钥下标),令A[i+j][i] = key[j]。 - 解
A·x = b:np.linalg.solve(AᵀA, Aᵀb)或np.linalg.lstsq,四舍五入取整。 - 转字符校验格式(如
XXX{...});若个别字符错位,改用前代法逐项求解交叉验证。
PoC
import numpy as np
key = np.array([0x4C,0x69,0x74,0x43,0x54,0x46,0x32,0x30,0x32,0x35], dtype=np.float64)
des = np.array([...], dtype=np.float64) # 长度 = len(flag) + len(key) - 1
n_flag = len(des) - len(key) + 1
A = np.zeros((len(des), n_flag))
for i in range(n_flag):
for j in range(len(key)):
A[i + j][i] = key[j]
x = np.linalg.solve(A.T @ A, A.T @ des) # 正规方程
flag = np.round(x).astype(np.uint32)
print(''.join(chr(c) for c in flag))
等价的直接前代(更稳,不依赖浮点):
flag = []
for i in range(n_flag):
acc = des[i] - sum(flag[t] * key[i - t] for t in range(max(0, i - len(key) + 1), i))
flag.append(int(round(acc / key[0])))
变体与关联
- 下标改为
i-j(互相关)时矩阵结构变成下三角 Toeplitz,同样可解;循环卷积((i+j) % n)对应 FFT 域逐点相除。 - 若涉及
& 0xffffffff或% 256,转为模方程,可用 z3 或逐项前代取模求解,不要直接套最小二乘。 - 若
key未知,可用已知明文(flag 格式前缀)反解密钥,再用密钥解剩余部分。 - 关联:[[code-analysis-reverse-crypto-encoding-identification-decrypt]](标准算法识别,本卡针对自定义线性变换);[[code-analysis-reverse-chacha20-binary-identification-features]](流密码特征识别)。
检测与防御
- CTF/算法侧识别:密文长度恰好比明文长
len(key)-1;循环里出现arr[i+j]形式的累加;没有 S 盒、移位、取模等非线性操作。 - 防御(若作为许可证/校验算法):不要使用纯线性变换保护数据,至少加入模 2³² 截断、非线性替换或带密钥的哈希/MAC,并避免把密钥与校验常量放在同一二进制中。