こんにちは。就職してからCTFやれてなかったんでつい最近やれてなかった残りのCpawCTFの問題を全部解きました。
今回はそれらの問題に対する簡単なWriteUpをまとめてみようと思います。
とは言っても、今回の問題はLevel3ということもあり、しっかりリサーチをしないとなかなか難しい問題ばかりです。
問題に挑む際は、できる限り様々なキーワードで検索をかけてみるか、多角的な視点をもって解法することをお勧めします。
#実行環境
Windows10
前提条件はLevel1&Level2のWriteUpで記載した状態のものと同じとして行います。
前回のWriteUp
#この記事を見る前に
今回の問題も、是非とも自分の手でまず解いてみてください。自分で解くことにより、自分にノウハウが蓄積できますし、また違う発見ができると思いますよ。
#WriteUp
Level3
Q23.[Reversing]またやらかした！
何かしらの実行ファイルが与えられます。
問題文を見るに恐らくprintfを書いていないファイルのようです。今回も同じようにIDAを使ってフラグを入手してみようと思います。
そう思ったんですが、この問題を解いた当時の自分ではアセンブリの命令文がうまく理解できず、より明確に答えへと近づけるツールはないかと思いIDAを諦め別のリバースエンジニアリングツールであるGhidraを用いて解法を行うことにしました。
（もちろん、IDAが悪いわけではないです。IDAのみでも十分解答にはたどり着けますのでご安心ください。）
Ghidraのインストール方法はこちらから
さて、一通りGhidraをインストール完了したらJDKを読み込ませてGhidraを起動します。
起動したらNon-Shared Projectにチェックを入れて新しくプロジェクトを開きます。
正常にプロジェクトが作成できたら以下のような画面が表示されると思います。
画面内の[File]を選択し、Inport Fileを選択し、与えられた実行ファイルをインポートします。
インポートが成功したら、その実行ファイルをダブルクリックすると、このような画面が表示されます。ここでアセンブリやデコンパイル結果を参照することができます。(Ghidra内のCodeBrowserという機能です。)
とその前に、恐らく以下のようなポップアップが表示されていると思うので、[Yes]を選択します。ここで実行ファイルの様々な情報を表示することができます。今回はチェックボックスをそのままに[Analyze]を選択してください。
フォーマット情報や何でコンパイルされたかも表示されます。すごいなあNSAは。
前の画面に戻ると思うので、そこのSymbol Treeというウィンドウに注目してください。プログラムが何を読み込んでいるのか、プログラム内の関数がまとめられていると思います。この中の[Functions]より、main(おそらくこのプログラムの核)を選択してみましょう。
すると左のDecompilerウィンドウに生成された疑似コードが表示されていると思います。(表示されるのは先ほどAnalyzeオプションで指定されていたDecompiler Switch Analysisのおかげです。)
なるほど、なんだかC言語っぽいですね。とりあえず書き起こしてみます。
undefined4 main(void)
{
int iVar1;
uint *puVar2;
int local_84;
uint local_7c [14];
uint local_44 [14];
local_7c[0] = 0x7a;←おそらく16進数？
local_7c[1] = 0x69;
local_7c[2] = 0x78;
local_7c[3] = 0x6e;
local_7c[4] = 0x62;
local_7c[5] = 0x6f;
local_7c[6] = 0x7c;
local_7c[7] = 0x6b;
local_7c[8] = 0x77;
local_7c[9] = 0x78;
local_7c[10] = 0x74;
local_7c[11] = 0x38;
local_7c[12] = 0x38;
local_7c[13] = 100;
iVar1 = 0xe;←16進数で14
puVar2 = local_44;
while (iVar1 != 0) {
iVar1 = iVar1 + -1;
*puVar2 = 0;
puVar2 = puVar2 + 1;
}
local_84 = 0;
while (local_84 < 0xe) {
local_44[local_84] = local_7c[local_84] ^ 0x19;←代入されている値と0x19との排他的論理和(XOR)をとっている(^ がxorを計算する演算子)
local_84 = local_84 + 1;
}
return 0;
}
どうやら配列内の数値を排他的論理和をとって計算した結果を別の配列に入れているようです。
printfがないようなので、以下のようにいろいろと書き直して実装してみます。
#include <stdio.h>
int main(void){
int var;
unsigned int *var1;
int local_84 = 0;
unsigned int local_7c[14];
unsigned int local_44[14];
local_7c[0]=0x7a;
local_7c[1]=0x69;
local_7c[2]=0x78;
local_7c[3]=0x6e;
local_7c[4]=0x62;
local_7c[5]=0x6f;
local_7c[6]=0x7c;
local_7c[7]=0x6b;
local_7c[8]=0x77;
local_7c[9]=0x78;
local_7c[10]=0x74;
local_7c[11]=0x38;
local_7c[12]=0x38;
local_7c[13]=100;
var1 = local_44;
var=14;
while(var!=0){
var = var + -1;
*var1=0;
var1=var1+1;
}
local_84 = 0;
while (local_84 < 0xe) {
local_44[local_84] = local_7c[local_84] ^ 0x19;
local_84 = local_84 + 1;
}
//追加
for(int i =0;i<14;i++){
printf("%c", local_44[i]);
}
return 0;
}
以上のコードを実行するとflagが入手できます。
おまけ
バーナム暗号
Q24.[Web]Baby's SQLi - Stage 2-
どうもBaby's SQLiの続きの問題のようです。
問題が完全に解けてはいないようなので再度select文を打ち込んでみると、
なんだか二番目のテーブルに怪しげなURLが見えますね、ここがステージ2になるようなのでこのサイトに飛んでみましょう。すると、
なにやらログインフォームの向こうにflagがあるようです。ただ、パスワードなんて知りませんし、皆目見当がつきません。
そこで思い出してほしいのですが、前の問題ではSQL文が打ち込めるフォームであったこと。
SQLインジェクションには多数の攻撃方法があったこと。
これらの情報をもとに、導き出せるのは、、、
**「パスワード入力部分に何かしらのSQL文を打ち込むことによりflagが取得できるのでは?」**という思考です。
適当に「SQL パスワード」とか調べてみると、いろいろと情報が出てくると思います。
そこで、パスワード入力部分に、以下のSQL文を入力すると、flagが獲得できます。
' OR 1=1--
このSQL文、恐ろしいことに以下の意味があります。
- 「'」
- ひとつ前の「'」と対となり文字列定数を終わらせる
- OR 1=1
- テーブルの値に関係なく検索条件を真とさせる
- 「--」 それ以降の内容をコメントとして無視させる
参考サイト:https://www.ipa.go.jp/security/awareness/vendor/programmingv2/contents/502.html
※現実世界でこんなことやったら本当に犯罪になるので絶対にやめましょう。まあないとは思いますが、このSQL文打ってログインできるようなサイトが現実にあった場合はサイトの管理者にこっそり教えてあげてください。
Q26.[PPC]Remainder theorem
複数の合同式の問題です。合同式とは割り算のあまりのみに注目した等式で、例えば8と2はどちらも3で割った余りが2です。これを合同式ではこう表します。
8 ≡ 2 (mod 3)
この合同式は8と2は3で割った余りのみに注目すれば同じ、という意味です。
問題文を見てみましょう。
x ≡ 32134 (mod 1584891)
x ≡ 193127 (mod 3438478)
問題文を見るに、
①32134とxは1584891で割った余りが等しい
②193127とxは3438478で割った余りが等しい
この二つの条件を満たすxを見つけていけばよいわけです。
プログラム的に書くとこんな感じですね。
x%1584891 == 32134%1584891 && x%3438478 == 193127%3438478
この条件式を用いてプログラムを記述してみましょう。(大体xの桁数が大きくなるのは想像できるので、スタートを大きめにしておくと実行時間も少しだけ短縮できると思います。)
#include<stdio.h>
int main(){
long long int x;
for(x=100000000;;x++){
if(x%1584891 == 32134%1584891 && x%3438478 == 193127%3438478){
printf("%lld",x);
break;
}
}
return 0;
}
これでflagが取得できます。
絶対もう少しスマートに解けると思います。(これしか解法思いつきませんでした...技術力がなさ過ぎて反省)
Q29.[Crypto] Common World
RSA暗号とは桁数の大きい合成数の素因数分解にかかる時間が非常に膨大である性質を利用した公開鍵暗号の一つです。
参考サイト
分かりやすく言うとサマーウォーズでcv.神木隆之介の主人公、小磯健二が暗算で解いてたやつです。
(**普通に考えて絶対に暗算で解ける問題ではないです。**鼻血だしてRSA暗号解読できるんだったら私なら喜んで鼻血を出しまくって世の中のシステムをめちゃくちゃにしているでしょう。主人公は多分この後亡くなったんだよね...)
問題文からは、RSA暗号の暗号化に使われた正整数e、巨大な素数の積n、暗号化された文cが与えられます。
また、ヒントから、もう一組e,n,cが与えられます。(cは異なる)
RSA暗号は一見すると無敵の暗号に見えますが、脆弱な作りにしてしまうとかなり簡単に復号されてしまいます。現にRSA暗号を作成する際はいくつか気を付けないことが存在したり、様々な攻撃方法があります。
参考サイト1
参考サイト2
これらのサイトを見たうえで改めて今回の問題を見てみると、今回のRSA暗号はnが同一のため、Common Modulus Attackという攻撃方法が使えることがわかります。
Common Modules Attackに関してはこのサイトさんがわかりやすく解説しています
今回は、こちらのサイトに記載されているコードを拝借してCommon modules Attackを行うことにします。
Pythonの実行環境が整っている方はそのままお使いのパソコンで解いても問題ありませんが、私はクソめんどくさがりなのでGoogleが公式に提供しているGoogle Colaboratoryを使用しました。Web上でPythonコードが実行できる優れものです。ライブラリのインポートもpipを使って行えますしかなり便利です。
Google Colaboratoryを開いたら[ファイル]→[ノートブックを新規作成]をクリックします。
すると新しく画面が表示されます。この画面の[コード]を押下しコードを記入していきます。
こちらのサイトのコードを実行したいのですが、gmpy2が標準で使えないため、ノートブックにgmpy2をインストールしようと思いましたが、エラーが出てしまいました。
いろいろと調べてこのサイトを見るに、どうも依存関係のライブラリがインストールできていないようなので、解決方法にかかれていたインストール文を記入して実行してみます。
インストールが正常終了したら再度gmpy2をpipインストールしてみます。今度はうまくいくはずです。
最後にこちらのサイトのコードを実行するとflagが入手できます。
import gmpy2,binascii
n = 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577
e1 = 13
e2 = 11
c1 = 14451037575679461333658489727928902053807202350950440400755535465672646289383249206721118279217195146247129636809289035793102103248547070620691905918862697416910065303500798664102685376006097589955370023822867897020714767877873664
c2 = 80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904
val = gmpy2.gcdext(e1,e2)
print("[+] gcd(e1,e2) : {}".format(val[0]))
print("[+] a:{}, b:{}".format(val[1],val[2]))
print("[+] e1*a + e2*b == gcd(e1,e2)? : {}".format((e1*val[1]+e2*val[2]) == val[0]))
if val[1] < 0:
a = -val[1]
b = val[2]
c1_inv = gmpy2.invert(c1,n)
c1a = pow(c1_inv, a, n)
c2b = pow(c2, b, n)
else:
a = val[1]
b = -val[2]
c2_inv = gmpy2.invert(c2,n)
c1a = pow(c1, a, n)
c2b = pow(c2_inv, b, n)
m = (c1a * c2b)%n
m,result = gmpy2.iroot(m,val[0])
print("[+] gmpy2.iroot(m,gcd(e1,e2)) : {}".format(result))
print("[+] m^e1(mod n) == c1? : {}".format(pow(m,e1,n) == c1))
print("[+] m^e2(mod n) == c2? : {}".format(pow(m,e2,n) == c2))
try:
flag = binascii.unhexlify(format(m, 'x')).decode()
except Exception as e:
flag = m
print("FLAG: {}".format(flag))
おまけ
復号した値をこちらにいれてみると...?
ポリュビオスの暗号表
余談
RSA暗号にもいろいろな脆弱性があります。現実世界では、RSA暗号方式のみが暗号化に使われるわけではなく、パディングを入れたりして用いられているようです。例:OAEP
終わりに
ここまで閲覧いただきありがとうございます。もしわかりにくいところがあればコメントでご指摘のほどよろしくお願いいたします。
さて、ここまでWriteUpを見た方ならわかると思いますが、これらの問題は割かし難しいです。
ただ、技術の進歩によってかなり柔軟に解くこともできることがわかりました。
月並みですが技術ってすごいですよね。特にセキュリティ技術とかは私たちの暮らしを陰ながら支えているんですもの。
ただ、こういった技術は正しい使い方をしないと簡単に悪用もできてしまうことも事実です。諸刃の剣と言ってもいい。
容易く技術を扱うことができれば、すごいディベロッパーになることもできますが、その技術を使って犯罪者になることもできます。
技術を使うのであればそれ相応に責任を負うことも必要である、ということをここまで見てくださった方には伝えたいです。ないとは思いますがここまでに紹介した技術を用いて犯罪行為等を行うのは絶対にやめましょう。
いやまあわかりますよ？正直私がCTF始めたのも**「合法的に犯罪ができる...!」とかいう危険人物の発想からですし、いろんなデータ扱ってるのとかまさしくハッカーごっこそのものですし気持ちはわかるんですよ。
でも犯罪だけは絶対しないでくださいね?**
技術は基本的に正しく使ってこそ真価を発揮するのですから。
私とのお約束です。
この記事で皆さんが「CTFおもしれ～！」って思ってくれたら人間冥利に尽きます。
それでは、またどこか次の記事でお会いしましょう。