# zer0pts CTF 2020 writeup

* **The English version is here:**
* https://hackmd.io/@hakatashi/BkG7zhfSU

## Overview

2020-03-07 00:00 - 2020-03-09 00:00 に48時間開催された zer0pts CTF 2020 にチームTSGのメンバーとして参加しました。結果は8847ptsで12位です。


凄まじい実力で近年頭角を現しつつあるチームzer0ptsによる初めてのCTFです。事前の宣言通り、「No boring guess」な最高のクオリティのCTFでした。ありがとうございます!

## ROR (Crypto, 260pts)

* 平文$m$を右に$i\;\left(0\leq i<len(m)\right)$bit回転シフトした値をRSAで暗号化した値が与えられる
* $N=2^{n_1}3^{n_2}7^{n_3},e$は不明

### Solution

* $N$は偶数なので、奇数を暗号化すると奇数に、偶数を暗号化すると偶数になる。

`zer0pts{0h_1t_l34ks_th3_l34st_s1gn1f1c4nt_b1t}`

{%gist hakatashi/fac3ce50f0e7febc4db7f5d7768246d9 %}

## nibelung (Crypto, 525pts)

* $F_p$ ($p$: 512bit) 上の6次一般線形群$GL_6(F_p)$上の演算で暗号化、復号化が定義される
* $p$は接続のたびにランダムな素数に設定される
* $U$を秘密鍵として$U\cdot X\cdot U^{-1}$で暗号化、$U^{-1}\cdot X\cdot U$で復号化
* 行列のすべての要素が256以下であるような任意の値$X$に対して暗号化・復号化を行うことができる
* 暗号化されたフラグが与えられる

### Solution

* 一般線形群は名前のとおり線形なので、36個ある各要素について単位ベクトルを暗号化して取得すれば線形合同方程式に帰着して解ける

`zer0pts{r1ng_h0m0m0rph1sm_1s_c00l}`

{%gist hakatashi/de69225d17617a0fd8c75c484d3ca6af %}

## diysig (Crypto, 394pts)

* RSAと、謎のハッシュ関数が実装されている
* 任意のデータを暗号化したデータとそのハッシュ値を得ることができる
* 任意のデータの復号後のデータのハッシュ値を得ることができる
* $N,e$は既知、$N$: 1024bit、$e=65537$
* ハッシュ関数は以下の通り

    def _hash(self, m):
        """ DIY Hash Function """
        H = 0xcafebabe
        M = m
        # Stage 1
        while M > 0:
            H = (((H << 5) + H) + (M & 0xFFFFFFFF)) & 0xFFFFFFFF
            M >>= 32
        # Stage 2
        M = H
        while M > 0:
            H = ((M & 0xFF) + (H << 6) + (H << 16) - H) & 0xFFFFFFFF
            M >>= 8
        # Stage 3
        H = H | 1 if m & 1 else H & 0xfffffffe
        return H

### Solution

* ハッシュ関数はなんかいろいろやってるが、一番やばいのは Stage 3 でハッシュ値のLSBを潰して$m$のLSBで塗りつぶしていること
* 署名の出力と合わせると任意のデータの復号後のデータの LSB 1bit が分かる
* →LSB Decryption Oracle Attack が適用可能

`zer0pts{n3v3r_r3v34l_7h3_LSB}`

{%gist hakatashi/0c30ac59b88927a452903f94d5a6f490 %}

サーバーに1024回TCPコネクションを張ったのでBANされないか心配でした (まあ)。

## dirty laundary (Crypto, 636pts)

* シャミアの秘密分散法とPaillier暗号の複合システム
* $F_p$上の2次多項式をランダムに生成し$x=1\sim5$に対応する$y$の値を生成する。shareは5つ全て与えられているので本来であれば直ちに復号できるはずだが$y$の値にノイズが加えられた上Paillier暗号により暗号化されているため復号できない。
* 演算中に導入される以下の係数はランダムに生成される。
* 秘密分散を生成する多項式の係数$a,b,c$および法$p$ (1024bit, cはフラグ)
$f(x)=ax^2+bx+c\bmod p$
* 秘密分散の値に加えられるノイズ$e_i$ (256bit)
$y_i=f(x_i)+e_i\:(x_i=1,2,3,4,5)$
* Paillier暗号の法$N_i$の素因数$p_i,q_i$ (1024bit, 512bit)
$N_i=p_iq_i\:(p_i\approx p+e_i)$
* Paillier暗号の暗号化係数$k_i$ (256bit)
$g_i=1+k_iN_i\bmod N_i^2$
* Paillier暗号の乱数$r_i$ (256bit)
$c_i=g_i^{y_i}r_i^{N_i}\bmod N_i^2$
* このうち$N_i,g_i,c_i$が与えられる

