Diffie-Hellman 私钥含少量未知比特:两半枚举建表中间相遇恢复共享密钥
crypto/protocol · verified
一句话结论
Diffie-Hellman 的私钥 a 只剩约 44 个比特不确定(内存 dump 里被 ? 遮住)时,不必做 2^44 全枚举:把 a 拆成两半各 22 bit,先枚举前半算出 g^{-a_left}·y mod p 建哈希表,再枚举后半算 g^{a_right} mod p 查表,2×2^22(约 840 万次模幂)即可恢复完整私钥,再算共享密钥解 AES。
原理
- DH 会话密钥的可分解性:
y = g^a mod p,K = g^{ab} mod p,AES key = SHA256(long_to_bytes(K))。恢复a就等价于恢复K。 - 未知比特的结构:给定
a的二进制模板(?表示未知位),把未知位按位置分成左、右两组,则a = a_left + a_right,其中a_left是高位未知位贡献、a_right是低位未知位贡献,且两者数值可通过已知段偏移拼出。 - 中间相遇:
y = g^{a_left}·g^{a_right} mod p,因此g^{-a_left}·y = g^{a_right} mod p。枚举a_left的所有取值(2^22)算出左边并存进字典;再枚举a_right的所有取值(2^22)算右边,命中字典即得两半。 - 为什么比全枚举快:全枚举是
2^44 ≈ 1.7e13次模幂,中间相遇是2·2^22 ≈ 8.4e6次,加速约2^21倍,用时从不可行降到 tqdm 可见的范围。 - 为什么拆成两半要按“位”而非按“段”:
?在模板里是散落的,按位置索引分组(原文先记录每个?的位下标,再二等分下标列表)才能保证左右两半的数值各自只需枚举自己那段未知位;按字符串split('?')分段也能拼出同样的数值,只要下标与倍率对齐。 - 哈希用
SHA256(long_to_bytes(K)):K是整数,long_to_bytes的长度随数值变化,但比对时是把K同一路径再算一遍,所以只要a正确,AES key必然一致。
触发条件
- 拿到 DH 参数
p、g,以及某一方的公钥y = g^a mod p(或能算出共享密钥的对端关系)。 - 私钥
a的二进制模板已知,未知位数足够小:两半各 ≤ 24 bit(哈希表 2^24 条约 1~2 GB 内存、可行)时稳;44 bit 是舒适区。 - 有密文(AES-ECB 等)可做最终验证,或能拿到 flag 前缀用于判定。
- 目标
p约 1024 bit,单次模幂用pow或gmpy2.powmod都在微秒~毫秒级。
利用步骤
- 从内存 dump / 抓包中取
p、g、y(被扫描方公钥)与另一方的公钥。 - 把
a的模板字符串(含?)记录下来,统计未知位数n_unknown。 - 反转字符串按下标记录每处
?的位置,把下标列表二等分;同时对已知段按2^(idx+1)累加得到两半的固定基数。 - 建表阶段:枚举前半未知位(
product('01', repeat=n_unknown//2)),aa = base_left + bits,算y * inverse(g^aa, p) mod p,存table[value] = bits。 - 查表阶段:枚举后半,
bb = base_right + bits,算g^bb mod p,命中table即拼出完整a(用所有?位置的下标还原)。 - 用
a算K = pow(y_peer, a, p)(或pow(g, a*b, p)),SHA256(long_to_bytes(K))得 AES key,解密密文并用 flag 开头(如ictf)判定命中。
PoC
from itertools import product
from Crypto.Util.number import inverse, long_to_bytes
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from gmpy2 import powmod
p, g, y, AES_data, tmp = ... # tmp 是含 '?' 的私钥模板('?' 表示未知位)
# '?' 在二进制表示里的下标(tmp[::-1] 的第 i 位 = 权重 2^i)
idx = [i for i, ch in enumerate(tmp[::-1]) if ch == '?']
idx = idx[::-1] # 反转后下标与“高位在前”的分段顺序对齐(原文写法)
idx.append(-1) # 末段权重 2^0 的哨兵,缺它 idx2 会越界
unknown = tmp.count('?')
idx1, idx2 = idx[:len(idx) // 2], idx[len(idx) // 2:]
parts = tmp.split('?')
p1, p2 = parts[:len(parts) // 2], parts[len(parts) // 2:]
base_left = sum(int(p1[i], 2) * 2 ** (idx1[i] + 1) for i in range(len(p1)) if p1[i])
base_right = sum(int(p2[i], 2) * 2 ** (idx2[i] + 1) for i in range(len(p2)) if p2[i])
table = {}
for bits in product('01', repeat=unknown // 2):
aa = base_left + sum(int(bits[k]) * 2 ** idx1[k] for k in range(len(bits)))
table[y * inverse(powmod(g, aa, p), p) % p] = bits
for bits in product('01', repeat=unknown - unknown // 2):
bb = base_right + sum(int(bits[k]) * 2 ** idx2[k] for k in range(len(bits)))
if powmod(g, bb, p) in table:
left = table[powmod(g, bb, p)]
full = list(left) + list(bits) # 两半按原顺序拼接
secret = sum(int(parts[i], 2) * 2 ** (idx[i] + 1) for i in range(len(parts)) if parts[i])
secret += sum(int(full[k]) * 2 ** idx[k] for k in range(unknown))
K = powmod(y, secret, p) # y 为对端公钥,等价于 g^(ab)
key = SHA256.new(long_to_bytes(K)).digest()
flag = AES.new(key, AES.MODE_ECB).decrypt(AES_data)
if b'ictf' in flag:
print(secret, flag)
break
变体与关联
- 变体:未知位分布在两端(如私钥只缺高位一段)时,中间相遇退化为“枚举高位 + 用
g^{-a}·y检查剩余”,实现更简单。 - 变体:若
a是很小的数(g^a未模约减)则直接整数开方/离散对数小范围搜索即可,无需建表。 - 变体:
p只有 64~80 bit 时可直接跑 Pollard rho / BSGS 求完整离散对数,不必利用部分比特。 - 关联:[[crypto-ecc-ecdh-small-nonce-brute-shared-point-key]](ECDH 侧的小 nonce 枚举)、[[crypto-prng-truncated-lcg-coppersmith-lattice-cvp]](另一类“部分比特已知”的格方法)。
检测与防御
- 防御:私钥不得以任何形式落入可读内存镜像、core dump、swap 或日志;对长期私钥使用 HSM/TEE 或至少
mlock/MADV_DONTDUMP并保证退出时清零(见 [[crypto-implementation-madv-dontdump-mlock-key-pages]]、[[crypto-implementation-memset-dead-store-elimination-key-wipe]])。 - 防御:DH 私钥长度要足够(≥ 256 bit 随机),不要用带固定结构的模板生成私钥;
p必须是安全素数,避免小子群攻击。 - 检测:进程内存出现明文私钥比特、
gmpy2.powmod高频调用、CPU 长时间单核满载(枚举建表的典型特征)。 - 响应:私钥可能泄露的会话一律视为已解密,轮换长期密钥并更换
g/p参数。