リバースエンジニアリングチャレンジ過去問 2008 Level2
Level2の前に、Level1を解くのに使ったPythonスクリプトを公開しておく。
模範解答のほうはC言語だけど、ほとんど同じ。
# Level1 encryptedDataList = [0xB7, 0x9A, 0x93, 0x93, 0x90, 0xDF, 0xA8, 0x90, 0x8D, 0x93, 0x9B, 0xDE] decryptedString = '' for data in encryptedDataList: decryptedString += chr(data ^ 0xff) print(decryptedString)
それではLevel2。
公式の模範解答が、すごくトリッキーに思えたので自分なりの回答を。
といっても一年前の問題だし、ググレばもっといいものがあるのかも。
公式では、改変されたMD5のアルゴリズムを不定のまま、問題の実行体を部分的に利用して解いているが、実は簡単なアルゴリズム。
これだけ。
以下のスクリプト使ってBrute Forceで解いた。
# Level2 import hashlib targetHackedMd5DataList = [0x43, 0x2B, 0xF7, 0xF4, 0x49, 0x90, 0xA3, 0x75, 0x7F, 0xD6, 0xEE, 0x19, 0xB8, 0x78, 0x81, 0x51] def doHackedMd5(targetString): temp = [] for i in targetString: temp.append(chr(ord(i) ^ 0xff)) m = hashlib.md5() m.update(''.join(temp)) tempList = [] for i in m.digest(): tempList.append(ord(i) ^ 0x86) return tempList def doBruteForce(): startValue = 0x00 endValue = 0xff for n1 in range(startValue, endValue + 1): for n2 in range(startValue, endValue + 1): print('Progress: %02x %02x XX XX' % (n1, n2)) for n3 in range(startValue, endValue + 1): for n4 in range(startValue, endValue + 1): tryingString = '%c%c%c%c' % (n1, n2, n3, n4) hackedMd5DataList = doHackedMd5(tryingString) if hackedMd5DataList == targetHackedMd5DataList: print('Hit! %02x %02x %02x %02x' % (n1, n2, n3, n4)) return True return False doBruteForce()
最初、どうせコマンド引数なんだからASCII文字の範囲だろうと思っていたら、ヒットしなくて焦った。
デバッガを使って、適当な引数hogeとか付けて実行し、あとからメモリ上のhogeという文字列をBrute Forceで出てきた結果と置き換えると、うまく答えを得ることができた。
リバースエンジニアリングチャレンジ過去問 2008 Level1
今年もリバースエンジニアリングチャレンジに挑戦しようと思う。
去年は二問目でハマってしまってやめちゃったので、過去問とか解いて準備しよう。
何気に一問目だけならランキング載ってるんだけどなぁ。
Grand Central Dispatchが面白そうだったのでやってみた
Google Code Jam 2009の予選は、なぜか土曜日だと勘違いしていて、実際はもろに仕事中だったので参加できなかった、という言い訳。
さて、我が家でも発売日からSnow Leopardが導入された。
Snow LeopardといえばOpenCLが気になるところだけど、このMacBookにはGeforce積んでないのでまだOpenCLは試せない。
実はIONなATOMマシンを自作したので、いずれLinuxで試したい。
並列実行でもうひとつ実装されたのが、Grand Central Dispatch。
ASCII.jpの記事がとても分かりやすい例を挙げてくれている。
マルチコア時代の新機軸！ Snow LeopardのGCD
http://ascii.jp/elem/000/000/455/455786/
自分でも試したい、ということで円周率を計算してみた。
アルゴリズムはWikipediaに載っていたインドで発明された？方法を採用。
円周率 - Wikipedia
http://ja.wikipedia.org/wiki/%E5%86%86%E5%91%A8%E7%8E%87
14世紀インドの数学者・天文学者であるサンガマグラマのマドハヴァは次のような π の無限級数表示を見いだしている……
まずは比較するために、並列化していないコード。
include <stdio.h> #include <math.h> #include <sys/time.h> #define MAX 500*1000*1000 double getTimeSecond() { struct timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec + (double)tv.tv_usec * 1e-6; } int main() { struct timeval startTime, endTime; double pi = 0.0; double t1, t2; int n; t1 = getTimeSecond(); for (n = 0; n < MAX; ++n) { pi += pow(-1, n) * (1.0 / (2 * n + 1)); } pi *= 4; t2 = getTimeSecond(); printf("%f\t%f\n", pi, t2 - t1); return 0; }
これを三回ぐらい実行してみた。
| π | 秒 |
|---|---|
| 3.141593 | 24.381985 |
| 3.141593 | 24.190699 |
| 3.141593 | 24.135658 |
だいたい24秒ぐらい。
次に、GCDを使ったコード。
計算する範囲は同じだが、それを1000分割して並列化している。
include <stdio.h> #include <math.h> #include <sys/time.h> #include <dispatch/dispatch.h> #define MAX 500*1000*1000 #define DIV 1000 double getTimeSecond() { struct timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec + (double)tv.tv_usec * 1e-6; } int main() { dispatch_group_t g = dispatch_group_create(); dispatch_queue_t q = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0); double result[MAX / DIV]; struct timeval startTime, endTime; double t1, t2; t1 = getTimeSecond(); int i; for (i = 0; i < MAX / DIV; ++i) { dispatch_group_async(g, q, ^{ int j = i; double p = 0.0; int n; for (n = j * DIV; n < j + DIV; ++n) { p += pow(-1, n) * (1.0 / (2 * n + 1)); } result[j] = p; } ); } dispatch_group_wait(g, DISPATCH_TIME_FOREVER); double pi = 0.0; for (i = 0; i < MAX / DIV; ++i) { pi += result[i]; } pi *= 4; t2 = getTimeSecond(); printf("%f\t%f\n", pi, t2 - t1); return 0; }
同じく、三回ぐらい実行してみる。
| π | 秒 |
|---|---|
| 3.142592 | 0.313952 |
| 3.142592 | 0.317246 |
| 3.142592 | 0.314269 |
むちゃくちゃ速い！
けど、なぜか精度が悪くなっている……。
足し算の順番が違うので、結果が異なることはもちろんありえるけど、ちょっと大きすぎる？
DIVを100にすると、SEGVで落ちたりするので、どこかバグってるのかも。
あとで確認しよう。
GCD簡単で面白いなぁ。
Google Code Jam 2009に登録してみた
60時間ぐらいでモンハン３にも満足して、オンラインの無料期間も終わったので少しクールダウン。
誰かに誘われるまでは、オフでも進めよう。
さて、アルゴリズムは門外漢なのだけれど、Code Jam 2009に登録してしまった。
C++の勉強になればいいなということでやってみる。
まずは過去問から。
2008年も過去問で一番古いやつから、Alien Numbers。
Alien Numbers
http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGIP6AQw
以下、解答含むネタばれ。
（過去問でも解答公開したらまずいんだろうか？？）
OpenCLプログラミングセミナー行ってきた
ctypesで関数ポインタを扱う
ctypesを使うとDLLが呼び出せることを前に書いた。
こんな感じで。
from ctypes import * user32 = windll.user32 user32.MessageBoxW(0, u'Python ctypes test', 0, 0)
ctypesの便利さはこんなものじゃない。
Pythonの関数を関数ポインタのように扱って、callback関数にしたり、CreateThreadしたりできる。
from ctypes import * user32 = windll.user32 kernel32 = windll.kernel32 def callbackFunction(): user32.MessageBoxW(0, u'MessageBox from callback function', 0, 0) return 0 functionType = CFUNCTYPE(c_int) functionPointer = functionType(callbackFunction) threadId = c_ulong(0) threadHandle = kernel32.CreateThread(0, 0, functionPointer, 0, 0, byref(threadId)) result = kernel32.WaitForSingleObject(threadHandle, 60*1000) if result: print('Timeout') else: print('Thread exited')
ctypesのおかげでWin32 API使ったコードでも、こんなに簡単にPythonだけで書くことが出来るようになっている。
Live-Androidを試す
Engadgetに面白い記事が載っていたので、さっそく試す。
元がLinuxとJavaなんだから不思議はないが、実際に動くとまた感動がある。
VMware Fusionで動かしてみた。
起動時のロゴ。
ロゴ２。
なぜかバッテリーがないとか言われる。
起動し終わったところ。
セッティング画面。
この状態ではネットワーク繋がらないので、特に何も出来ることはない。
Android搭載ネットブックとかこんな感じになるのかも知れない。
