James Manger’s CCA on RSAES-OAEP

Introduction

98年，Daniel BlechenbacherPKCS #1 v1.5 RSA给日了[1]，所以PKCS #1 v2.0 RSA加入了这个Optimal Asymmetric Encryption Padding(OAEP)。

PKCS #1 v2.0 RSA says, “a chosen ciphertext attack is ineffective to against a plaintext-aware encryption scheme such as RSAES-OAEP”.

RSAES-OAEP

OAEP就是一种对RSA加密的一种填充方案。

Chosen Ciphertext Attack

• integrity check failspow(c, d, n) >= B
• decryption failspow(c, d, n) < B

RSA一个很fishy的一点就是它的malleability

Reproduction

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  import os from Crypto.Util.number import * p = getPrime(512) q = getPrime(512) n = p*q e = 0x10001 print(p, q, n, sep='\n') m = bytes_to_long(os.urandom(16)) print(m) c = pow(m, e, n) print(c) d = inverse(e, (p-1)*(q-1)) B = 2**(1024-8) while True: inp = int(input("$")) print(pow(inp, d, n) > B)  然后根据攻击流程写出exp   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71  from pwn import * r = process(argv=["python3", "OAEP.py"]) e = 0x10001 p, q, n, m, c = [int(r.recvline()) for _ in range(5)] # print(p,q,n,m,c) B = 2**(1024-8) # Step 1 f1 = 1 i = 0 while True: i += 1 f1 = f1 * 2 % n # start from 2 payload = pow(f1, e, n) * c % n # Decrypt: f1 * m r.sendlineafter(b"$ ", str(payload)) response = r.recvline(keepends=False) print(i, response) if response == b"True": # f1 * m > B break # else: continue # Now, f1 * m is in [B, 2B), hence f1/2 * m is in [B/2, B) f1_2 = f1 // 2 assert(f1_2*m >= B//2 and f1_2*m < B) # Step 2 f2 = ((n+B)//B) * f1_2 i = 1 while True: if i > 1: f2 = f2 + f1_2 # f2 * m is in [n/2, n+B) i += 1 payload = pow(f2, e, n) * c % n # Decrypt: f2 * m r.sendlineafter(b"$", str(payload)) response = r.recvline(keepends=False) print(i, response) if response == b"False": # n < f2 * m < n + B break # else: continue # Now, f2 * m is in [n, n+B) print(f2*m >= n and f2*m < n+B) ceiling = lambda a, b: a//b + (1 if a % b != 0 else 0) # Step 3 # f2 * m is in [n, n+B), so m is in [n/f2, (n+B)/f2) m_min = ceiling(n, f2) m_max = (n+B) // f2 time = 0 while m_min != m_max: time += 1 f_tmp = (2*B) // (m_max - m_min) # ftmp * m is in [2n, 2n+2B) i = (f_tmp * m_min) // n f3 = ceiling(i*n, m_min) payload = pow(f3, e, n) * c % n r.sendlineafter(b"$ ", str(payload)) response = r.recvline(keepends=False) print(i, time, response) if response == b"True": # i*n + B < f3 * m < i*n + 2*B m_min = ceiling(i*n + B, f3) else: # i*n < f3 * m < i*n + B m_max = (i*n+B) // f3 print(m_min == m == m_max) r.interactive() 

PoC成功！

Extension

It is important that the error messages output in steps 4 [interger-to- octets conversion] and 5 [OAEP decoding] be the same.

1. Bleichenbacher, Daniel. “Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS# 1.” Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1998.

2. Manger, James. “A chosen ciphertext attack on RSA optimal asymmetric encryption padding (OAEP) as standardized in PKCS# 1 v2. 0.” Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2001.

3. Boneh, Dan, Antoine Joux, and Phong Q. Nguyen. “Why textbook ElGamal and RSA encryption are insecure.” International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2000.