用 Hamming 距离线性约束 + 整数规划恢复 256 位密钥:浮点泄露 + SHA-256 哈希对
ctf/crypto · verified
一句话结论
当每个样本给出一个浮点数 c 和一条 SHA-256 哈希 h,而 c 实际是“256 位秘密 s 与 h 的 Hamming 距离 / 256”时,可把 c 还原成整数 C=round(c·256),利用恒等式 d(h,s)=weight(h)+Σ_j s_j(1-2h_j) 为每个样本建立一条 0/1 整数规划约束,111 条样本即可用 pulp + CBC 解出 256 位秘密;秘密的 MD5 作 AES-CTR 密钥即可解出 flag。
原理
- Hamming 距离展开:对二进制向量
h与s,d(h,s) = Σ_j [h_j ≠ s_j] = Σ_j h_j(1-s_j) + (1-h_j)s_j = weight(h) + Σ_j s_j(1-2h_j)。 因此Σ_j (1-2h_ij)·s_j = d_i - weight(h_i),左边对未知s_j∈{0,1}是线性的。 - 浮点泄露:题目输出
c_i,其 8 位小数值对应d_i/256的近似;C_i = round(c_i*256)即整数距离。只要c_i的小数精度足够,C_i就等于真实距离。 - 为什么 111 条够:未知数是 256 个二进制位,每条样本提供一个整数线性方程;
pulp用 CBC 求解 0/1 规划,模型在真值处可行。原文用 111 条约束(floats[:111]与hashes[:111])即可解出唯一 256 位秘密。 - 后续解密:解出的 32 字节
secret作为MD5(secret)的输入,得到 16 字节 AES key;密文用AES-CTR、nonce=b"suan"解密。 - 成立前提:浮点输出没有截断到丢失距离信息;哈希与秘密的位序/字节序在建模时一致;密文与样本在同一
output.txt中且可区分 64 字符哈希与偶数长度十六进制密文。
触发条件
- 题目/日志给出多组
(浮点数, 64 位十六进制哈希),浮点数在[0,1]且与哈希-秘密的 Hamming 距离成比例。 - 样本数量足以约束全部秘密位(原文 111 条对 256 位)。
- 有 Python +
pulp(CBC 求解器)或任意 0/1 ILP 求解器。 - 最后一段十六进制密文与样本在同一文件中,可用于验证解出的密钥。
利用步骤
- 解析
output.txt:用正则提取小数[01]?\.\d+与十六进制串;过滤掉 64 字符哈希,剩下的偶数长度十六进制串中最后一段是密文。 - 把前 111 个浮点数与 111 条哈希配对;对每条哈希按位展开成 256 维 0/1 向量
Y_i。 - 令
C_i = round(float_i*256),建立 256 个二进制变量s_j,对每个样本添加约束:Σ_j (1 - 2*Y_i[j]) * s_j == C_i - sum(Y_i)。 - 用
pulp.PULP_CBC_CMD求解,读出 256 位并转成 32 字节secret。 key = MD5(secret).digest();用AES.new(key, AES.MODE_CTR, nonce=b"suan")解密密文,得到 flag。
PoC
import re, math
from hashlib import md5
import pulp
from Crypto.Cipher import AES
data = open("output.txt", "r").read()
floats = [float(x) for x in re.findall(r'(?<![0-9a-f])([01]?\.\d+)', data)]
hexes = re.findall(r'\b[0-9a-fA-F]+\b', data)
ct_hex = [h for h in hexes if len(h) % 2 == 0 and len(h) != 64][-1]
ciphertext = bytes.fromhex(ct_hex)
hashes = re.findall(r'\b[0-9a-fA-F]{64}\b', data)
def bits(h):
return [int(b) for byte in bytes.fromhex(h) for b in f"{byte:08b}"]
pairs = list(zip(floats[:111], hashes[:111]))
Y, C = [], []
for f, h in pairs:
b = bits(h)
Y.append(b)
C.append(round(f * 256))
prob = pulp.LpProblem("recover", pulp.LpMaximize)
s = [pulp.LpVariable(f"s{j}", cat="Binary") for j in range(256)]
for i in range(len(Y)):
prob += pulp.lpSum((1 - 2 * Y[i][j]) * s[j] for j in range(256)) == C[i] - sum(Y[i])
prob.solve(pulp.PULP_CBC_CMD(msg=False))
secret = bytearray()
for i in range(32):
v = 0
for j in range(8):
v = (v << 1) | int(s[i * 8 + j].value())
secret.append(v)
key = md5(bytes(secret)).digest()
plain = AES.new(key, AES.MODE_CTR, nonce=b"suan").decrypt(ciphertext)
print(plain.decode(errors="replace"))
变体与关联
- 距离变体:如果浮点是
1 - 距离/256,取补即可;若是字节级匹配数/编辑距离,也可以类似展开成线性约束。 - 哈希变体:SHA-256/SHA-512/自定义哈希均可,只要哈希的位向量已知且秘密与哈希同长。
- 求解器变体:
pulp/OR-Tools/Z3 的Optimize;样本有噪声时可改为容差约束或最大似然。 - 关联:[[crypto-hash-md5-three-way-collision-nested-fastcoll]](哈希构造)、[[ctf-crypto-linear-hash-collision-lll]](线性哈希约束)。
检测与防御
- CTF 性质:这是对“泄露 Hamming 距离”这一设计缺陷的攻击。
- 设计防御:不要输出与密钥相关的距离/相似度;需要距离时加入噪声或只给区间;密钥使用 KDF/高熵随机值,不要用 MD5 派生 AES key。
- 检测:日志/接口中出现大量
(浮点, 哈希)对且浮点精度异常时,评估是否泄露了隐藏向量的距离信息。