TJ CTF 2024

Alkane [209 pts]

I hate standing in line for gas….

Here’s the Python source:

schedule = # ommitted because too long for writeup

key = open("flag.txt","rb").read()

key = key.replace(b"tjctf{", b"").replace(b"}", b"")

message = bytearray(b"yellow submarine")

def get_bit(b, n):
    byte = b[n // 8]
    return (byte >> (7 - (n % 8))) & 1

def set_bit(b, n, v):
    byte = b[n // 8]
    byte &= ~(v << (7 - (n % 8)))
    byte |= v << (7 - (n % 8))
    b[n // 8] = byte
    return b

def bfri(i):
    a = hex(i)[2:]
    if (len(a) % 2 == 1):
        a = "0" + a
    return bytes.fromhex(a)

def xor(x1, x2):
    assert len(x1) == len(x2)
    return b"".join([bfri(x1[i] ^ x2[i]) for i in range(len(x1))])

def band(x1, x2):
    assert len(x1) == len(x2)
    return b"".join([bfri(x1[i] & x2[i]) for i in range(len(x1))])

def rrot(x1, n):
    arr = bytearray(x1)
    for i in range(len(x1)):
        arr[(i + n) % len(x1)] = x1[i]
    return arr

def lrot(x1, n):
    arr = bytearray(x1)
    for i in range(len(x1)):
        arr[i] = x1[(i + n) % len(x1)]
    return arr

def keysch(k):

    out = bytearray(b"\x00"*16)

    arr = [0 for i in range(128)]

    for i in range(128):
        for bit_loc in schedule[i]:
            arr[i] ^= get_bit(k, bit_loc)

    for i in range(128):
        out = set_bit(out, i, arr[i])
    
    return out


def enc(p, k):
    dat = bytearray(p)
    return xor(p, keysch(k))

def dec(c, k):
    dat = bytearray(c)
    return xor(c, keysch(k))

c = enc(message, key)

print("m:", message)
print("c:", c)

So… what exactly is going on here?

Let’s break it down step-by-step.

Step 1

key = open("flag.txt","rb").read()

key = key.replace(b"tjctf{", b"").replace(b"}", b"")

message = bytearray(b"yellow submarine")

flag.txt becomes the key, minus the flag prefix and suffix. The message being encrypted is “yellow submarine”.

Step 2

def enc(p, k):
    dat = bytearray(p)
    return xor(p, keysch(k))

c = enc(message, key)

The encryption itself is just a XOR between the message plaintext and some key generated by calling keysch(k).

Step 3

def keysch(k):

    out = bytearray(b"\x00"*16)

    arr = [0 for i in range(128)]

    for i in range(128):
        for bit_loc in schedule[i]:
            arr[i] ^= get_bit(k, bit_loc)

    for i in range(128):
        out = set_bit(out, i, arr[i])
    
    return out

The keyschedule function first creates a bytearray of b'\x00*16'. Then, it creates an array arr filled with 128 0’s. arr turns out to represent the binary of the ciphertext.

Step 3.1

We then enter a for loop with 128 iterations. For each iteration, we enter another for loop that loops through every bit_loc in schedule[i]. arr[i] is XORed with the result of get_bit(k, bit_loc).

def get_bit(b, n):
    byte = b[n // 8]
    return (byte >> (7 - (n % 8))) & 1

By just testing custom inputs on this function, I figured out that get_bit simply returns the nth bit of b == k == flag.

Step 3.2

After the whole 128-iteration for loop completes, we enter another for loop. Here, we simply set out equal to the result of set_bit(out, i, arr[i]).

def set_bit(b, n, v):
    byte = b[n // 8]
    byte &= ~(v << (7 - (n % 8)))
    byte |= v << (7 - (n % 8))
    b[n // 8] = byte
    return b

Similar to the get_bit function. set_bit simply sets the nth bit of b == out == keysch return value to v.

Finally, we return out.

So, essentially, each bit of the result of keysch, which is XORed with the plaintext “yellow submarine” to produce the ciphertext, is equivalent to the XOR of 64 (the length of each array in schedule) bits of the flag.

z3????

no. we have 128 equations, 128 variables, and 64 variables per equation. A bit too much for z3 to handle, unfortunately.

xor == add

128 equations and 128 variables… hmmm… suspicious. But it’s not a linear system of equations… right?

Well, actually, it is! It’s all because XOR is a function with various interesting properties. For this challenge in particular, the important property is that XOR is essentially equivalent to binary addition with no carry. Just take a look at its inputs and outputs:

\[0 \oplus 0 ==> 0\]
\[1 \oplus 1 ==> 0\]
\[1 \oplus 0 ==> 1\]
\[0 \oplus 1 ==> 1\]

So how can that help us?

Well, since we’re working with only singular bits (we’re XORing the individual bits of the flag, so all numbers being XORed are 0 or 1), we can actually just make this a system of equations in an integer ring of mod 2, since it essentially makes addition become binary addition without carry!

So, now, it’s as simple as using schedule to figure out what bits are being XORed together for each position, figure out the result of keyschedule (which is just equal to ct ^ m, i.e. the ciphertext and message XORed), and put all that information into a matrix in SageMath under an IntegerModRing of 2. Once we have it all in a matrix, we can just solve with SageMath’s matrix magic.

Here’s the Sage implementation:

schedule = # too large so not included in writeup

from Crypto.Util.strxor import strxor
from Crypto.Util.number import *
import galois
from tqdm import trange
import numpy as np

LEN = 128

m = bytearray(b'yellow submarine')
ct = b'\xb7\x8e\xb3\xd9\xfd\xf2\x1f\xa2\xeaz\xe3\x0f\x00xj\x08'
keysch_res = strxor(m, ct)
res_bin = "{:0128b}".format(bytes_to_long(keysch_res))

matrix = []
for i in range(LEN):
    matrix_row = [0 for _ in range(LEN)]
    for j in range(len(schedule[i])):
        if schedule[i][j] % 8 == 0:
            continue
        matrix_row[schedule[i][j]] = matrix_row[schedule[i][j]] ^^ 1
    matrix.append(matrix_row)

ys = []
for i in range(LEN):
    ys.append(int(res_bin[i]))

R = IntegerModRing(2)
M = Matrix(R, matrix)
b = vector(R, ys)

print(''.join(map(str, list(M.solve_right(b)))))
print(long_to_bytes(int(''.join(map(str, list(M.solve_right(b)))), 2)))

And we get the flag!

tjctf{l1neeruwu8215413}

Nightxade: CTF Writeups