CTF学习/crypto/Bleichenbacher 与 PKCS#1 v1.5 填充 Oracle（含 ROBOT

Bleichenbacher 与 PKCS#1 v1.5 填充 Oracle（含 ROBOT

考点概念

Bleichenbacher 攻击针对 RSA 加密中 PKCS#1 v1.5 填充的有效性提示（padding oracle）工作。

合法明文填充格式为 00 02 || PS（≥8 字节非零）|| 00 || M。攻击者把密文 c 乘以 s^e（模 n）得到新密文 c'，服务器解密后若填充有效返回"有效"、无效则返回错误，这就是 oracle。攻击者观察大量 s 的 oracle 输出，用区间收缩法逐步把明文所在的区间 [2B, 3B-1]（B = 2^(8(k-2))，k 为模数字节数）缩小到单点，从而完全恢复明文。

攻击分 3 步：Step1 找盲化/起点 s0；Step2 用 2a/2b/2c 三种策略选新 s；Step3 用命中的 s 收缩全部候选区间。

填充结构作为整数的表达：待加密块 EB = 00 || 02 || PS || 00 || M 共 k 字节（k 为模数字节数，PS 为非零随机字节且不少于 8 字节，故合法消息至少 11 字节），把 EB 看大端整数 em，则"合法 PKCS#1 v1.5 加密块"恰好等价于 2B ≤ em ≤ 3B – 1，其中 B = 2^(8(k-2))；这是因为首字节 00、次字节 02 固定为 2B 的段起点，第三字节到末尾（低 8(k-2) 位）任意。

oracle 的数学关系：

查询 q(s) = oracle(c * s^e mod n)，其解密值为 ms mod n，返回"有效"当且仅当存在整数 r ≥ 0 使 2B ≤ ms – rn < 3B（r 即 ms 除以 n 的商）。

区间收缩规则（设当前候选区间集合 M，单区间记 [a, b]）：

Step 2a（首轮单区间）取 s 从 ceil(n / (3B)) 起逐一递增探测；

Step 2b（后续轮单区间）r 从 r ≈ 2(bs_prev – 2B)/n 起递增，对每个 r 在 s 区间 [ceil((2B + rn)/b), floor((3B – 1 + rn)/a)] 内探测

Step 2c（多区间）s 从 s_prev + 1 起递增；Step 3 对每个 [a, b] 与命中的 s，先算 r 的可行范围 [ceil((as – 3B + 1)/n), floor((bs – 2B)/n)]，对每个 r 产新区间 [max(a, ceil((2B + rn)/s)), min(b, floor((3B – 1 + rn)/s))]，区间宽度按约 2/s 收缩，直到某区间收缩为单点即得 m*s0 mod n，再乘 s0 的逆即恢复 m。

第一轮收敛的完整演算：取 n = 67591 = 257 * 263（17 bit，k = 3 字节），B = 2^8 = 256，合法区间 [2B, 3B – 1] = [512, 767]；设真实填充块 em = 0x0002FF = 767

e = 3，密文 c = 767^3 mod 67591，767^2 = 588289，767^3 = 451217663，451217663 = 67591*6675 + 47738，即 c = 47738。

Step1：c 自身解密为 767 合法，无需盲化，s0 = 1。

Step2a：起点 s = ceil(n / (3B)) = ceil(67591 / 768) = ceil(88.01) = 89，探测 oracle(c * 89^3)：解密值 = 76789 mod 67591 = 68263 mod 67591 = 672，落在 [512, 767] 内，有效，s1 = 89。

Step3 收缩：对区间 [512, 767]、s = 89 计算 r 可行范围：r_min = ceil((51289 – 3256 + 1) / 67591) = ceil((45568 – 767)/67591) = ceil(44801/67591) = 1；r_max = floor((76789 – 2*256)/67591) = floor(67751/67591) = 1；仅 r = 1，新区间 = [max(512, ceil((512 + 67591)/89)), min(767, floor((767 + 67591)/89))] = [ceil(68103/89), floor(68358/89)] = [766, 767]（68103/89 ≈ 765.2 取 766；68358/89 ≈ 767.9 取 767）。

一轮就把候选从 256 个（区间 512 至 767）压到 2 个（766 与 767），随后按 Step 2b 继续扫描下一批 s，区间宽度按约 2/s 的比例继续减半，最终收缩到单点 767，剥离头部 00 02 得消息 0xFF。真实参数（2048 位 n）时逻辑不变，仅查询次数指数上升，

96 位密钥约 59 轮、515 万次查询即完整复现该流程。

识别特征

服务器/服务解密后返回区分"填充正确/错误"两种不同响应（错误码、时长、报文差异）。 TLS 握手使用 RSA 密钥交换（cipher suite 含 RSA），且服务端对 PKCS#1 v1.5 填充错误区分响应。 已知服务端公钥 (n, e)，能构造任意密文并观察到 oracle 布尔结果。

若服务器把 RSA 解密结果用作消息密钥或签名前缀，也可配合 CBC 类 oracle 场景。

靶场题目&Writeup

