UofTCTF 2024

UofTCTF 2024

Export Grade Cipher [crypto 10 solve]

chall

import ast
import threading
from exportcipher import *
try:
    from flag import FLAG
except:
    FLAG = "test{FLAG}"

MAX_COUNT = 100
TIMEOUT = 120 # seconds

def input_bytes(display_msg):
    m = input(display_msg)
    try:
        m = ast.literal_eval(m)
    except:
        # might not be valid str or bytes literal but could still be valid input, so just encode it
        pass
    if isinstance(m, str):
        m = m.encode()
    assert isinstance(m, bytes)
    return m

def timeout_handler():
    print("Time is up, you can throw out your work as the key changed.")
    exit()

if __name__ == "__main__":
    print("Initializing Export Grade Cipher...")
    key = int.from_bytes(os.urandom(5),"little")
    cipher = ExportGradeCipher(key)
    print("You may choose up to {} plaintext messages to encrypt.".format(MAX_COUNT))
    print("Recover the 40-bit key to get the flag.")
    print("You have {} seconds.".format(TIMEOUT))
    # enough time to crack a 40 bit key with the compute resources of a government
    threading.Timer(TIMEOUT, timeout_handler).start()
    
    i = 0
    while i < MAX_COUNT:
        pt = input_bytes("[MSG {}] plaintext: ".format(i))
        if not pt:
            break
        if len(pt) > 512:
            # don't allow excessively long messages
            print("Message Too Long!")
            continue
        nonce = os.urandom(256)
        cipher.init_with_nonce(nonce)
        ct = cipher.encrypt(pt)
        print("[MSG {}] nonce: {}".format(i, nonce))
        print("[MSG {}] ciphertext: {}".format(i, ct))
        # sanity check decryption
        cipher.init_with_nonce(nonce)
        assert pt == cipher.decrypt(ct)
        i += 1
    recovered_key = ast.literal_eval(input("Recovered Key: "))
    assert isinstance(recovered_key, int)
    if recovered_key == key:
        print("That is the key! Here is the flag: {}".format(FLAG))
    else:
        print("Wrong!")

import os

class LFSR:
    def __init__(self, seed, taps, size):
        assert seed != 0
        assert (seed >> size) == 0
        assert len(taps) > 0 and (size - 1) in taps
        self.state = seed
        self.taps = taps
        self.mask = (1 << size) - 1

    def _shift(self):
        feedback = 0
        for tap in self.taps:
            feedback ^= (self.state >> tap) & 1
        self.state = ((self.state << 1) | feedback) & self.mask
    
    def next_byte(self):
        val = self.state & 0xFF
        for _ in range(8):
            self._shift()
        return val


class ExportGradeCipher:
    def __init__(self, key):
        # 40 bit key
        assert (key >> 40) == 0
        self.key = key
        self.initialized = False
    
    def init_with_nonce(self, nonce):
        # 256 byte nonce, nonce size isnt export controlled so hopefully this will compensate for the short key size
        assert len(nonce) == 256
        self.lfsr17 = LFSR((self.key & 0xFFFF) | (1 << 16), [2, 9, 10, 11, 14, 16], 17)
        self.lfsr32 = LFSR(((self.key >> 16) | 0xAB << 24) & 0xFFFFFFFF, [1, 6, 16, 21, 23, 24, 25, 26, 30, 31], 32)
        self.S = [i for i in range(256)]
        # Fisher-Yates shuffle S-table
        for i in range(255, 0, -1): 
            # generate j s.t. 0 <= j <= i, has modulo bias but good luck exploiting that
            j = (self.lfsr17.next_byte() ^ self.lfsr32.next_byte()) % (i + 1)
            self.S[i], self.S[j] = self.S[j], self.S[i]
        j = 0
        # use nonce to scramble S-table some more
        for i in range(256):
            j = (j + self.lfsr17.next_byte() ^ self.lfsr32.next_byte() + self.S[i] + nonce[i]) % 256
            self.S[i], self.S[j] = self.S[j], self.S[i]
        self.S_inv = [0 for _ in range(256)]
        for i in range(256):
            self.S_inv[self.S[i]] = i
        self.initialized = True
    
    def _update(self, v):
        i = self.lfsr17.next_byte() ^ self.lfsr32.next_byte()
        self.S[v], self.S[i] = self.S[i], self.S[v]
        self.S_inv[self.S[v]] = v
        self.S_inv[self.S[i]] = i
    
    def encrypt(self, msg):
        assert self.initialized
        ct = bytes()
        for v in msg:
            ct += self.S[v].to_bytes()
            self._update(v)
        return ct
    
    def decrypt(self, ct):
        assert self.initialized
        msg = bytes()
        for v in ct:
            vo = self.S_inv[v]
            msg += vo.to_bytes()
            self._update(vo)
        return msg


