RSA LSB 奇偶预言机:乘 2^e 查询 m mod 2 二分恢复明文
crypto/rsa · verified
一句话结论
如果服务端对任意 RSA 密文返回其解密结果的最低位(奇偶性),攻击者可以反复提交 c·2^{e·i} mod n,每次让明文翻倍并观察是否越过 n,用二分法在约 n.bit_length() 次查询内恢复完整明文。
原理
- 设原始密文
c ≡ m^e (mod n)。构造c_i = c·2^{e·i} mod n,则其解密结果为m_i ≡ m·2^i (mod n)。 - 服务端只返回
m_i mod 2。因为n是奇数,m_i = 2^i·m - q_i·n的奇偶性等于q_i mod 2,其中q_i = floor(2^i·m / n)。 q_i的二进制表示正是m/n的前i位小数;q_i mod 2就是第i位。因此每次查询给出明文在[0,n)区间中的一个二分方向。- 维护区间
[L,U](初始[0,n]):若最低位为 0,说明2^i·m mod n落在当前区间的下半部分,令U=(L+U)//2;否则令L=(L+U)//2。 - 迭代
n.bit_length()次后区间宽度小于 1,U即为明文整数m。 - 该攻击只要求“最低位”这一个比特的泄露;错误信息、调试接口、侧信道都可能提供它。查询次数远少于 Bleichenbacher。
触发条件
- 服务端对任意密文解密并返回明文的奇偶性(或可区分奇偶的行为)。
- 攻击者已知
n、e、c,能反复提交任意密文。 - 没有速率限制或查询次数足够(约 1024/2048 次)。
- 明文在
[0,n)内按标准 RSA 表示;若明文有填充,恢复的是填充后的整数,需要再解析。
利用步骤
- 确认 oracle 返回的是
m mod 2,并确定其 True/False 与奇偶的对应关系。 - 预计算
multiplier = pow(2, e, n),避免每次重复计算。 - 初始化
L=0、U=n、cur=c;循环n.bit_length()次: -cur = cur * multiplier % n- 查询oracle(cur);为 0 则U=(L+U)//2,为 1 则L=(L+U)//2。 - 循环结束返回
U,转字节得到明文。 - 用
pow(U,e,n)==c校验;若失败,检查 oracle 极性、是否每次连接重置状态、是否返回的是字节而非比特。
PoC
from pwn import *
from sage.all import ZZ
from Crypto.Util.number import long_to_bytes
HOST = 'target.example.com'
PORT = 1337
N = ...
E = 65537
C = ...
def get_oracle(fake_cipher):
# 按题目协议实现:返回 0 表示明文为偶数,1 表示奇数
io = remote(HOST, PORT, level='error')
io.recvuntil(b"Give me cipher: ")
io.sendline(hex(fake_cipher).encode())
response = io.recvall()
io.close()
return 0 if b"Even" in response else 1
def lsb_oracle_attack(N, e, c, oracle):
N = ZZ(N)
left, right = ZZ(0), N
cur = ZZ(c)
multiplier = pow(2, e, N)
for i in range(N.bit_length()):
cur = (cur * multiplier) % N
lsb = oracle(cur)
if lsb == 0:
right = (left + right) // 2
else:
left = (left + right) // 2
return int(right)
m_int = lsb_oracle_attack(N, E, C, get_oracle)
print(long_to_bytes(m_int))
变体与关联
- 变体:oracle 返回
m mod 2^k的多个低位时,可一次缩小2^k倍区间,查询次数大幅减少。 - 变体:oracle 返回“明文是否小于 n/2”而不是奇偶性,等价于最高位泄露,可直接二分。
- 变体:RSA-OAEP 的首字节零检查对应 Manger 攻击;PKCS#1 v1.5 填充合法性对应 Bleichenbacher 攻击。
- 关联:[[crypto-rsa-manger-oaep-first-byte-oracle]]、[[crypto-rsa-bleichenbacher-pkcs1v15-padding-oracle]]、[[crypto-rsa-rabin-random-square-root-oracle]](其他解密预言机)。
检测与防御
- 防御:不要返回明文任何比特或可用于推断比特的行为;解密接口统一返回固定格式、恒定时间。
- 防御:使用 RSA-OAEP 并加入完整性校验,避免对任意密文解密;对解密接口做认证与速率限制。
- 检测:同一来源大量提交不同密文、每次仅改变最低位相关结构、查询次数接近模数位数。
- 响应:确认 LSB 泄露后下线接口、轮换密钥,并审计历史解密请求。