TokyoWesterns CTF 4th 2018 Write-up

[TokyoWesterns CTF 4th 2018](https://tokyowesterns.github.io/ctf2018/) に チーム [m1z0r3](https://ctftime.org/team/7694) として参加して、1015点で53位でした。

自分は以下の4問を解き、416点を入れました。

- **SimpleAuth** （55pt） - Warmup / Web
- **scs7** （112pt） - Warmup / Crypto
- **mondai.zip** （95pt） - Warmup / Misc
- **Revolutional Secure Angou** （154pt） - Crypto

忘れないうちに Write-up を書きます。

## SimpleAuth

問題文のURLにアクセスするとソースコードが見える

```php
if (!empty($_SERVER['QUERY_STRING'])) {
    $query = $_SERVER['QUERY_STRING'];
    $res = parse_str($query); // ココ
    if (!empty($res['action'])){
        $action = $res['action'];
    }
}
```

ここの `parse_str($query)` の処理が間違っており、 [PHP Manual](http://php.net/manual/ja/function.parse-str.php) を読むと、第二引数がない場合は **現在のスコープに勝手に変数をセットする** らしい。

というわけで `$hashed_password` をセットすれば良い。

```
/?action=auth&hashed_password=c019f6e5cd8aa0bbbcc6e994a54c757e
```

にアクセスすれば FLAG が降ってくる。

## scs7

`nc crypto.chal.ctf.westerns.tokyo 14791` をすると、暗号化された FLAG が送られ、その後メッセージを送信すると暗号化して返してくれる。

色々試した結果、以下のことがわかった。

- 暗号文は、メッセージをHexエンコードしたものを59進法に変換したものである。
- ただし、59進法で使われる 0-58 をどの記号に割り当てるかは毎回バラバラである。

したがって、はじめに 0-58 がどの記号に対応するか対応表を作ってしまえば、暗号化された FLAG を復号することができる。具体的には `chr(59)` から `chr(117)` までを試して、暗号文の最後の桁の文字を見ると、それが 0-58 の数字に対応する。

```python
#!/usr/bin/env python
import socket

HOST = 'crypto.chal.ctf.westerns.tokyo'
PORT = 14791

def sock(ip, port):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((ip, port))
    return s, s.makefile('rw', bufsize=0)

def read_until(f, delim='\n'):
    data = ''
    while not data.endswith(delim):
        data += f.read(1)
    return data

def main():
    print 'nc %s %s\n' % (HOST, PORT)
    s, f = sock(HOST, PORT)

    result = read_until(f).strip()
    print result
    encrypted_flag = result.split(': ')[1]
    print read_until(f).strip()

    table = {}
    for i in range(59, 118):
        print read_until(f, ': ').strip() + chr(i)
        s.send(chr(i) + '\n')
        result = read_until(f).strip()
        print result
        table[result[-1]] = i - 59

    flag = 0
    for i, s in enumerate(encrypted_flag[::-1]):
        flag += table[s] * (59 ** i)

    print
    print hex(flag)[2:-1].decode('hex')

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

## mondai.zip

`mondai.zip` が渡され、解凍すると中からまた Zip ファイル（パスワード付き）が出てきて、パスワードを解読して解凍するとまた Zip ファイルが出てきて… みたいな問題。

ちなみに、1番目のパスワードが一番難しかった… 他の人が2番目まで解いてくれたので残りをやった。

### 1番目のパスワード

ファイル名がそのままパスワード

### 2番目のパスワード

`capture.pcapng` を開くと、不自然なデータを持つ ICMP パケットが並んでおり、データサイズに着目するとパスワードがわかる

```bash
$ tshark -n -t e -r capture.pcapng -Y 'icmp and ip.dst == 192.168.11.5' -T fields -e data.len
```

```python
print(''.join([chr(i) for i in [87, 101, 49, 99, 111, 109, 101]]))
```

### 3番目のパスワード

`list.txt` がパスワードリストで、どれかが正解

```python
from zipfile import ZipFile

password_list = open('list.txt', 'r').read().split('\n')
with ZipFile('mondai.zip') as zf:
    for password in password_list:
        try:
            zf.extractall(pwd=password)
            print '+ Completed! Pass: ' + password
            break
        except:
            continue
```

### 4番目のパスワード

ファイル名が MD5 ハッシュ値で、元のメッセージがパスワード

### 5番目のパスワード

`README.txt` を見ると、 "password is too short" とのことなので総当たりを試す

解凍すると `secret.txt` が出てくるので、指示通り ( `TWCTF{(2)_(5)_(1)_(4)_(3)}` ) に FLAG を組み立てる

## Revolutional Secure Angou

:warning: **（私は数学弱者なので、以下は数学的に正しくない可能性が大いにあります。ご注意ください）**

$ q \times e \equiv 1  \pmod{P} $ より、次のように考えた。 


```math
qe = px + 1
```

```math
x = \frac{q}{p}e - \frac{1}{p} \approx \frac{q}{p}e \left(\because 0 \lt \frac{1}{p} \ll 1 \right)
```

ここで、 $p$ と $q$ は巨大な素数であり、 $\frac{q}{p}$ の値はそこまで大きくならないと仮定すると、 $x$ の値は $e$ と大幅には変わらない（ブルートフォース可能）と判断した。

また、

```math
qe = px + 1
```

```math
ne = p^2 x + p
```

```math
p^2 = \frac{ne - p}{x} \approx \frac{ne}{x} \left(\because ne \gg p \right)
```

となるので、$x$ を徐々に増加さながら、 $\frac{ne}{x}$ を超えない最大の平方数を計算し、その平方根を元の式に代入して成立するか確かめた。

```ruby
require 'openssl'

key = OpenSSL::PKey::RSA.new File.read('publickey.pem')
e, n = key.e.to_i, key.n.to_i

# num 以下の最大の平方数を求める
def search_square(num)
  ds = num.to_s.reverse.scan(/..|.$/).reverse.map(&:reverse)
  k, n = 0, 0
  ds.each do |d|
    k = (k.to_s + d.to_s).to_i
    j = 0
    j += 1 while ((n.to_s + j.to_s).to_i + 1) ** 2 <= k
    n = (n.to_s + j.to_s).to_i
  end
  n
end

2.upto(1000000) do |x|
  puts x if x % 1000 == 0
  p = search_square(n * e / x)
  q = n / p
  if p * (p * x + 1) == n * e
    puts "+ p: #{p}"
    puts "+ q: #{q}"
    break
  end
end

# rsatool.py を用いて、秘密鍵 (privatekey.pem) を生成する
#   $ python rsatool.py -f PEM -o privatekey.pem -p [p] -q [q]

key = OpenSSL::PKey::RSA.new File.read('privatekey.pem')
File.binwrite('flag', key.private_decrypt(File.binread('flag.encrypted')))
```