MMACTFというCTFに、3人 (@ymduu, @yosupot, @___zoj) で出ていました。
結果は44位 (国内 8位)でした。
Pattern Lock(1)
絶対既に考えてる人がいるだろうなあと思ってググったらやはり既に考えてる人が居た -終-
Pattern Lock(2)
ちょっと特殊な巡回セールスマンなのでbitDP。O(N^3 * 2^N)(N:点の数)ぐらいだったと思う。終了。
How to use?
ちょっとググるとdumpbin.exeで関数の正しい呼び出すときの名前(？)がわかるんやでみたいな記事を発見したので試す。 dumpbin.exe /exports howtouse.dll。
試すと"?fnhowtouse@@YAHH@Z"で呼び出せばいいということがわかるので呼び出す。
あとは関数を呼び出して色々試したらnを引数として与えるとflagのn番目の文字のアスキーコードを返す関数のような気がしてきたので、全部出力して文字に直したらflagになった。
stream...
無敵最強株シュミレーター ->https://gist.github.com/yosupo06/904cc5d9f914e8ac482b
結果は44位 (国内 8位)でした。
Pattern Lock(1)
絶対既に考えてる人がいるだろうなあと思ってググったらやはり既に考えてる人が居た -終-
Pattern Lock(2)
ちょっと特殊な巡回セールスマンなのでbitDP。O(N^3 * 2^N)(N:点の数)ぐらいだったと思う。終了。
Smart Cipher System(1/2)
暗号の値(2桁)と1文字が一対一対応してるので自明、ABCDE……みたいな文字列を投げて対応を見て復号スクリプトを書いた。
色々試すと連続する元の文二文字によって対応する暗号の値が変わる、最初の一つは特別(文字の長さと頭文字によって決まる？)ということがわかる。
最初の一つが謎だが、どうせMMA{hogehoge}なので気にしないことにした(爆)
ではどのような規則で変わっているのかということを知りたい気持ちになるが、二文字の暗号化後の値の差だったり一桁目の和(？)だったりで謎。
連続する2文字と暗号化後の値はどうやら一対一対応しているっぽいので、"a"+(英大文字/英小文字/0-9/{/}から二つとって並べたもの)を全部(64^2通り)サーバーに投げつけて結果を観察するスクリプトを書いた。
途中でサーバーに蹴らたりせんかなあと怯えながら待ってたら無事d["暗号の値"]="平文二文字"の辞書が完成したのでそれを使って復号スクリプトを書いた。
Pythonで得たhtmlをいじるいい経験になった(こなみ)
Smart Cipher System(3)
色々試すと連続する元の文二文字によって対応する暗号の値が変わる、最初の一つは特別(文字の長さと頭文字によって決まる？)ということがわかる。
最初の一つが謎だが、どうせMMA{hogehoge}なので気にしないことにした(爆)
ではどのような規則で変わっているのかということを知りたい気持ちになるが、二文字の暗号化後の値の差だったり一桁目の和(？)だったりで謎。
連続する2文字と暗号化後の値はどうやら一対一対応しているっぽいので、"a"+(英大文字/英小文字/0-9/{/}から二つとって並べたもの)を全部(64^2通り)サーバーに投げつけて結果を観察するスクリプトを書いた。
途中でサーバーに蹴らたりせんかなあと怯えながら待ってたら無事d["暗号の値"]="平文二文字"の辞書が完成したのでそれを使って復号スクリプトを書いた。
Pythonで得たhtmlをいじるいい経験になった(こなみ)
Smart Cipher System(4)
まず1個の場合で試すと、rotate(5)が行われていることがわかる
2個の場合で試すと、1文字目はrotate(5)、2文字目はrotate(1文字目のASCii)であることがわかる
なので、i文字目はrotate(i-1文字目のASCii)という予想が立つのだけど、文字数を増やすと崩壊する
aaaaaaaaaaとかから1文字変えて試したりすると、どうやら前述の規則でデコードした後、なんらかの規則でシャッフルされているものが出されているんだろうと思う
hgHVqSXXLoYRZuvxMEAtUMXBWxdtldQYzQsbOJNpvmgkmを入れると全部違う文字が出てくる(この文字列は適当にプログラムで作った)ので、それで45文字のときのシャッフル規則を見つけて、それがわかれば簡単にデコードできるので終了
Login as admin!
自明なBlind SQL問 使ったコードはこちら→（ここにコード貼ろうと思ったけど別問題のために使って上書きしてしまった）
Splitted
Partial Content な HTTP通信をしている pcap ファイルが与えられる。
Wireshark の Export Object をすると断片化された flag.zip が出てくる。
あとはヘッダの Content-Range 見ながら手作業で重ねる。
展開すると psd が出てきたので GIMP で開いて終了。
RPS
50回連続でじゃんけんで勝とうやみたいなの。
(1/2)^50を引き当てるのは無理なので、どうにかしたい
srand(/dev/random)がされているので、乱数予測は不可能に見える
ところがdisasすると/dev/randomを一回ローカル変数に積んで、名前を入力して、そしてsrandという順番で行われている
名前入力がgetsなので、ここでa*大量とか突っ込むと/dev/randomを保存していたはずの場所がaaaaに書き換えられる。
後はそれをシードにした乱数をバーーッって出力して温もりのある手打ちで終了
How to use?
$ file howtouse
howtouse: PE32 executable for MS Windows (DLL) (GUI) Intel 80386 32-bit
より DLL と分かる。
ファイルがdllだとわかったので読み込んで関数を実行してみる。が、関数のアドレスの取得に失敗する。謎。ちょっとググるとdumpbin.exeで関数の正しい呼び出すときの名前(？)がわかるんやでみたいな記事を発見したので試す。 dumpbin.exe /exports howtouse.dll。
試すと"?fnhowtouse@@YAHH@Z"で呼び出せばいいということがわかるので呼び出す。
あとは関数を呼び出して色々試したらnを引数として与えるとflagのn番目の文字のアスキーコードを返す関数のような気がしてきたので、全部出力して文字に直したらflagになった。
Signer and Verifier
RSA暗号に選択暗号文攻撃？をしろという問題
問題概要としては
$n$ と $e$ がわかっている
$ d ≡ e^{-1} $ として、
$ f(x) ≡ x^d % p $
を求める関数を考える(署名関数)
$X$ が与えられるので $f(X)$ を求めたい
$f(x)$ は $x=X$ 以外にだったら好きに使うことができる
という感じ
まず、$5^d$ と $7^d$ を求める
そして拡張ユーグリッドで $5^d A + 7^d B ≡ 1$ となる $A, B$ を求める
すると、$f(5X) ≡ 5^d X^d$ と $f(7X) ≡ 7^d X^d$ を求めれば
$A f(5X) + B f(7X) ≡ X^d$ となり、$X^d$ が求められる
Simple Hash
まずバイナリを読むと、どうやら文字列に対しローリングハッシュが行われていることがわかる
つまり
$hash(S[0..i]) = (577 \times hash(S[0..i-1]) + $ i文字目のASCiiコード $)\ \% \ (10^{15}+37)$
みたいな感じでハッシュが先頭の文字から順番に計算されている
$hash(S[0..i]) = (577 \times hash(S[0..i-1]) + $ i文字目のASCiiコード $)\ \% \ (10^{15}+37)$
みたいな感じでハッシュが先頭の文字から順番に計算されている
これが求める値(忘れた、なんだっけ)になるような文字列を作れという問題
これは、適当に半分全列挙することで(baby-step giant-stepに似てると感じたけども、なんか名前ついてるんだろうか) $O(\sqrt{Mod})$ で求められる、それでも結構つらかった
具体的な方法は以下
Step1: 適当な30文字列をたくさん作る。
Step2: 適当な30文字の文字列を1個作る( $B$ とする)
Step1で作った文字列のなかから1つ選び( $A$ とする)、$A+B$ という文字列を作ることを考える。
$hash(A+B)$ はいくつになるだろうか？
実は、$hash(A+B) ≡ 577^{30} hash(A) + hash(B)$ となる
よって、作りたい値をXとすれば、最初に作った文字列のなかに
$hash(A) ≡ X - hash(B)\ /\ (577^{30})$
なるAが存在すればよい。
このような文字列Aが存在するかは、Step1で作った文字列のハッシュについてのハッシュマップ(ゃゃこしぃ…)を作っておけばStep1で作った文字列すべてをまとめて定数時間で調べられる。
よって、最初のステップで文字列を $\theta(\sqrt{mod})$ 個ぐらい作っておけば $\theta(\sqrt{mod})$ 回ぐらいの試行で(出てくるハッシュが一様分布ならばという仮定がつくが、まあ結構一様感あるしOKでしょ)出てくると期待できる。
これで $O(\sqrt{mod})$ です。やったね
ちなみに出てきたのは
ちなみに出てきたのは
zmgxzdinfufkkcfdsxhrdvgyvfloyvJWPSGNENOQAWYAZEZGSKJIJDPCVAEW
Uploader
/<\?|php/を全て消去するアップローダがある。（正規表現はcase-sensitiveであることに注意）
PHPは <script language="PHP"> ~~ </script> というタグでも実行できるので、これで突破。適当にコマンド実行したら /flag というファイルが有ることがわかり cat して終わり。
stream...
バイナリが落ちてきて中身を見るとpcapっぽいのでWiresharkで見る。
application/x-mms-framed という Windows系のストリーミング通信であることが分かる。
Export Objectでデータを抽出できた。（Wiresharkは神）
バイナリファイルで WMV の Object ID の所までヘッダをtrimすると断片的なWMVが完成。
それを ffmpeg に投げたら動画が復元された（ffmpegは神）
名古屋城画像が与えられる。tEXtチャンクも無く、 strings -aしても特に手がかりが見つからない。困る。
stego write upとかで検索していたら「フィルターをかけたらflagが出てきた」みたいな記事が散見されたのでそれかなあと見当をつける。
もっと検索するとStegsolve.jarとかいうお便利ツールが見つかったのでそれで色々なフィルターを試す。
色々フィルターを試したらflagが出てくるものがあった。
stego write upとかで検索していたら「フィルターをかけたらflagが出てきた」みたいな記事が散見されたのでそれかなあと見当をつける。
もっと検索するとStegsolve.jarとかいうお便利ツールが見つかったのでそれで色々なフィルターを試す。
色々フィルターを試したらflagが出てくるものがあった。
Money Game
バイナリを読むと、srand(time(NULL))なので、全部の株価が予想できる
なので適当に動的計画法でそれなりの戦略を組んだら1/5ぐらいの確率でクリアできるプログラムができたので投げる。
その2はformat string attackだろうということは思ったが、面倒なので飛ばしてしまった
無敵最強株シュミレーター ->https://gist.github.com/yosupo06/904cc5d9f914e8ac482b
MQAAAA
Base64文字列を解読すると #@~^MQAAAA== Um.bwDR+1tKcJtH) Dtnm6VlTmhKDN|rd{K46EdmCObWU8rbjRIAAA==^#~@ という文字列が出てくる。
プログラムで使うダンプかなんかかなと思い、Githubで「MQAAAA」で検索。
出てきたの により VBScript.Encode だと分かる。
ここを参考に解読。
