SECCON CTF for Beginners writeup

# はじめに

自分はKUDoS(3位)というチームでcryptoを担当し、

* Noisy equations
* RSA Calc
* Encrypter

を解きました。

他の方がRSA Calcなどのwriteupは書くと思うので、取り急ぎ、EncrypterのWriteupだけ載せます。

## 調査1

http://encrypter.quals.beginners.seccon.jp/

が与えられます。

動作確認をしてみると、どうやら上の枠にBASE64エンコードしたものを入力すると、それに応じて同じくBASE64エンコーディングしたものが得られます。

ためしに`test_comment`をBASE64でエンコードしたものを入力してみます。
![スクリーンショット (9).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/5cb9e79c-d7de-f71c-fb1c-816bcd61ed57.png)

ちなみに、同じ入力でも、ボタンを押すたびに結果が変わります。

![スクリーンショット (10).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/6e1cbe22-708c-f277-f506-b48139f45260.png)

解読しようにも意味が分かりません。まあ、暗号文を解読なんて普通出来ませんし。

![スクリーンショット (11).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/9252bd0b-d073-e1b0-b0e3-3e154df486fe.png)


## 調査2

次は、内部でどういう暗号化が行われているか調べます。

ソースコードを見ると、以下の部分が。

```html:index.html
<script type="text/javascript">
document.querySelector('#exec').addEventListener('click', () => {
  fetch('/encrypt.php', {
    'method': 'POST',
    'headers': {
      'Content-Type': 'application/json',
    },
    'body': JSON.stringify({
      'mode': document.querySelector('input[name="mode"]:checked').value,
      'content': document.querySelector('#input').value
    })
  }).then(resp => resp.json())
  .then(obj => {
    if (obj.error) {
      document.querySelector('#error').innerText = obj.error;
      document.querySelector('#output').innerText = '';
    } else {
      document.querySelector('#error').innerText = '';
      document.querySelector('#output').innerText = obj.result;
    }
  });
});
    </script>
```

どうやら

http://encrypter.quals.beginners.seccon.jp/encrypter.php

にPOSTメソッドを送っているようです。この`php`ファイルが入手できれば…、といったところですが、残念ながらうまくいきません。

## 推測1

(ここからは若干推測して、結果論としてうまくいった感があります。)

まず、`test_comment`のように12byteを暗号化すると、最終的に`\x40\xc2 ... \xf9`という32byteが返ってきます(ここではすべてbase64でのエンコード、デコードは考えていません)。

他の長さの文字列でも試してみると、

* 0 ~ 15byteの入力 → 32byteの出力
* 16 ~ 31byteの入力 → 48byteの出力

...

ここからの推測のまとめとして、

* 入力が16の倍数でないなら、16の倍数になるように **パディング** して、謎の+16byte分追加して出力。
* 入力が16の倍数なら、謎の+16byte分追加して出力。

## 推測2

さて、今度は先ほどの`test_comment`を暗号化して得られた`QMI6kAjgYG2lfXR1JKRPKa4AiQPMYYNhvQ2WgOUAAfk=`(**BASE64デコードはしていないことに注意**)という情報を復号してみましょう。

OKと出て、復号された`test_comment`の情報は得られません。
![スクリーンショット (12).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/d7563863-e5a4-d449-34c0-4630dc4bdc7d.png)

この入力の末尾を何文字か消してみましょう。まずは0606506Dのエラー。

![スクリーンショット (13).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/98d3380c-a045-ce24-3892-2d92f29a89be.png)

さらに消すと06065064のエラー。 **これは1回だけです。**

![スクリーンショット (14).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/4b54acb4-cddf-8747-6086-14a3c2f216b1.png)

更に消すと、invalid content。
![スクリーンショット (15).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/a226aff8-a266-5b62-f9d6-06d491442057.png)

どうも1回しかでないエラーが怪しすぎるので、ググってみます。

![スクリーンショット (16).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/210de28d-3c0a-db7d-fd47-e5a9d80abcfc.png)

一番上を見てみると、`AES-256-CBC`の文字が。結論付けるのは早計ですが、おそらくAESの暗号利用モードで同じようなエラーが発生することがわかります。

これなら推測1のパディングについては説明がつきます。

## 疑問点

* AESのうち、本当にCBCなのか？
* 推測1で付与される16byteはなんなのか？
* 付与される16byteは末尾についてるの？それとも先頭？

1つめについては、残念ながらそうだと信じて進みましょう。無理ならまたここに戻ってきます。

