No Padding, No Problem (90)

RSA chosen-ciphertext attack (CCA)

Problem

Oracles can be your best friend, they will decrypt anything, except the flag's ciphertext. How will you break it? Connect with nc mercury.picoctf.net 30048.

Solution

This is a chosen-ciphertext attack (CCA) against RSA. We are able to choose any ciphertext, except the flag's ciphertext, to decrypt.

TL;DR: we can use cโ€ฒ=cโˆ—2ec'=c * 2^e as the ciphertext, then halve the result.

Proof

Note that:

  1. cdโ‰กm(modn)c^d \equiv m \pmod n

  2. dd is chosen such that edโ‰ก1(modฯ•(n))ed \equiv 1 \pmod {\phi(n)}, i.e. ed=1+kฯ•(n),kโˆˆN0ed=1 + k\phi(n), k\in \mathbb{N_0}.

The decryption of cโ€ฒc' would yield:

(cโˆ—2e)dmodโ€‰โ€‰nโ‰กcdโˆ—2edmodโ€‰โ€‰nโ‰ก(cdmodโ€‰โ€‰n)(2edmodโ€‰โ€‰n)modโ€‰โ€‰nโ‰กmโˆ—(21+kฯ•(n)modโ€‰โ€‰n)modโ€‰โ€‰nโ‰กmโˆ—2โˆ—(2kฯ•(n)modโ€‰โ€‰n)modโ€‰โ€‰n\begin{align} (c * 2^e)^d \mod n &\equiv c^d * 2^{ed} \mod n \\ &\equiv (c^d \mod n)(2^{ed} \mod n) \mod n \\ &\equiv m * (2^{1+k\phi(n)} \mod n) \mod n \\ &\equiv m * 2 * (2^{k\phi(n)} \mod n) \mod n \\ \end{align}

From Euler's Theorem, if gcd(a,n)=1gcd(a,n)=1 , then

aฯ•(n)โ‰ก1(modn)a^{\phi(n)} \equiv 1\pmod n

Thus, we have

mโˆ—2โˆ—(2kฯ•(n)modโ€‰โ€‰n)modโ€‰โ€‰nโ‰ก2mmodโ€‰โ€‰nm * 2 * (2^{k\phi(n)} \mod n) \mod n \equiv 2m \mod n

At this point, we can halve the result to get mm .

Script

from Crypto.Util.number import *
from pwn import *
from decimal import *
import re

getcontext().prec = 1000

conn = remote('mercury.picoctf.net', 30048)
raw_text = conn.recvuntil('Give me ciphertext to decrypt:').decode()

print(raw_text)

m = re.search(r"n: ([0-9]+)\ne: ([0-9]+)\nciphertext: ([0-9]+)", raw_text)
n = int(m[1])
e = int(m[2])
c = int(m[3])

to_decrypt = c * pow(2, e, n) % n

conn.send(str(to_decrypt) + '\r\n')

print("Sent:", to_decrypt)

result = conn.recvline().decode()

print(result)

m = re.search(r"([0-9]+)", result)
result = int(Decimal(m[1]) / 2)

print(hex(result))
print('Result:', long_to_bytes(result))

References

Last updated