authored by kurenaif
Lets' party started! please tell me magic word
from Crypto.Util.Padding import pad, unpad
import Crypto.Cipher.AES as AES
import json
import secrets
import string
import random
import base64
import os
FLAG = os.getenv("FLAG", "flag{dummy}")
DETECTION_COUNT = 10000
MAGIC_LENGTH = 150
key = secrets.token_bytes(16)
magic_key = ''.join(random.choices(string.ascii_letters, k=MAGIC_LENGTH))
magic_key = json.dumps({"key": magic_key})
def encrypt(plaintext):
cipher = AES.new(key=key, mode=AES.MODE_CBC)
encrypted_flag = cipher.encrypt(pad(pad(pad(plaintext.encode(), 16), 16), 16))
return cipher.iv + encrypted_flag
def decrypt(iv_ciphertext):
assert len(iv_ciphertext) >= 16*3
iv = iv_ciphertext[:16]
ciphertext = iv_ciphertext[16:]
cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
a = unpad(unpad(unpad(cipher.decrypt(ciphertext), 16), 16), 16).decode()
return a
def query(c):
try:
text = decrypt(c)
except:
return "decrypt error"
try:
json.loads(text)["key"]
return "ok"
except:
return "json error"
print("encrypted_word:", base64.b64encode(encrypt(magic_key)).decode())
for i in range(DETECTION_COUNT):
q = input("> ")
if q == magic_key:
print("Congratz! flag is here", FLAG)
print(query(base64.b64decode(q)))
if i >= DETECTION_COUNT:
print("WARNING WARNING evil attacker detected WARNING WARNING")
ランダムな150文字の英字文字列magic_keyを作り、それを{"key": magic_key}というJSON文字列にしています。 我々はこのJSON文字列であるmagic_key`を当てることができたらフラグを得られます。
なお、我々には、2つのパターンの結果が得られます。
- パディングが正常に除去され、デコードが成功したか
- JSONの"key"が正常に抽出できたか
これらの情報を使って10000という回数で当てることが目標です。
解法
Padding Oracle Attackの考察
今回のAESはCBCモードですが、CBCではブロックごとに
$$
P_i = D_K(C_i) \oplus C_{i-1}
$$
なので、攻撃者は前の暗号文ブロック$C_{i-1}$をいじることで、復号後の平文ブロック$P_i$を好きなようにXORで変えられることがわかります($D_K$は復号関数)。
さて、PKCS#7のようなパディングの場合、最後のバイトが\x01になってそれが整合しているかをオラクルで試せるため256通り試せばよいことがわかります。次に\x02\x02とやることで中身が復元できるというのがPadding Oracle Attackです。
さて、今回のコードに戻りましょう。decrypt関数を見るとunpad(unpad(unpad(cipher.decrypt(ciphertext), 16), 16), 16).decode()とunpadを3回やっていることがわかります。そのため、これが成功するためには\x01\x01\x01とならないといけませんが、我々が知りえる情報はdecryptに成功したか失敗したかの2つのみです。ということは、unpadを3回連続で通すためには、
$$
(1/255)^3 \approx 6.03 \times 10^{-8}
$$
となります。さて、1回あたりの成功確率$p$に対し、試行回数$n$のとき、1回以上成功する確率は
$$
1-(1-p)^n
$$
と表され、今回$p$は極端に小さいため
$$
1-(1-p)^n \approx np
$$
と近似できます。さて、$p \approx 6.03 \times 10^{-8}$、$n = 10000$より、
$$
np \approx 10^4 \cdot 6.03 \times 10^{-8} = 6.03 \times 10^{-4}
$$
となり、成功率は0.06%と明らかに不可能です。
つまり、今回の課題をクリアするためには、別の方法を考える必要があります。
先頭ブロックの復元
今回のブロックサイズは16なので、1ブロック目は
IV|{"key" :"...
となっています。JSONは先頭の空白を無視するため、IVと{の間にスペースを入れることでJSONの開始位置を好きな位置にずらすことができます。
IV|{"key":"...
IV| {"key":"...
さて、
スペースを入れる前をfrom_str、スペースを入れた後の文字列をto_strとしましょう。
CBC復号の第一ブロックは、
$$
P_1 = D_K(C_1) \oplus IV
$$
と表すことができます。
この時、$IV' = IV \oplus (from_{str}[i] \oplus to_{str}[i])$に変更すると、
\begin{align}
P_1' &=& D_K(C_1) \oplus IV \oplus (from_{str}[i] \oplus to_{str}[i]) \\
&=& (D_K(C_1) \oplus IV) \oplus from_{str}[i] \oplus to_{str}[i]\\
&=& P_1 \oplus from_{str}[i] \oplus to_{str}[i]
\end{align}
と表すことができ、平文がto_str[i]に置換できます。
このようにして、最初の16バイトを当てることができます。
2ブロック目以降の復元
このまま続けることも可能ですが、2ブロック目以降の調査を行うためには、{"key": という接頭辞を2ブロック目の先頭にそろえる必要があります。そして、未知部分を探索するためには$52^8$通り試す必要があるため、別の方法を考える必要があります。
ここで、decrypt errorが出る条件を考えましょう。
unpad(unpad(unpad(cipher.decrypt(ciphertext), 16), 16), 16).decode()という処理ですが、
- いずれかのunpadが失敗
- decode()が失敗
のどちらかになります。ここで、IVのみを改ざんするということは、末尾ブロックは不変であるといえます。つまり、1番のunpadが失敗というのは考えにくいです。
つまり、IVのみを改ざんすることによって発生するdecrypt errorは、UTF-8 decodeに失敗したということが言えます。
そこで、次はUTF-8 decode が失敗する条件を利用して、未知バイトに関する情報を得ることを考えます。
下記のサイトによると、UTF-8には各文字のバイト列が指定されたビットパターンを満たしている必要があります。
https://www.unicode.org/versions/Unicode17.0.0/core-spec/chapter-3/#G27506
先頭バイト$b_1$は0xC2 ~ 0xDFであり、次のバイト$b_2$は0x80 ~ 0xBFである必要があります。ただし、0xC0, 0xC1は禁止されています。
つまり、$b_1,b_2$のいずれかが上記の範囲を外れるのなら、UTF-8 decodeは例外を投げ、decrypt errorが返却されます。
ここで、string.ascii_lettersを格納したguess_charを考えましょう。
guess_charは必ず
$$
guess_{char} \in [0x41, 0x5A] \cup [0x61, 0x7A]
$$
に収まり、上位2ビットは必ず01となります。
ここで、0xC0でXORを取ると、上位2ビットは必ず10となります。
これにより、$guess_{char} \oplus 0xC0$をすることで、$b_2$は必ず正しいバイトになります。
後は、$b_1$がどのようなときに失敗するのでしょうか。
$$
b_1(chr) = guess_{char} \oplus 0xC0 \oplus chr
$$
というchrを総当たりで探すことを考えてみましょう。便宜上、$guess_{char} \oplus 0xC0$を$t$とします。
すると、これらは、英字のXORとなるため、上位2ビットは00となり、
$$
t \in [0x00, 0x3F]
$$
となります。
そして、
$$
b_1(chr) = 0xc0 \oplus t
$$
より、$b_1$が0xC2 ~ 0xDFにある条件は下位6ビットが0x02 ~ 0x1Fという条件に等価であるといえます。
したがって、デコード失敗になるのは、
$$
t \in [0x00, 0x01] \cup [0x20, 0x3F]
$$
となります。
この時、大文字Aと小文字aを考えましょう。この差は0x20となります。
ということは、同じアルファベットでも、大文字小文字が違うなら、右側の範囲0x20 ~ 0x3Fに入ります。
つまり、0x00, 0x01のいずれかの比較が行えたら良いわけです。
もし、t=0なら、guess_char = chrであり、t=1ならguess_char = chr ^ 1です。
以上より、decrypt errorが出た文字から2つずらして、decrypt errorがでるのなら大文字と小文字がずれており、decrypt errorが出ないのなら、後者であると判断できます。
以上の考えから探索を行えば、14バイトを特定することができます。そして残った最後の2文字は"とchrでxorを取ることにより判定することができます。
後は、これを用いて復元することで今回の問題を解くことができます。
from pwn import *
import base64
import string
HOST = "cbc-magic-word.seccon.games"
PORT = 3333
MAGIC_LEN = 150
io = remote(HOST, PORT)
def find_prefix():
from_str = "{\"key\": \""
to_str = " {\"key\": "
buf = bytearray(base_ct)
for i, (a, b) in enumerate(zip(from_str, to_str)):
buf[i] ^= ord(a) ^ ord(b)
base64_cands = string.ascii_letters + string.digits + "+/"
prefix = ""
start = len(from_str)
end = start + 7
for i in range(start, end):
for cand in base64_cands:
trial_ct = buf.copy()
trial_ct[i] ^= ord(cand) ^ ord('"')
io.sendlineafter(b">", base64.b64encode(trial_ct))
res = io.recvline().strip()
if b"ok" in res:
prefix += cand
print("prefix:", prefix)
buf[i] ^= ord(cand) ^ ord(" ")
break
return prefix
def find_magic_key():
prefix = find_prefix()
chunk = ""
chars = string.ascii_letters
for i in range(9):
guess_chrs = ""
for pos in range(12 if i == 0 else 13, -1, -1):
for chr in chars:
# ---- Query A: make (pos) look like 0xE1, force (pos+1) into continuation-ish
ct = base_ct[-(16*(5+i)):].copy()
ct[pos+1] ^= 0xc0
ct[pos] ^= 0xe1 ^ ord(chr)
io.sendlineafter(b">", base64.b64encode(ct))
res = io.recvline()
if b'decrypt error' not in res:
continue
# ---- Query B: make (pos) look like forbidden 0xC1, force (pos+1) continuation-ish
ct = base_ct[-(16*(5+i)):].copy()
ct[pos+1] ^= 0xc0
ct[pos] ^= 0xc1 ^ ord(chr)
io.sendlineafter(b">", base64.b64encode(ct))
res = io.recvline()
if b'decrypt error' not in res:
continue
# ---- Query C (v1): try 3-byte with E0 and two continuation-ish bytes
ct = base_ct[-(16*(5+i)):].copy()
ct[pos+2] ^= 0xc0
ct[pos+1] ^= 0xc0
ct[pos] ^= 0xe0 ^ ord(chr)
io.sendlineafter(b">", base64.b64encode(ct))
res = io.recvline()
v1 = b'decrypt error' in res
# ---- Query D (v2): tweak the 2nd byte differently to trigger E0 exception behavior
ct = base_ct[-(16*(5+i)):].copy()
ct[pos+2] ^= 0xc0
ct[pos+1] ^= 0xe0
ct[pos] ^= 0xe0 ^ ord(chr)
io.sendlineafter(b">", base64.b64encode(ct))
res = io.recvline()
v2 = b'decrypt error' in res
if v1 ^ v2:
guess_chrs = chr + guess_chrs
print(f"[utf8] step = {i} pos = {pos} guess_chr = {guess_chrs}")
break
for _ in range(2):
target = '{"key":'.ljust(len(guess_chrs))
for chr in chars:
ct = base_ct[-(16*(5+i)):].copy()
for idx, (a, b) in enumerate(zip(guess_chrs, target)):
ct[idx] ^= ord(a) ^ ord(b)
ct[len(guess_chrs)] ^= ord(chr) ^ ord('"')
io.sendlineafter(b">", base64.b64encode(ct))
res = io.recvline().strip()
if b"ok" in res:
guess_chrs += chr
print(f"[json] +1 => {guess_chrs}")
break
chunk = guess_chrs + chunk
print(f"[utf8] step = {i} pos = {pos} | chrs = {chunk} | total = {len(chunk)}/{MAGIC_LEN}")
if len(prefix + chunk) == MAGIC_LEN:
return prefix + chunk
else:
raise ValueError("failed to find magic key")
io.recvuntil(b"encrypted_word:")
encrypted_word = io.recvline().strip().decode()
base_ct = bytearray(base64.b64decode(encrypted_word))
magic_key = find_magic_key()
io.sendline(f'{{"key": "{magic_key}"}}'.encode())
io.interactive()
Flag: SECCON{MakeSomeNoise~~~~~pad-pad-pad-And-Unpad-Unpad-Unpad}