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=c2ec'=c * 2^e as the ciphertext, then halve the result.

Proof

Note that:

  1. cdm(modn)c^d \equiv m \pmod n

  2. dd is chosen such that ed1(modϕ(n))ed \equiv 1 \pmod {\phi(n)}, i.e. ed=1+kϕ(n),kN0ed=1 + k\phi(n), k\in \mathbb{N_0}.

The decryption of cc' would yield:

(c2e)dmodncd2edmodn(cdmodn)(2edmodn)modnm(21+kϕ(n)modn)modnm2(2kϕ(n)modn)modn\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

m2(2kϕ(n)modn)modn2mmodnm * 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