Harekaze mini CTF Writeup

#1. はじめに
2020/12/26 10:00 JST～2020/12/27 10:00 JST で開催された「Harekase mini CTF」にチーム「N30Z30N」としてソロ参加しました。Welcome以外に3問を解き、604点37位でした。

#2. Writeup
## 2-0 Welcome(Misc, warmup)
>Harekaze mini CTF 2020へようこそ! フラグは HarekazeCTF{4nch0rs_4we1gh} です。

typoしないよう、コピペで入力しました。
**HarekazeCTF{4nch0rs_4we1gh}**

## 2-1 rsa(Crypto, easy)
>知床鈴: (((晴風の乗組員は連絡用に鍵ペアを作ることになったけど、秘密鍵を自分で持っておくのは怖いから、これも暗号化しちゃおう……)))

``` task.py
from Crypto.Util.number import getStrongPrime, getRandomRange

with open("flag", "rb") as f:
  flag = int.from_bytes(f.read(), "big")

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 65537
c1 = pow(flag, e, n)
c2 = pow(p + q, e, n)
c3 = pow(p - q, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c1=}")
print(f"{c2=}")
print(f"{c3=}")
```

```output.txt
n=133957491909745071464818932891535809774039075882486614948793786706389844163167535932401761676665761652470189326864929940531781069869721371517782821535706577114286987515166157005227505921885357696815641758531922874502352782124743577760141307924730988128098174961618373787528649748605481871055458498670887761203
e=65537
c1=35405298533157007859395141814145254094484385088710533905385734792407576252003080929963085838327711405177354982539867453717921912839308282313390558033140654288445877937672625603540090399691469218188262950682485682814224928528948502206046863184746747265896306678488587444125143233443450049838709221084210200357
c2=23394879596667385465597018769822552384439114548016006879565586102300995936951562766011707923675690015217418498865916391314367448706185724546566348496812451258316472754407976794025546555423254676274654957362894171995220230464953432393865332807738040967281350952790472772600745096787761443699676372681208295288
c3=54869102748428770635192859184579301467475982074831093316564134451063250935340131274147041633101346896954483059058671502582914428555153910133076778016989842641074276293354765141522703887273042367333036465503084165682591308676428523152462442280924054400997210800504726635778588407034149919869556306659386868798
```

$e$ は奇数なので、$c_2 + c_3 \equiv (p+q)^{e}+(p-q)^{e} \equiv 2p^{e} \equiv 0 \mod{p}$ なので、$GCD((c_2+c_3),N)$ を計算することで $p$ を算出することができます。あとは通常の復号処理をすればOKです。

```solve.py
from Crypto.Util.number import *
import gmpy2

n = 133957491909745071464818932891535809774039075882486614948793786706389844163167535932401761676665761652470189326864929940531781069869721371517782821535706577114286987515166157005227505921885357696815641758531922874502352782124743577760141307924730988128098174961618373787528649748605481871055458498670887761203
e = 65537
c1=35405298533157007859395141814145254094484385088710533905385734792407576252003080929963085838327711405177354982539867453717921912839308282313390558033140654288445877937672625603540090399691469218188262950682485682814224928528948502206046863184746747265896306678488587444125143233443450049838709221084210200357
c2 = 23394879596667385465597018769822552384439114548016006879565586102300995936951562766011707923675690015217418498865916391314367448706185724546566348496812451258316472754407976794025546555423254676274654957362894171995220230464953432393865332807738040967281350952790472772600745096787761443699676372681208295288
c3 = 54869102748428770635192859184579301467475982074831093316564134451063250935340131274147041633101346896954483059058671502582914428555153910133076778016989842641074276293354765141522703887273042367333036465503084165682591308676428523152462442280924054400997210800504726635778588407034149919869556306659386868798

p = gmpy2.gcd(c2 + c3, n)
q = n // p
phi = (p-1)*(q-1)
d = inverse(e, phi)
print(long_to_bytes(pow(c1, d, n)).decode())
```
**HarekazeCTF{RSA_m34n5_Rin_Shiretoko_Ango}**

## 2-2.QR (Crypto, easy)
>日本のCTFではQRコードに関連する問題がよく出題されます[要出典]

``` task.py
import qrcode

with open("flag", "r") as f:
  flag = f.read().strip()

qr = qrcode.QRCode(border=0)
qr.add_data(flag)
qr.make(fit=True)

matrix = qr.get_matrix()
matrix2 = [ [0 for _ in range(len(matrix) - 1) ] for _ in range(len(matrix) - 1)]

for y in range(len(matrix)-1):
  for x in range(len(matrix)-1):
    matrix2[y][x] = (matrix[y][x] + matrix[y+1][x] + matrix[y][x+1] + matrix[y+1][x+1]) % 4

print(matrix2)
```

