ångstromCTF 2021 - Oracle of Blair

問題概要

Not to be confused with the ORACLE of Blair. Source

nc crypto.2021.chall.actf.co 21112

server.py

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

key = os.urandom(32)
flag = open("flag","rb").read()

while 1:
	try:
		i = bytes.fromhex(input("give input: "))
		if not i:
			break
	except:
		break
	iv = os.urandom(16)
	inp = i.replace(b"{}", flag)
	if len(inp) % 16:
		inp = pad(inp, 16)
	print(
		AES.new(key, AES.MODE_CBC, iv=iv).decrypt(inp).hex()
	)

何となくpadding oracleの逆みたいな感じがします（が、違います）

解説

プログラムの内容と問題

• 入力の{}をFLAGに書き換えたうえで、ランダムなivでAESのdecodeをします。
• AESはCBCモードです。

というざっくりとした内容をしているのですが、まずivがランダムであることから考えます。

• AES-CBCの復号では、以下が成立します。
  • $p[i] = c[i-1] \verb|^| dec(c[i]), c[-1] = iv$
  • この式から分かる通り、$c$は次のブロックにのみ影響を与えます。
• そのため、例えば$c[0] = 0$とすることで$c[1]$以降のブロックにivの影響を与えない、といったことが可能です。

ということでivの問題は突破しました。

この上で鍵を調べていくのですが、ブロック暗号の特徴「同じブロックを暗号化・復号すると全く同じ結果になる」という性質を使います。例えば15byte\x00が続いた後に1byte何かあるブロックの復号結果を知っているとして、これは未知の1byteについて全探索することでその文字が何だったのか知ることが出来ます。フラグフォーマットがactf{...}なので多分aです。

最初の1byteが確定したら今度は14byteの\x00の後ろにFLAGを付けた際の該当ブロックの復号結果と、既知の情報に1byteの全探索を組み合わせたブロックの復号結果を一致させることで、2byte目を知ることが出来ます。

以降も同様にして、1byteずつ前から判別していくことでフラグを知ることが出来ます。

solve.py

# crypto.2021.chall.actf.co 21112
from pwn import *
import sys
# context.log_level = "debug"

r = remote("crypto.2021.chall.actf.co", 21112)

flag = ""
BLOCK_SIZE = 16
iv = b"\x00" * BLOCK_SIZE
while True:
    block_num = len(flag) // BLOCK_SIZE + 2
    base = iv + b"\x00" * ((BLOCK_SIZE - 1) - (len(flag) % BLOCK_SIZE))
    r.recvuntil(b"give input: ")
    r.sendline((base + b"{}").hex())
    out = bytes.fromhex(r.recvline().decode().strip())[BLOCK_SIZE * (1 + len(flag) // BLOCK_SIZE) : BLOCK_SIZE * (2 + len(flag) // BLOCK_SIZE)]

    for i in range(128):
        payload = base + flag.encode() + i.to_bytes(1, 'little')
        r.recvuntil(b"give input: ")
        r.sendline(payload.hex())
        out2 = bytes.fromhex(r.recvline().decode().strip())[BLOCK_SIZE * (1 + len(flag) // BLOCK_SIZE) : BLOCK_SIZE * (2 + len(flag) // BLOCK_SIZE)]
        if out == out2:
            flag += chr(i)
            break
    print(flag)
    if flag[-1] == "}":
        break