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

crypto
,

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#!/usr/bin/python3
from Crypto.PublicKey import RSA
from Crypto.Util.number import *

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

def menu():0
    print()
    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())
        used.append(m)

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

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

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

        else:
            m = decrypt(c)

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

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

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

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.

Attack

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 .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from pwn import *
import gmpy2
from Crypto.Util.number import *

v1 = 2
v2 = 3

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

Bonus

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!