Crypto CTF 2020 Writeup

Trailing Bits

The description says that both of head and tail bits are lost, so I just tried adding some bits both of them.

from itertools import product
with open('output.txt') as f:
    s = f.read().strip()

for i, j in product(range(10), repeat=2):
    try:
        bits = '1'*i + s + '1'*j
        x = bytes.fromhex(f'{int(bits, 2):x}')
        if b'CCTF{' in x:
            print(x)
            break
    except:
        pass

Flag: CCTF{it5_3n0u9h_jU5T_tO_sH1ft_M3}

Amsterdam

There are two stages in encrypt().

1. Calculate m from msg.
2. Calculate c from m.

We need to carry out the inverse operation for each stage.

Decrypt m from c

In encrypt(), c is decided by lower 2 bits of m. Conversely, we can reconstruct m using c. This is the most difficult part in this challenge.

Thinking c in ternary, each trit indicates a piece of information about the lower 2 bits of m. We can reconstruct by comparing m and c from lower digit.

Decrypt msg from m

Now we know m, we can also calculate the value of n because this value is equal to the bit length of m. Furthermore, since n is small enough, we can search for k using brute-force. All that is left is to recover msg by calculating:

\[ {\rm msg} = \sum_{2 \le i \le n, m_i=1} \binom{n-i}{k}\]

from Crypto.Util.number import *
from functools import reduce
import operator
from output import enc

# enc = 5550332817876280162274999855997378479609235817133438293571677699650886802393479724923012712512679874728166741238894341948016359931375508700911359897203801700186950730629587624939700035031277025534500760060328480444149259318830785583493

def comb(n, k):
    if k > n :
        return 0
    k = min(k, n - k)
    u = reduce(operator.mul, range(n, n - k, -1), 1)
    d = reduce(operator.mul, range(1, k + 1), 1)
    return u // d 

def enc_to_m(enc):
    mbits = ''
    two = 0 
    while enc > 0:
        if enc % 3 == 0:
            mbits = f'{two}{mbits}'
        elif enc % 3 == 1:
            mbits = f'{1-two}{mbits}'
            two = 0
        else:
            mbits = f'{1-two}{mbits}'
            two = 1
        enc //= 3
    return int(mbits, 2)

def m_to_msg(m, n, k):
    m = bin(m)[2:]
    msg = 0
    for i in range(2, n+1):
        if m[i-1] == '1':
            msg += comb(n-i, k)
            k -= 1

    return msg

m = enc_to_m(enc)
n = len(bin(m)[2:])
for k in range(n):
    msg = m_to_msg(m, n, k)
    try:
        msg = bytes.fromhex(f'{msg:x}')
        if b'CCTF{' in msg:
            print(msg)
            break
    except:
        pass 

Flag: CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!}