题目：PKCS#1 v1.5 padding oracle 识别：攻击者可对任意提交的密文拿到布尔结果，命中识别特征第 1、3 条。 解题： 计算 k = n 的字节数、B = 2^(8*(k-2))，初始区间 M = [[2B, 3B-1]]。 Step1 找 s0：本地 c 本身有效，s0 = 1（真实环境 c 无效时需先盲化找 s0）。 主循环：单区间且首轮用 Step 2a 从 s = ceil(n/(3B)) 起递增探测；单区间后续轮用 Step 2b 按 r 递推扫描 s 范围（下界用 b、上界用 a）；多区间用 Step 2c 的 s_prev + 1 递增。 Step 3 用新命中的 s 收缩区间集合，直到某区间两端相等。 对恢复的整数剥离 00 02 [PS] 00 前缀得原始消息，除以 s0 得真实明文。本地 96 位密钥约 59 轮、约 515 万次 oracle 查询跑通全流程

工具：原理与题库页参考 https://ctf-wiki.org/crypto/asymmetric/rsa/padding_oracle/ ；

论文复现 https://link.springer.com/article/10.1007/BFb0055716 ；ROBOT 变体官网 The ROBOT Attack – Return of Bleichenbacher's Oracle Threat

脚本

import gmpy2
import random
​
random.seed(20261023)
​
def build_key(bits=96):
   while True:
       p = gmpy2.next_prime(random.getrandbits(bits // 2))
       q = gmpy2.next_prime(random.getrandbits(bits // 2))
       n = p * q
       if n.bit_length() < bits – 4:
           continue
       phi = (p – 1) * (q – 1)
       e = 3
       if gmpy2.gcd(e, phi) == 1:
           return n, e, pow(e, -1, phi)
​
def pkcs1_encrypt(msg, n, e):
   k = (n.bit_length() + 7) // 8
   mlen = len(msg)
   pslen = k – 3 – mlen
   assert pslen >= 8
   ps = bytes(random.choice(range(1, 256)) for _ in range(pslen))
   em = b"\\x00\\x02" + ps + b"\\x00" + msg
   return pow(int.from_bytes(em, "big"), e, n)
​
def pkcs1_oracle_valid(c, n, d):
   k = (n.bit_length() + 7) // 8
   em = pow(c, d, n).to_bytes(k, "big")
   if len(em) < 11:
       return False
   if em[0] != 0 or em[1] != 2:
       return False
   sep = em.find(b"\\x00", 2)
   return sep >= 10
​
def bleichenbacher(c, n, e, oracle):
   k = (n.bit_length() + 7) // 8
   B = 1 << (8 * (k – 2))
   oracle_calls = [0]
   def oc(cc):
       oracle_calls[0] += 1
       return oracle(cc)
   s = 1
   while not oc(c * pow(s, e, n) % n):
       s += 1
   M = [[2 * B, 3 * B – 1]]
   s_prev = s
   iters = 0
   while True:
       iters += 1
       assert iters < 20000, "迭代次数过多"
       if len(M) == 1 and s_prev == 1:
           s = (n + 3 * B – 1) // (3 * B)
           while not oc(c * pow(s, e, n) % n):
               s += 1
       elif len(M) > 1:
           s = s_prev + 1
           while not oc(c * pow(s, e, n) % n):
               s += 1
       else:
           a, b = M[0]
           found = False
           r = 2 * (b * s_prev – 2 * B) // n
           while not found:
               s_lo = (2 * B + r * n + b – 1) // b
               s_hi = (3 * B – 1 + r * n) // a
               for s2 in range(max(s_lo, s_prev + 1), s_hi + 1):
                   if oc(c * pow(s2, e, n) % n):
                       s = s2
                       found = True
                       break
               r += 1
       newM = []
       for a, b in M:
           r_min = (a * s – 3 * B + n) // n
           r_max = (b * s – 2 * B) // n
           for r in range(r_min, r_max + 1):
               lo = max(a, (2 * B + r * n + s – 1) // s)
               hi = min(b, (3 * B – 1 + r * n) // s)
               if lo <= hi:
                   newM.append([lo, hi])
       M = newM
       if len(M) == 1 and M[0][0] == M[0][1]:
           return M[0][0], iters, oracle_calls[0]
       s_prev = s
​
def main():
   n, e, d = build_key(96)
   msg = b"A"
   c = pkcs1_encrypt(msg, n, e)
   oracle = lambda cc: pkcs1_oracle_valid(cc, n, d)
   m_rec, iters, n_q = bleichenbacher(c, n, e, oracle)
   k = (n.bit_length() + 7) // 8
   em = m_rec.to_bytes(k, "big")
   sep = em.find(b"\\x00", 2)
   assert sep >= 10
   rec = em[sep + 1:]
   assert rec == msg
   print("SUCCESS: 恢复 PKCS#1 v1.5 填充明文 =", rec.decode())
   print("迭代轮数 =", iters, " oracle 查询次数 =", nc)
   print("flag: flag{bleichenbacher_oracle_poc}")
​
main()