2つめについては、まず考慮すべき点として、

*(調査1からわかるように)同じ平文の入力でも異なる暗号文の出力が返ってくる
*その異なる出力のいずれもが、復号の際にはエラーを吐かない。


つまり、この謎の16byteが異なる出力を発生させる原因かつ、さらに正しく復号できる要素であると推測します。推測ばかりですみません。

この謎の16byteについて、(AES-CBCであると仮定した場合)正体として考えられるのは2通り。

* 初期化ベクトル`iv`である。つまり、`php`側で行われているのはkeyは固定されていて、ランダム`iv`を生成、暗号文に付与。
* 暗号化鍵`key`である。つまり、`iv`は固定。`key`をランダム生成、暗号文に付与。

ですが、後者は基本的にないと思います。根拠として、key与えられたら誰でも簡単に他人のメッセージ解読できますからね。
基本的にAESのkeyは絶対にバラしてはいけません。こんなシンプルな理由です。


3つめについて。
[cryptohack](https://cryptohack.org/)というcrypto問題に特化した常設CTFがあるのですが、
この中のAES絡みの問題で軒並みivを先頭につけるものが多かった、という経験則から先頭と判断します。

以上、推測9割で構成された自分の結論として、

「AES-CBCモードで暗号化。付与されるのはivで、一般に先頭が多い。」

です。

## 解法

ここまでくればあとは簡単です。実装はそんなに簡単ではないですが。

"CTF CBC" でググってもらえればわかりますが、Padding Oracle AttackというCBCの脆弱性への攻撃があります。

これは、
* 任意の平文に対する暗号文を教えてくれる
* 任意の暗号文に対する平文は教えてくれないが、**復号の成功 / 失敗は教えてくれる**

という条件で威力を発揮します。

詳細は各自調べてください。とりあえず省略します。

## ソルバ

詳細はまた後で書きます。とりあえずソルバだけ。

```python:solver.py
import base64
import json
import requests
import sys

# 対象のURLにメッセージを送って、復号可能かを問い合わせている
# 成功ならOK
# 失敗なら06065064などが返ってくるはず。
def send(c):
    enc = base64.b64encode(c).decode()
    response = requests.post(
        'http://encrypter.quals.beginners.seccon.jp/encrypt.php',
        json.dumps({
	        "mode":"decrypt",
	        "content":enc
        }),
        headers={'Content-Type': 'application/json'})
    if 'result' in response.json():
        #print(response.json()['result'])
        return True
    else:
        #print(response.json()['error'])
        return False

# ここに、Encrypted　flagを押したときに得られる暗号文を書く
result = 'pNmwsjHdkHcxxzV9a+LqaWtmh0/648PE5GCp5ipO2+ZLWF4IcWYMBnnwoVVpHQEUishPiUycWTffU0zezr1AKg=='
result = base64.b64decode(result)

# 以下、先頭16byteに対するPadding Oracle Attackの実装
# この部分を
# iv = result[16:32]
# c_0 = result[32:48]
# などと増やしていくと、次の16byteの復号が可能。
iv = result[0:16]
c_0 = result[16:32]
assert (len(iv) == 16)
assert (len(c_0) == 16)

_list =  []
while (len(_list) < 16):
    offset = len(_list) + 1
    mid = b''
    for i in range(len(_list)):
        mid += (_list[i] ^ (i + 1) ^ offset).to_bytes(1, 'big')
    mid = mid[::-1]

    ans_mid = []
    for i in range(256):
        send_message = b'\x00' * (16 - offset) + (i).to_bytes(1, 'big') + mid + c_0
        assert(len(send_message) == 32)
        if i % 20 == 0:
            print("{} done.".format(i))
        if send(send_message):
            print(hex(i))
            ans_mid.append(i)
    if len(ans_mid) != 1:
        print("error")
        sys.exit()

    _list.append(ans_mid[0])
    print("list : {}".format(_list))

iv_check = b''
for i in range(len(_list)):
    iv_check += (_list[i] ^ (i + 1) ^ 0x10).to_bytes(1, 'big')
iv_check = iv_check[::-1]
assert(send(iv_check + c_0))
m = b''
for i in range(len(_list)):
    m += (iv_check[i] ^ 0x10 ^ iv[i]).to_bytes(1, 'big')
print(m)
```


`ctf4b{p4d0racle_1s_als0_u5eful_f0r_3ncrypt10n}`