今回の問題は、Research UNIX version1 上でコンパイルされた PDP-11/20 の実行ファイルを人力で逆アセンブルしてみるという問題となる。
PDP-11 では特殊なエンディアンの方式が採用されていた。これは 32 ビットワードを構成する 2 つの 16 ビットワードはビッグエンディアンで格納され、16 ビットワードはリトルエンディアンで格納がされる。
詳しくは以下のリンク先を見てほしい。
https://ja.wikipedia.org/wiki/PDP-11
ただし、今回は 32 ビットのデータを扱っていないため、リトルエンディアンだけ抑えておけば問題ない。
重要なのは、ヘッダーが終わった 12 バイト目からプログラムが実行されるということである。 ヘッダーに関して詳しく知りたい場合、以下のリンク先を見てほしい。
https://www.bell-labs.com/usr/dmr/www/man51.pdf
エンディアンと同様に以下のリンク先が詳しい。
実行ファイルに file コマンドを行ってみると以下の出力が見られる。
> file a.out a.out: PDP-11 old overlay
ここから PDP-11 のバイナリであることがわかる。
実行ファイルに cat コマンドを行ってみると以下のような出力が見られると思う。
> cat a.out 4 � � � � � � � B`�passwd is in R2
passwd is in R2 という文字列から最終的な計算結果は R2 レジスタに入るとわかる。
xxd コマンドを利用し、2 進数でダンプを行う。
> xxd -g 1 -b a.out 00000000: 00000101 00000001 00110100 00000000 00000000 00000000 ..4... 00000006: 00000000 00000000 00000000 00000000 00000000 00000000 ...... 0000000c: 00000001 00001010 00000010 00001010 10000001 00001010 ...... 00000012: 10000010 00001010 11000001 00001100 11000001 00001100 ...... 00000018: 11000001 00001100 11000001 00001100 11000010 00001100 ...... 0000001e: 01000010 01100000 11111111 00000001 01110000 01100001 B`..pa 00000024: 01110011 01110011 01110111 01100100 00100000 01101001 sswd i 0000002a: 01110011 00100000 01101001 01101110 00100000 01010010 s in R 00000030: 00110010 00100000 00000000 00001010 2 ..
このバイナリを読み解いていくのがこの問題となる。
まず、ヘッダーを取り除く。前述の通りヘッダは 12 バイトであり、プログラムはヘッダ直後から実行されていくためである。 ヘッダーを取り除くと以下の様になる。(アドレスと ascii コードも取り除いている)
00000001 00001010 00000010 00001010 10000001 00001010 10000010 00001010 11000001 00001100 11000001 00001100 11000001 00001100 11000001 00001100 11000010 00001100 01000010 01100000 11111111 00000001
基本的に 16 ビットワードを１命令として扱うため、16 ビットずつ見ていこう。
以下二進数はリトルエンディアンとして 1 バイト逆に置き換えたものである。
0000101000 000001
上位 4 ビットに値がないことから 2 オペンランド命令でないことがわかる。 また、11 ビット目が 0 でないことから無条件分岐命令でないこともわかる。
要するにこれは、1 オペランド命令となる。1 オペランド命令は上位 10 ビットが命令コードとなるので 0000101000 が命令となる。参考リンク先では、8 進数で命令コードが表現されているので 0000101000 を 8 進数に置き換えると 50 である。50 は CLR 命令であるので、レジスタを 0 クリアしていることがわかる。レジスタは 2~0 ビットで指定するので R1 を 0 クリアしていることがわかる。
CLR R1
0000101000 000010
前の命令と同じ命令コードなので CLR 命令であることがわかる。また、レジスタは 10 であるので R2 を示していることがわかる。
CLR R2
0000101010 000001
CLR 命令と同様に１オペランド命令である。0000101010 は 8 進数で表すと 52 であり、INC 命令であることがわかる。またレジスタは R1 を示していることがわかる。
INC R1
0000101010 000010
前の命令と同じく INC 命令である。レジスタは 10 であるため R2 である。
INC R2
0000110011 000001
この命令も 1 オペランド命令である。11011 を 8 進数にすると 63 であり、ASR 命令であるとわかる。またレジスタは R1 である。
ASR R1
また、この命令が 4 命令続く。
0000110011 000010
この命令は前の命令と同じく ASR 命令であり、レジスタが 10 であることから R2 となる。
ASR R2
0110 000001 000010
この命令の場合、11 ビット目が 0 であり、最上位ビットから 4 ビットにデータがあることから 2 オペランド命令であることがわかる。2 オペランド命令は最上位ビットから 4 ビットが命令コードを表すので、0110 が命令コードとなる。0110 を 8 進数に変換すると、6 となる。よって ADD 命令であることがわかる。また、レジスタは 8/~6 ビット目と 2/~0 ビット目が source と destination を示すので、source が R1 であり、destination が R2 であることがわかる。
ADD R1, R2
00000001 11111111
この命令の場合、11 ビット目が 0 かつ上位 7 ビットに命令コードがないため条件分岐命令であることがわかる。その場合、参考先のように命令を解釈すると、0000000100000000 となり 4XX であるとわかる。また、11111111 は無条件分岐のオフセットは符号付整数であるため、2 の補数表現からマイナスであることがわかる。よって無限ループとなっている。
BR -1(実際はラベル)
今回元となった機械語のプログラムは以下になる。
/ tukuCTF GrandpaMemory clr r1 clr r2 inc r1 inc r2 asl r1 asl r1 asl r1 asl r1 asl r2 add r1, r2 1: br 1b hint: <passwd is in R2 \0\n>
まず、r1 と r2 レジスタを 0 クリアする。その後、r1,r2 をインクリメントし r1=1,r2=1 とする。また、asl は左シフトで値を 2 倍にする命令である。よって、計算結果は R2=18 となる。
TsukuCTF22{18}