witches_symmetric_exam (SECCON CTF 2022 Quals) WriteUp

# はじめに
この記事は [1日1CTF Advent Calendar 2024](https://qiita.com/advent-calendar/2024/1-day-1-ctf) の 1 日目の記事です。

# 問題
witches_symmetric_exam (問題出典: SECCON CTF 2022 Quals)

> crypto witch made a exam. The exam has to communicate with witch and saying secret spell correctly. Have fun ;)

GitHub リポジトリ: https://github.com/SECCON/SECCON2022_online_CTF/tree/main/crypto/witches_symmetric_exam

## 問題概要

```problem.py
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from flag import flag, secret_spell

key = get_random_bytes(16)
nonce = get_random_bytes(16)


def encrypt():
    data = secret_spell
    gcm_cipher = AES.new(key, AES.MODE_GCM, nonce=nonce)
    gcm_ciphertext, gcm_tag = gcm_cipher.encrypt_and_digest(data)

    ofb_input = pad(gcm_tag + gcm_cipher.nonce + gcm_ciphertext, 16)

    ofb_iv = get_random_bytes(16)
    ofb_cipher = AES.new(key, AES.MODE_OFB, iv=ofb_iv)
    ciphertext = ofb_cipher.encrypt(ofb_input)
    return ofb_iv + ciphertext


def decrypt(data):
    ofb_iv = data[:16]
    ofb_ciphertext = data[16:]
    ofb_cipher = AES.new(key, AES.MODE_OFB, iv=ofb_iv)

    try:
        m = ofb_cipher.decrypt(ofb_ciphertext)
        temp = unpad(m, 16)
    except:
        return b"ofb error"

    try:
        gcm_tag = temp[:16]
        gcm_nonce = temp[16:32]
        gcm_ciphertext = temp[32:]
        gcm_cipher = AES.new(key, AES.MODE_GCM, nonce=gcm_nonce)

        plaintext = gcm_cipher.decrypt_and_verify(gcm_ciphertext, gcm_tag)
    except:
        return b"gcm error"

    if b"give me key" == plaintext:
        your_spell = input("ok, please say secret spell:").encode()
        if your_spell == secret_spell:
            return flag
        else:
            return b"Try Harder"

    return b"ok"


print(f"ciphertext: {encrypt().hex()}")
while True:
    c = input("ciphertext: ")
    print(decrypt(bytes.fromhex(c)))
```

任意のデータを鍵が共通の AES_OFB → AES_GCM で復号化して、途中でエラーが出た時は OFB, GCM のどちらでエラーが出たのか教えてくれる (ただし復号化の結果は返さない) オラクルがあるので、
- 復号化すると `give me key` となるような暗号文
- AES_GCM → AES_OFB で暗号化した暗号文 (最初に渡される) を復号化したもの

を求める問題。

