Links

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. 1.
    cdm(modn)c^d \equiv m \pmod n
  2. 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