[LINE CTF 2022] Forward-or

Key entropy is small. # of key[0:10] = # of key[0:10] = $4^10$, so meet in the middle approach is working. Beware of CTR mode.

 

solver.py

from present import Present
from itertools import product
from Crypto.Util.strxor import strxor
from tqdm import tqdm

def xor(a:bytes, b:bytes) -> bytes:
    return bytes(i^j for i, j in zip(a, b))

class CTRMode():
    def __init__(self, key, nonce=None):
        self.key = key # 20bytes
        self.cipher = DoubleRoundReducedPresent(key)
        if None==nonce:
            nonce = os.urandom(self.cipher.block_size//2)
        self.nonce = nonce # 4bytes
    
    def XorStream(self, data):
        output = b""
        counter = 0
        for i in range(0, len(data), self.cipher.block_size):
            keystream = self.cipher.encrypt(self.nonce+counter.to_bytes(self.cipher.block_size//2, 'big'))
            if b""==keystream:
                exit(1)

            if len(data)<i+self.cipher.block_size:
                block = data[i:len(data)]
            block = data[i:i+self.cipher.block_size]
            block = strxor(keystream[:len(block)], block)
            
            output+=block
            counter+=1
        return output

    def encrypt(self, plaintext):
        return self.XorStream(plaintext)

    def decrypt(self, ciphertext):
        return self.XorStream(ciphertext)

class DoubleRoundReducedPresent():

    def __init__(self, key):
        self.block_size = 8
        self.key_length = 160 # bits
        self.round = 16
        self.cipher0 = Present(key[0:10], self.round)
        self.cipher1 = Present(key[10:20], self.round)
    
    def encrypt(self, plaintext):
        if len(plaintext)>self.block_size:
            print("Error: Plaintext must be less than %d bytes per block" % self.block_size)
            return b""
        return self.cipher1.encrypt(self.cipher0.encrypt(plaintext))
    
    def decrypt(self, ciphertext):
        if len(ciphertext)>self.block_size:
            print("Error: Ciphertext must be less than %d bytes per block" % self.block_size)
            return b""
        return self.cipher0.decrypt(self.cipher1.decrypt(ciphertext))





cand_key = [''.join(key) for key in product('0123', repeat=10)]

mitm1 = {}

nonce = bytes.fromhex('32e10325')

C = xor(bytes.fromhex('3201339d0fcffbd1'), b'LINECTF{')
P = nonce + bytes(4)

C_all = bytes.fromhex("3201339d0fcffbd152f169ddcb8349647d8bc36a73abc4d981d3206f4b1d98468995b9b1c15dc0f0")

'''
cipher = CTRMode('32013230202123003302'.encode(), nonce)
print(cipher.decrypt(C_all))

exit()
'''

# key[0:10]
for key in tqdm(cand_key):
    cipher = Present(''.join(key).encode(), 16)
    mid = cipher.encrypt(P)
    mitm1[mid] = key

# key[10:20]
for key in tqdm(cand_key):
    cipher = Present(''.join(key).encode(), 16)
    mid = cipher.decrypt(C)
    if mid in mitm1:
        key1 = mitm1[mid]
        key2 = key
        print(key1+key2) # 32013230202123003302
        z = key1+key2
        cipher = CTRMode(z.encode(), nonce)
        print(cipher.decrypt(C_all))
        break