Challenge description

RSA strikes strikes strikes strikes strikes again again again again again!

Author: JoshDaBosh

Drag Racing

rsa2.py

from Crypto.Util.number import getStrongPrime, bytes_to_long, long_to_bytes
f = open("flag.txt").read()
m = bytes_to_long(f.encode())
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 65537
c = pow(m,e,n)
print("n =",n)
print("e =",e)
print("c =",c)

d = pow(e, -1, (p-1)*(q-1))

c = int(input("Text to decrypt: "))

if c == m or b"actf{" in long_to_bytes(pow(c, d, n)):
    print("No flag for you!")
    exit(1)

print("m =", pow(c, d, n))

Background

The first few lines of code initialize the parameters for the RSA encryption and encrypt the flag. We get the encrypted flag c the modulus n and the public exponent e.

After that we can provide an input text which will get decrypted and we get the decrypted value back.

print("m =", pow(c, d, n))

Great so we will just provide the encrypted flag c as input and get the decrypted value back. Well unfortunately we have some restriction on what we are allowed to decrypt. We are not allowed to provide the ciphertext that contains the flag and we the ciphertext is not allowed to be the flag.

if c == m or b"actf{" in long_to_bytes(pow(c, d, n)):
    print("No flag for you!")
    exit(1)

We need to find a way of decrypting the encrypted flag but we are not allowed to just provide the encrypted value.

Solution

While we are not allowed to provide the encrypted value itself, we can provide any other value we want. One of the (generally unwanted) properties of RSA is that is partially homomorphic, particular with respect to multiplication.

Homomorphic encryption (HE) allows us to perform computations on the ciphertext without losing our ability to decrypt it. In fact, we can multiply a ciphertext by a value and then decrypt the ciphertext, and the resulting plaintext will be the original plaintext multiplied by the same value we used for multiplication. Full Homomorphic Encryption (FHE) even allows us to add and multiply with the ciphertext. HE can be incredibly useful because it enables the possibility to provide data to an untrusted 3 party and this 3 party can perform operations without knowing the underlying data. Due to the popularity of Cloud Computing this has become a very active field of research.

Unfortunately in this case, we can just multiply the ciphertext value c with a random value r and send it back to the server c_blind. The decrypted ciphertext p_blind will not contain the flag anymore since the plaintext is now m*r. Therefore we will get the decrypted value back. Once we have the decrypted value p_blind we just need to multiply the inverse of r (r^-1) to obtain the flag.

$$c_{blind} = c*r^e \mod n$$

$$p_{blind} = (c*r^e)^d \mod n$$

$$flag = p_{blind}*r^{-1} \mod n$$

$$flag = (c*r^e)^d * r^{-1} \mod n$$

$$flag = c^d*r^{ed} * r^{-1} \mod n$$

$$flag = m \mod n$$

Solve script

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from pwn import *
from Crypto.Util.number import getStrongPrime, bytes_to_long, long_to_bytes

host = args.HOST or 'challs.actf.co'
port = int(args.PORT or 32400)

io = connect(host, port)

io.recvuntil(b"n = ")
n = int(io.recvline().strip())
io.recvuntil(b"e = ")
e = int(io.recvline().strip())
io.recvuntil(b"c = ")
c = int(io.recvline().strip())


print("n =", n)
print("e =", e)
print("c =", c)

# Get random number
r = randint(1, n)

c_blind = str((pow(r, e, n) * c) % n)
c_blind = c_blind.encode("ascii")
print(b"c_blind =", c_blind)

io.recvuntil(b"Text to decrypt:")
io.sendline(c_blind)

io.recvuntil(b"m = ")
p_blind = int(io.recvline().strip())

flag = (p_blind * pow(r, -1, n)) % n

print("flag =", long_to_bytes(flag))

io.close()

Output:

[x] Opening connection to challs.actf.co on port 32400
[x] Opening connection to challs.actf.co on port 32400: Trying 34.145.241.80
[+] Opening connection to challs.actf.co on port 32400: Done
n = 100963233624860038197627735393359436603895968632385284100792214915444818472967757614580848587867381066178275510620837168603569241152003670616445510226193650389495274901832662347603174225281633537729665087132051659390273696069824542458131860795224016120849753512227030022789761336628759259090663818546203323103
e = 65537
c = 81045886406383373095942400026617040375276544725137102574846938275265961470508373189405368865071739048909654445596632838949097886221459878404904415266057257764378042289714480234188955069611881666819620328989528867655149595808374526548141135317444400948247843232806649387751337942237609995969237560983745003665
b'c_blind =' b'94447985360632470711877889073376624051363330391725810822985507236113706402859573494546610066569861728599660948488282003972540407963139891776408750216026990910203861433536010625524825583108140899599802003454839457399674167046174053030099201149520797398743598035163701541885670902608210977073417005483187844152'
flag = b'actf{rs4_is_sorta_homom0rphic_50c8d344df58322b}'
[*] Closed connection to challs.actf.co port 32400