### Solution

よく見ると$p_i\approx p+e_i$であるところの $p$: 1024bit に対して $e_i$: 256bit とめちゃくちゃ小さい。すなわち5つの$N_i$の素因数$p_i$は上位75%が共通している。格子の匂いがする。

あいにくこのような場合に使える手法は記憶になかったが、がんばって検索すると[この論文](https://hal.archives-ouvertes.fr/hal-01288914/document)がヒットした (2010年の論文らしい。クール)

論文によれば、$q$のサイズが$\alpha$ビットで、$p$の上位$t$ビットが共通しているRSA公開鍵が$k$個与えられたとき、

$$t\geqq\frac{k}{k-1}\alpha$$

を満たす場合格子を用いて解読可能である。今回の問題では$t=768,\alpha=512,k=5$なので、きれいに条件を満たす。

論文を参考に、以下のような行ベクトルで構成される格子を考える。

$$
\mathcal{L}=\left[\begin{array}{ccccccccccccccc}
K & 0 & 0 & 0 & 0 & N_{2} & N_{3} & N_{4} & N_{5} & 0 & 0 & 0 & 0 & 0 & 0\\
0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & 0 & N_{3} & N_{4} & N_{5} & 0 & 0 & 0\\
0 & 0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & -N_{2} & 0 & 0 & N_{4} & N_{5} & 0\\
0 & 0 & 0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & -N_{2} & 0 & -N_{3} & 0 & N_{5}\\
0 & 0 & 0 & 0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & -N_{2} & 0 & -N_{3} & -N_{4}
\end{array}\right]
$$

ただし$n$を$N$のサイズとして$K=2^{n-t}$である。このとき最短ベクトルにおける基底の係数が$q_1,\cdots,q_5$となり、素因数分解可能となる。これはLLLを適用してSVPを解き、最短ベクトルの最初の5つの要素を見れば計算可能である。

これにより$N_i$の素因数を得た。ここからPaillier暗号が復号可能 ($k_i$は$g_i=1+k_iN_i$より直ちに得られる) なので、$y_i$を得られる。

$p_i=p+e_i+\delta_i\:(\delta_i<\text{approx 1000})$とおき、$f(x)$周辺の式を整理すると

$$
\begin{aligned}
f\left(1\right)-\delta_{1} &=y_{1}-p_{1}\bmod p\\
f\left(2\right)-\delta_{2} &=y_{2}-p_{2}\bmod p\\
f\left(3\right)-\delta_{3} &=y_{3}-p_{3}\bmod p\\
f\left(4\right)-\delta_{4} &=y_{4}-p_{4}\bmod p\\
f\left(5\right)-\delta_{5} &=y_{5}-p_{5}\bmod p\\
\end{aligned}
$$

となる。

ところで

$$
\begin{aligned}
f\left(1\right)-3f\left(2\right)+3f\left(3\right)-f\left(4\right)=&\left(a+b+c\right)-3\left(4a+2b+c\right)\\
&+3\left(9a+3b+c\right)-\left(16a+4b+c\right)\\
=&0
\end{aligned}
$$

なので、$d_i:=y_i-p_i$とおくと、

$$
d_1-3d_2+3d_3-d_4=kp-\delta_1+3\delta_2-3\delta_3+\delta_4\:(k\in\mathbb{Z})
$$

となり$p$の小さい倍数の良い近似値が得られる。なお実際には$k=1$であった。

また、

$$
\begin{aligned}
3f\left(1\right)-3f\left(2\right)+f\left(3\right)=&3\left(a+b+c\right)-3\left(4a+2b+c\right)\\
&+\left(9a+3b+c\right)\\
=&c
\end{aligned}
$$

より

$$
3d_1-3d_2+d_3\bmod p=c-3\delta_1+3\delta_2-\delta_3
$$

を上で計算した$p$の近似値を用いて計算すると、$c$の近似値

c = 20713161535193761558784128809506534938870667474516138291919014014508231236559472271196444472147718083977745751388526121905625505

を得る。これを文字列に直すと

"zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!\x19\xA1"

下のほうはエスパーして、フラグは

`zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!!}`

となった。

{%gist hakatashi/0fce3ea3e73c4ef1615108594ed46b2e %}