Home Blog About GitHub

pwnthem0le is a Turin-based, hacking students group born out of CyberChallenge 2018. Read more about us!

22 December 2018

X-MAS CTF 2018 - Santa's List 1 & 2 Writeup

by mr96

These two challenge are very similar: the only difference is that in the first one we can do how many requests we want to the server, while in the second one we are limited to 5 requests. We’ll treat only the second, showing a solution that works in 4 requests.
We’re given the Python code used on the server:

from Crypto.PublicKey import RSA
from Crypto.Util.number import *

FLAG = open('flag.txt', 'r').read().strip()

def menu():0
    print('[1] Encrypt')
    print('[2] Decrypt')
    print('[3] Exit')
    return input()

def encrypt(m):
    return pow(m, rsa.e, rsa.n)

def decrypt(c):
    return pow(c, rsa.d, rsa.n)

rsa = RSA.generate(1024)
flag_encrypted = pow(bytes_to_long(FLAG.encode()), rsa.e, rsa.n)
used = [bytes_to_long(FLAG.encode())]

print('Ho, ho, ho and welcome back!')
print('Your list for this year:\n')
print('Sarah - Nice')
print('Bob - Nice')
print('Eve - Naughty')
print('Galf - ' + hex(flag_encrypted)[2:])
print('Alice - Nice')
print('Johnny - Naughty')

for i in range(5):
    choice = menu()

    if choice == '1':
        m = bytes_to_long(input('\nPlaintext > ').strip().encode())

        print('\nEncrypted: ' + str(encrypt(m)))

    elif choice == '2':
        c = int(input('\nCiphertext > ').strip())

        if c == flag_encrypted:
            print('Ho, ho, no...')

            m = decrypt(c)

            for no in used:
                if m % no == 0:
                    print('Ho, ho, no...')

                print('\nDecrypted: ' + str(m))

    elif choice == '3':
        print('Till next time.\nMerry Christmas!')

print('Too many requests made... Disconnecting...')

Code Analysis

The code looks very simple, basically we’re given the encrypted flag, encrypted with a secure RSA key with the standard exponent (as it is not specified when creating the key). We can encrypt whatever we want, but we can’t decrypt things that, when decrypted, are multiples of the flag or multiples of the things we’ve encrypted.


The first thing is to recover the modulus : suppose we encrypt two different integers obtaining , then we have that

and so , most likely with if we choose the integers such that .

Once we recovered the rest is trivial: take the least prime such that it divides the decrypted flag (I’m lazy so I waited for it to be equal to 2), so we have

then simply decrypt 2 to get and multiply it with the previous result to get the decimal value of the flag. Use whatever long_to_bytes function to get the string.

Here’s the Python code for the attack, I did the last part by hand using the interactive mode from pwntools, the script simply recovers .

from pwn import *
import gmpy2
from Crypto.Util.number import *

v1 = 2
v2 = 3

r = remote("", 16002)
r.recvuntil("Galf - ")
flag = int(r.recvline().decode().rstrip("\n"),16)
for _ in range(6):
print(r.recvuntil("Encrypted: "))
c1 = int(r.recvline().decode().rstrip("\n"))
print(r.recvuntil("Encrypted: "))
c2 = int(r.recvline().decode().rstrip("\n"))
n = gmpy2.gcd(v2 ** 65537 - c2, v1 ** 65537 - c1)
assert pow(v1, 65537, n) == c1
assert flag % 2 == 0
to_send = flag//2


The modulus can be recovered with only one request, that is

The flag can be also recovered with only one requests, but this is a little bit trickier and left to the reader :) simply notice that, with this method, we only need 2 requests!

tags: crypto  rsa