Christmas CTF 2019 / Christmas Pocket

As a crypto newbie, I’ve been studying cryptography lately. At the first Christmas CTF I ever entered, there were about two crypto challenges. I gave up quickly on the “hide and seek” challenge, and shortly after took on the “Christmas Pocket” challenge that came out next.

At first I skimmed the code and tried to wing it by intuition with no equations — and predictably, I just floundered and burned time. After clearing my head, I spent about an hour and ten minutes on the subway organizing the equations on my iPad, and out came a few relations that looked capable of recovering the private key. The moment I got home I wrote the code and the challenge fell. I felt really good about how much crypto I’d studied recently, haha.

(The “hide and seek” challenge was RSA. From a rough read of the code without any math, it looked like the most I could recover was the top 512 bits of p. And even if I set up the equations and got those 512 bits, I couldn’t picture the next step, so I gave up, haha..)

Solution

The source code provided by the challenge is as follows.

import binascii
from random import randint
from math import gcd
import gmpy

class pockets:
    def __init__(self):
        self.max_string_len = 28
    def gen_key(self):
        self.pocket = [randint(1,10)]

        for i in range(8 * self.max_string_len - 1):
            s = sum(self.pocket)
            self.pocket.append(s + randint(s, s*3))

        s = sum(self.pocket)
        self.mod = randint(s, s*3)

        self.mul = randint(1,self.mod)
        while gcd(self.mul,self.mod) != 1:
            self.mul = randint(1,self.mod)

        self.pubkey = list(map(lambda x : self.mul * x % self.mod, self.pocket))

    def encrypt(self,msg):
        if len(msg)  > 30:
            print("Message is too long!")
            return ''
        binary = bin(int(binascii.hexlify(msg),16))[2:]
        l = len(binary)
        if l % 8 != 0:
            binary = binary.rjust(l + (8-(l%8)),'0')
        c = 0
        for i in range(len(binary)):
            if binary[i] == '1':
                c += self.pubkey[i]
        return hex(c)[2:]

    def decrypt(self,enc):
        enc = int(enc,16)
        inv = int(gmpy.invert(self.mul, self.mod))
        m = inv * enc % self.mod
        s = ''
        for i in reversed(self.pocket):
            if m >= i:
                m -= i
                s += '1'
            else:
                s += '0'
        s = binascii.unhexlify(hex(int(s[::-1],2))[2:])
        return s

flag = open('flag','rb').read()[:28]
p = pockets()
p.gen_key()
print('public key: ' + str(p.pubkey))
print('encrypted: ' + p.encrypt(flag))

We have to analyze the key generation, encryption, and decryption. The public and private keys are:

Public  Key : pubkey
Private Key : mul, mod, pocket

The public key is provided through the output file, so it’s a value we know. I figured that if I could find a weakness in the encryption or decryption, I could compute the private key from the public key.

Analyzing key generation, encryption, and decryption and writing an equation for each variable gives:

p[i] = pocket[i]
1 <= p[0] <= 10 ----- A
3^i-3^(i-1) <= (3^i-3^(i-1))/p[i] <= p[i] <= (5^i - 5^(i-1))/p[i] <= (5^i - 5^(i-1))*10

s[i] = p[0] + p[1] + ... + p[i]
3^i <= s[i] <= 5^i * 10

n = mod
m = mul
1 <= m <= n
gcd(m, n) = 1
pubkey[i] = m * p[i] % n
m*p[i] = k*n + pubkey[i]

p[0] <= pubkey[0] = m * p[0] <= n * p[0] ----- B

2 * p[0] <= pubkey[1] = m * p[1] <= 4*n*p[0] ----- C

2 <= 2*p[0] <= p[1] <= 4*p[0] <= 40
m*p[1] = k*n + pubkey[1]
m*p[1] - pubkey[1] = k*n <= 40n - pubkey[1] ----- D

Equation B tells us pubkey[0] <= n*p[0]. So if we factor pubkey[0] and pick out a value between 1 and 10, that value is pocket[0]. Factoring the given value, the candidates between 1 and 10 are 3 or 5. Since mul = pubkey[0]/pocket[0], we only need to consider the two mul values corresponding to pocket[0] being 3 or 5.

Equation A lets us bound equation C, and looking at C and D together reveals the range of k: it’s between 1 and 40. Brute-forcing over k yields candidate values of n. That gives us two of the three private-key values — mul and mod.

Now it’s time to recover the last private-key value, pocket. Since pubkey = mul*pocket (mod mod), we compute inv, the inverse of mul modulo mod. Then pocket = inv * pubkey (mod mod) recovers the values.

Recovering the private key through the process above and decrypting gives the flag.

import binascii
from random import randint, seed
from math import gcd
import gmpy, gmpy2

pubkey = [57547174720929319669417981787834313194612810663813495370531016263447357728731699157659796170432781491310583323984204686633067191303305, 7230019189526071368255992435183734432388646764251159135692547283856631509443555154580729756304347754554964777045318900566603425390798, ...skip...]
encrypted = '1304d3988965eceeb40dd91a7c97c0e04851d0a362d6b8b671ef8471568cf685df8f09ed8d55ca9a3383f846ac74fc4b7d468387154f4f6dc7'

def decrypt(enc, mul, mod, pocket):
    enc = int(enc,16)
    inv = int(gmpy.invert(mul, mod))
    m = inv * enc % mod
    s = ''
    for i in reversed(pocket):
        if m >= i:
            m -= i
            s += '1'
        else:
            s += '0'
    s = binascii.unhexlify(hex(int(s[::-1],2))[2:])
    return s

'''
m = mul
n = mod
'''

cnt = 0
p0 = 3 # 3 or 5
m = pubkey[0] // p0

nList = []

for p1 in range(2, 41):
  for k in range(1,41):
    n = (m*p1 - pubkey[1]) // k
    gcd = gmpy2.gcd(m,n)
    modulo = (m*p1 - pubkey[1]) % k
    if gcd == 1 and modulo == 0 and (n >= pow(3, 8*28) and n <= pow(5, 8*28)*3) and m <= n:
      cnt +=1
      nList.append(n)

for n in nList:
  pocket = [p0]
  for i in range(1, 8*28):
    inv = int(gmpy.invert(m, n))
    p = inv * pubkey[i] % n
    pocket.append(p)
  print(decrypt(encrypted, m, n, pocket))

# b'X-MAS{Pocket_o_Fukuramasete}'