if __name__ == "__main__":
    cipher = ExportGradeCipher(int.from_bytes(os.urandom(5)))
    nonce = os.urandom(256)
    print("="*50)
    print("Cipher Key: {}".format(cipher.key))
    print("Nonce: {}".format(nonce))
    msg = "ChatGPT: The Kerckhoffs' Principle, formulated by Auguste Kerckhoffs in the 19th century, is a fundamental concept in cryptography that states that the security of a cryptographic system should not rely on the secrecy of the algorithm, but rather on the secrecy of the key. In other words, a cryptosystem should remain secure even if all the details of the encryption algorithm, except for the key, are publicly known. This principle emphasizes the importance of key management in ensuring the confidentiality and integrity of encrypted data and promotes the development of encryption algorithms that can be openly analyzed and tested by the cryptographic community, making them more robust and trustworthy."
    print("="*50)
    print("Plaintext: {}".format(msg))
    cipher.init_with_nonce(nonce)
    ct = cipher.encrypt(msg.encode())
    print("="*50)
    print("Ciphertext: {}".format(ct))
    cipher.init_with_nonce(nonce)
    dec = cipher.decrypt(ct)
    print("="*50)
    try:
        print("Decrypted: {}".format(dec))
        assert msg.encode() == dec
    except:
        print("Decryption failed")

solve

sumaary

The class ExportGradeCipher is implemented in ExportGradeCipher.py.

1. In this class, the state is initialized by the function init_with_nonce using key and nonce.

2. After that, the function _update constructs a nfsr(non linear shift register) of lfsr17 and lfsr32, and appears to perform encryption using them.

3. In encrypt, after outputting the location of one character of msg in the S array as ct, the output of 256 bytes of nfsr and the location of one character of msg are swapped.

   def _update(self, v):
       i = self.lfsr17.next_byte() ^ self.lfsr32.next_byte()
       self.S[v], self.S[i] = self.S[i], self.S[v]
          
   def encrypt(self, msg):
       assert self.initialized
       ct = bytes()
       for v in msg:
           ct += self.S[v].to_bytes(1,"little")
           self._update(v)
           return ct
   

cryptanisis

Suppose we have an S array of length 4 and msg is b”\x00\x01\x02\x03”

i	0	1	2	3
S[i]	2	4	6	8

1. If you follow the processing of the encrypt function in order, the first character is when v=0 and the ct at that time is ct[0]=2.

2. The self._update(v) causes a swap self.S[v], self.S[i] = self.S[i], self.S[v]. We know that v=0 here, so let’s assume i=1. Then the table transitions as follows.

i	0	1	2	3
S[i]	4	2	6	8

1. We see that v in the second week is v=1 and that ct at that time is ct[1]=2. I want you to wait a moment. This time, the array S is all set to different values, so the same value ct[0]=ct[1]=2 could be used for something.
   • S[v], self.S[i] = self.S[i], self.S[v] means that v can set itself and swap its value with the i-th value, and if the same value appears here, we know that it was swapped with the i-th value in the process at this time. So, at this point, we know the output i of the nfsr when the same value appears for the first time.
2. The rest is a repeat of this.

By the time you reach the end, you have obtained a certain amount of S array and nfsr output i. And considering that the nonce changes only S array in this setup, repeating the above process up to the upper limit will give us almost perfect nfsr output.

solver

Therefore, now that we have obtained the output of nfsr, we can also reverse the initial state of lfsr32 by considering that lfsr17 is within the brute force range. At this point, checking whether the upper 2bytes are such that they are 0xAB will reduce the number of candidate solutions.

self.lfsr32 = LFSR(((self.key >> 16) | 0xAB << 24) & 0xFFFFFFFF, [1, 6, 16, 21, 23, 24, 25, 26, 30, 31], 32)