## 考察
[Wikipedia](https://ja.wikipedia.org/wiki/%E6%9A%97%E5%8F%B7%E5%88%A9%E7%94%A8%E3%83%A2%E3%83%BC%E3%83%89#Output_Feedback_(OFB)) の AES_OFB の復号化の図を眺めると、Padding Oracle Attack を用いることで、任意の平文を AES(_ECB) で暗号化した結果がわかりそう。そうすれば、好き勝手に AES_OFB で暗号化/復号化 可能。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/942569/95b244f9-b31f-4b74-8071-be16850abb28.png)

実装はこんな感じ。

```py
def encrypt(plaintext):
    ciphertext = b""
    for i in range(16):
        for j in range(256):
            c = (bytes([j]) + ciphertext).rjust(16, b"\x00")
            c = strxor(c, bytes([i + 1]) * 16)
            io.sendline((plaintext + c).hex().encode())
        for j in range(256):
            res = io.recvuntil(b"error")
            if b"gcm error" in res:
                ciphertext = bytes([j]) + ciphertext
    return ciphertext
```

[Wikipedia](https://ja.wikipedia.org/wiki/Galois/Counter_Mode) の AES_GCM の仕組みも眺めてみると、これもさっきのオラクルがあれば何でもできそう。復号化も、暗号化も、タグ生成も可能。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/942569/2c414f28-30bd-63bb-8a25-77db29e4a05f.png)


## 実装

[pycryptodome の実装](https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py) とにらめっこして頑張って実装する。

```py
from pwn import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.strxor import strxor
from Crypto.Cipher._mode_gcm import _ghash_portable, _GHASH

io = process(["python3", "problem.py"])

io.recvuntil(b"ciphertext: ")
ciphertext = bytes.fromhex(io.recvline().strip().decode())


def encrypt(plaintext):
    ciphertext = b""
    for i in range(16):
        for j in range(256):
            c = (bytes([j]) + ciphertext).rjust(16, b"\x00")
            c = strxor(c, bytes([i + 1]) * 16)
            io.sendline((plaintext + c).hex().encode())
        for j in range(256):
            res = io.recvuntil(b"error")
            if b"gcm error" in res:
                ciphertext = bytes([j]) + ciphertext
    return ciphertext


# ciphertext を復号する

# 1. OFB

ofb_iv = ciphertext[:16]
ciphertext = ciphertext[16:]
plaintext = b""
while len(ciphertext):
    c = encrypt(ofb_iv)
    plaintext += strxor(c, ciphertext[:16])
    ofb_iv = c
    ciphertext = ciphertext[16:]

plaintext = unpad(plaintext, 16)

# 2. GCM

gcm_tag = plaintext[:16]
gcm_nonce = plaintext[16:32]
gcm_ciphertext = plaintext[32:]

hash_subkey = encrypt(b"\x00" * 16)
ghash_in = gcm_nonce + b"\x00" * 15 + b"\x80"
j0 = _GHASH(hash_subkey, _ghash_portable).update(ghash_in).digest()
nonce_ctr = j0[:12]
iv_ctr = (bytes_to_long(j0) + 1) & 0xFFFFFFFF

plaintext = b""
while len(gcm_ciphertext):
    c = encrypt(nonce_ctr + long_to_bytes(iv_ctr, 4))
    if len(gcm_ciphertext) < 16:
        c = c[: len(gcm_ciphertext)]
    plaintext += strxor(c, gcm_ciphertext[:16])
    gcm_ciphertext = gcm_ciphertext[16:]
    iv_ctr = (iv_ctr + 1) & 0xFFFFFFFF

secret_spell = plaintext

print(f"{secret_spell = }")


# b"give me key" を暗号化する

# 1. GCM (nonce はさっきのを使い回す)

plaintext = b"give me key"
iv_ctr = (bytes_to_long(j0) + 1) & 0xFFFFFFFF
c = encrypt(nonce_ctr + long_to_bytes(iv_ctr, 4))
c = c[: len(plaintext)]
gcm_ciphertext = strxor(c, plaintext)

hash = (
    _GHASH(hash_subkey, _ghash_portable)
    .update(
        gcm_ciphertext
        + b"\x00" * (31 - len(gcm_ciphertext))
        + bytes([8 * len(gcm_ciphertext)])
    )
    .digest()
)
gcm_tag = strxor(hash, encrypt(j0))
plaintext = pad(gcm_tag + gcm_nonce + gcm_ciphertext, 16)

# 2. OFB

ofb_iv = b"hiikunZ_hogehoge"  # 16 bytes ならなんでもいい
ciphertext = ofb_iv

while len(plaintext):
    c = encrypt(ofb_iv)
    ciphertext += strxor(c, plaintext[:16])
    ofb_iv = c
    plaintext = plaintext[16:]

print(f"{ciphertext.hex() = }")

io.recvuntil(b"ciphertext: ")
io.sendline(ciphertext.hex().encode())
io.recvuntil(b"ok, please say secret spell:")
io.sendline(secret_spell)
io.interactive()
```

flag: `SECCON{you_solved_this!?I_g1ve_y0u_symmetr1c_cipher_mage_certificate}`