caphosraです. IERAE CTF 2024にTSGとして参加しました. Cryptoのderangement, Weak PRNGとmiscのgnalangの計3問解いたのでwriteupを書きたいと思います.

分量と難易度的にgnalangのwriteupがメインになります.

Crypto: derangement 見出しへのリンク

長さ15のランダムな文字列をランダムに並べ替えたものが与えられ, その元の文字列を求める問題. 並び替えた文字列のどの文字も元の文字列と異なることが保証されている.

とりあえず回数上限近くまで並べ替え後の文字列を受け取って, 各 \(i\) 文字目についてありえない文字のリストを構成する. その上で, そのリストに含まれていない文字を順に並べていけば良い.

#!/usr/bin/python3

from ptrlib import *

proc = Socket("XXX.XXX.XXX.XXX", 55555)

LENGTH = 15
LOOP = 280

banned = list()
for _ in range(LENGTH):
    banned.append(list())

word = None
for _ in range(LOOP):
    proc.sendlineafter("> ", "1")
    proc.recvuntil("hint: ")
    hint = proc.recvline().decode()
    if not word:
       word = hint

    assert len(hint) == LENGTH

    for i in range(LENGTH):
        if hint[i] not in banned[i]:
            banned[i].append(hint[i])

determined = ""
for i in range(LENGTH):
    print(f"len(banned[{i}]) = {len(banned[i])}")
    if len(banned[i]) != LENGTH - 1:
        proc.close()
    for c in word:
        if c not in banned[i]:
            determined += c

print(f"magic word = {determined}")

proc.sendlineafter("> ", "2")
proc.sendlineafter("> ", determined)

proc.interactive()

実行結果は以下の通り.

