LINE CTF 2024: haki-tako-game Solver & Writeup (in the comment)

solve.py

from socket import create_connection
import itertools
import binascii
import struct
import json
import math


class Tube:
    def __init__(s, host, port, debug=False):
        s.host = host
        s.port = port
        s.sock = create_connection((host, port))
        s.debug = debug

    def recv(s, size=1024) -> bytes:
        buf = s.sock.recv(size)
        if s.debug:
            print(f"[Tube#recv] {buf=}")
        return buf

    def recv_until(s, expected: bytes) -> bytes:
        buf = b""
        while True:
            buf += s.sock.recv(1)
            if expected in buf:
                break
        if s.debug:
            print(f"[Tube#recv_until] {buf=}")
        return buf

    def send(s, buf: bytes):
        if s.debug:
            print(f"[Tube#send] {buf=}")
        s.sock.send(buf)

    def send_line(s, buf: bytes):
        s.send(buf + b"\n")

    def close(s):
        s.sock.close()
        if s.debug:
            print("[Tube#close] closed")


def main():
    tube = Tube("34.146.137.8", "11223")

    def recv():
        return json.loads(tube.recv(16384).strip())

    def send(x):
        return tube.send(x)

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

    def split_16(data: bytes) -> [bytes]:
        return [data[16 * n : 16 * (n + 1)] for n in range(math.ceil(len(data) / 16))]

    def decrypt_cfb(msg: bytes) -> [bytes]:
        msg += b"\x00" * max(
            256 - len(msg), (msg_block_len_in_hex + 32) // 2 - len(msg)
        )
        msg = binascii.hexlify(msg)

        assert len(msg) <= msg_block_len_in_hex + 32
        assert 512 < len(msg)
        assert len(msg) <= 1024

        send(msg)

        temp = recv()
        assert temp["msg"] == "CFB Decryption"
        return split_16(binascii.unhexlify(temp["ret"]))

    def decrypt_cbc(msg: bytes) -> [bytes]:
        msg += b"\x00" * min(
            max(256 - len(msg), msg_block_len_in_hex + 32 - len(msg)) + 16,
            512 - len(msg),
        )
        msg = binascii.hexlify(msg)

        assert msg_block_len_in_hex + 32 < len(msg)
        assert 512 < len(msg)
        assert len(msg) <= 1024

        send(msg)

        temp = recv()
        assert temp["msg"] == "CBC Decryption"
        return split_16(binascii.unhexlify(temp["ret"]))

    iv = binascii.unhexlify("5f885849eadbc8c7bce244f8548a443f")
    initial_data = recv()
    nonce = binascii.unhexlify(initial_data["nonce"])
    target_ciphertext = binascii.unhexlify(initial_data["ct"])

    ct_len_in_byte = len(target_ciphertext)
    msg_block_len_in_hex = (16 * (math.ceil(ct_len_in_byte / 16))) * 2

    blocks = split_16(target_ciphertext)

    keys = []
    for i in range(len(blocks)):
        keys.append(nonce + struct.pack(">I", i + 2))
        assert len(keys[-1]) == 16

    cts = []
    encrypted_key_candidates = []
    for i in range(0, len(keys), 10):
        cts = decrypt_cfb(
            b"\x00" * 16 + b"".join(b"\x00" * 16 + key for key in keys[i : i + 10])
        )
        encrypted_key_candidates += cts[3::2]
    print(f"[+] {encrypted_key_candidates = }")
    # print(len([xor(x, y) for x, y in zip(blocks, encrypted_key_candidates)][1:-3]))
    key_bruteforce_list = [
        bytes([0] * 14 + [x, y]) for x, y in itertools.product(range(256), repeat=2)
    ]
    encrypted_keys = []
    for i in range(1, len(keys) - 3):
        key_cand = encrypted_key_candidates[i]
        kp = keys[i]
        cur = 0
        while cur < len(key_bruteforce_list):
            kci_blocks = [xor(key_cand, b) for b in key_bruteforce_list[cur : cur + 25]]
            cand = decrypt_cbc(b"".join(kci_blocks))
            cand_xored = [xor(x, y) for x, y in zip(cand, [iv] + kci_blocks)]
            res = [i for i, b in enumerate(cand_xored) if b == kp]
            if len(res) > 0:
                encrypted_keys.append(kci_blocks[res[0]])
                break
            cur += 25
        print([xor(x, y) for x, y in zip(encrypted_keys, blocks[1:])])
    assert len(encrypted_keys) == 17
    pin = b"".join(xor(x, y) for x, y in zip(encrypted_keys, blocks[1:]))[13:-3]

    tube.send(binascii.hexlify(pin))
    print(recv())

    tube.close()


