Manger RSA-OAEP 首字节零预言机:三步区间压缩恢复明文
crypto/rsa · verified
一句话结论
RSA-OAEP 解密时会检查恢复出的整数 m 是否小于 B = 2^{8(k-1)}(首字节为 0x00)。如果服务端把这个检查结果以可区分的方式返回,攻击者提交 c·f^e mod n 并观察 f·m mod n < B 是否成立,用三步区间压缩即可在约 log2(n) 次查询内恢复完整明文。
原理
- OAEP 解码前,RSA 解密得到整数
m;合法 OAEP 块要求m < B,其中k是模数字节长度,B = 2^{8(k-1)}。服务端若对“首字节是否为 0”给出不同响应,就构成一个比特预言机。 - 提交
c' = c·f^e mod n,解密得到m' = f·m mod n;oracle 返回的是布尔值[f·m mod n < B]。 - Step 1:从
f1=2开始不断翻倍,直到首次出现f1·m mod n < B。这给出一个缩放因子,使m落入[0, B/f1)附近的区间。 - Step 2:令
f2 = floor((n+B)/B)·f1/2,若 oracle 为假则每次加f1/2,直到 oracle 为真。此时区间收缩为[ceil(n/f2), floor((n+B)/f2)],宽度约B/f2,且包含m。 - Step 3:在区间
[mmin, mmax]上做二分:取f = floor(2B/(mmax-mmin))、i = floor(f·mmin/n)、f3 = ceil(i·n/mmin);查询f3,根据 oracle 结果把mmax或mmin更新为(i·n+B)/f3或ceil((i·n+B)/f3)。区间不断缩小,最终mmin即明文。 - 攻击成立的关键是
2B < n,且 oracle 只泄露“是否小于 B”这一比特;它不需要私钥,也不需要知道 OAEP 的随机种子。
触发条件
- 服务端使用 RSA-OAEP 解密,并把“首字节是否为 0x00 / OAEP 解码是否通过”以可区分方式返回(错误信息、状态码、连接行为、耗时)。
- 攻击者已知
n、e、目标密文c,能反复提交任意密文。 2B < n(标准 RSA 模数满足)。- 无速率限制或查询预算足够(约
n.bit_length()次)。
利用步骤
- 从公钥提取
n、e,确认服务端使用 OAEP 且错误可区分。 - 实现
padding_oracle(trial_c):发送密文,按响应判断解密结果首字节是否为0x00;注意 True 必须对应“小于 B”。 - Step 1:
f1=2,当 oracle 为假时f1*=2,直到首次为真。 - Step 2:按公式初始化
f2,当 oracle 为假时f2 += f1//2,直到为真。 - Step 3:按区间二分公式迭代,直到
mmin == mmax。 - 返回
mmin,转字节;去掉 OAEP 填充后得到消息。
PoC
from pwn import *
from sage.all import ZZ
import logging
logging.basicConfig(level=logging.INFO)
HOST = 'target.example.com'
PORT = 1337
N = ZZ(0x...)
E = ZZ(65537)
C = ZZ(0x...)
def padding_oracle(trial_c):
try:
io = remote(HOST, PORT, level='error')
io.sendline(hex(trial_c).encode())
response = io.recvall()
io.close()
# True 表示解密结果首字节为 0x00(m < B)
return b"Success" in response or b"Decrypted" in response
except Exception as e:
logging.error(f"Oracle connection error: {e}")
return False
def _step_1(oracle, n, e, c):
f1 = 2
while not oracle((pow(f1, e, n) * c) % n):
f1 *= 2
return f1
def _step_2(oracle, n, e, c, B, f1):
f2 = ((n + B) // B) * f1 // 2
while not oracle((pow(f2, e, n) * c) % n):
f2 += f1 // 2
return f2
def _step_3(oracle, n, e, c, B, f2):
mmin = (n + f2 - 1) // f2 # ceil(n / f2)
mmax = (n + B) // f2 # floor((n + B) / f2)
while mmin < mmax:
f = (2 * B) // (mmax - mmin)
i = (f * mmin) // n
f3 = (i * n + mmin - 1) // mmin # ceil(i*n / mmin)
if oracle((pow(f3, e, n) * c) % n):
mmax = (i * n + B) // f3
else:
mmin = (i * n + B + f3 - 1) // f3
return mmin
def manger_attack(oracle, n, e, c):
k = (n.bit_length() + 7) // 8
B = 2 ** (8 * (k - 1))
assert 2 * B < n, "Manger 条件不满足: 2B 必须小于 N"
f1 = _step_1(oracle, n, e, c)
f2 = _step_2(oracle, n, e, c, B, f1)
return _step_3(oracle, n, e, c, B, f2)
m = manger_attack(padding_oracle, N, E, C)
print(m)
print(hex(int(m)))
说明:原文脚本的
_step_1写作while padding_oracle(...);若 oracle 的 True 表示“首字节为 0”,正确极性应为while not oracle(...)。实际题目必须按返回值调整。
变体与关联
- 变体:oracle 返回的是“OAEP 解码是否成功”而非严格的“首字节为 0”,只要失败条件与
m < B等价即可。 - 变体:若服务端只泄露“m 的最高位”而不是
< B,可先做区间归一化,再套类似的二分。 - 变体:PKCS#1 v1.5 的填充合法性对应 Bleichenbacher 攻击,查询量与区间结构不同。
- 关联:[[crypto-rsa-bleichenbacher-pkcs1v15-padding-oracle]]、[[crypto-rsa-lsb-parity-oracle]]、[[crypto-rsa-rabin-random-square-root-oracle]]。
检测与防御
- 防御:OAEP 解码失败必须返回统一错误、统一状态码、恒定时间,不能泄露“首字节是否为 0”。
- 防御:对解密接口做认证、速率限制和查询审计;新协议优先使用 ECDHE 等不依赖 RSA 解密的密钥交换。
- 检测:同一来源高频提交不同密文、每次密文呈
c·f^e结构、响应耗时/长度分布异常。 - 响应:确认预言机存在后下线或改为恒定时间实现,轮换密钥并审计历史解密请求。