$ ./exploit.py
[+] __init__: Successfully connected to XXX.XXX.XXX.XXX:55555
len(banned[0]) = 14
len(banned[1]) = 14
len(banned[2]) = 14
len(banned[3]) = 14
len(banned[4]) = 14
len(banned[5]) = 14
len(banned[6]) = 14
len(banned[7]) = 14
len(banned[8]) = 14
len(banned[9]) = 14
len(banned[10]) = 14
len(banned[11]) = 14
len(banned[12]) = 14
len(banned[13]) = 14
len(banned[14]) = 14
magic word = t`2KQ#yWR}:J_j\
[ptrlib]$ Congrats!
 IERAE{th3r35_n0_5uch_th!ng_45_p3rf3ct_3ncrypt!0n}
Connection limit reached. Exiting...

FLAG: IERAE{th3r35_n0_5uch_th!ng_45_p3rf3ct_3ncrypt!0n}

Crypto: Weak PRNG 見出しへのリンク

Pythonのrandomモジュールのgetrandbits(32)を使って生成された乱数がいくつか与えられるので, それより前に生成された乱数を推測してください, という問題.

検索すると, まんまな記事があったのでそのコードをほぼ丸パクリ参考にして解いた.

#!/usr/bin/python3

#
# Referenced: https://zenn.dev/hk_ilohas/articles/mersenne-twister-previous-state
#

from ptrlib import *
import random

proc = Socket("XXX.XXX.XXX.XXX", 19937)

#
# Basic operations
#
def untemper(x):
    x = un_bitshift_right_xor(x, 18)
    x = un_bitshift_left_xor(x, 15, 0xefc60000)
    x = un_bitshift_left_xor(x, 7, 0x9d2c5680)
    x = un_bitshift_right_xor(x, 11)
    return x


def un_bitshift_right_xor(x, shift):
    i = 1
    y = x
    while i * shift < 32:
        z = y >> shift
        y = x ^ z
        i += 1
    return y


def un_bitshift_left_xor(x, shift, mask):
    i = 1
    y = x
    while i * shift < 32:
        z = y << shift
        y = x ^ (z & mask)
        i += 1
    return y

def get_prev_state(state):
    for i in range(623, -1, -1):
        result = 0
        tmp = state[i]
        tmp ^= state[(i + 397) % 624]
        if ((tmp & 0x80000000) == 0x80000000):
            tmp ^= 0x9908b0df
        result = (tmp << 1) & 0x80000000
        tmp = state[(i - 1 + 624) % 624]
        tmp ^= state[(i + 396) % 624]
        if ((tmp & 0x80000000) == 0x80000000):
            tmp ^= 0x9908b0df
            result |= 1
        result |= (tmp << 1) & 0x7fffffff
        state[i] = result
    return state

#
# Main
#
nums = list()
collected = 0
while collected < 624:
    proc.sendlineafter("> ", "1")
    proc.recvuntil("data:\n")
    for _ in range(16):
        if collected < 624:
            nums.append(int(proc.recvline()))
            collected += 1
        else:
            break

mt_state = [untemper(x) for x in nums]
prev_mt_state = get_prev_state(mt_state)
random.setstate((3, tuple(prev_mt_state + [0]), None))

predicted = [random.getrandbits(32) for _ in range(624)]
print(f"secret: {predicted[623]}")

proc.sendlineafter("> ", "2")
proc.sendlineafter("> ", str(predicted[623]))

proc.interactive()

実行結果は以下の通り.

$ ./exploit.py
[+] __init__: Successfully connected to XXX.XXX.XXX.XXX:19937
secret: 2223950067
[ptrlib]$ Correct! Here is your flag:
IERAE{WhY_4r3_n'7_Y0u_u51n6_4_CSPRNG_3v3n_1n_2024}

FLAG: IERAE{WhY_4r3_n'7_Y0u_u51n6_4_CSPRNG_3v3n_1n_2024}

ポート番号がちゃんと19937になっているところにこだわりを感じた.

Misc: gnalang 見出しへのリンク

このwriteupのメインディッシュ. 問題設定がとても面白かった. 何してたらこんなに面白い問題が思いつくのか.

この問題では, 以下を満たすプログラムを構成することが要求される:

Info
  • 与えられた文字列が回文かどうかを判定できる
  • Javascriptとして実行してもshellscriptとして実行しても正常終了する (!?!?!?)
  • $, #, //, <!--, -->, \n, 半角スペースを含んではならない (!?!?!?!?!?)
  • ソースコード自体が回文である必要がある (!?!?!?!?!?!?!?)

いわゆるpolyglotを作る問題に加えて回文である必要があり, しかも行コメントが禁止されているので, ソースコードをすべて反転してコメントアウトしたものを後ろからくっつけるという安直な方法は封じられている. ゆえ, まず回文で実行可能なソースコードを考える必要があると考えた.

以降登場するソースコード全般において, あまりに読みにくかったので構文を無視して適当な字数で改行を入れた. もちろん, 実際に利用し提出したソースコードに改行は含まれていない.

1. Javascriptで回文になっている回文判定コードを構成する 見出しへのリンク

まず, Javascriptでソースコードが回文となっても実行できるものを考える. /* */という形式のコメントが封じられていないのでこれを使ってうまいコードを作れればいいのだが, ここでかなり詰まった. 夕飯時にその場にいたTSGのメンバーに相談し, hakatashiさんから以下のような構成を提案してもらった:

m=NaN;m/=1/*)[ereh](*/*([here])*/1=/m;NaN=m

なんと上記のコードは回文になっていて, かつ[here]のところに任意の式を入れて実行できる. ちょうど式を反転させた部分がコメントになっているのと, NaNが反転させてもNaNで代入してもエラーにならないことがうまく使われている. 賢すぎる. もちろんこれはありがたく使わせてもらった.

適当な回文判定の式を作り,

function(){abc=require("fs").readFileSync(0,"utf8");
if(abc==abc.split("").reverse().join("")){console.log("Yes")}else{console.log("No")}}()

先述の雛形に入れ込めば以下のようなコードが完成する.

m=NaN;m/=1/*))(}})"oN"(gol.elosnoc{esle})"seY"(gol.elosnoc{))""(nioj.)
(esrever.)""(tilps.cba==cba(fi;)"8ftu",0(cnySeliFdaer.)"sf"(eriuqer=cba{)(noitcnuf(*/
*(function(){abc=require("fs").readFileSync(0,"utf8");
if (abc==abc.split("").reverse().join("")){console.log("Yes")}
else{console.log("No")}}())*/1=/m;NaN=m

文は埋め込めないので, 式にするために関数で包む必要があった.

2. Shellscriptで回文になっている回文判定コードを構成する 見出しへのリンク

Shellscriptの場合, ソースコードを回文にするのはJavascriptより簡単だった. exitを使って途中で抜け出してしまえば, あとは構文さえ守っていればエラー落ちすることはないからだ. つまり,

[here];exit;tixe;[ereh]

とすればよい.

それよりも問題なのは, $を使わずに標準入力を取ってきて回文判定できるかどうかである. この問題はまともに取り組むと大変そうなので, 愚直実装をbase64でencodeしたもの埋め込んで, それを実行時にevalする方針をとった.

愚直実装は以下の通り.

a=`cat -`;b=`echo $a|rev`;if [ "$a" = "$b" ]; then echo "Yes"; else echo "No"; fi

あとはこれをbase64でencodeしたものをつかって,

eval `echo -n "YT1gY2F0IC1gO2I9YGVjaG8gJGF8cmV2YDtpZiBbICIkYSIgPSAiJGIiIF07IHRoZW4gZWNobyAiWWVzIjsgZWxzZSBlY2hvICJObyI7IGZp"
| base64 -d`;exit

これを反転させたものを後ろにつなぎ, 半角スペースをタブに置き換えれば, 条件を満たす回文コードが完成する.

eval	`echo	-n	"YT1gY2F0IC1gO2I9YGVjaG8gJGF8cmV2YDtpZiBbICIkYSIgPSAiJGIiIF07IHRoZW4gZWNobyAiWWVzIjsgZWxzZSBlY2hvICJObyI7IGZp"
	|	base64	-d`;exit;tixe;`d-	46esab	|
	"pZGI7IybOJCIvh2YlBSZzxWZgsjIzVWWiAyboNWZg4WZoRHI70FIiIGJiASPgISYkICIbBiZptDY2Vmc8FGJg8GajVGY9I2Og1CI0F2Yg1TY"	n-	ohce`	lave

3. 合体する 見出しへのリンク

あとはこれらのコードを合体させたい. 色々考えた結果, 以下のようなものにたどり着いた.

a=/*;[shell];"*/NaN;[js];NaN/*";[llehs];*/=a

a=/*;[shell];"*/NaN;[js];NaN/*";[llehs];*/=a

[shell]の部分と[js]の部分は適当にJavascriptとshellscriptに読み替えてもらいたい.

この式はshellscriptとして解釈すると, aにワイルドカードを使ったパス/*を代入してから[shell]部を実行する流れとなっている. [shell]内でexitしまえば, あとは構文エラーがなければ何が来ても良いのだが, そこでJavascriptのコードが邪魔をしてくる. その対策として, ダブルクオーテーションで[js]部を囲ってしまうことで正常終了するようにしている.

Javascriptとして解釈する場合はちょうど/* */で[shell]部とその他細々としたものがコメントアウトされるので正常に動作する.

以上を踏まえて2つのコードを合体させると以下のようになる.

a=/*;eval	`echo	-n	"YT1gY2F0IC1gO2I9YGVjaG8gJGF8cmV2YDtpZiBbICIkYSIgPSAiJGIiIF07IHRoZW4gZWNobyAiWWVzIjsgZWxzZSBlY2hvICJObyI7IGZp"
	|	base64	-d`;exit;"*/NaN;m=NaN;m/=1/*))(}})"oN"(gol.elosnoc{esle
})"seY"(gol.elosnoc{))""(nioj.)(esrever.)""(tilps.cba==cba(fi
;)"8ftu",0(cnySeliFdaer.)"sf"(eriuqer=cba{)(noitcnuf(*/
*(function(){abc=require("fs").readFileSync(0,"utf8");if(abc==abc.split("").reverse().join("")){console.log("Yes")}else{console.log("No")}}())
*/1=/m;NaN=m;NaN/*";tixe;`d-	46esab	|
	"pZGI7IybOJCIvh2YlBSZzxWZgsjIzVWWiAyboNWZg4WZoRHI70FIiIGJiASPgISYkICIbBiZptDY2Vmc8FGJg8GajVGY9I2Og1CI0F2Yg1TY"	n-	ohce`	lave;*/=a

上ではJavascriptとしてsyntax highlightしたが, shellにするとこんな感じ.

a=/*;eval	`echo	-n	"YT1gY2F0IC1gO2I9YGVjaG8gJGF8cmV2YDtpZiBbICIkYSIgPSAiJGIiIF07IHRoZW4gZWNobyAiWWVzIjsgZWxzZSBlY2hvICJObyI7IGZp"
	|	base64	-d`;exit;"*/NaN;m=NaN;m/=1/*))(}})"oN"(gol.elosnoc{esle
})"seY"(gol.elosnoc{))""(nioj.)(esrever.)""(tilps.cba==cba(fi
;)"8ftu",0(cnySeliFdaer.)"sf"(eriuqer=cba{)(noitcnuf(*/
*(function(){abc=require("fs").readFileSync(0,"utf8");if(abc==abc.split("").reverse().join("")){console.log("Yes")}else{console.log("No")}}())
*/1=/m;NaN=m;NaN/*";tixe;`d-	46esab	|
	"pZGI7IybOJCIvh2YlBSZzxWZgsjIzVWWiAyboNWZg4WZoRHI70FIiIGJiASPgISYkICIbBiZptDY2Vmc8FGJg8GajVGY9I2Og1CI0F2Yg1TY"	n-	ohce`	lave;*/=a

競技後に改めて見ると余計な部分が多いが, とりあえずこれですべての条件を満たすコードが完成した.

FLAG: IERAE{0mg_th3y_4r3_s0_t0re13nt_68a80ad1}

こういうmisc面白い. 面白いと一言で言えてしまうのは喉元過ぎていて熱さを忘れているから, という可能性は大いにある.

まとめ 見出しへのリンク

もっと知識と技術をつけて出直してきます.

(おまけ) 時間の使い方 見出しへのリンク

参戦が若干遅れたのでpwnやrevの簡単な問題はもうすでに別のTSGのメンバーによって解かれていた. そこでとりあえず誰も手をつけていなかったCrypto 2問を片付け, gnalangに手を出して解いた. gnalangはfirst bloodを逃し2番目だった.

次に5に手を出し, かなり時間を溶かした. 5をうらさんが解いた後は仮眠を挟んでThe Kudryavka Sequenceに移り, そのまま沼らして解くことが出来ずに時間が来てしまった.

参考 見出しへのリンク

Mersenne Twister (MT19937) で未来と過去の乱数列を予測してみる【Python】 - Zenn