RTACTF 2023 春 - 並走感想

長時間CTFに飽いた強者たちの遊びことRTACTFの第２回が開催されました。前回は走者として参加しましたが、今回は私は走者を退いて一参加者として参戦しました。だこつさんの画面が見たかったので……

というわけで並走writeupです。当日のアーカイブはこちら

XOR-CBC
Collision-DES
Reused AES
1R-AES
感想

XOR-CBC

目標タイム： 480秒記録： 560.06秒（4位）

与えられている暗号化スクリプトは長いので省略しますが、次の図のような暗号化が行われていて、平文の先頭は RTACTF{ であることが保証されているので既知です。

XOR-CBC Explained:

     plain 0       plain 1       plain 2
        |             |             |
        v             v             v
IV --> XOR  +------> XOR  +------> XOR
        |   |         |   |         |
        v   |         v   |         v
key -> XOR  | key -> XOR  | key -> XOR
        |   |         |   |         |
        +---+         +---+         |
        |             |             |
        v             v             v
[IV] [cipher 0]    [cipher 1]    [cipher 2]

cipher 0 は $cipher_0 = IV \oplus key \oplus plain_0$ と表されて、 $cipher_0, IV$ と $plain_0$ の8バイト中7バイトが既知なので、1バイト全探索すれば $key$ が求められます。正しい $key$ が得られているかどうかは「フラグが読めるか」「パディングが正常になっているか」をみればわかります。

読めるフラグを256通りの中から探すのに失敗して、パディングが正常かどうかを見ればよいのに気がつくのに時間をかけてしまって目標タイムに届かなかったのが無念でした。

from ptrlib import chunks, xor
cipher = chunks(bytes.fromhex("6528337d61658047295cef0310f933eb681e424b524bcc294261bd471ca25bcd6f3217494b1ca7290c158d7369c168b3"), 8)

iv, cipher = cipher[0], cipher[1:]

for x in range(256):
    plain = b"RTACTF{" + bytes([x])
    k = xor(iv, xor(cipher[0], plain))

    last_c = cipher[0]

    m = plain
    for c in cipher[1:]:
        m += xor(c, xor(last_c, k))
        last_c = c

    if m[-1] == 7:
        print(m)

Collision-DES

目標タイム： 720秒記録： 529.61 秒（3位）

from Crypto.Cipher import DES
from Crypto.Util.Padding import pad
import os

FLAG = os.getenv("FLAG", "RTACTF{**** REDACTED ****}")

def encrypt(key, plaintext):
    cipher = DES.new(key, DES.MODE_ECB)
    return cipher.encrypt(pad(plaintext, 8))

if __name__ == '__main__':
    key1 = os.urandom(8)
    print(f"Key 1: {key1.hex()}")
    key2 = bytes.fromhex(input("Key 2: "))

    assert len(key1) == len(key2) == 8, "Invalid key size :("
    assert len(set(key1).intersection(set(key2))) == 0, "Keys look similar :("

    plaintext = b"The quick brown fox jumps over the lazy dog."
    if encrypt(key1, plaintext) == encrypt(key2, plaintext):
        print("[+] You found a collision!")
        print(FLAG)
    else:
        print("[-] Nope.")

DESで、相異なる2つの鍵で1つの平文を暗号化して同一の平文になることがありますか？　という問題です。まあそういうことがあることもあると思うけど、平文が固定されているので流石にそんなペアを見つけることはできないでしょう。となると、違う鍵に見えて実は同じ挙動をする鍵になっている必要があって、こういうときにDESでは鍵は64bit中の56bitしか使われないという話を思い出します。

Wikipediaでそのエピソードを調べて、「じゃあどのbitが使われないのか調べにDESの実装見に行くか」をしかけたところで「RTACTFでそんなことしてる暇ないだろ」と思い直して、鍵を1バイトずつ変化させて同じになるペアを探す、という方針に切り替えました。これがうまくハマったのは良かった。各バイトのLSBがそうというのは全然気がついていませんでした。

from ptrlib import Socket
from Crypto.Cipher import DES
from Crypto.Util.Padding import pad

sock = Socket("nc 35.194.118.87 7002")
key1 = bytes.fromhex(sock.recvlineafter("1: ").decode())

plaintext = b"The quick brown fox jumps over the lazy dog."
key2 = list(key1)

def encrypt(key, plaintext):
    cipher = DES.new(key, DES.MODE_ECB)
    return cipher.encrypt(pad(plaintext, 8))

for i in range(8):
    for c in range(256):
        if c == key1[i]:
            continue

        key2[i] = c
        if encrypt(key1, plaintext) == encrypt(bytes(key2), plaintext):
            print("found")
            break
    else:
        print("not found")
        quit()


print(key1.hex())
print(bytes(key2).hex())
sock.sendlineafter("2: ", bytes(key2).hex())
sock.interactive()

ところでこの問題の len(set(key1).intersection(set(key2))) == 0 という制約だとkey1 に最下位bitのみがことなる2バイトがあるときに問題が解けなくなってしまうので、普通に1バイトずつ比較して同じのがあったらだめ、ということにしたら良かったと思います

Reused AES

目標タイム： 1080秒記録： 1966.67秒（4位）

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os

iv = os.urandom(16)
key = os.urandom(16)
FLAG = os.getenv("FLAG", "RTACTF{**** REDACTED ****}").encode()

def encrypt(data):
    cipher = AES.new(key, AES.MODE_CFB, iv)
    return cipher.encrypt(pad(data, 16))

if __name__ == '__main__':
    print(encrypt(FLAG).hex())
    print(encrypt(input("> ").encode()).hex())

シンプルな問題で良いですね。CFBという文字を見た瞬間に「暗号利用モード」で検索しました。

なんかWikipediaに書いてある挙動と違ってデータが1バイトずつ処理されていそうであるだとか、サーバが入力を受け付けるときはhex encodingされていない想定であるだとかにひっかかって無限に時間を浪費していましたが、とりあえず \0 を暗号化すれば1バイト目のストリームキーが手に入るので、あとは既知の平文と\0 を組み合わせて1バイトずつ特定しました。

from ptrlib import Socket, xor

l = 1
known = b""

while len(known) < l:

    sock = Socket("nc 35.194.118.87 7001")
    
    a = bytes.fromhex(sock.recvline().decode())
    if l == 1:
        l = len(a)

    sock.sendlineafter("> ", (known + b"\0" * (len(a) - len(known))))
    y = bytes.fromhex(sock.recvline().decode())
    m = xor(a, y)[len(known)]
    print(bytes([m]))
    sock.close()
    known = known + bytes([m])
    print(known)

1R-AES

目標：1320秒記録：3030.96秒（7位）

import aes
import os

key = os.getenv("KEY", "*** REDACTED ***").encode()
assert len(key) == 16

flag = os.getenv("FLAG", "RTACTF{*** REDACTED ***}")
assert flag.startswith("RTACTF{") and flag.endswith("}")
la = flag[len("RTACTF{"):-len("}")]
assert len(la) == 16

cipher = aes.AES(key)
print("enc(la):", cipher.encrypt_block(la.encode()).hex())

while True:
    cipher = aes.AES(key)
    plaintext = bytes.fromhex(input("msg > "))
    assert len(plaintext) == 16
    print("enc(msg):", cipher.encrypt_block(plaintext).hex())

AESの実装は aes/aes.py at d6857518fa95f08352a250242b0cf21d2544e470 · boppreh/aes · GitHubですが、ラウンド数が1になるように改造されています。

1ラウンドだと以下の処理のループの部分が一回も回らないので、処理は add_round_key sub_bytes shift_rows add_round_key のみ、未知の値は16バイト x 2個のラウンド鍵のみになります。

    def encrypt_block(self, plaintext):
        """
        Encrypts a single block of 16 byte long plaintext.
        """
        assert len(plaintext) == 16

        plain_state = bytes2matrix(plaintext)

        add_round_key(plain_state, self._key_matrices[0])

        for i in range(1, self.n_rounds):
            sub_bytes(plain_state)
            shift_rows(plain_state)
            mix_columns(plain_state)
            add_round_key(plain_state, self._key_matrices[i])

        sub_bytes(plain_state)
        shift_rows(plain_state)
        add_round_key(plain_state, self._key_matrices[-1])

        return matrix2bytes(plain_state)

解いてるときはAES, 少ラウンド数, Chosen-Plaintext Attack可能 → はい内部状態を求めるんですね、になりましたが意外と想定は平文があっているかを前から見ればよかったらしいです。ブロック単位で処理してるからだめだろうな〜と思ってその選択肢は捨ててました……。

とりあえずラウンド数の少ないブロック暗号はz3とおもって一旦はz3での攻略をめざしましたが、S-Boxが非線形なので素直には組めず諦めました。

次にラウンド鍵の数が少ないことに着目して、ラウンド鍵1, 2 の1バイトずつを全探索（2バイト全探索 x 16回）で暗号化に成功するやつだけ残すようにして候補を絞り込んだらどうか、という方針でやりました。これを組むのに時間がかかったけど、方針としてはあってたっぽいです。説明が面倒になってしまって適当を書いています、いま。

鍵の対応だけz3 でそれっぽく出して、探索は普通にやりました。

from ptrlib import Socket

import aes
from aes import bytes2matrix, sub_bytes, shift_rows, add_round_key, matrix2bytes
import os

subkey_pos = [
(0,0),
(1,1),
(2,2),
(3,3),
(1,0),
(2,1),
(3,2),
(0,3),
(2,0),
(3,1),
(0,2),
(1,3),
(3,0),
(0,1),
(1,2),
(2,3),
]

subkey_pos2 = [
 (0,0),
 (0,1),
 (0,2),
 (0,3),
 (1,0),
 (1,1),
 (1,2),
 (1,3),
 (2,0),
 (2,1),
 (2,2),
 (2,3),
 (3,0),
 (3,1),
 (3,2),
 (3,3),
]

def make_dummy_state(a, b, v):
    s = [ [0 for _ in range(4)] for _ in range(4) ]
    s[a][b] = v
    return s

sock = Socket("nc 35.194.118.87 7003")
encrypted_flag = bytes.fromhex(sock.recvlineafter(":").decode())

pairs = []

for _ in range(20):
    plaintext = os.urandom(16)
    sock.sendlineafter("msg > ", plaintext.hex())
    ciphertext = bytes.fromhex(sock.recvlineafter(":").decode())
    pairs.append((plaintext, ciphertext))

key1 = [[0 for _ in range(4)] for _ in range(4)]
key2 = [[0 for _ in range(4)] for _ in range(4)]

for key_pos in range(16):
    ky = key_pos // 4
    kx = key_pos % 4
    sx1, sy1 = subkey_pos[key_pos]
    sx2, sy2 = subkey_pos2[key_pos]

    candidates = [0 for _ in range(256**2)]
    for (plaintext, target) in pairs:
        for x in range(256):
            for y in range(256):

                plain_state = bytes2matrix(plaintext)
                add_round_key(plain_state, make_dummy_state(sx1, sy1, x))

                sub_bytes(plain_state)
                shift_rows(plain_state)

                add_round_key(plain_state, make_dummy_state(sx2, sy2, y))

                c =  matrix2bytes(plain_state)

                if c[key_pos] == target[key_pos]:
                    candidates[256*y + x] += 1

    p = candidates.index(max(candidates))
    key1[sx1][sy1] = p % 256
    key2[sx2][sy2] = p // 256

    print(key1, key2)

key = os.getenv("KEY", "*** REDACTED ***").encode()
assert len(key) == 16

cipher = aes.AES(key)
cipher._key_matrices[0] = key1
cipher._key_matrices[-1] = key2

print(cipher.decrypt_block(encrypted_flag))

感想

そこそこの成績を出せたのと、時間はかかっても独力で全部解けたのとで満足しています。ptr-yudaiの問題、どれもシンプルだけど面白くて良かったです。

ただ、走者じゃなくてもめちゃめちゃ緊張はしました。1問目で正解のフラグがどれかわからなくて困っているとき「負け、負ける！」とか思わず口走ってしまっていた。こんなのを毎週やっていると思うと競技プログラマはすごいですね。

運営してくれた皆さん、企画と配信を盛り上げてくれた皆さん、一緒に走った皆さんありがとうございました。またやってほしいです