Desmedt-Odlyzko 签名伪造:用签名预言机线性组合伪造目标消息的 RSA 签名
crypto/rsa · verified
一句话结论
RSA 签名满足乘法同态:s(m1)·s(m2) mod n = s(m1·m2 mod n)。如果攻击者能获得任意消息的签名,就可以选择一组消息,使其哈希值的乘积(或带整数指数的线性组合)等于目标消息哈希,再把对应签名相乘/求逆,伪造出目标消息的合法签名。
原理
- 教科书 RSA 签名:
s = H(m)^d mod n,验证为s^e mod n == H(m)。由于指数运算的乘法性质,s(m1)·s(m2) ≡ (H(m1)H(m2))^d ≡ s(H(m1)H(m2) mod n) (mod n)。 - 更一般地,若
H(m_target) ≡ ∏ H(m_i)^{a_i} (mod n)(a_i可为负整数),则s_target ≡ ∏ s_i^{a_i} (mod n),负指数用模逆实现。 - 攻击的核心是找一组“可签名消息”,使其哈希值在模
n下生成目标哈希。常用做法是把哈希值分解到小素数基上,把每个哈希表示成指数向量;用线性代数/LLL 找到整数系数组合,使组合后的指数向量等于目标哈希的指数向量。哈希不光滑时,换一批消息或调整目标,直到找到可解关系。 - 因此该攻击不破坏 RSA 本身,而是利用“签名接口对任意消息开放 + 哈希不是随机预言/没有域分离”这一组合。若签名方案使用 RSA-PSS 或对消息做随机化/域分离,乘法关系不再直接对应到目标哈希,攻击失效。
触发条件
- 服务端提供签名预言机,允许攻击者对任意(或大量可控)消息请求签名。
- 签名是教科书式
H(m)^d mod n或等价的无域分离哈希签名,验证只比较s^e == H(m)。 - 目标消息的哈希可以表示为所查询消息哈希的整数系数乘积(模
n);通常要求哈希值对小素数基光滑或能通过格方法找到关系。 - 攻击者能离线计算与服务端一致的哈希函数,并能提交伪造签名。
利用步骤
- 确认签名方案:获取
n、e,确认验证式为pow(s,e,n) == H(m),且H与签名接口一致。 - 实现
hash_oracle(m_int),必须与服务端逐字节一致(编码、哈希算法、是否截断)。 - 实现
sign_oracle(m_int),通过菜单/协议获取任意消息的签名。 - 调用 Desmedt-Odlyzko 攻击实现(如 crypto-attacks 的
desmedt_odlyzko.attack(hash_oracle, sign_oracle, N, e, target_m)):对目标哈希与候选消息哈希做小素数分解/线性组合,求整数系数。 - 用系数组合签名:正指数直接乘,负指数取模逆后乘,得到
s_target。 - 本地验证
pow(s_target,e,N) == H(target),通过后提交给服务端校验接口。
PoC
from pwn import *
import hashlib
from Crypto.Util.number import bytes_to_long
from desmedt_odlyzko import attack # crypto-attacks 项目实现
HOST = '10.0.0.1'
PORT = 1337
N = 0x...
E = 65537
TARGET_MESSAGE = b"Transfer 1000000 to Hacker's Account"
io = remote(HOST, PORT)
def my_hash_oracle(m_int):
# 必须与服务端一致:编码方式、哈希算法、截断规则
m_bytes = str(m_int).encode()
return bytes_to_long(hashlib.sha256(m_bytes).digest())
def my_sign_oracle(m_int):
io.sendlineafter(b"Choice: ", b"1")
io.sendlineafter(b"Message (hex): ", hex(m_int)[2:].encode())
io.recvuntil(b"Signature: ")
return int(io.recvline().strip(), 16)
target_m_int = bytes_to_long(TARGET_MESSAGE)
forgery = attack(
hash_oracle=my_hash_oracle,
sign_oracle=my_sign_oracle,
N=N,
e=E,
target_m=target_m_int,
)
assert pow(forgery, E, N) == my_hash_oracle(target_m_int)
io.sendlineafter(b"Choice: ", b"2")
io.sendlineafter(b"Message: ", TARGET_MESSAGE.hex().encode())
io.sendlineafter(b"Signature: ", hex(forgery)[2:].encode())
print(io.recvall().decode())
说明:核心的哈希分解/线性组合算法在
desmedt_odlyzko.attack中;原文只提供交互桥接。若攻击过程中光滑界B过大导致分解困难,需要调整候选消息或目标消息。
变体与关联
- 变体:目标哈希不光滑时,可以收集更多消息签名,或用 LLL 在指数向量格中寻找更短的关系。
- 变体:若签名前有固定填充但填充可预测,仍可能构造乘法关系;RSA-PSS 的随机盐会破坏该关系。
- 变体:ElGamal/ECDSA 等签名方案不具备同样的乘法同态,需不同的伪造思路。
- 关联:[[crypto-rsa-bleichenbacher-pkcs1v15-padding-oracle]](RSA 填充预言机)、[[crypto-rsa-lsb-parity-oracle]](解密预言机)、[[crypto-rsa-common-modulus]](同模数下的 RSA 代数关系)。
检测与防御
- 防御:使用 RSA-PSS 或带域分离的签名方案,避免教科书式
H(m)^d。 - 防御:签名接口不要对任意攻击者可控消息开放;加入认证、速率限制、消息白名单与审计。
- 检测:日志中出现大量签名请求、请求消息呈随机/小素数构造特征、同一账号短时间内获取大量签名。
- 响应:确认签名预言机被滥用后,吊销相关密钥、作废已签发签名,并审计历史签名记录。