ångstromCTF 2021 writeup[Crypto]

問題ファイルや私が書いたソルバは (https://github.com/Vegctrp/CTFs/tree/master/angstrom2021/crypto)にあります。

Relatively Simple Algorithm(40pts, 725solves)

RSAの復号を計算するだけです。

actf{old_but_still_good_well_at_least_until_quantum_computing}

Exclusive Cipher(40pts, 499solves)

flagフォーマットのactf{がメッセージのどこかに対応しているはずなので、actf{の位置で全探索します。

actf{who_needs_aes_when_you_have_xor}

Keysar v2(40pts, 569solves)

コードを読むに単一換字式暗号なので、気合で対応表を作りました。アポストロフィは保存されているので、暗号文で頻出する"b'r"が"I'm"では？というようにアポストロフィ周りを気合で読みました。

actf{keyedcaesarmorelikesubstitution}

sosig(70pts, 504solves)

RSA暗号。eがやたらデカいのでwiener's attackか、それが無理ならBoneh-Durfee attackかという気持ちになります。wiener's attackが通ったので勝ちです。

actf{d0ggy!!!111!1}

Home Rolled Crypto(70pts, 173solves)

自作ブロック暗号。平文のある位置のbitcとkeyの対応する3bitk1,k2,k3に対して、((((((c&k1)^k1)&k2)^k2)&k3)^k3)を暗号化結果の対応するbitにしています。

ここで真理値表を作るなりしてc,kとf(c,k)=((c&k)^k)の関係を見ると、
$$
f(c,k) =
\begin{cases}
1 & ((c,k)=(0,1)) \\
0 & (\text{otherwise})
\end{cases}
$$
となります。したがって、g(c,k1,k2,k3)=((((((c&k1)^k1)&k2)^k2)&k3)^k3)としてgの性質を頑張って調べると、
$$
g(c,k_1,k_2,k_3) =
\begin{cases}
1-c & (k_1=k_2=k_3=0) \\
1 & ((k_1,k_2,k_3)=(0,0,1) \text{or} (1,0,1)) \\
0 & (\text{otherwise})
\end{cases}
$$
となることがわかります。

次に、各bitに対応する$(k_1,k_2,k_3)$を決定します。ただし、
$$
\begin{cases}
k_1=k_2=k_3=0 \\
\text{otherwise}
\end{cases}
$$
のどちらかを特定すればよいです。これは、"00"*16と"ff"*16を入力したときの出力結果を見て、2数の出力結果のうちbitが異なっている部分のみが$k_1=k_2=k_3=0$であるとわかります。

ここまでわかれば、あとはサーバーから与えられる任意の文に対して正しい暗号化をおこなえるはずです。正しい暗号化結果を返すとflagを得られます。

actf{no_bit_shuffling_is_trivial}

Follow the Currents(70pts, 270solves)

keystream()で使われているkeyは16bitなので、全探索できます。

actf{low_entropy_keystream}

I'm so Random(100pts, 237solves)

二つのGeneratorの出力の積を2回まで得ることができます。1回目の各Generatorの出力をa1,a2とすると、2回目の出力は(a1*a1%10**12)//10000, (a2*a2%10**12)//10000となります。

a1は$10^7\sim 10^8$の間の値であることがわかっているので、全探索できます。

actf{middle_square_method_more_like_middle_fail_method}

Substitution(130pts, 135solves)

flagの各文字をasciiに変換したリスト${k_1,\ldots,k_n}$を持っていて、入力value($v$とします)に対して$(v^{n-1}k_1 + v^{n-2}k_2 +\cdots+k_n)%691$を返すので${k_1,\ldots,k_n}$を求める、という問題です。$f(v)=(v^{n-1}k_1 + v^{n-2}k_2 +\cdots+k_n)%691$とすると、任意の$v$に対する$f(v)$を得られるので、これを行列の式で表すと以下のようになります。剰余の691は省略しています。

$$
\begin{bmatrix}
1 & 0 & 0 & \cdots & 0 \\
1 & 1 & 1 & \cdots & 1 \\
1 & 2 & 4 & \cdots & 2^{n-1} \\
1 & 3 & 9 & \cdots & 3^{n-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & 690 & 690^2 & \cdots & 690^{n-1} \\
\end{bmatrix}
\begin{bmatrix}
k_n \\
k_{n-1} \\
\vdots \\
k_1
\end{bmatrix}=
\begin{bmatrix}
f(0) \\
f(1) \\
f(2) \\
f(3) \\
\vdots \\
f(690)
\end{bmatrix}
$$

この状態で、$$\begin{bmatrix}
k_n \\
k_{n-1} \\
\vdots \\
k_1
\end{bmatrix}$$を得ることを考えます。ここでflagの長さ$n$は不明ですが、690以下であるはずなので全探索します。$n$を固定して、
$$
\left[
\begin{array}{ccccc|c}
1 & 0 & 0 & \cdots & 0 & f(0)\\
1 & 1 & 1 & \cdots & 1 & f(1)\\
1 & 2 & 4 & \cdots & 2^{n-1} & f(2)\\
1 & 3 & 9 & \cdots & 3^{n-1} & f(3)\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
1 & n-1 & (n-1)^2 & \cdots & (n-1)^{n-1} & f(n-1)\\
\end{array}\right]
$$
について掃き出し法か何かで左側の$n\times n$行列を単位行列にしてやれば、
$$
\left[
\begin{array}{ccccc|c}
1 & 0 & 0 & \cdots & 0 & k_n\\
0 & 1 & 0 & \cdots & 0 & k_{n-1}\\
0 & 0 & 1 & \cdots & 0 & k_{n-2}\\
0 & 0 & 0 & \cdots & 0 & k_{n-3}\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & 0 & \cdots & 1 & k_1\\
\end{array}\right]
$$
となり${k_1,\ldots,k_n}$が得られるはずです。さらにflagに対応する正しい${k_1,\ldots,k_n}$は各$k_i$がasciiのそれっぽい値になっているはずなので、これも条件に入れて全探索します。するとflagが見つかるはずです。

actf{polynomials_20a829322766642530cf69}

Oracle of Blair(160pts, 136solves)

任意の入力に対してAES-128-CBCで復号した結果を得ることができます。入力を任意にできる上にCBCの復号なので、b"\x00"*16をふんだんに使うことで実質AES-ECBの復号結果を任意に得られるような気がしてきます。たとえば、

| b"\x00"*16 | x | b"\x00"*16 | y |を入力すると、返ってくる復号結果は
| ? | AES-decrypt(x, key) | ? | AES-decrypt(y,key) |
となっており、x,yそれぞれに対してAESの復号結果を得ることができます。

よって、正しいflagをactf{xxxxx}とすると、

| b"\x00"*16 | b"\x00"*10 + b"actf{x" | b"xxxx}" + b"\x00"*11 | b"\x00"*16 | b"\x00"*10 + b"actf{?" |
のように入力し、最後の?の部分を変えていって、ブロックの復号結果が一致するかどうかを見ることで正しいflagの6文字目を当てることができます。

これを繰り返すことでflagの文字を前から順にすべて特定することができます。

actf{cbc_more_like_ecb_c}