Codegate Preliminary 2020 | Halffeed

from Crypto.Cipher import AES


def aes_encrypt(key, data):
    assert isinstance(key, bytes) and isinstance(data, bytes)
    assert len(key) == 16 and len(data) == 16

    aes = AES.new(key, AES.MODE_ECB)
    return aes.encrypt(data), aes.encrypt(key)


def pad(data):
    assert isinstance(data, bytes)
    assert len(data) <= 16

    if len(data) != 16:
        data += b'\x01' + b'\x00' * (15 - len(data))
    return data


class HalfFeed(object):
    # Abstract Version of mixFeed

    def __init__(self, key):
        assert isinstance(key, bytes)
        assert len(key) == 16
        self.key = key

    def feed_plus(self, tag, data):
        assert isinstance(tag, bytes) and isinstance(data, bytes)
        assert len(tag) == 16 and len(data) <= 16

        enc_data = bytes(b1 ^ b2 for b1, b2 in zip(tag, data))
        feed_data = pad(data)[:8] + pad(enc_data)[8:]
        tag = bytes(b1 ^ b2 for b1, b2 in zip(tag, feed_data))

        return tag, enc_data

    def feed_minus(self, tag, data):
        assert isinstance(tag, bytes) and isinstance(data, bytes)
        assert len(tag) == 16 and len(data) <= 16

        dec_data = bytes(b1 ^ b2 for b1, b2 in zip(tag, data))
        feed_data = pad(dec_data)[:8] + pad(data)[8:]
        tag = bytes(b1 ^ b2 for b1, b2 in zip(tag, feed_data))

        return tag, dec_data

    def encrypt(self, nonce, plaintext):
        assert isinstance(nonce, bytes) and isinstance(plaintext, bytes)
        assert len(nonce) == 16

        delta = len(plaintext) % 16
        delta = delta.to_bytes(16, byteorder='little')

        Kn, _ = aes_encrypt(self.key, nonce)
        T, K = aes_encrypt(Kn, nonce)

        ciphertext = b''
        for i in range(0, len(plaintext), 16):
            T, block = self.feed_plus(T, plaintext[i:i+16])
            ciphertext += block
            T, K = aes_encrypt(K, T)

        T = bytes(b1 ^ b2 for b1, b2 in zip(T, delta))
        T, _ = aes_encrypt(K, T)

        return ciphertext, T

    def decrypt(self, nonce, ciphertext, tag):
        assert isinstance(nonce, bytes) and isinstance(ciphertext, bytes)
        assert len(nonce) == 16

        delta = len(ciphertext) % 16
        delta = delta.to_bytes(16, byteorder='little')

        Kn, _ = aes_encrypt(self.key, nonce)
        T, K = aes_encrypt(Kn, nonce)

        plaintext = b''
        for i in range(0, len(ciphertext), 16):
            T, block = self.feed_minus(T, ciphertext[i:i+16])
            plaintext += block
            T, K = aes_encrypt(K, T)

        T = bytes(b1 ^ b2 for b1, b2 in zip(T, delta))
        T, _ = aes_encrypt(K, T)

        if T != tag:
            return None

        return plaintext

#!/usr/bin/env python3
from halffeed import HalfFeed


nonce = 0
nonce_list = []


def recv_data(text):
    data = input('{} = '.format(text)).strip()
    return bytes.fromhex(data)


def send_data(text, data):
    assert isinstance(data, bytes)
    print('{} = {}'.format(text, data.hex()))


def encrypt(halffeed):
    global nonce
    P = recv_data('plaintext')

    if b'cat flag' in P:
        print('[EXCEPTION] Invalid Command "cat flag"')
        exit()

    C, T = halffeed.encrypt(nonce.to_bytes(16, byteorder='big'), P)

    send_data('ciphertext', C)
    send_data('tag', T)
    nonce += 1


def decrypt(halffeed):
    N = recv_data('nonce')
    C = recv_data('ciphertext')
    T = recv_data('tag')

    if N in nonce_list:
        print('[EXCEPTION] Nonce Misuse')
        exit()

    nonce_list.append(N)

    P = halffeed.decrypt(N, C, T)

    if P is None:
        print('[EXCEPTION] Authentication Failed')
        exit()

    send_data('plaintext', P)


def execute(halffeed):
    N = recv_data('nonce')
    C = recv_data('ciphertext')
    T = recv_data('tag')

    P = halffeed.decrypt(N, C, T)

    if P is not None:
        cmds = P.split(b';')
        for cmd in cmds:
            if cmd.strip() == b'cat flag':
                with open('./flag') as f:
                    print(f.read())
            else:
                print('[EXCEPTION] Unknown Command')
    else:
        print('[EXCEPTION] Authentication Failed')
    exit()


def print_menu():
    print('1) Encrypt')
    print('2) Decrypt')
    print('3) Execute')
    print('4) Exit')


def main():
    with open('./secretkey', 'rb') as f:
        hf = HalfFeed(f.read())

    for i in range(10):
        print_menu()
        option = input('> ')
        if option == '1':
            encrypt(hf)
        elif option == '2':
            decrypt(hf)
        elif option == '3':
            execute(hf)
        else:
            return


if __name__ == '__main__':
    main()

図

どうやら、 mixfeedというAESを用いた暗号化方式（？）の亜種だとか。AESでの暗号化と、順々に更新されるtagでセキュアに暗号化されている

暗号化

$K_{nonce} = Enc_{key}(nonce)$

$Tag_0 = Enc_{Knonce}(nonce), K_0 = Enc_{Knonce}(K_{nonce})$

$C_i = Tag_{i} \oplus P_i$

$Tag'_i = C_i(8..16) || P_i(0..8)$

$Tag_{i+1} = Enc_{Ki}(Tag'_i)$

$K_{i+1} = Enc_{Ki}(K_i)$

復号

$K_{nonce} = Enc_{key}(nonce)$

$Tag_0 = Enc_{Knonce}(nonce), K_0 = Enc_{Knonce}(K_{nonce})$

$P_i = Tag_{i} \oplus C_i$

$Tag'_i = C_i(8..16) || P_i(0..8)$

$Tag_{i+1} = Enc_{Ki}(Tag'_i)$

$K_{i+1} = Enc_{Ki}(K_i)$

最後にtagが正しいか確認する

暗号化と復号は同じ処理になる。

solution

pt = b'\x00'*11 + b';cat ' + b'a'*16
ct1, _ = get_enc(pt)
t1 = sxor(ct1[16:], pt[16:])

pt = b'flag;' + b'd'*11
t2, ct2 = feed_plus(t1, pt)

pt = b'b'*16 + b'e'*16
ct, _ = get_enc(pt)
t3 = sxor(ct[16:], pt[16:])

pt = b'b'*16 + sxor(t2[:8], t3[:8]) + b'd'*8
_, tag = get_enc(pt)

ct = ct1[:16] + ct2
do_exec(0, ct, tag)

# CODEGATE2020{F33D1NG_0N1Y_H4LF_BL0CK_W1TH_BL0CK_C1PH3R}

\0\0\0\0\0\0\0\0\0\0\0; cat flag;dddddddddd という暗号文を作る。

まず、 \0\0\0\0\0\0\0\0\0\0\0; cat aaaaaaaaaaaaaaaaを暗号化してもらう。すると nonce = 0でのtag0 が手に入るから、これで後続のflag;ddddddddddを手動で暗号化できる。

ただし、このままではタグは当然合わないので、この暗号文にあうタグを作る。

まずbbbbbbbbbbbbbbbbeeeeeeeeeeeeeeeeを暗号化する。そしてnonce = 1でのtag0を手に入れ、