Skip to content

Instantly share code, notes, and snippets.

@elliptic-shiho

elliptic-shiho/solve.py

Last active March 28, 2024 07:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save elliptic-shiho/67778c6447c54d8be8ff066746461bbc to your computer and use it in GitHub Desktop.
Save elliptic-shiho/67778c6447c54d8be8ff066746461bbc to your computer and use it in GitHub Desktop.
Download ZIP
LINE CTF 2024: haki-tako-game Solver & Writeup (in the comment)
Raw
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()
Raw
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
@elliptic-shiho
Copy link
Author

elliptic-shiho commented Mar 24, 2024 •
edited

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment