一緒に爆弾を解除しよう！
前回の Data Lab から 2 学期が経ち、ようやく CSAPP の実験を行う時間ができました。今回の実験は Bomb Lab と呼ばれ、ストーリーの背景は Dr.Evil が設計した爆弾で、正しい 6 つの文字列を入力することで解除できるというものです。私たちは逆アセンブルを通じて、爆弾の実行可能ファイルを解析し、爆弾を解除するための 6 つの文字列を解読する必要があります。
実験概要#
実験資料は CMU のウェブサイトから入手できます：https://csapp.cs.cmu.edu/3e/labs.html
圧縮ファイルには合計 3 つのファイルがあります
.
├── README
├── bomb // 爆弾の実行可能ファイル
└── bomb.c // 爆弾の一部のソースコード
まずbomb.cファイルを見てみましょう。
ここから爆弾の大まかな動作プロセスがわかります：
- 1 行の文字列を読み取る
phase_i関数を使用して入力が有効かどうかを判断する
したがって、各phase関数の検証プロセスを研究すれば、文字列の内容を逆算できるでしょう。
objdump -d bomb > bomb.sを使用して爆弾の逆アセンブルファイルを取得します。
左側でtmuxを使用して GDB デバッグを行い、右側でアセンブリコードを確認します。
次に、爆弾を解除する作業を始めましょう！
Phase_1#
phase_1 のアセンブリコードは以下の通りです。
string_not_equal は edi、esi の 2 つの文字列ポインタを受け取り、2 つの文字列を比較します。もし 2 つの文字列が等しければ eax は 0 を出力します。
したがって、phase_1の役割は入力された文字列と 0x402400 に存在する文字列が等しいかどうかを比較し、test を使用して出力が 0 であるかどうかを判断します。もし 0 であれば通過し、そうでなければexplode_bombを呼び出します。
したがって、私たちの答えは 0x404200 にある文字列です。GDB で確認します。
GDB の使い方については、こちらの CMU マニュアルを参照してください：https://csapp.cs.cmu.edu/2e/docs/gdbnotes-x86-64.pdf
ヒント：Dr.Evil はファイル入力を使用することを許可しています：
./bomb <file>、これにより毎回爆弾を解除する際の煩雑な繰り返し入力を避けることができます。
では、最初の爆弾を解除してみましょう。まずanswer.txtに先ほど得た文字列を書き込みます。
最初の文字列はすでに通過しました。
Phase_2#
phase_2 のアセンブリコードは以下の通りです。
この関数は前のものよりもかなり長く、read_six_numbersも呼び出しています。また、多くの分岐ジャンプ命令があります。
400efe: 48 83 ec 28 sub $0x28,%rsp
400f02: 48 89 e6 mov %rsp,%rsi
400f05: e8 52 05 00 00 call 40145c <read_six_numbers>
スタックに 0x28 のスペースを割り当て、6 つの数字をスタックに格納します。
400f0a: 83 3c 24 01 cmpl $0x1,(%rsp)
400f0e: 74 20 je 400f30 <phase_2+0x34>
400f10: e8 25 05 00 00 call 40143a <explode_bomb>
もし最初の数字が 1 でなければ、爆弾が爆発します。
400f17: 8b 43 fc mov -0x4(%rbx),%eax
400f1a: 01 c0 add %eax,%eax
400f1c: 39 03 cmp %eax,(%rbx)
400f1e: 74 05 je 400f25 <phase_2+0x29>
400f20: e8 15 05 00 00 call 40143a <explode_bomb>
もし次の数字が現在の数字の 2 倍でなければ、爆弾が爆発します。
400f25: 48 83 c3 04 add $0x4,%rbx
400f29: 48 39 eb cmp %rbp,%rbx
400f2c: 75 e9 jne 400f17 <phase_2+0x1b>
400f2e: eb 0c jmp 400f3c <phase_2+0x40>
rbxは最後の数字の次の位置を指し、ここまで読み取った場合は 6 つの数字がすべて処理されたことを示します。
以上の分析から、2 番目の文字列は以下の要件を満たす必要があります。
- 6 つの数字で構成されている
- 最初の数字は 1 である
- 2 番目以降の各数字は前の数字の 2 倍である
したがって、文字列は1 2 4 8 16 32です。
Phase_3#
phase_3 のアセンブリコードは以下の通りです。
多くの規則的なジャンプ命令があり、最初にsscanfがあります。したがって、前に出てきた 0x4025cf に格納されているのは読み取るフォーマットであるはずです。GDB で表示して確認します。
入力する文字列は 2 つの数字である必要があります。
400f6a: 83 7c 24 08 07 cmpl $0x7,0x8(%rsp)
400f6f: 77 3c ja 400fad <phase_3+0x6a>
0x8(%rsp)は最初の数字で、もしそれが 7 より大きければ爆弾が爆発します。
400f71: 8b 44 24 08 mov 0x8(%rsp),%eax
400f75: ff 24 c5 70 24 40 00 jmp *0x402470(,%rax,8)
400f7c: b8 cf 00 00 00 mov $0xcf,%eax
400f81: eb 3b jmp 400fbe <phase_3+0x7b>
400f83: b8 c3 02 00 00 mov $0x2c3,%eax
400f88: eb 34 jmp 400fbe <phase_3+0x7b>
400f8a: b8 00 01 00 00 mov $0x100,%eax
400f8f: eb 2d jmp 400fbe <phase_3+0x7b>
400f91: b8 85 01 00 00 mov $0x185,%eax
400f96: eb 26 jmp 400fbe <phase_3+0x7b>
400f98: b8 ce 00 00 00 mov $0xce,%eax
400f9d: eb 1f jmp 400fbe <phase_3+0x7b>
400f9f: b8 aa 02 00 00 mov $0x2aa,%eax
400fa4: eb 18 jmp 400fbe <phase_3+0x7b>
400fa6: b8 47 01 00 00 mov $0x147,%eax
400fab: eb 11 jmp 400fbe <phase_3+0x7b>
最初の数字に基づいて 2 番目の数字を選択します。これはswitch文のようなもので、最初の数字が 0 であれば、0x02470 にジャンプします。GDB でその場所に何が格納されているかを確認します。
0x400f7c にジャンプし、% eax=0xcf、つまり 207 です。
400fbe: 3b 44 24 0c cmp 0xc(%rsp),%eax
400fc2: 74 05 je 400fc9 <phase_3+0x86>
400fc4: e8 71 04 00 00 call 40143a <explode_bomb>
2 番目の数字が % eax と等しいかどうかを判断し、等しくなければ爆弾が爆発します。
したがって、この文字列の一つの形式は0 207です。最初の数字によって、2 番目の数字は他にも異なる値を持つ可能性があります。
Phase_4#
phase_4 のアセンブリコードは以下の通りです。
ここでは、同様にsscanfを呼び出し、さらにfunc4という関数も呼び出しています。
いつものように、まずsscanfが受け取るフォーマットを見てみましょう。
ここでも 2 つの数字が見えます。
40102e: 83 7c 24 08 0e cmpl $0xe,0x8(%rsp)
401033: 76 05 jbe 40103a <phase_4+0x2e>
401035: e8 00 04 00 00 call 40143a <explode_bomb>
最初の数字は 14 以下でなければなりません。
40103a: ba 0e 00 00 00 mov $0xe,%edx
40103f: be 00 00 00 00 mov $0x0,%esi
401044: 8b 7c 24 08 mov 0x8(%rsp),%edi
401048: e8 81 ff ff ff call 400fce <func4>
14、0、最初の数字を引数としてfunc4に渡します。次に、func4内で何が起こるかを分析します。
ここには 2 つの分岐ジャンプがあり、2 回の再帰呼び出しがあります。これは二分探索のようなプログラムであると推測され、C 形式に書き直してみましょう。
int func4(int i, int j, int target) {
int mid = ((i - j + ((i - j) >> 31)) >> 1) + j;
if (mid == target) {
return 0;
} else if (mid < target) {
return 2 * func4(i, mid + 1, target) + 1;
} else {
return 2 * func4(mid - 1, j, target);
}
}
出力を 0 にするためには、常に左を探し続け、midの右側には決して到達しない必要があります。したがって、最初の数字は14、0を入力することが可能です。したがって、最初の数字の可能な値は7、3、1、0です。
401051: 83 7c 24 0c 00 cmpl $0x0,0xc(%rsp)
401056: 74 05 je 40105d <phase_4+0x51>
401058: e8 dd 03 00 00 call 40143a <explode_bomb>
最後に、2 番目の数字が 0 であるかどうかを確認します。したがって、この文字列は3 0を取ることができます。
Phase_5#
phase_5 のアセンブリコードは以下の通りです。
ここには 2 つの文字列定数0x4024b0と0x40245eがあり、GDB でそれらが何であるかを確認します。
"maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you"
"flyers"
私の浅い推測では、最初の文字列は辞書であるべきで、使用時にオフセット0x4024b0(%rdx)があるためです。2 番目の文字列はターゲット文字列で、<string_not_equal>を使用して、ユーザーが入力した文字列が辞書を通じて翻訳された後、ターゲットと同じであるかどうかを比較します。
この仮定に基づいて、辞書を通じて翻訳されるプロセスを注意深く観察します。
40108b: 0f b6 0c 03 movzbl (%rbx,%rax,1),%ecx
40108f: 88 0c 24 mov %cl,(%rsp)
401092: 48 8b 14 24 mov (%rsp),%rdx
401096: 83 e2 0f and $0xf,%edx
401099: 0f b6 92 b0 24 40 00 movzbl 0x4024b0(%rdx),%edx
ここで%clは%ecxレジスタの下位 8 ビットで、これを 0xf で AND 演算することで下位 4 ビットを取得します。したがって、翻訳時には文字バイトの下位 4 ビットをオフセットとして使用します！
したがって、"flyers" に対応する辞書のオフセットは "9 15 14 5 6 7" であり、いくつかの要件を満たす文字列を生成するための Python スクリプトを書くことができます。
spell = [9, 15, 14, 5, 6, 7]
for offset in range(8):
result = "".join(chr(num + 16 * offset) for num in spell)
print(f"Offset {offset * 16} : {result}")
実行結果：
したがって、5 番目の文字列は IONEFG である可能性があります。私たちの推測は正しかったようです。アセンブリコードを逐一読み込むことなく答えを得ることができました。
Phase_6#
この関数の長さは明らかに前のものよりも長くなっています。ここに最も重要な部分のコードを示します。
このコードが何をしているのか簡単に説明します。詳細な分析は省略しますので、興味のある読者はソースコードをダウンロードして確認してください。
メモリにはリンクリストが格納されています。
まず 6 つの数字を読み取り、範囲は 1 から 6 の間です。
次に、これら 6 つの数字を 7 で補完します。つまり、i=7-iです。
数字iをインデックスとして、リンクリストの第iノードを探し、そのノードを指すポインタをスタックに入れます。
スタック内のノードの順序に従って、各ノードのnextnodeポインタを再書き込み、リンクリストのノードの順序をスタックの順序に合わせます。
最後に、リンクリスト内のノードのdataが降順であるかどうかを確認します。
ノード内の数字を降順に並べるためには、順序は3 4 5 6 1 2である必要があります。7 で補完すると4 3 2 1 6 5となり、これが私たちが求める文字列です。
爆弾解除成功#
これで、爆弾を解除するために必要な 6 つの文字列がすべて求められました。answer.txtに書き込みます。
./bomb answer.txtを実行すると、得られます。
このラボは、真の逆アセンブルにとっては hello world レベルですが、x86-64 アセンブリと GDB の基本的なコマンドに慣れることができました。
全体として、これは非常に面白い実験で、全く止まることができませんでした。