0CTF Writeup: oneTimePad2
Japanese Version
Task
oneTimePad1と同じように暗号化スクリプトoneTimePad2.pyとciphertxtが入ったzipファイルがもらえる。
今度は\(GF(2^{128})\)のブロック暗号システムのようだ。
\begin{align}
C_i &= M_i + R_i \\
\begin{bmatrix}
R_{i+1} \\
1
\end{bmatrix} &=
\begin{bmatrix}
A & B\\
0 & 1\\
\end{bmatrix}^{N_i}
\begin{bmatrix}
R_{i} \\
1
\end{bmatrix} \\
N_{i+1} &= N_i^2\\
\end{align}
\(C_1 \dots, C_5 , M_1, \dots, M_4, A, B \)が既知である。\(M_5\)にフラグがあるようだ。
秘密鍵は\(N_1\)なのでこれを解読したい。
解析
まず、行列の累乗を計算する。
\begin{align}
\begin{bmatrix}
A & B\\
0 & 1\\
\end{bmatrix}^{n} &=
\begin{bmatrix}
A^n & A^{n-1} B + A^{n-2} B + \dots + B \\
0 & 1
\end{bmatrix} \\
&=
\begin{bmatrix}
A^n & \frac{(A^{n} - 1)B}{A - 1}\\
0 & 1
\end{bmatrix}
\end{align}
したがって
\[
R_{2} = A^{N_1} R_{1} + \frac{(A^{N_1} - 1)B}{A - 1}
\]
これを\(A^{N_1}\)について解くと
\[
A^{N_1} = (R_2 + B (A - 1)^{-1})(R_1 + B(A-1)^{-1})^{-1}
\]
よって\(A^{N_1}\)の値は計算できる。
\(N_1\)を計算するのは離散対数問題といって一般の体では計算するのは難しいが、少なくとも\(GF(2^{128})\)なら離散対数は現実的な時間で計算できるようだ。
解法
pari/gpで離散対数を計算する処理までを行った。
gistc2a4481d5f18d35e913503664320a016
$ gp -q doit.gp x^123 + x^117 + x^116 + x^114 + x^113 + x^112 + x^110 + x^109 + x^108 + x^107 + x^104 + x^99 + x^98 + x^97 + x^95 + x^93 + x^91 + x^89 + x^87 + x^84 + x^83 + x^82 + x^81 + x^80 + x^78 + x^74 + x^69 + x^68 + x^66 + x^62 + x^57 + x^53 + x^52 + x^51 + x^45 + x^43 + x^42 + x^41 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^25 + x^22 + x^19 + x^18 + x^17 + x^15 + x^14 + x^13 + x^12 + x^10 + x^8 + x^5 + x^2 + 1 76716889654539547639031458229653027958
10秒くらい待つと離散対数が計算できたので元のプログラムを改変して復号した。
gistedf58b1bf3484af727d98a7ebda023ff
$ python exploit.py
['\r\xa8\xe9\xe8J\x99\xd2M\x0fx\x8cqn\xf9\xe9\x9c', '\xc4G\xc3\xcf\x12\xc7\x16 m\xee\x92\xb9\xceY\x1d\xc0', 'r-BF)\x18b\x11 \xec\xe6\x8a\xc6NI:', 'A\xea:p\xdd\x7f\xe2\xb1\xd1\x16\xacH\xf0\x8d\xbf+', '&\xbdc\x83O\xa5\xb4\xcbu\xe3\xc6\rIg`\x92', '\x1b\x91\xdf^^c\x1e\x8e\x9eP\xc9\xd8\x03P$\x9c']
['One-Time Pad is ', 'used here. You w', "on't know that t", 'he flag is flag{']
One-Time Pad is used here. You won't know that the flag is flag{LCG1sN3ver5aFe!!}.��Y���+�]j�
flag文字列が自分の解法とあまり一致していない気がするので離散対数をもとめずとも計算できるのかもしれない。
English Version
Task
In the provided zip file, there are an encryption script 'oneTimePad2.py' and 'ciphertext'.
In this time, the crypt system is built on \(GF(2^{128})\)
\begin{align}
C_i &= M_i + R_i \\
\begin{bmatrix}
R_{i+1} \\
1
\end{bmatrix} &=
\begin{bmatrix}
A & B\\
0 & 1\\
\end{bmatrix}^{N_i}
\begin{bmatrix}
R_{i} \\
1
\end{bmatrix} \\
N_{i+1} &= N_i^2\\
\end{align}
We know \(C_1 \dots, C_5, M_1, \dots, M_4, A, B \).
The flag must be in \(M_5\).
We want to detect the value of \(N_1\) in order to break this system.
Analysis
First, let's compute the matrix power.
\begin{align}
\begin{bmatrix}
A & B\\
0 & 1\\
\end{bmatrix}^{n} &=
\begin{bmatrix}
A^n & A^{n-1} B + A^{n-2} B + \dots + B \\
0 & 1
\end{bmatrix} \\
&=
\begin{bmatrix}
A^n & \frac{(A^{n} - 1)B}{A - 1}\\
0 & 1
\end{bmatrix}
\end{align}
Therefore,
\[
R_{2} = A^{N_1} R_{1} + \frac{(A^{N_1} - 1)B}{A - 1}
\]
By solving this equation for \(A^{N_1}\),
\[
A^{N_1} = (R_2 + B (A - 1)^{-1})(R_1 + B(A-1)^{-1})^{-1}
\]
Then, we can conpute the value of \(A^{N_1}\).
Task to compute the value of \(N_1\) from \(A^{N_1}\) is called 'discrete logarithm problem', which is known to be difficult for general fields.
Fortunately, in this field \(GF(2^{128})\), the discrete logarithm is computable in a reasonable time.
Solution
We compute the descrete logarithm with PARI/GP.
gistc2a4481d5f18d35e913503664320a016
$ gp -q doit.gp x^123 + x^117 + x^116 + x^114 + x^113 + x^112 + x^110 + x^109 + x^108 + x^107 + x^104 + x^99 + x^98 + x^97 + x^95 + x^93 + x^91 + x^89 + x^87 + x^84 + x^83 + x^82 + x^81 + x^80 + x^78 + x^74 + x^69 + x^68 + x^66 + x^62 + x^57 + x^53 + x^52 + x^51 + x^45 + x^43 + x^42 + x^41 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^25 + x^22 + x^19 + x^18 + x^17 + x^15 + x^14 + x^13 + x^12 + x^10 + x^8 + x^5 + x^2 + 1 76716889654539547639031458229653027958
It took around ten seconds before we have the discrete logarithm.
Then, we decrypted the cipher text with a modified version of the encryption program.
gistedf58b1bf3484af727d98a7ebda023ff
$ python exploit.py
['\r\xa8\xe9\xe8J\x99\xd2M\x0fx\x8cqn\xf9\xe9\x9c', '\xc4G\xc3\xcf\x12\xc7\x16 m\xee\x92\xb9\xceY\x1d\xc0', 'r-BF)\x18b\x11 \xec\xe6\x8a\xc6NI:', 'A\xea:p\xdd\x7f\xe2\xb1\xd1\x16\xacH\xf0\x8d\xbf+', '&\xbdc\x83O\xa5\xb4\xcbu\xe3\xc6\rIg`\x92', '\x1b\x91\xdf^^c\x1e\x8e\x9eP\xc9\xd8\x03P$\x9c']
['One-Time Pad is ', 'used here. You w', "on't know that t", 'he flag is flag{']
One-Time Pad is used here. You won't know that the flag is flag{LCG1sN3ver5aFe!!}.��Y���+�]j�
Now, we have the flag, but there may be another solution which does not require to compute discrete logarithms, since our solution seems to be different from what the flag suggests.
