ksnctf 21 Perfect Cipher 200pt

#問題

https://ksnctf.sweetduet.info/problem/21

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/27137d5b-c516-6ffb-1c0e-a0ae0f708060.png)


#解いてみた

問題文を翻訳してみます。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/b7ce676c-3642-22f1-78ac-eb1b265e79c5.png)

暗号に関する説明ですね。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/6394fa76-078b-040b-10d2-348cdb7dd5f6.png)

zipファイルをダウンロードして、解凍すると以下のファイルが保存されていました。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/9861afd7-9383-52dc-36fc-e6424b18ae32.png)

pcapじゃないけどWiresharkに紐づいてるファイルが2つあったので読み込ませてみるとエラーになりました。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/7c957f84-60d6-fbb4-82e0-a62547a6cc16.png)

pcap以外よく知りませんが、一応encというファイルも使用できるようです。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/0aa64a7c-c19b-e786-ab99-5140fb6d2183.png)

まぁ今回はたまたま拡張子が一緒だったというだけのことだと思います。

encrypt.cppを見てみると、main関数があったので、こっちがメインのプログラムだと推測されます。
main中を見てみると

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/d9d35243-a25a-76db-45da-591cfdf1c251.png)

と書かれています。
encrypt.keyを使ってencrypt.cppを暗号化したものがencrypt.encと推測できます。
flagの方も一緒ですね。

たぶん最終的にやりたいこととしてはflag.jpgを作れば答えが書いてあるんだと思います。

encrypt関数を見てみると以下のような感じでしょうか。

- encrypt.cppを読み込む
- encrypt.cppのバイト数を先頭4バイトを使ってencrypt.encに書き込む
- 乱数を生成する
- 生成した乱数とencrypt.cppをxorする
- 生成した乱数をencrypt.keyに書き込み、xorした結果をencrypt.encに書き込む

xorの性質を確認しておきます。

```
A xor B = C のとき
B xor C = A
C xor A = Bがなりたつ

xorする順番は逆でもなりたつ。
```

なのでまとめると

```
encrypt.cpp xor encrypt.key = encrypt.enc
ということをしているので、encrypt.keyを算出するには
encrypt.cpp xor encrypt.enc = encrypt.key
をすればいい
```

ということになります。
さっきの話だとencrypt.cppとencrypt.encのバイト数が4違うはずなので一応確認してみます。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/59d2097b-6632-04a6-da70-c5d8fb8207d6.png)

あってるみたいです。
事前に先頭4バイトを削ってからxorします。
∵先頭4バイトにファイルサイズが書かれているため。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/3ae281c0-01ec-3aaf-1809-0b71e0dcbe66.png)

いい感じのkeyファイルができました。あってると信じます。

さて、ここから何をすればいいんでしょう。
一度立ち戻ってみます。

全体の流れとしては以下です。

- encrypt.cppとencrypt.encからencrypt.keyを出す
- encrypt.keyからflag.keyを出す
- flag.keyとflag.encからflag.jpgを出す
- flag.jpgに答えが書いてあるはず

今ようやく1つ目が終わったところです。
まだ2つ目かと思ったけど3番目はxorすればいいだけで4番目は画像ファイル見ればいいだけなので、実質2が最後の関門っぽい。

2をやるにあたって流れとしては乱数を予測するんだと思うんですよね。

例えば
1,2,3,4　とくれば次は5
1,2,4,8　とくれば次は16
みたいな。

main関数をもう一度見てみると

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/d9d35243-a25a-76db-45da-591cfdf1c251.png)

となっているので、flagを暗号化したflag.keyはencrypt.keyの続きを予測すればおのずと見えてくる的な。

2をやるには乱数生成のところを見るしかないです。
ここでもう一つのcppファイルmt19937ar.cppが出てきます。
乱数を生成しているファイルです。
開いてみると先頭にかなりコメントがあって、急造した感じではなかった。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/8cbf091f-e2fd-18fc-c531-eed549f87b56.png)

一般に作られてそうなので検索してみます。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/168fb144-aa59-730b-3a1e-0c878354907e.png)

だそうです。乱数の世界は未知の領域です。

短所のところを見ると予測可能と書かれていました。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/357b3919-fe99-d84c-5918-0fad7208af71.png)

具体的な予測方法が書かれてなかったので、検索してみます。
[Mersenne Twisterの出力を推測してみる - ももいろテクノロジー](http://inaz2.hatenablog.com/entry/2016/03/07/194147)

すごい人がいるもんです。
624個ランダム数が与えられれば次から予測できるらしい。
ちなみにPythonのRandomもこれを使ってるみたいなので、Pythonの乱数も同じ方法で予測できるらしいです。
このサイトに書いてあったプログラムを使って、encrypt.keyの先頭から624個取得して、そこから続きを予測するように編集。

ちなみにflag.encは78560バイトでした。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/b7957508-2615-d4d5-dfc0-a64d566f9792.png)

先頭4バイトはflag.jpgのバイト数が書かれているので78560-4をした78556バイト必要。
78556バイトというのは乱数でいうと19639個の乱数が必要。
∵乱数は4バイトずつ使ってるので78556÷4=19639。

混乱してきました。まとめると

- encrypt.keyの先頭から4バイトずつ624個取得するとそれ以降の乱数を予測できるようになる。
- encrypt.keyは2600バイト。
- 今2496バイト（4バイトずつ624個）は使ったので予測する最初の104バイト（2600-2496）はencrypt.keyの残りなので使わない。
- その続きの78556バイト（19639個の乱数）をflag.keyとして保存する。

まとめたところでなんかよくわかりませんね。書き間違いとかありそうな気がしています。。。

まぁ上記プログラムを実行したところ、flag.keyができあがりました。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/1bac3d57-0ee3-0f5b-232a-52fba990dbec.png)

さて、これを使ってflag.encとflag.keyのXORを計算します。
flag.encは先頭4バイトを事前に削除しておきます。
そして実行してjpgファイルが作成できました。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/62115e0f-e3a9-2631-bc6d-df089c36bc59.png)

まさかの失敗。。。
一応バイナリエディタで開いてみます。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/ca5b0099-3d24-2183-b379-9145bb8eb90a.png)

まさかの画像ファイル開けないけど中に書いてあるパターン。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17681/a994d771-fb2f-6cb4-56be-cdd7e7d2152f.png)