X-MAS CTF 2018 / Santa's List

Solution

#!/usr/bin/python3
from Crypto.PublicKey import RSA
from Crypto.Util.number import *

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

def menu():
    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')

while True:
    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

The challenge code is shown above.

Looking up the docs for the RSA class’s generate method, we can confirm that the default value of e is 65537.

Because the challenge provides encryption and decryption oracles, we can also recover n.

c = m**e (mod n)

Outside the congruence modulo n, m**e can be written as:

m**e = k*n + c
k*n = m**e + c

Since we know m, e, and c, we can compute kn. Using the encryption oracle with several different values of m gives several different kn values; taking their GCD yields n.

Below is the decryption oracle. The if m % no == 0: part acts as a filter. Because of it, the flag value and the values used with the encryption oracle cannot be decrypted.

    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))

But things get a little different in the congruence modulo n. (Thanks to @zanywhale for kindly answering my pesky questions every time. ^_^)

a*m % m == 0 (mod n)

The identity holds when a*m is less than or equal to n, but may fail once a*m exceeds n.

This property lets us bypass the filter, so we can run a chosen-ciphertext attack. Pick a suitable a, then submit the following c to the decryption oracle:

c = (a**e % n)*(flag_encrypted)

This ultimately yields a*flag; computing the inverse of a modulo n and multiplying it back gives the flag.

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

#context.log_level='debug'

e = 65537

cmd = "python3 ./xmas.py"
p = process(cmd.split(" "))

p.recvuntil("Galf - ")
flag_encrypted = int(p.recvline()[:-1], 16)

c = []
m = [2,3,4]

for m_ in m:
  p.sendlineafter("Exit\n", "1")
  p.sendlineafter("> ", number.long_to_bytes(m_))
  p.recvuntil('nEncrypted: ')
  c.append(int(p.recvline()[:-1]))

kn = []

for i in xrange(3):
  kn.append(m[i]**e - c[i])

tmp = gmpy2.gcd(kn[0], kn[1])
n = gmpy2.gcd(tmp, kn[2])

assert( gmpy2.powmod(m[0], e, n) == c[0] )

val = 2123123
inv = number.inverse(val, n)

c_ = flag_encrypted * gmpy2.powmod(inv,e,n)
p.sendlineafter("Exit\n", "2")
p.sendlineafter("> ", str(c_))

print("n   = 0x%x" % n)
print("val = 0x%x" % val)
print("inv = 0x%x" % inv)
p.interactive()

Reference

https://blog.encrypted.gg/720

https://pwnthemole.github.io/crypto/2018/12/22/xmasctfsantaslist.html