if __name__ == "__main__":
    main()

solve_log

Sat Mar 23 13:02:56 JST 2024 ~/prog/ctf/linectf-2024/haki-tako-game
> time python solve.py
[+] encrypted_key_candidates = [b'1\x83\r~\x9d\xf6:0\xa5\xcd\xd8\xee\x01\xfe\x00\x00', b'\xf0v\xef\xc2F\xd1\xf2\xdf\x04\x19|^\xf9E\x00\x00', b'U\xf1\x8d\xf6\xf4S\r\xe5\x0c\xc2\x83`\x93\xe0\x00\x00', b'\x13\xe9}\xd1\x19k(\xcb\xfc[\xcfQ6;\x00\x00', b'\x83z\x825\x19\xc1\x0c*\\Z\xf7\xb3\xfd\\\x00\x00', b'\x06J0\xc9-\xe3A\x01\x9e\xa0\x96H\\\xdb\x00\x00', b'\x97M\xc7\xb7<M]\xfb\x08\xf2\xcd&\xbc\xb2\x00\x00', b'U\xcd\xab\xbb\xbd\xc7\x01\xab\xdc\x9bY[\x8b\xc0\x00\x00', b'y\x8e\x8e(\xd2\x10\x07Q\x8c=\x1d\x8c\x12\x07\x00\x00', b'\x8c\xbf7\x83\x02~U\x8b\xd2\xe7\xf9i\x9d\xa1\x00\x00', b'J\xd0\x16\x83\x95|\xdb\x85wcI\xd5,w\x00\x00', b'>\xbb\x9bH\x9fu?F\xef1\xd81\x96\xc7\x00\x00', b'\xc6)\xfdF6\x91\r?\xac\xb0rfi\xd3\x00\x00', b'y\xbf]\xd1@@\x17\x86\xe9\x85\xca\xc9?\x06\x00\x00', b"\x18\xba\xaf'\x98-l\xf8\xc3\xf9X \x8a\xdc\x00\x00", b'\xcd\xa8\x96\xf46{x\x9a0\x16\x0c\xa3gg\x00\x00', b'\x97k1<z\x02ee\xf5\xe4\xc3B\xce\xeb\x00\x00', b'\xa3\x8f\xc4\x89\x83\xe5\xc3"\xca@\xaf\x0fX\xef\x00\x00', b'\x04\xe4\xa9\x07+\xc7\xa1\xd5\x86\x96\x11t\xff\xe3\x00\x00', b'\xaf\x1e\xcd\x8a[\xfc\x87\xb6\xce\x1b\x8b\xab\xbc\xe2\x00\x00', b'\xc2\xb3\xb7X\xa5\xc8#\xa4\xea}0ic\xee\x00\x00', b'T \x03ZoQ\x1c\x81\x9b\xf8\xd6G\x0b\xbb\x00\x00', b'T \x03ZoQ\x1c\x81\x9b\xf8\xd6G\x0b\xbb\x00\x00', b'T \x03ZoQ\x1c\x81\x9b\xf8\xd6G\x0b\xbb\x00\x00', b'T \x03ZoQ\x1c\x81\x9b\xf8\xd6G\x0b\xbb\x00\x00', b'T \x03ZoQ\x1c\x81\x9b\xf8\xd6G\x0b\xbb\x00\x00', b'T \x03ZoQ\x1c\x81\x9b\xf8\xd6G\x0b\xbb\x00\x00', b'T \x03ZoQ\x1c\x81\x9b\xf8\xd6G\x0b\xbb\x00\x00', b'T \x03ZoQ\x1c\x81\x9b\xf8\xd6G\x0b\xbb\x00\x00', b'T \x03ZoQ\x1c\x81\x9b\xf8\xd6G\x0b\xbb\x00\x00']
[b'ion code is..vX2']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t', b'oFUcl\x8bG\xb4,\x9d\xd4\xd7\xdcs\xe7!']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t', b'oFUcl\x8bG\xb4,\x9d\xd4\xd7\xdcs\xe7!', b'oo\xb6\xdf\xbcJ\xb2H\x80\x1eAg\x8bf\x9b\x8c']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t', b'oFUcl\x8bG\xb4,\x9d\xd4\xd7\xdcs\xe7!', b'oo\xb6\xdf\xbcJ\xb2H\x80\x1eAg\x8bf\x9b\x8c', b';\x9b;(NlQ\x82(o\xe3U\x93\xc8\xc4G']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t', b'oFUcl\x8bG\xb4,\x9d\xd4\xd7\xdcs\xe7!', b'oo\xb6\xdf\xbcJ\xb2H\x80\x1eAg\x8bf\x9b\x8c', b';\x9b;(NlQ\x82(o\xe3U\x93\xc8\xc4G', b'\xa3\x9a\xca\x03\xe8M\xfd\x04\x97]\xfa\xee\x95x$\x95']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t', b'oFUcl\x8bG\xb4,\x9d\xd4\xd7\xdcs\xe7!', b'oo\xb6\xdf\xbcJ\xb2H\x80\x1eAg\x8bf\x9b\x8c', b';\x9b;(NlQ\x82(o\xe3U\x93\xc8\xc4G', b'\xa3\x9a\xca\x03\xe8M\xfd\x04\x97]\xfa\xee\x95x$\x95', b'\x0c\xadDgA\x9c?\x8c\xd0h\x16\x05\xd8*N\xf6']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t', b'oFUcl\x8bG\xb4,\x9d\xd4\xd7\xdcs\xe7!', b'oo\xb6\xdf\xbcJ\xb2H\x80\x1eAg\x8bf\x9b\x8c', b';\x9b;(NlQ\x82(o\xe3U\x93\xc8\xc4G', b'\xa3\x9a\xca\x03\xe8M\xfd\x04\x97]\xfa\xee\x95x$\x95', b'\x0c\xadDgA\x9c?\x8c\xd0h\x16\x05\xd8*N\xf6', b'V*\x13y1\xa2\x16\xd3\x00\xf7\x08\xcdo\x9b\x91\x00']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t', b'oFUcl\x8bG\xb4,\x9d\xd4\xd7\xdcs\xe7!', b'oo\xb6\xdf\xbcJ\xb2H\x80\x1eAg\x8bf\x9b\x8c', b';\x9b;(NlQ\x82(o\xe3U\x93\xc8\xc4G', b'\xa3\x9a\xca\x03\xe8M\xfd\x04\x97]\xfa\xee\x95x$\x95', b'\x0c\xadDgA\x9c?\x8c\xd0h\x16\x05\xd8*N\xf6', b'V*\x13y1\xa2\x16\xd3\x00\xf7\x08\xcdo\x9b\x91\x00', b't\x0f@k\xeeL\x00\x97\xe5iB\xa1\xda\xa2=S']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t', b'oFUcl\x8bG\xb4,\x9d\xd4\xd7\xdcs\xe7!', b'oo\xb6\xdf\xbcJ\xb2H\x80\x1eAg\x8bf\x9b\x8c', b';\x9b;(NlQ\x82(o\xe3U\x93\xc8\xc4G', b'\xa3\x9a\xca\x03\xe8M\xfd\x04\x97]\xfa\xee\x95x$\x95', b'\x0c\xadDgA\x9c?\x8c\xd0h\x16\x05\xd8*N\xf6', b'V*\x13y1\xa2\x16\xd3\x00\xf7\x08\xcdo\x9b\x91\x00', b't\x0f@k\xeeL\x00\x97\xe5iB\xa1\xda\xa2=S', b'\xe5\x9a\xb9S\xc62\xd7grK^\x92\xab\x15\xe7~']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t', b'oFUcl\x8bG\xb4,\x9d\xd4\xd7\xdcs\xe7!', b'oo\xb6\xdf\xbcJ\xb2H\x80\x1eAg\x8bf\x9b\x8c', b';\x9b;(NlQ\x82(o\xe3U\x93\xc8\xc4G', b'\xa3\x9a\xca\x03\xe8M\xfd\x04\x97]\xfa\xee\x95x$\x95', b'\x0c\xadDgA\x9c?\x8c\xd0h\x16\x05\xd8*N\xf6', b'V*\x13y1\xa2\x16\xd3\x00\xf7\x08\xcdo\x9b\x91\x00', b't\x0f@k\xeeL\x00\x97\xe5iB\xa1\xda\xa2=S', b'\xe5\x9a\xb9S\xc62\xd7grK^\x92\xab\x15\xe7~', b'\xe5\xcb\x8d7\xba\x82C(\xf0]J\xa9\xd3\xc8{B']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t', b'oFUcl\x8bG\xb4,\x9d\xd4\xd7\xdcs\xe7!', b'oo\xb6\xdf\xbcJ\xb2H\x80\x1eAg\x8bf\x9b\x8c', b';\x9b;(NlQ\x82(o\xe3U\x93\xc8\xc4G', b'\xa3\x9a\xca\x03\xe8M\xfd\x04\x97]\xfa\xee\x95x$\x95', b'\x0c\xadDgA\x9c?\x8c\xd0h\x16\x05\xd8*N\xf6', b'V*\x13y1\xa2\x16\xd3\x00\xf7\x08\xcdo\x9b\x91\x00', b't\x0f@k\xeeL\x00\x97\xe5iB\xa1\xda\xa2=S', b'\xe5\x9a\xb9S\xc62\xd7grK^\x92\xab\x15\xe7~', b'\xe5\xcb\x8d7\xba\x82C(\xf0]J\xa9\xd3\xc8{B', b':]b\x88\xee,P\xc8\xd4S\xf1\xd9\xa5\xee\xf4\xbb']
[b'ion code is..vX2', b'/\x1bkX\x19\x10\xe9\x14\x01e\xcbv\r\x17\xdaV', b'\xbc*fN\xfa\x94YW y\xbe&\t64"', b'A\xd6\xeb\xbe\xc8K\x12\xa8?\x9cg\xbf\xcd\x92\xf2\x07', b'\x16T\xdfH\xc9Vs\xe6\xcb\x9f\x15\xd2\x93\x190\xec', b'\x8c\xd9\xa3S{R\xaf\x0et}\x07x5\xd0\x0c\t', b'oFUcl\x8bG\xb4,\x9d\xd4\xd7\xdcs\xe7!', b'oo\xb6\xdf\xbcJ\xb2H\x80\x1eAg\x8bf\x9b\x8c', b';\x9b;(NlQ\x82(o\xe3U\x93\xc8\xc4G', b'\xa3\x9a\xca\x03\xe8M\xfd\x04\x97]\xfa\xee\x95x$\x95', b'\x0c\xadDgA\x9c?\x8c\xd0h\x16\x05\xd8*N\xf6', b'V*\x13y1\xa2\x16\xd3\x00\xf7\x08\xcdo\x9b\x91\x00', b't\x0f@k\xeeL\x00\x97\xe5iB\xa1\xda\xa2=S', b'\xe5\x9a\xb9S\xc62\xd7grK^\x92\xab\x15\xe7~', b'\xe5\xcb\x8d7\xba\x82C(\xf0]J\xa9\xd3\xc8{B', b':]b\x88\xee,P\xc8\xd4S\xf1\xd9\xa5\xee\xf4\xbb', b'\x96\x93E#\x87u\xa6\x90M"\xc3\xa8\xab. D']
{'flag': 'LINECTF{93a1ca7bc58accbb0200507dc3da45c0}'}

real	3m45.029s
user	0m9.157s
sys	0m1.808s

We have a ciphertext $(\mathrm{nonce}, \mathbf{c}, \mathrm{tag})$ which was encrypted by AES-128-GCM and we can access to the oracle that can query three kinds: Flag check, "truncated" CFB decryption, and CBC decryption. IV is fixed and known.

Notation & definitions:

• A byte sequence is denoted by bold font
• $i$-th byte of the byte sequence $\mathbf{b}$ is denoted by $\mathbf{b}[i]$
  • We denote the length of a byte sequence $\mathbf{b}$ by $\mathrm{len}(\mathbf{b})$
• The concatenation of $\mathbf{a}$ and $\mathbf{b}$ is denoted by $\mathbf{a}\mathbin{\parallel}\mathbf{b}$

Any byte sequence $\mathbf{b}$ can embed to $\mathbb{F} _ {2^8}^N$ where $N := \mathrm{len}(\mathbf{b})$. In this writeup, we use 16-bytes aligned byte sequence only so we assume $\forall \mathbf{b}$. $16\mid \mathrm{len}(\mathbf{b})$.

$i$-th block of the byte sequence is denoted by $\mathbf{b}^{(i)}$. i.e. $\mathbf{b}^{(i)} := \lbrack\mathbf{b}[16i], \mathbf{b}[16i+1], \ldots, \mathbf{b}[16i + 15]\rbrack$.

The encrypt function of AES-128 is denoted by $\mathrm{Enc} _ k\colon \mathbb{F} _ {2^8}^{16}\to \mathbb{F} _ {2^8}^{16}$ and $\mathrm{Dec} _ k := \mathrm{Enc} _ k^{-1}$. In this writeup, we assume $\mathrm{Enc} _ k$ is bijection. so $\mathrm{Dec} _ k$ is well-defined. More, we will omit $k$ because it is fixed all-over the challenge.

We abuse the $+$ operation for two same-length byte sequences from $\mathbb{F} _ {2^8}^N$ where $N$ is the length of them.

Mathematical model of "Mode of operations"

In this challenge, we need to exploit the three mode of operations: GCM, CFB, and CBC. so we formulate them at first but the encryption-part of GCM is just CTR. so we omit the details of all-of-GCM.

A corresponded ciphertext of $\mathbf{m}$ with CTR mode is $\mathbf{c}^{(i)} := \mathbf{m}^{(i)} + \mathrm{Enc}(\mathrm{counter} _ i)$. In GCM and 12-bytes nonce, we have $\mathrm{counter} _ i := \mathrm{nonce}\mathbin{\parallel} f(i + 2)$ where $f\colon \mathbb{N}\ni n\mapsto \lbrack \lfloor n/2^{24}\rfloor\bmod {2^8}, \lfloor n/2^{16}\rfloor\bmod {2^8}, \lfloor n/2^8\rfloor\bmod {2^8}, n\bmod {2^8}\rbrack\in\mathbb{F} _ {2^8}^4$.

A corresponded plaintext of $\mathbf{c}$ with CFB mode is $\mathbf{m}^{(i)} := \mathrm{Enc}(\mathbf{c}^{(i)}) + \mathbf{c}^{(i-1)}$ with $\mathbf{c}^{(-1)} := IV$.

We can access to the CFB oracle but that is truncated. the truncated ciphertext is denoted by its symbol with overline, like $\overline{\mathbf{c}}$. it satisfies $\exists! a, b\in\mathbb{F} _ {2^8}$. $\mathbf{c}^{(i)} = \overline{\mathbf{c}}^{(i)} + \lbrack 0, 0, \ldots, 0, a, b\rbrack$.

A corresponded plaintext of $\mathbf{c}$ with CBC mode is $\mathbf{m}^{(i)} := \mathrm{Dec}(\mathbf{c}^{(i)}) + \mathbf{c}^{(i-1)}$ with $\mathbf{c}^{(-1)} := IV$.

The challenge

We have a ciphertext $\mathbf{c}$ that is encrypted by AES-128-GCM with 12-bytes nonce. We can use truncated-CFB and CBC oracle.

At first, If we get $\mathrm{Enc}(\mathrm{nonce}\mathbin{\parallel} f(i + 2))$ for every $i$, we can decrypt $\mathbf{c}$. but we can't get it. however we can get truncated result of it using truncated-CFB. Indeed, we can try to decrypt $0\mathbin{\parallel} 0\mathbin{\parallel} \mathbf{t} _ 0\mathbin{\parallel} 0\mathbin{\parallel} \mathbf{t} _ 1\mathbin{\parallel} 0\mathbin{\parallel} \cdots\mathbin{\parallel} 0 \mathbin{\parallel} \mathbf{t} _ n$ where $0$ as a zero block and $\mathbf{t} _ i := \mathrm{nonce} \mathbin{\parallel} f(i + 2)$ by CFB. then we can get $\overline{\mathrm{Enc}(IV)\mathbin{\parallel} \mathrm{Enc}(0)\mathbin{\parallel} \mathrm{Enc}(0)+\mathbf{t} _ 0\mathbin{\parallel} \mathrm{Enc}(\mathbf{t} _ 0)\mathbin{\parallel} \mathrm{Enc}(0) + \mathbf{t} _ 1\mathbin{\parallel} \mathrm{Enc}(\mathbf{t} _ 1),\mathbin{\parallel} \cdots \mathbin{\parallel} \mathrm{Enc}(\mathbf{t} _ n)}$. So we can get $\overline{\mathrm{Enc}(\mathbf{t} _ i)}$ by CFB.

We need to recover two LSBs. More clearly, we need to guess $(b _ {i1}, b _ {i2})\in\mathbb{F} _ {2^8}^{2}$ which satisfies $\mathbf{b} _ i + \overline{\mathrm{Enc}(\mathbf{t} _ i)} = \mathrm{Enc}(\mathbf{t} _ i)$ for every $i$ and $\mathbf{b} _ i := \lbrack 0, 0, \ldots, 0, b _ {i1}, b _ {i2} \rbrack$.

We can use CBC decryption oracle for it. In fact, we can prove $\forall\mathbf{x}\in\mathbb{F}^{16} _ {2^8}$. $\mathrm{Dec}(\mathbf{x} + \overline{\mathrm{Enc}(\mathbf{t} _ i)}) = \mathrm{Enc}(\mathbf{t} _ i) \iff \mathbf{x} = \mathbf{b} _ i$ since $\mathrm{Enc}$ is bijection.

If we decrypt $\overline{\mathrm{Enc}(\mathbf{t} _ i)} + 0\mathbin{\parallel} \overline{\mathrm{Enc}(\mathbf{t} _ i)} + 1\mathbin{\parallel} \cdots \mathbin{\parallel}\overline{\mathrm{Enc}(\mathbf{t} _ i)} + n$, we get:

$$ \mathrm{Dec}(\overline{\mathrm{Enc}(\mathbf{t} _ i)})+IV\mathbin{\parallel} \mathrm{Dec}(\overline{\mathrm{Enc}(\mathbf{t} _ i)} + 1)+\overline{\mathrm{Enc}(\mathbf{t} _ i)}\mathbin{\parallel}\cdots\mathbin{\parallel} \mathrm{Dec}(\overline{\mathrm{Enc}(\mathbf{t} _ i)}+n)+\overline{\mathrm{Enc}(\mathbf{t} _ i)}+(n-1). $$

$IV$ and $\overline{\mathrm{Enc}(\mathbf{t} _ i)} + j$ for every $i, j\in\mathbb{N}$ is known, so we can check $\mathrm{Dec}(\overline{\mathrm{Enc}(\mathbf{t} _ i)}+j)+\overline{\mathrm{Enc}(\mathbf{t} _ i)}+(j-1) \stackrel{?}{=} \mathbf{t} _ i +\overline{\mathrm{Enc}(\mathbf{t} _ i)}+(j-1)$.

25 candidates length is 16 * 25 = 400 [bytes] and we need to decrypt 17 blocks, so we need to query $17 \times \lceil 65536 / 25\rceil = 17\times 2622 = 44574$ times for bruteforce it. these condition satisfies the challenge's constraint.