find the key.
http://www.sabamiso.net/yoggy/8f203533f89f57f5e5be707168b8c069
llvm is compilier infrastructure.
LLVM bitcodeを読む問題。
以下、Linux環境で。
$ wget http://www.sabamiso.net/yoggy/8f203533f89f57f5e5be707168b8c069 $ file 8f203533f89f57f5e5be707168b8c069 8f203533f89f57f5e5be707168b8c069: gzip compressed data, was "challenge", from Unix, last modified: Mon Jan 30 17:18:36 2012, max compression $ cat 8f203533f89f57f5e5be707168b8c069| gzip -cd > challenge.bc $ file challenge.bc challenge.bc: LLVM bitcode
ちなみにMac OS Xだと愛想のない返事が返ってくるので注意。。
$ file challenge.bc challenge.bc: data
ちなみにLLVM bitcodeファイルの先頭は"BC"で始まります。覚えておきましょう。
$ hexdump -C challenge.bc | head -2 00000000 42 43 c0 de 21 0c 00 00 7c 01 00 00 01 10 00 00 |BC..!...|.......| 00000010 12 00 00 00 07 81 23 91 41 c8 04 49 06 10 32 39 |......#.A..I..29|
この問題を解くにはLLVM環境が必要。次の手順で適当なディレクトリにインストール。
$ wget http://llvm.org/releases/3.0/llvm-3.0.tar.gz $ tar xvfz llvm-3.0.tar.gz $ cd llvm-3.0.src $ ./configure --prefix=/usr/local/llvm $ make $ sudo make install
LLVM bitcodeを実行する場合は次の手順で。
$ /usr/local/llvm/bin/lli challenge.bc input the key: aaa wrong answer... $ /usr/local/llvm/bin/lli challenge.bc input the key: bbb wrong answer...
正解のキーワードを入力する問題らしいということがわかる。特に通信などは行っていないため正解データはバイナリファイルの中に入っているっぽい雰囲気であることがわかる。
次の手順でLLVM bitcodeの内容を確認してみる。llvm-disはLLVM bitcodeをディスアセンブルするコマンド。
$ /usr/local/llvm/bin/llvm-dis challenge.bc -o challenge.ll $ lv challenge.ll
LLVMアセンブリコードの仕様はLLVMのサイトにあるのでとりあえずメモ。
LLVM Language Reference Manual
意味はわからなくてもとりあえずコードをじーっと見ていると、元々のCのソースコードの変数・関数の名前がそのまま残っていることがわかる。
@encrypted_correct_msg = global [34 x i8] c"\93\F2\D1\92\A4\D5\C1\ED\C5\8E\E3\DA\8A\FF\DA\83\E4\9F\98\AA\90\84\AD\91\91\AC\90\80\AD\86\86\BD\DA\00", align 1
@v1 = global i8 -1, align 1
@v2 = global i8 97, align 1
@.str = private unnamed_addr constant [16 x i8] c"wrong answer...\00", align 1
@.str1 = private unnamed_addr constant [27 x i8] c"this is the right answer!!\00", align 1
@.str2 = private unnamed_addr constant [15 x i8] c"input the key:\00", align 1
・
・
・
define void @wrong() {
%1 = call i32 @puts(i8* getelementptr inbounds ([16 x i8]* @.str, i32 0, i32 0))
call void @exit(i32 1) noreturn nounwind
unreachable
; No predecessors!
ret void
}
・
・
・
define void @correct() {
%1 = call i32 @puts(i8* getelementptr inbounds ([27 x i8]* @.str1, i32 0, i32 0))
call void @exit(i32 1) noreturn nounwind
unreachable
; No predecessors!
ret void
}
・
・
・
define i32 @main(i32 %argc, i8** %argv) {
・
・
・
プログラムは入力された文字列が不正解だった場合はwrong()関数、正解だった場合はcorrect()関数が実行され、実行されるとそれぞれ"wrong answer..."、"this is the right answer!!"の文字列が表示されるらしい。 また、@encrypted_correct_msg変数に格納されているバイト列が正解の文字列を暗号化したっぽいデータらしいことがわかる。
もう少しよく読むと、プログラムは次の動作をすることがわかる。
- main()関数中にwrong()が二回登場している。何かのチェックに引っかかった場合はプログラムが即終了する。
- チェックをくぐりぬけてmain()関数の最後でcorrect()が実行されるような文字列を入力すればいいらしい。
LLVMアセンブリコード内には文字列のチェックが2つ存在する。
まず第一のチェック。入力された文字列の長さを@encrypted_correct_msgと比較している。@encrypted_correct_msgは33バイト+"\00"のデータが格納されているので、正解の文字列は33文字であることがわかる。LLVMアセンブリコードの;====の部分にコメントを追加している。
;==== len = strlen(buf); ====
%16 = getelementptr inbounds [64 x i8]* %buf, i32 0, i32 0
%17 = call i32 @strlen(i8* %16) nounwind readonly
store i32 %17, i32* %len, align 4
;==== if (len != strlen(encrypted_correct_msg)) { ====
%18 = load i32* %len, align 4
%19 = call i32 @strlen(i8* getelementptr inbounds ([34 x i8]* @encrypted_correct_msg, i32 0, i32 0)) nounwind readonly
%20 = icmp ne i32 %18, %19
br i1 %20, label %21, label %22
次に第二のチェック。
;==== ここからforループはじまり ====
;==== for (i = 0; i < len; ++i) { ====
; <label>:23 ; preds = %55, %22
%24 = load i32* %i, align 4
%25 = load i32* %len, align 4
%26 = icmp ult i32 %24, %25
br i1 %26, label %27, label %58
; <label>:27 ; preds = %23
;==== c = buf[i] ^ v1; ====
%28 = load i32* %i, align 4
%29 = getelementptr inbounds [64 x i8]* %buf, i32 0, i32 %28
%30 = load i8* %29, align 1
%31 = zext i8 %30 to i32
%32 = load i8* @v1, align 1
%33 = zext i8 %32 to i32
%34 = xor i32 %31, %33
%35 = trunc i32 %34 to i8
store i8 %35, i8* %c, align 1
;==== v1 = v1 ^ v2; ====
%36 = load i8* @v1, align 1
%37 = zext i8 %36 to i32
%38 = load i8* @v2, align 1
%39 = zext i8 %38 to i32
%40 = xor i32 %37, %39
%41 = trunc i32 %40 to i8
store i8 %41, i8* @v1, align 1
;==== v2 = c ^ 0xaa; ====
%42 = load i8* %c, align 1
%43 = zext i8 %42 to i32
%44 = xor i32 %43, 170
%45 = trunc i32 %44 to i8
store i8 %45, i8* @v2, align 1
;==== if (c != encrypted_correct_msg[i]) wrong(); ====
%46 = load i8* %c, align 1
%47 = zext i8 %46 to i32
%48 = load i32* %i, align 4
%49 = getelementptr inbounds [34 x i8]* @encrypted_correct_msg, i32 0, i32 %48
%50 = load i8* %49, align 1
%51 = zext i8 %50 to i32
%52 = icmp ne i32 %47, %51
br i1 %52, label %53, label %54
; <label>:53 ; preds = %27
call void @wrong()
br label %54
; <label>:54 ; preds = %53, %27
br label %55
;==== ここはfor()の++iが実行されている ====
; <label>:55 ; preds = %54
%56 = load i32* %i, align 4
%57 = add i32 %56, 1
store i32 %57, i32* %i, align 4
br label %23
;==== ここでforループおわり ====
Cのコードにまとめると2つ目のチェックはこんな感じ。
for (i = 0; i < len; ++i) {
c = buf[i] ^ v1;
v1 = v1 ^ v2;
v2 = c ^ 0xaa;
if (c != encrypted_correct_msg[i]) wrong();
}
LLVMアセンブリコードを見ると、v1, v2の初期値はそれそれ0xffと0x61であることが分かる。
@v1 = global i8 -1, align 1 ;8ビットなので-1は0xFF @v2 = global i8 97, align 1
@encrypted_correct_msgの先頭は0x93が格納されているので、このチェックループを通る1文字目は
0x93 ^ 0xff -> 0x6c -> 'l'
であることが分かる。 以降c, v1, v2の値を順次求めると、最終的に入力する文字列が"llvm is compilier infrastructure."であるときにチェックループを脱出し、correct()関数が実行されることがわかる。
解き方としては、LLVM bitcodeを実行ファイルに変換してその中身を逆アセンブル＆デバッガで追いかけるのもあり。 LLVM bitcodeはLLVMに含まれているllcコマンドを使用して各アーキテクチャのアセンブラへ変換することができる。
$ /usr/local/llvm/bin/llc challenge.bc -o challenge.s $ gcc challenge.s -o challenge $ ./challenge input the key: ^C