GrandpaMemory

今回の問題は、Research UNIX version1 上でコンパイルされた PDP-11/20 の実行ファイルを人力で逆アセンブルしてみるという問題となる。

PDP エンディアン

PDP-11 では特殊なエンディアンの方式が採用されていた。これは 32 ビットワードを構成する 2 つの 16 ビットワードはビッグエンディアンで格納され、16 ビットワードはリトルエンディアンで格納がされる。

詳しくは以下のリンク先を見てほしい。

https://ja.wikipedia.org/wiki/PDP-11

ただし、今回は 32 ビットのデータを扱っていないため、リトルエンディアンだけ抑えておけば問題ない。

Research UNIX version1 のヘッダー

重要なのは、ヘッダーが終わった 12 バイト目からプログラムが実行されるということである。 ヘッダーに関して詳しく知りたい場合、以下のリンク先を見てほしい。

https://www.bell-labs.com/usr/dmr/www/man51.pdf

PDP-11 の命令

エンディアンと同様に以下のリンク先が詳しい。

PDP エンディアン

解き方

PDP-11 のバイナリであることを知る

実行ファイルに 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 レジスタに入るとわかる。

2 進数に変換して出力する

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 ビットワードを1命令として扱うため、16 ビットずつ見ていこう。

00000001_00001010

以下二進数はリトルエンディアンとして 1 バイト逆に置き換えたものである。

0000101000 000001

上位 4 ビットに値がないことから 2 オペンランド命令でないことがわかる。 また、11 ビット目が 0 でないことから無条件分岐命令でないこともわかる。

要するにこれは、1 オペランド命令となる。1 オペランド命令は上位 10 ビットが命令コードとなるので 0000101000 が命令となる。参考リンク先では、8 進数で命令コードが表現されているので 0000101000 を 8 進数に置き換えると 50 である。50 は CLR 命令であるので、レジスタを 0 クリアしていることがわかる。レジスタは 2~0 ビットで指定するので R1 を 0 クリアしていることがわかる。

CLR R1

00000010_00001010

0000101000 000010

前の命令と同じ命令コードなので CLR 命令であることがわかる。また、レジスタは 10 であるので R2 を示していることがわかる。

CLR R2

10000001 00001010

0000101010 000001

CLR 命令と同様に1オペランド命令である。0000101010 は 8 進数で表すと 52 であり、INC 命令であることがわかる。またレジスタは R1 を示していることがわかる。

INC R1

10000010_00001010

0000101010 000010

前の命令と同じく INC 命令である。レジスタは 10 であるため R2 である。

INC R2

11000001_00001100

0000110011 000001

この命令も 1 オペランド命令である。11011 を 8 進数にすると 63 であり、ASR 命令であるとわかる。またレジスタは R1 である。

ASR R1

また、この命令が 4 命令続く。

11000010_00001100

0000110011 000010

この命令は前の命令と同じく ASR 命令であり、レジスタが 10 であることから R2 となる。

ASR R2

01000010_01100000

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

11111111_00000001

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}

© 2021-2024 SecHack365-Fans All Right Reserved.