一、背景故事1998年Daniel Bleichenbacher发表了一篇震惊密码学界的论文——针对PKCS#1 v1.5填充的适应性选择密文攻击。这篇论文揭示了一个残酷的事实只要服务器对非法填充和其他错误返回不同的响应攻击者就能在无需私钥的情况下解密任意密文。这个攻击在现实世界造成了巨大影响OpenSSL多次被曝出相关漏洞直到现在仍有系统受其威胁。二、PKCS#1 v1.5 填充格式在深入攻击前我们必须理解RSA加密时的填充规则Plain Text-------------------------------------------------- | 0x00 | 0x02 | 随机非零字节... | 0x00 | 明文 | --------------------------------------------------加密流程明文必须比模数短至少11字节在明文前插入0x00 0x02用随机非零字节填充至合适长度在明文前插入0x00分隔符三、Padding Oracle 的威力所谓的padding oracle是指服务器在解密时会检查填充是否合法如果填充合法 → 继续处理可能报其他错误如果填充非法 → 返回特定错误如Bad padding关键洞察攻击者不需要知道明文只需要知道填充是否正确这个布尔值。四、攻击原理详解Phase 1Blinding盲化我们需要找到一个整数 s0使得 c0c⋅mod n 解密后有合法填充。由于原始密文 c 本身就是合法的所以 s01 总是可行的。此时m0mod nm⋅s0 mod nPhase 2寻找边界我们从 s2 开始搜索直到找到一个 s 使得 c⋅se mod n 有合法填充。根据PKCS#1规则合法填充意味着2B≤m⋅s mod n3B其中 Bk 是密钥字节长度。Phase 3区间收窄这是攻击的核心。对于每个找到的合法 s我们可以得到一个关于 m 的不等式rB/s≤m(r1)B/s通过收集多个这样的区间利用中国剩余定理逐步缩小 m 的范围。Phase 4唯一解当区间集合缩小到只有一个整数时我们就得到了明文 m。五、完整解题代码Pythonfrom math import ceil from Crypto.Util.number import long_to_bytes def bleichenbacher_attack(c, n, e, oracle, k): c: 密文 n: 模数 e: 公钥指数 oracle: 填充预言机函数返回True表示填充合法 k: 密钥字节长度 B 1 (8 * (k - 1)) # Phase 1: Blinding s 1 while not oracle(pow(c * pow(s, e, n), 1, n)): s 1 M [(2 * B, 3 * B - 1)] # Phase 2-3: Narrowing intervals while len(M) gt; 1: found False for candidate in range(ceil(2 * n / (3 * B)), n): s candidate if oracle(pow(c * pow(s, e, n), 1, n)): new_M [] for (a, b) in M: lower ceil((a * s - 3 * B 1) / n) upper (b * s - 2 * B) // n for r in range(lower, upper 1): start max(a, ceil((2 * B r * n) / s)) end min(b, (3 * B - 1 r * n) // s) if start lt; end: new_M.append((start, end)) M new_M found True break if not found: s 1 # Phase 4: Extract result m M[0][0] return long_to_bytes(m)六、防御建议使用OAEP填充替代不安全的PKCS#1 v1.5统一错误信息所有解密失败都返回相同错误恒定时间验证避免时序攻击限制查询次数防止暴力枚举
深入剖析 Bleichenbacher‘s Padding Oracle Attack
一、背景故事1998年Daniel Bleichenbacher发表了一篇震惊密码学界的论文——针对PKCS#1 v1.5填充的适应性选择密文攻击。这篇论文揭示了一个残酷的事实只要服务器对非法填充和其他错误返回不同的响应攻击者就能在无需私钥的情况下解密任意密文。这个攻击在现实世界造成了巨大影响OpenSSL多次被曝出相关漏洞直到现在仍有系统受其威胁。二、PKCS#1 v1.5 填充格式在深入攻击前我们必须理解RSA加密时的填充规则Plain Text-------------------------------------------------- | 0x00 | 0x02 | 随机非零字节... | 0x00 | 明文 | --------------------------------------------------加密流程明文必须比模数短至少11字节在明文前插入0x00 0x02用随机非零字节填充至合适长度在明文前插入0x00分隔符三、Padding Oracle 的威力所谓的padding oracle是指服务器在解密时会检查填充是否合法如果填充合法 → 继续处理可能报其他错误如果填充非法 → 返回特定错误如Bad padding关键洞察攻击者不需要知道明文只需要知道填充是否正确这个布尔值。四、攻击原理详解Phase 1Blinding盲化我们需要找到一个整数 s0使得 c0c⋅mod n 解密后有合法填充。由于原始密文 c 本身就是合法的所以 s01 总是可行的。此时m0mod nm⋅s0 mod nPhase 2寻找边界我们从 s2 开始搜索直到找到一个 s 使得 c⋅se mod n 有合法填充。根据PKCS#1规则合法填充意味着2B≤m⋅s mod n3B其中 Bk 是密钥字节长度。Phase 3区间收窄这是攻击的核心。对于每个找到的合法 s我们可以得到一个关于 m 的不等式rB/s≤m(r1)B/s通过收集多个这样的区间利用中国剩余定理逐步缩小 m 的范围。Phase 4唯一解当区间集合缩小到只有一个整数时我们就得到了明文 m。五、完整解题代码Pythonfrom math import ceil from Crypto.Util.number import long_to_bytes def bleichenbacher_attack(c, n, e, oracle, k): c: 密文 n: 模数 e: 公钥指数 oracle: 填充预言机函数返回True表示填充合法 k: 密钥字节长度 B 1 (8 * (k - 1)) # Phase 1: Blinding s 1 while not oracle(pow(c * pow(s, e, n), 1, n)): s 1 M [(2 * B, 3 * B - 1)] # Phase 2-3: Narrowing intervals while len(M) gt; 1: found False for candidate in range(ceil(2 * n / (3 * B)), n): s candidate if oracle(pow(c * pow(s, e, n), 1, n)): new_M [] for (a, b) in M: lower ceil((a * s - 3 * B 1) / n) upper (b * s - 2 * B) // n for r in range(lower, upper 1): start max(a, ceil((2 * B r * n) / s)) end min(b, (3 * B - 1 r * n) // s) if start lt; end: new_M.append((start, end)) M new_M found True break if not found: s 1 # Phase 4: Extract result m M[0][0] return long_to_bytes(m)六、防御建议使用OAEP填充替代不安全的PKCS#1 v1.5统一错误信息所有解密失败都返回相同错误恒定时间验证避免时序攻击限制查询次数防止暴力枚举