```output.txt
[[3, 2, 2, 2, 2, 3, 2, 1, 1, 1, 2, 2, 1, 1, 2, 3, 3, 3, 3, 2, 1, 1, 2, 3, 2, 2, 3, 2, 2, 2, 2, 3],
 [2, 1, 2, 2, 1, 2, 2, 0, 1, 2, 2, 3, 3, 1, 0, 2, 0, 0, 3, 2, 2, 1, 1, 3, 2, 2, 2, 1, 2, 2, 1, 2],
 [2, 2, 0, 0, 2, 2, 2, 1, 2, 3, 3, 3, 3, 2, 2, 2, 2, 3, 3, 2, 2, 2, 3, 0, 2, 2, 2, 2, 0, 0, 2, 2],
 [2, 2, 0, 0, 2, 2, 2, 2, 3, 3, 3, 3, 2, 2, 3, 1, 1, 3, 3, 3, 2, 2, 0, 0, 2, 2, 2, 2, 0, 0, 2, 2],
 [2, 1, 2, 2, 1, 2, 2, 2, 0, 0, 2, 2, 3, 3, 2, 1, 2, 3, 3, 3, 2, 1, 2, 3, 2, 2, 2, 1, 2, 2, 1, 2],
 [3, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 2, 3, 3, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 2, 3],
 [2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 1, 1, 1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 1, 2, 2, 2, 2, 2, 2],
 [1, 0, 0, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 2, 2, 3, 3, 2, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 0, 1],
 [2, 1, 0, 1, 2, 2, 2, 3, 3, 2, 1, 2, 3, 2, 2, 2, 3, 3, 2, 2, 1, 2, 3, 2, 3, 3, 3, 3, 2, 2, 1, 1],
 [3, 3, 2, 2, 3, 3, 1, 1, 3, 3, 1, 2, 3, 1, 2, 3, 3, 0, 2, 1, 2, 3, 0, 3, 2, 2, 3, 2, 0, 1, 1, 0],
 [2, 3, 0, 0, 0, 3, 1, 0, 2, 2, 1, 3, 2, 1, 2, 1, 2, 0, 3, 3, 0, 3, 2, 2, 2, 2, 3, 2, 0, 0, 1, 1],
 [0, 2, 3, 2, 3, 3, 2, 2, 2, 1, 2, 3, 2, 3, 3, 1, 2, 0, 0, 0, 0, 3, 2, 1, 2, 3, 2, 2, 2, 1, 2, 3],
 [0, 2, 3, 2, 3, 3, 3, 3, 2, 2, 2, 1, 1, 2, 2, 2, 3, 3, 2, 2, 3, 0, 0, 3, 2, 2, 2, 2, 2, 2, 3, 3],
 [0, 2, 0, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 2, 3, 2, 1, 1, 2, 2, 3, 0, 3, 1, 1, 1, 0, 2, 0, 2],
 [1, 3, 0, 3, 2, 2, 2, 3, 3, 1, 1, 3, 0, 0, 2, 1, 2, 2, 2, 3, 3, 1, 1, 2, 3, 2, 0, 0, 0, 1, 2, 1],
 [3, 3, 3, 0, 3, 2, 1, 2, 3, 1, 0, 1, 3, 0, 3, 2, 3, 2, 1, 2, 3, 3, 1, 0, 1, 2, 2, 2, 1, 0, 1, 1],
 [3, 2, 2, 3, 0, 3, 2, 3, 3, 2, 2, 1, 2, 3, 2, 3, 3, 2, 1, 1, 3, 0, 3, 1, 1, 3, 0, 3, 1, 1, 2, 1],
 [3, 2, 2, 2, 2, 2, 3, 0, 2, 1, 3, 2, 1, 2, 2, 3, 3, 3, 2, 2, 0, 0, 0, 2, 2, 3, 2, 2, 2, 3, 2, 0],
 [0, 2, 1, 2, 1, 1, 3, 0, 2, 0, 1, 2, 2, 3, 3, 3, 0, 3, 2, 3, 0, 3, 2, 2, 3, 2, 1, 3, 3, 2, 2, 1],
 [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 3, 2, 1, 3, 2, 1, 2, 2, 2, 1, 1, 2, 2, 3, 3, 1, 0, 2, 3],
 [3, 3, 2, 1, 2, 3, 2, 2, 2, 3, 3, 2, 1, 1, 1, 0, 2, 3, 2, 1, 1, 3, 3, 2, 1, 2, 0, 2, 1, 1, 2, 0],
 [2, 2, 1, 0, 2, 3, 3, 3, 2, 3, 0, 3, 1, 0, 1, 1, 1, 2, 2, 1, 2, 0, 0, 3, 1, 1, 2, 1, 2, 3, 3, 3],
 [0, 2, 3, 2, 2, 2, 3, 2, 0, 2, 3, 1, 0, 1, 3, 2, 1, 2, 2, 2, 3, 3, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2],
 [2, 3, 0, 3, 1, 1, 2, 2, 1, 2, 2, 1, 2, 2, 3, 3, 2, 2, 2, 2, 3, 2, 0, 1, 3, 0, 0, 0, 2, 0, 1, 2],
 [2, 2, 2, 1, 0, 1, 1, 2, 2, 2, 2, 1, 3, 2, 2, 0, 3, 1, 1, 1, 2, 3, 1, 2, 3, 2, 2, 3, 3, 2, 2, 1],
 [2, 2, 2, 2, 2, 2, 1, 2, 3, 2, 1, 0, 1, 1, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 2, 3, 2, 1, 0],
 [3, 2, 2, 2, 2, 3, 2, 1, 2, 1, 0, 0, 1, 2, 3, 3, 2, 2, 1, 2, 3, 1, 1, 3, 2, 1, 1, 2, 2, 0, 0, 0],
 [2, 1, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 3, 0, 2, 1, 3, 0, 3, 1, 2, 3, 2, 2, 3, 2, 0, 0, 1],
 [2, 2, 0, 0, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 3, 0, 3, 2, 2, 2, 2, 1, 2, 3, 3, 3, 3, 3, 2, 1, 1],
 [2, 2, 0, 0, 2, 2, 2, 0, 2, 2, 0, 1, 2, 2, 3, 0, 3, 3, 2, 1, 2, 2, 1, 1, 2, 2, 1, 2, 3, 3, 2, 0],
 [2, 1, 2, 2, 1, 2, 2, 0, 2, 2, 0, 2, 3, 2, 3, 3, 2, 3, 2, 1, 3, 0, 2, 1, 3, 3, 1, 1, 2, 2, 1, 0],
 [3, 2, 2, 2, 2, 3, 2, 1, 2, 2, 1, 1, 2, 3, 3, 2, 3, 3, 1, 0, 2, 0, 3, 3, 3, 2, 1, 1, 3, 2, 0, 1]]
```
33 マス × 33 マスの 二次元バーコードに対し、黒 = 1、白 = 0 として、(自マス+右マス+下マス+右下マス) mod 4 を計算した 32 × 32 の行列に encode したデータが与えられます。
プログラムを書くのが面倒くさかったので（というのと、decode 結果の二次元バーコードを目視したかったので）、Excel 方眼紙（！）を使って解きました。
最初に、output.txt の中身を Excel のシート上展開します（「], [」を「\r\n」で置換し、先頭末尾の「[」「]」を削除した後 CSV 形式で保存して読み込みました）。
![QR_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/429434/512a72d0-d64e-358d-674e-e6fa38e77683.png)
入力用シートです。1 を入力すると黒く塗るよう条件付き書式を設定しました。
![QR_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/429434/dc1156c5-df13-1270-9959-72d9e94c5fc2.png)
入力用シートの値をもとに encode した結果を示す検証用シートです。output.txtの中身と一致するセルが黄色くなるよう条件付き書式を設定しました。
![QR_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/429434/75e17be4-06d0-268b-94d8-20e4422c9273.png)
以下、検証用シートの 32×32 マスが全て黄色くなるよう、入力用シートを描画（黒く塗りたいところに1を入力）します。最初に「縦 H1 ~ H7、横 A8 ~ H8」を処理（全部白なので何も入れない）、その次は「縦 I1 ~ I8、横 A9 ~ I9」・・・という具合に、処理済サイズを 8×8、9×9・・・となるよう入力を進めていきます。慣れてくるとサクサクできたので、まぁ結果オーライでしょう。
![QR_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/429434/9bd0b971-e656-61fd-10cf-7f56c7d9771d.png)

**HarekazeCTF{d0_y0u_7hink_qr_ch4113ng3_i5_r3411y_in_d3m4nd}**

## 2-3. Easy Flag Checker (Reversing, warmup)
>このバイナリに文字列を与えると、フラグであるかどうかチェックしてくれます。

chall というバイナリファイルが配られます。
まずは、ida freeで中身を確認しました。
![writeup_ida.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/429434/1253b84a-a211-d85e-a460-b2f5cc611e54.png)
angrで行けそうだったので丸投げしてしまいました。

```
Python 3.8.6 (default, Sep 25 2020, 09:36:53) 
[GCC 10.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import angr
>>> p = angr.Project("./chall")
>>> state = p.factory.entry_state()
>>> sim = p.factory.simulation_manager(state)
>>> sim.explore(find=(0x400000+0x1321,),avoid=(0x400000+0x133b,))
<SimulationManager with 1 found, 70 avoid>
>>> print(sim.found[0].posix.dumps(0))
b'HarekazeCTF{0rth0d0x_fl4g_ch3ck3r!}'
```
**HarekazeCTF{0rth0d0x_fl4g_ch3ck3r!}**

#3. おわりに
ほとんど食べ残してしまったので、持ち帰って「お腹をすかせてから」きっちり美味しく食べたいと思います。