Nevertheless, since about 30 candidates for the key remain, and considering that this cipher can only affect nonce and key, the key can be checked if the cipher is the same for that plaintext by performing the cipher again.

Thus, the following is my implementation. Note that I have used a matrix to speed up the lfsr.

from pwn import *
import ast
import random
from tqdm import tqdm
from exportcipher import *

class LFSR:
    def __init__(self, seed, taps, size):
        assert seed != 0
        assert (seed >> size) == 0
        assert len(taps) > 0 and (size - 1) in taps
        self.state = seed
        self.size = size
        self.taps = taps
        self.mask = (1 << size) - 1
        self.mat = matrix(GF(2),size,size)
        for i in range(size-1):
            self.mat[i,i+1] = 1
        for t in self.taps:    
            self.mat[-1,-t-1] = 1
        self.state_vec = vector(GF(2),[int(i) for i in bin(seed)[2:].zfill(size)])
        
    def _shift(self):
        feedback = 0
        for tap in self.taps:
            feedback ^^= (self.state >> tap) & 1
        self.state = ((self.state << 1) | feedback) & self.mask
        
    def next_byte(self):
        val = self.state & 0xFF
        for _ in range(8):
            self._shift()
        return val
            
    def _shift_mat(self, k):
        state_vec = self.mat^(8*k)*self.state_vec
        return int("".join([str(i) for i in list(state_vec)[-8:]]),2)

    def after_255_256_next_byte(self):
        val1 = self._shift_mat(255+256)
        val2 = self._shift_mat(256+256)
        val3 = self._shift_mat(257+256)
        val4 = self._shift_mat(258+256)
        return bytes([val1,val2,val3,val4])
    def check(self, vec):
        vec = vector(GF(2),[int(i) for i in bin(vec[0])[2:].zfill(8)+bin(vec[1])[2:].zfill(8)+bin(vec[2])[2:].zfill(8)+bin(vec[3])[2:].zfill(8)])
        self.inv_mat = self.mat^(-1)
        if list(self.inv_mat^(8*514)*vec)[:8] == [int(i)for i in bin(0xab)[2:].zfill(8)]:
            return int("".join([str(i) for i in list(self.inv_mat^(8*514)*vec)[8:]]),2)
        return False

def bxor(a,b): return bytes([_a^^_b for _a,_b in zip(a,b)])

lfsr17s = []
lfsr32s = []
for key in tqdm(range(256**2)):
    lfsr17 = LFSR((key & 0xFFFF) | (1 << 16), [2, 9, 10, 11, 14, 16], 17)
    lfsr17s.append(lfsr17.after_255_256_next_byte())

io = remote("0.cloud.chals.io","23753")
# io = process(["python3","chal.py"])
CNT = 256
lfsr = [-1 for i in range(CNT)]
pt = [(i)%256 for i in range(CNT)]

for __ in tqdm(range(100)):
    random.shuffle(pt)
    io.sendlineafter(b": ",str(bytes(pt)).encode())
    nonce = ast.literal_eval(io.recvline().decode().split("nonce: ")[1])
    ct = ast.literal_eval(io.recvline().decode().split("ciphertext: ")[1])
    S    = [-1 for i in range(256)]
    print(lfsr.count(-1))

    for i in range(CNT):
        if not ct[i] in S:
            S[pt[i]] = ct[i]
        else:
            if lfsr[ct[:i].index(ct[i])] != -1:
                continue
            lfsr[ct[:i].index(ct[i])] = pt[i]
            S[pt[i]] = ct[i]
            S[S.index(ct[i])] = -1


lfsr32 = LFSR(((0x123456 >> 16) | 0xAB << 24) & 0xFFFFFFFF, [1, 6, 16, 21, 23, 24, 25, 26, 30, 31], 32)

for i in tqdm(range(256**2)):
    a = lfsr32.check(bxor(bytes(lfsr[:4]),lfsr17s[i]))
    if a != False:
        key1 = i
        key2 = a
        key = key1 + (key2 << 16)
        cipher = ExportGradeCipher(key)
        cipher.init_with_nonce(nonce)
        if ct == cipher.encrypt(pt):
            io.sendlineafter(b": ", str(key))
            io.interactive()
            exit()
# uoftctf{wH0_w0u1D_h4ve_7houGHt_l0ng_nONceS_CAnt_S4ve_w3ak_KeYS}