CpawCTFでCTFの勉強をしていたのですが、ネット上にLevel3の解説が落ちていなかったのでここにまとめたいと思います。ここでは、自分の解き方を紹介するのでより効率の良い解き方があるかもしれません。
Q23.[Reversing]またやらかした！
今回の問題ではstringコマンドを使ってもフラグを見つけることはできません。そこでIDAを用いてmain関数で何を行っているか見てみましょう。
以上のアセンブリを読み解くと、スタック領域の14個の変数に対して19という値をxorしていることになります。これはバーナム暗号ですね。
元の値 19をxorしたあとの値
7A → 63 (c)
69 → 70 (p)
78 → 61 (a)
6E → 77 (w)
62 → 7B ({)
6F → 76 (v)
7C → 65 (e)
6B → 72 (r)
77 → 6E (n)
78 → 61 (a)
74 → 6D (m)
38 → 21 (!)
38 → 21 (!)
64 → 7D (})
実際に計算してみるとフラグをゲットすることができます。
Q24.[Web]Baby's SQLi - Stage 2-
level2のQ22の問題の続きです。Q22でデータベースを参照したときの2行目に問題ページのURLが記載されているのでそこから問題ページに飛びましょう。
問題ページにはユーザー名とパスワードを入力するフォームがあります。バックエンドでユーザー名とパスワードから認証処理をする仕組みになっていると予測できます。
バックエンドで以下のクエリ文を生成していると考えてみましょう。
string query = "SELECT * FROM user_table WHERE user_name='" + request.getParameter("user") + "'"
"AND password='" + request.getParameter("password") + "'"
今回の問題ではユーザー名は与えられているため、パスワードの入力のみとなります。もちろん、パスワードはわからないのでSQLiによりパスワードがわからなくても上記のSQL文が通るように考えてみます。以下の入力をパスワードフォームに与えてみました。
' OR '1'='1
では、この入力から完成されるクエリ文を見てみましょう。
SELECT * FROM user_table WHERE user_name='porisuteru' AND password='' OR '1'='1'
'1'='1'はTrueとなるので上記のSQL文は通ります。実際こちらの入力でフラグをゲットできました。
Q26.[PPC]Remainder theorem
1584891で割って32134余り、3438478で割って193127余る整数xを１つ出力すればよい問題となっています。
つまり、xを1584891で割って32134余る数でfor文を回して、その中で3438478で割って193127余る時にxを出力するプログラムを作ってみましょう。
#include <bits/stdc++.h>
using namespace std;
int main(){
for (long long i = 0; i < 1000000000; i++)
{
long long x = 1584891*i + 32134;
if(x % 3438478 == 193127){
cout << x << endl;
break;
}
}
return 0;
}
Q29.[Crypto] Common World
問題文で与えられている(e,N)はRSA暗号の公開鍵を表しています。
RSA暗号では、平文をm,暗号文をc,公開鍵を(e,N),秘密鍵をdとすると
\begin{align}
N &= pq\,(pとqは異なる素数)\\
c &= m^e\,(mod\,N)\\
d &= e^{-1}\,(mod\,(p-1)(q-1))\\
m &= c^d\,(mod\,N)\,(復号時)
\end{align}
上記の式から分かるように復号するにはp,qの値が必要です。しかし、攻撃者はNを与えられてもp,qを素因数分解を行い見つけるのに計算時間がかかります。この素因数分解の困難性が暗号の安全性を担保しています。
今回の問題では、e=11とe=13の場合について同様のNに対して平文を暗号化しています。つまり以下の式が成り立ちます。
\begin{align}
c_1 &= m^{11}\,(mod\,N)\\
c_2 &= m^{13}\,(mod\,N)\\
↓\\
\frac{c_2}{c_1} &= m^2\,(mod\,N)
\end{align}
与えられた2つの暗号文の割り算を実行し、その結果に対して平方根を求めればそれが平文となります。
多桁の計算となるので自力でプログラムを実装するか、既存のツールを使用しましょう。
私は、こちらのツールを利用させていただきました。
以下が解答となります。
\frac{c_2}{c_1} = 180040032052240663195289808096837316\\
m = \sqrt{\frac{c_2}{c_1}}=424311244315114354\\