東京工業大学 ロボット技術研究会

東京工業大学の公認サークル「ロボット技術研究会」のブログです。 当サークルの日々の活動の様子を皆さんにお伝えしていきます。たくさんの人に気軽に読んでもらえると嬉しいです。
新歓特設ページ        ロボット技術研究会 HP        ロボット技術研究会 twitter公式アカウント

2015年09月

「ロボット技術研究会」通称「ロ技研」は、その名前の通りロボットの制作や研究はもとより、電子工作や機械工作、プログラミングなどの幅広い分野にわたるものつくり活動を行っています。

カテゴリ一覧: loading

MMA CTF 1st 2015 writeup

MMACTFというCTFに、3人 (@ymduu, @yosupot, @___zoj) で出ていました。
結果は44位 (国内 8位)でした。

Pattern Lock(1)

絶対既に考えてる人がいるだろうなあと思ってググったらやはり既に考えてる人が居た -終-

Pattern Lock(2)

ちょっと特殊な巡回セールスマンなのでbitDP。O(N^3 * 2^N)(N:点の数)ぐらいだったと思う。終了。

Smart Cipher System(1/2)

暗号の値(2桁)と1文字が一対一対応してるので自明、ABCDE……みたいな文字列を投げて対応を見て復号スクリプトを書いた。

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)$
みたいな感じでハッシュが先頭の文字から順番に計算されている

これが求める値(忘れた、なんだっけ)になるような文字列を作れという問題

これは、適当に半分全列挙することで(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は神)


Nagoya Castle
名古屋城画像が与えられる。tEXtチャンクも無く、 strings -aしても特に手がかりが見つからない。困る。

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 だと分かる。
ここを参考に解読。
 

DistanceFieldを用いた2Dサンドボックスゲーム

突然ですが皆さんMinecraftは好きですか?ニックさんです。僕はMinecraftは大好きです。
圧倒的な自由度や無限に生成されるゲームフィールド、何でも破壊・設置可能なシステム、
Minecraftが世界中のゲームプレイヤーやゲームエンジニアに与えた影響はすさまじい物があるでしょう。
ちなみにMinecraftについてのレビュー記事が4gamerに良くまとまっています。

結局のところ「Minecraft」とは何だったのか?(リンク先:4gamer.net)


今日のブログの内容は、Minecraftみたいなサンドボックス型ゲームいいよね!ってことで僕が作っている
サンドボックス型の2Dオープンワールドゲームのご紹介をします。
特に今日はレンダリング回りについて話そうと思います。


いくらMinecraftのようなゲームが良いよね!って言っても同じように作ればただのパクりです。
ただのパクリも面白いんですが、Minecraftライクなゲームは世の中に溢れているので、
どうせならもっと違ったことがやりたいなぁ~と思っていたところに15さはら君に教えてもらった技術が
記事タイトルにもあるDistanceFieldです。(さはら君ありがとう)

DistanceFieldとは剛体までの最短距離を敷き詰めたスカラー値のグリッドのことで、
これとバイリニア補間を併用すれ線形近似をした連続空間を構成可能です。
まずはその利用例を見てみましょう。
DistanceField

左の図は壁までの距離を0~1のグレイスケールで表示した図です。グリッド上なのでカクカクしてますね。
右の図は左の図をフラグメントシェーダーを用いてバイリニア補間したものです。
結構滑らかにつながっている事がお分かりでしょうか?

またDistanceFieldは壁までの距離や法線ベクトルも高速に取得できます。
当たり判定も比較的簡単に少ない計算量で行えるので流体のシミュレーションなどでよく使われるそうです。
DistanceField2

もちろんゲームにも使われていて、例をとしてUnrealEngineでのアンビエントオクルージョンや、
G-Games制作のThe Tomorrow Childrenでも利用されているようです。


さて、今回のゲームは2Dで見下ろし型のサンドボックス型ゲームです。
DistanceFieldは有用な技術ですが、単一種類のオブジェクトの距離しか扱えないため、
Minecraftのように「岩」「土」「レンガ」などの種類を持たせることが出来ません。
そこで私が勝手に考えたのがColoredDistanceFieldという技術です。
ColoredDistanceFieldは単純で、グリッドに浮動小数点である距離値の他に、
オブジェクト情報である「Color」として整数型の値も埋め込みます。
ColoredDistanceField

この図の一番右の画像がColoredDistanceFieldを利用して描画された図です。
三色の色情報を埋め込んで、その境界付近は適当にグリッド間で線形補間することで合成しています。
これによって距離情報を埋め込んだ浮動小数点テクスチャと種類情報を埋め込んだ整数型テクスチャを
フラグメントシェーダに渡すだけでシェーダー側からたくさんの種類のオブジェクトを描き分けることが出来ます。
やったぜ。


以上の技術を使って描画されたゲーム画面がこちらです。
GameField

実際はテクスチャに埋め込んだ離散化された情報だけを持っているのですが、
線形補間でもそれっぽく見えるものですね。


ちなみにこの画面を出力するまでの描画パスは次のとおりです。
RenderGameField

ColoredDistanceFieldの情報を使ってベースカラーマップやら法線マップやらを先に出力して、
そこからシャドウマップやらフォンシェーディングやらで遅延レンダリングしています。
DistanceFieldを使うと嬉しいのが、距離情報が簡単に取れるのでアンビエントオクルージョンもすぐ出来ます。
嬉しい!


そしてDistanceFieldの特徴として、オブジェクトを変形するときは変形範囲のみ
グリッドの値を書き換えれば良いのでゲーム中フィールドの破壊や創造も簡単です。

anime
もりもり岩肌を削れていますね。動的に影やシェーディングがなされているとこにも注目!


現状製作出来ているものはこんな感じです。
来週9/13(日)に開催されるGAME^3というイベントに出展するので興味がある方は是非見に来てください。
Bitbucketにもソースを上げているので中身が気になる方はこちらもどうぞ。

工大祭に間に合うと良いですね。あと研究も進めば良いですね。
ギャラリー
  • 自作キーボードを作ろうver1.0
  • 自作キーボードを作ろうver1.0
  • 自作キーボードを作ろうver1.0
  • 自作キーボードを作ろうver1.0
  • 第14回ROBO-ONE Light 結果報告
  • ロボット技術研究会紹介
  • ロボット技術研究会紹介
  • rogy2016冬合宿 in 戸狩
  • rogyサバゲ:†革命†をもっと
記事検索
最新コメント