追記:選考を通過してセキュリティキャンプ全国大会2016に参加できるらしいです。やったぜ。

どうも。rogyCTF部のやむどぅ(@ymduu)です。
実はつい先日締め切りだったセキュリティキャンプ全国大会2016に応募していました。
セキュキャン界隈にはどうやら応募用紙を晒す風習があるそうなので、僕も晒していこうかなという感じです。
よろしくお願いします。
(CTFではないのですが、一番近いのがCTFなのでカテゴリはCTFにしました)

共通問題はまるまる載せると結構長い上に、他の人の応募用紙を読むときに気になるのはどちらかというと選択問題の回答のような気がするので共通問題はダイジェスト版で。
はよ選択問題読ませろ!って方は続きからどうぞ。

共通問題1

今までの製作物をありったけ自慢してくださいみたいな問題。
僕はグローバル理工兄弟Programmer PANIC!について書きました。
グローバル理工兄弟については初めての言語で初めてのGUIプログラミングをした時の苦労と楽しさ、Programmer PANIC!についてはゲームのコンセプトややりたかった事、工夫点、苦労話など。

共通問題2

今までに技術的に躓いたところとどうやって解決したかと同様の点で躓いている人間にどのようなアドバイスをしますかという問題。

中学生の時、初めてゲームを作ろうとした時に困った関数の返り値と値渡しについて数学の参考書まで出しながら考えた思い出を思い出しながら書きました。

一つのサンプルコードがわからん!って場合でも実は複数の理由が複合していたりするので、まず何が分からないのかをはっきりさせてから文献なりインターネットなり人なりに当たるといいですよという話と、分かったら同じようなパターンをいろいろ試すといいですよという話を書きました。

理解してから色々なパターンを試すと身に着くのが早まるのはマジなのでおすすめです。



共通問題3

(1)セキュキャンで受けたい講義とその理由、(2)セキュキャンで学びたいことややりたいことを述べよという問題。

(1)では、

4-D 実行ファイルの防御機構を突破せよ、

2-A スマートフォン向けゲームのセキュリティ、

1-DDissecting Malware -x86 Windows malware analysis-

の三つを挙げ、それぞれ要約すると

4-D

ゲームに脆弱性があったため任意コード実行されてしまい不正コピーが蔓延り、大きな損害を出す原因となったPSPの話を挙げてゲームを製作する場合でもセキュリティに気をつける必要があるという話

2-A

自分が必死で調整したゲームのパラメータを不正に書き換えられたり、オンラインゲームで不正が蔓延しゲームが詰まらなくなるのはゲーム製作勢として悲しいので作ったゲームを守りたいという話

1-D

一通りx86のアセンブリ言語は読めるようになったが、0ctfで実力不足を思い知り、今の実力ではreversingを社会に役立てることはできないのでもっとreversing力を高めたいという話
をしました。
(2)では、分からなかったことが分かるのは楽しいので分からなかった事をたくさん知りたい、だとかバイナリが好き、だとかSECCON本戦に行く時にメンバーが足りないくらい周りにセキュリティに興味のある人間が居ないのでセキュリティ友達がほしい、だとかその辺のことを書きました。


今要約しながら見直すとゲーム色が強い回答になっている気がしますネ
選択問題は応募用紙から丸々コピーしたものを載せます。割と長いので続きからどうぞ。

選択問題1

メモリアドレスを見ていろいろ考える問題。調子に乗って実験した内容を全部書いたりAAでメモリマップを表現したりしたら(4500字ほどのはずなのに)10000文字制限に引っかかって(謎)難儀しました。

問題: 以下は変数hogeとfugaのメモリアドレスを表示するプログラムと、その実行結果です。 実行結果のhogeとfugaのメモリアドレスを見て、思うことを説明してください。
 ・ソースコード
・実行結果
    hoge address = 0x7fff539799f0
    fuga address = 0x7fca11404c70

回答:
このフォームから送信するとタブによる字下げが消滅してしまうため、タブによる字下げは半角スペースによる字下げに置換してある。
私がこのコードと出力結果を見てまず初めに思ったことは、「これは64bitのOSで実行しているな」という事である。
まず、前提としてhogeとfugaがメモリのどの領域を指すポインタとなるかについて述べておく。hogeは、int型の要素数10個の配列の先頭アドレスであり、これはローカル変数なのでスタック上にint10個分の領域が確保される。
一方fugaには、malloc(1)の返り値が格納される。malloc(arg)は、ヒープ領域からargバイトの領域を割り当て、それを指すポインタを返す関数である。つまり、printfが行われる時、fugaには割り当てられたヒープ領域のアドレスが格納されていると考えられる。

次に、私が64bitOSで実行していると判断した理由であるが、私が64bitのバイナリをgdbでデバッグすると、スタックのアドレスは 0x7fff~となっているのを何度も見ているからである。また、スタック上のアドレスであるはずの0x7fff539799f0自体が32bitの整数には収まらない数値であることからも、これは64bitOS上で動作しているのではないか、と考えるに至った。

これ以上プログラムと出力を睨んでいても何かを思いつくのは難しいと思ったので、早速実行してみることにした。ここからが本番である。
環境は、既に手元にあったUbuntu 14.04(64bit)とLinux Mint 17.1(64bit)を使用した。
まず、gccでオプションを何も付けず普通にコンパイル、実行した結果を載せる。
$ gcc test.c
$ ./a.out
hoge address = 0x7fffa9e52810
fuga address = 0xa35010
以上のような結果が得られた。
複数回実行するとhogeとfugaのアドレスは変化するものの、概ね上記のアドレスの近くに配置されているように見えた。
この出力を見て私が思ったことは、問題に述べられている出力よりfugaのアドレスがかなり小さい、もっと言うと、「スタック領域とヒープ領域が離れすぎている」ということである。
問題で与えられた出力は、私が「普通に」プログラムを実行した時の出力よりもスタック領域とヒープ領域がかなり近いのである。
ここで、私は三つの仮説を立てた。
I.上のプログラムが実行された時は極端にメモリが不足していた
II.ヒープ領域がスタックの方向に伸びていきスタックに近づいていた
III.何らかの事情でスタック領域の近くにヒープ領域が置かれた

私が行った実験について述べる前に、プログラムが実行されている時のメモリの様子について述べておこうと思う。メモリの様子についてはこのサイト(http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2010/2011-01-25/)を参考にした。
図についてはURLを見ればよいのだが、私はスタックは上に伸びていくものを想像することが多いので以下のように考えることとした。
低位アドレス、
機械語
データ
BSS領域
ヒープ領域(高位アドレスに伸びていく)
(未使用領域)
スタック(低位アドレスに伸びていく)
高位アドレス
このサイト(http://d.hatena.ne.jp/nutsxx/20080603/1212460165)によると、ヒープ領域とスタック領域の間の領域は、
共有ライブラリのロード領域
メモリ・マップト・ファイル用領域
プロセス間共有メモリ用領域
メモリ・マップト・I/O用領域
メモリ・マップトによる追加HEAP領域
に使われるようだ。
また、このスライド(http://www.slideshare.net/bata_24/katagaitai-ctf-1-57598200)の23ページ目によると、上の共有ライブラリ(共有オブジェクト) とは、libc.soなど、であるということが分かった。
以下の実験は、この知識を前提に行った。
以下の実験において、「ヒープ領域とスタック領域の間の領域」を「未使用領域」と表記することとする。

以下、この仮説を検証するために私が行った実験について述べる。
実験I
この実験の目的は、「空きメモリが非常に少ない状況でプログラムを実行すれば未使用領域が少なくなり、題意のような出力が得られるのではないか」という仮説を検証することである。
メモリが不足している状況を作るために、Ubuntuの仮想マシンに割り振るメモリのサイズをだんだん小さくしてプログラムを実行してみた。2048MB、1024MB、512MBの三通りについて実験を行った。
結果:
2048MB
hoge address = 0x7fff5e29bb10
fuga address = 0x1974010
1024MB
hoge address = 0x7fff7adf5080
fuga address = 0xf35010
512MB
hoge address = 0x7fff1ed2f5a0
fuga address = 0x17c5010
特に目立った違いは見られなかった。特に、メモリを512MBにした時はUbuntuが非常に重くなり、ターミナルの起動、シャットダウンにも難儀するほど顕著にメモリが不足していたが、結果に大きな差は見られなかった。実験Iより、メモリが不足していたという仮定は正しいとは考えづらい。
実験II
この実験は、mallocで「普通に」メモリを確保しヒープ領域を成長させ、題意のような場所にmallocでメモリを確保できるかを調べることである。
この実験では、問題で与えられたコードを書き換え、以下のようなコードで実験を行った。
BUFの値を変更することで、malloc(1)の返り値がfugaに入る前に確保するメモリの量を調整することができる。
mallocの引数を大きくせずBUFでmallocの回数を指定するようにしたのは、一度に大量のメモリを確保しようとすると失敗するためである。
BUF=1000程度なら一瞬で終了するので、BUF=10000000で実行したところ、allocated:0x709291810と出力したあたりで重くなり、そのまま実行するとOSがフリーズした。
BUF=100000の場合、正常終了し、fuga address = 0x25513ee10となった。
以上の実験より、mallocを繰り返すと、確かにヒープ領域は高位アドレスに向かって成長するが、題意のようなアドレスに到達する前にフリーズし、mallocを繰り返してメモリを圧迫しても題意の出力は得られないということが分かった。

今までの実験により、メモリの事情により題意の出力を得るのは難しいということが分かった。
なので、仮説III.何らかの事情でスタック領域の近くにヒープ領域が置かれた、という説が濃厚である、と私は考えた。
ヒープ領域は、先ほどのスライド(http://www.slideshare.net/bata_24/katagaitai-ctf-1-57598200)によると、bss領域の隣となることが分かるので、機械語、データ領域、bss領域の連続した3領域が確保されるアドレス、もっと言うと機械語(プログラム)がロードされる領域が変化すればヒープのアドレスも変化することが期待できる。
しかし、普通にコンパイルした場合、実行ファイルのメモリアドレスは実行ファイルの中に記されており、変化することは無い。私はこの事を利用して選択問題8に解答した。objdumpすると、命令の横にアドレスが表示されている。
しかし、実行ファイルがロードされるアドレスをランダム化し、攻撃を難しくするセキュリティ機構が存在することを思い出した。
PIE(Position Independent Executable)である。
PIEをオンにすると、実行ファイルがロードされるアドレスがランダムになり、実行ファイルがどこに配置されているか分からないため、実行ファイル内にあるコードを使って攻撃を行おうにも実行ファイルがメモリ上のどこにあるか不明なためそれを調べることから行う必要があり、攻撃の難易度が上昇する。
これを使えば、機械語がロードされる領域が変化し、ヒープ領域の場所も変化するかもしれないと考えた。
そこで、私はPIE有効、無効それぞれの実行ファイルを実行し、メモリマップを見るという実験を行おうと考えた。これが実験IIIである。
実験III
・問題のプログラムについて、PIE有効、無効についてそれぞれ実行ファイルを用意し、実行時のメモリマップをgdbで見る。
まずはPIE有効、無効それぞれのバイナリを用意した。
有効:
$gcc -fPIE -pie -o pie test.c
無効:
$gcc -o nopie test.c
まずPIE無効なバイナリについてgdbでメモリマップを見た。gdbでi proc mapとするとメモリマップを見ることができる。
          Start Addr           End Addr       Size     Offset objfile
            0x400000           0x401000     0x1000        0x0 /home/ymduu/デスクトップ/seccampmon/nopie
            0x600000           0x601000     0x1000        0x0 /home/ymduu/デスクトップ/seccampmon/nopie
            0x601000           0x602000     0x1000     0x1000 /home/ymduu/デスクトップ/seccampmon/nopie
            0x602000           0x623000    0x21000        0x0 [heap]
      0x7ffff7a15000     0x7ffff7bd0000   0x1bb000        0x0 /lib/x86_64-linux-gnu/libc-2.19.so
      0x7ffff7bd0000     0x7ffff7dcf000   0x1ff000   0x1bb000 /lib/x86_64-linux-gnu/libc-2.19.so
      0x7ffff7dcf000     0x7ffff7dd3000     0x4000   0x1ba000 /lib/x86_64-linux-gnu/libc-2.19.so
      0x7ffff7dd3000     0x7ffff7dd5000     0x2000   0x1be000 /lib/x86_64-linux-gnu/libc-2.19.so
      0x7ffff7dd5000     0x7ffff7dda000     0x5000        0x0
      0x7ffff7dda000     0x7ffff7dfd000    0x23000        0x0 /lib/x86_64-linux-gnu/ld-2.19.so
      0x7ffff7fdc000     0x7ffff7fdf000     0x3000        0x0
      0x7ffff7ff8000     0x7ffff7ffa000     0x2000        0x0
      0x7ffff7ffa000     0x7ffff7ffc000     0x2000        0x0 [vdso]
      0x7ffff7ffc000     0x7ffff7ffd000     0x1000    0x22000 /lib/x86_64-linux-gnu/ld-2.19.so
      0x7ffff7ffd000     0x7ffff7ffe000     0x1000    0x23000 /lib/x86_64-linux-gnu/ld-2.19.so
      0x7ffff7ffe000     0x7ffff7fff000     0x1000        0x0
      0x7ffffffde000     0x7ffffffff000    0x21000        0x0 [stack]
  0xffffffffff600000 0xffffffffff601000     0x1000        0x0 [vsyscall]
0x400000以降に実行ファイルがロードされており、そのすぐ上位のアドレスにヒープがあることがわかる。
次に、PIE有効なバイナリについてgdbでメモリマップを見た、このとき、gdbではアドレスをランダムにする機構がオフになってしまうため、set disable-randomization offとしておいた。
以下はPIE有効な場合のメモリマップである。
          Start Addr           End Addr       Size     Offset objfile
      0x7f7443b09000     0x7f7443cc4000   0x1bb000        0x0 /lib/x86_64-linux-gnu/libc-2.19.so
      0x7f7443cc4000     0x7f7443ec3000   0x1ff000   0x1bb000 /lib/x86_64-linux-gnu/libc-2.19.so
      0x7f7443ec3000     0x7f7443ec7000     0x4000   0x1ba000 /lib/x86_64-linux-gnu/libc-2.19.so
      0x7f7443ec7000     0x7f7443ec9000     0x2000   0x1be000 /lib/x86_64-linux-gnu/libc-2.19.so
      0x7f7443ec9000     0x7f7443ece000     0x5000        0x0
      0x7f7443ece000     0x7f7443ef1000    0x23000        0x0 /lib/x86_64-linux-gnu/ld-2.19.so
      0x7f74440d2000     0x7f74440d5000     0x3000        0x0
      0x7f74440ee000     0x7f74440f0000     0x2000        0x0
      0x7f74440f0000     0x7f74440f1000     0x1000    0x22000 /lib/x86_64-linux-gnu/ld-2.19.so
      0x7f74440f1000     0x7f74440f2000     0x1000    0x23000 /lib/x86_64-linux-gnu/ld-2.19.so
      0x7f74440f2000     0x7f74440f3000     0x1000        0x0
      0x7f74440f3000     0x7f74440f4000     0x1000        0x0 /home/ymduu/デスクトップ/seccampmon/pie
      0x7f74442f3000     0x7f74442f4000     0x1000        0x0 /home/ymduu/デスクトップ/seccampmon/pie
      0x7f74442f4000     0x7f74442f5000     0x1000     0x1000 /home/ymduu/デスクトップ/seccampmon/pie
      0x7f744612e000     0x7f744614f000    0x21000        0x0 [heap]
      0x7fffea06b000     0x7fffea08c000    0x21000        0x0 [stack]
      0x7fffea1fe000     0x7fffea200000     0x2000        0x0 [vdso]
  0xffffffffff600000 0xffffffffff601000     0x1000        0x0 [vsyscall]
実行ファイルとヒープ領域がスタック領域のすぐ下位のアドレスにあることがわかる。
このときの出力は
hoge address = 0x7fffea08a980
fuga address = 0x7f744612e010
であり、題意の出力に似た、スタックとヒープが近いという出力結果が得られた。
また、確かにfugaがヒープ領域の中、hogeがスタック領域の中を指していることも確認でき、嬉しい気持ちになった。
さて、ではなぜPIEを有効にするとこのようにヒープとスタックが近づくのだろうか、と思う。
これについて調べた結果を述べる前に、まず自分で理由を想像したものを述べる。
これについて考える時に、ヒープとスタックの間の「未使用領域」は「メモリ・マップト・ファイル用領域」にも使われる、という事(このレポートの上方参照)を思い出した。この領域は、mmapでメモリを割り当てる領域なのである。
そして、スタック領域のすぐ下のアドレスは、まさにその「未使用領域」である。
私は、通常の実行ファイルを実行する時のようにmmapでlibcをメモリの上に配置した後にmmapで実行ファイルをlibc同様に「未使用領域」に配置した結果このようなことになったのではないか、と考えた。
さて、私はこれを検証するために、readelfコマンドを使ってヘッダの情報を見てみることにした。以下にpie,nopie,libc-2.19.soそれぞれのreadelf -hの結果を示す。
この解答は4500字程度のはずなのに、10000文字を超えていると表示され送信できないため、readelfの結果は必要な部分だけ添付することとする。

$ readelf -h pie
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
 (略)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              DYN (Shared object file)
  (略)

$ readelf -h nopie
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  (略)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  (略)

$ readelf -h /lib/x86_64-linux-gnu/libc-2.19.so
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  (略)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              DYN (Shared object file)
  (略)

ここで注目すべきはTypeである。readelf -hの結果を見ると、libc-2.19.soとpieはDYN (Shared object file)、nopieはEXEC (Executable file)となっていることが分かる。
shared objectというのはおそらく共有オブジェクトのことであるので、libc-2.19.soとpieは共有オブジェクトであり、nopieはそうでないことが分かる。
よって、「PIEを有効にしたことにより、出力が共有オブジェクトになった」ということがわかり、出力が共有オブジェクトになった結果、上で示したスライドの「共有オブジェクト領域」に配置されるようになったのではないか、と思うことができる。

結論として、「私がこのソースコード、出力を見て、上に述べた実験をして思ったこと」は、
このプログラムはスタック領域にint10個分の配列、ヒープ領域に1バイトのメモリを確保し、そのアドレスを表示するプログラムであるが、PIEが有効であるため実行ファイルがスタックの比較的近く(共有オブジェクト領域)にロードされ、結果としてヒープとスタックがかなり近い場所に発生したことを表す出力が得られたものである。と思った。

選択問題3(edited)

出題者はUSBメモリからブートする講義の人だとエスパーしたのですがどうなんですかねという感じ。
ここだけの話をするとGWにx86エミュレータを作る本を買って作りながら書いていたのですが、この問題に関しては本とネットで調べた内容を羅列するだけにとどまってしまった気がします。

問題:
RAMは主記憶装置、HDDやSSDなどは補助記憶装置と呼ばれます。一般にCPUは主記憶装置上のプログラムしか実行できません。ではなぜ、私たちは普段から補助記憶装置に書き込んだプログラムを実行できているのでしょうか?パソコンの電源を入れてからのストーリーを考えてみてください。

回答:
問題文でも述べられている通り、CPUはRAM(主記憶装置)の上にあるプログラムしか実行できない。普通に考えれば、WindowsやLinuxなどのOSがプログラムをRAMの上にロードし、それを実行している、と考えるところである。しかし、WindowsやLinuxなどのOS自体がHDDやSSDなどの補助記憶装置の上に保存されているため、そのOS自体はどのプログラムがRAMにロードするのか?という問題が浮上する。
そこで、「パソコンの電源を入れてからのストーリーを考えよ」という問題に沿って、以下の二つに問題を分けて考えてみようと思う。
I.パソコンの電源を入れてからOSがRAMにロードされ、実行されるまで
II.OSが起動してから、一般的なソフトウェアがRAMにロードされ、実行されるまで
以下はこの二つのプログラムの起動についてそれぞれ議論していこうと思う。
I.パソコンの電源を入れてからOSがRAMにロードされ、実行されるまで
前述の通り、OS自体もHDDやSSDなどの補助記憶装置に保存されているため、直接実行することはできない。なので、最初からRAMに「OSをロードするような」何らかのプログラムがロードされているのではないか、と考えた。しかし、RAMは揮発性メモリなので、電源が入っていない間は情報を保持することができないはずである。ではどうしているのだろうか、と考えて、その点を書籍やインターネットで調べてみたところ、「不揮発性メモリに保存されている」二つのソフトウェアに突き当たった。それがBIOSとUEFIである。
パソコンの電源を入れて一番最初に実行されるのは、OSではなく、BIOSやUEFIといったようなソフトウェアである。これらのソフトウェアは、不揮発性メモリに保存されており、これはRAMと同じ主記憶装置として扱われるものなので、パソコンの電源を入れてすぐに実行することができる。
ここでは、一例としてBIOSからMBR(マスターブートレコード)の存在するドライブを起動する場合について述べることとする。
BIOSは、①起動可能なデバイス(HDD、SSD、USBメモリ、など)を探し、②最初に見つけた起動可能なデバイスのブートセクタ(デバイスの先頭512バイト)をメモリの0x7C00番地にロードし、そこに処理を移す。
なお、①の「起動可能なデバイスを探す」というのは、具体的には、各デバイスのブートセクタを確認し、ブートシグニチャ(0xAA55)があるかどうかを確認する(あったら起動可能である)という作業である。
ここで、HDDやSSDのように複数パーティションを持つドライブの場合、主記憶装置に読み込まれるのはMBR(マスターブートレコード、以下MBR)である。MBRは、MBRに含まれるパーティション情報を読み込み、起動可能なパーティションを探す。起動可能フラグが立っているパーティションを見つけたら、そのパーティションに含まれるブートローダーを主記憶装置に読み込み、制御を読み込んだプログラムに移す。
ここでメモリに読み込まれるのがブートローダーであり、次に実行されるものである。
ブートセクタから読み込まれるブートローダーはまだOSを起動するものではない。
それは、近年のOSは複雑化しており、ロードの処理をデバイスの先頭512バイトであるブートセクタに収めるのは難しいため、ブートセクタから読み込まれるローダーは二段階目のローダーを主記憶装置に読み込むだけのプログラムにしておいて、二段階目のローダーでOSを主記憶装置に読み込む、という仕組みになっていることが多いからである。
ブートローダーは、二段階目のローダーをまた0x7c00番地に配置するために、自分自身を0x600に移動し、その後で二段階目のローダーを0x7c00に読み込み、制御をそこに移す。
ブートローダーによって読み込まれた二段階目のローダー(OSを読み込むもの)によっていよいよOSが主記憶装置にロードされ、OSが立ち上がる。
このような一連の処理のことをブートストラップという。
ここでは触れなかったが、UEFIについても、「コンピュータの起動における役割においては」同じであり、OSの読み込みである。
ただし、UEFIは、512バイトの制限があるMBRではなく、ディスクの第一パーティションをFAT32でフォーマットし、システムパーティションとしたものの中にブートローダーを置く。UEFIは、APIを扱うためのSDKが公開されており、C言語でブートローダーを記述することも可能である。
MBRのように512バイトの制限がないため、上で述べたような多段階のロードを行う必要がないので、一つのプログラムでOSをロードできる上に、そのプログラムもC言語のような高級言語で記述できるため、UEFIの上で動作するプログラムは記述しやすいというメリットがある。
II. OSが起動してから、一般的なソフトウェアがRAMにロードされ、実行されるまで
OSが起動しても、主記憶装置にないプログラムは実行することができない。我々がC言語などで書き、コンパイル、リンクして生成した実行ファイルも、HDDやSSDなどの補助記憶装置に保存されるため、直接は実行できないことになる。以下は、このような実行ファイルがOSのもとでどのように実行されるかを述べたいと思う。
そもそも、以上のようにして生成されたファイルはあくまでファイルであり、それ自身をCPUが機械語として読み込んで実行できるわけではない。
補助記憶装置上に保存されたファイルを実行すると、すでに立ち上がっているOSがメモリ、入出力、CPUなどのリソースを与え、実行ファイルや必要なライブラリなどが与えられたメモリにロードされることにより、プロセスが発生する。これにより、実行ファイルに記録されていた機械語が主記憶装置にロードされたため、これは機械語として実行することができ、ソフトウェアを利用することができる。
メモリ上にロードされたプログラムは、まず、フェッチ(プログラムカウンタが指すメモリの値にある機械語を読み込む作業)され、CPUに読み込まれる。次に、読み込まれた命令はデコード(読み込んだ機械語命令が何を意味しているか解析する作業)され、実行する準備が行われる。ここでプログラムカウンタを進める作業が行われる。最後に、読み込んだ命令を実行する。これを繰り返すことで、CPUによって機械語プログラムが実行される。このことを、フェッチ実行サイクルという。
これは、メモリ上にロードされたプログラムであれば、OSであっても我々が作成した実行ファイルであっても同じである
まとめると、
I:電源を入れると、不揮発性メモリに入ったソフトウェアから、小さい機械語プログラムを順番に読み込んでいき、読み込まれたローダーによって大きなOSが起動する。
II:用意された実行ファイルはOSからリソースをもらい、プロセスとなって実行される。
(補足:)OSや実行ファイルなどのプログラムは、以上に述べたようなフェッチ実行サイクルによってCPUに読み込まれ、実行されていく。
ということである。

選択問題4(edited)

みんな大好きごちうさ問題。問題に変なところがあり、問い合わせるも一度は「公平性のため解答できません」的な返答が返ってきて困った。

確かに一人に答えるのは不公平だなあ、などと思いながらコードを書いていたら問題が修正されたのでよかったです。(こなみ)

作問者曰く曖昧な部分(回答で「曖昧なので、このように解釈した」と述べた部分)は意図的に曖昧にしていたらしいです。意図に気づかずお問い合わせからclarを投げてしまったのでつらい。






赤字が問題の修正部分。

問題:

突然だが、RH Protocolで用いられるRHパケットのフォーマットを以下に示す。なおRH Protocolは実在しないプロトコルであり、その内容について特に意味は無い。

Format of RH Packet

|————————|—————...—|———————…—|———————...—|———————...—|

|  Magic (2byte)     | Source(20byte)|Destination(20byte)| Data Length(4byte)| Data( variable )      |

|————————|—————...—|———————…—|———————...—|———————...—|

 

char Magic [2];

char Source[20]; /* null(‘\0’) terminated ascii strings */

char Destination[20]; /* null(‘\0’) terminated ascii strings*/

uint32_t DataLength; /* min 0, max 4,294,967,295 */

char Data[DataLength]; /* null(‘\0’) terminated ascii strings */

 

バイトオーダーはbig endian(network byte order)とする。

 

添付するバイナリは、とあるRHストリームのうち片方向のみを抽出したものである。このバイナリストリームを読み込み、1つのRHパケットが以下の条件のすべてにマッチするときに標準出力に文字列”PASS”、 それ以外の場合は”REJECTED”と表示するCもしくはC++のプログラムを記述し、実行結果と共に提出せよ。また、マッチングにかかるCPUサイクル及びメモリ使用量を計測し記載した場合、評価に加味する。

 

Condition(条件)1: Magicがchar[0] = ‘R’、 char[1] = ‘H’であること。

Condition 2: Sourceが”rise-san”または”cocoa-san”であること。なお、”RiSe”や”Cocoa”など、小文字大文字が混ざっていても、マッチさせること。

Condition 3: Destinationが”Chino-chan”または”Chino"であること。なお、cond. 2と同じく、小文字大文字が混ざっていても、マッチさせること。

Condition 4: Sourceが”cocoa-san”かつDestinationが”Chino”の場合はREJECTする。

Condition 5:  Dataに下記の文字列を厳密に含むこと。

char** valid_order_brand =

{

    “BlueMountain"

    “Columbia”,

    “OriginalBlend"

};

Condition 6: Dataに下記の文字列を厳密に含まないこと。なお、cond. 5よりも、cond. 6が優先される。

char** invalid_order_brand =

{

    “DandySoda"

    “FrozenEvergreen”
};


回答:

ソースコードとコメントに全て書いたためそれを載せる。



選択問題8

頑張ってアセンブリ言語を読む問題。

本質じゃなさそうでも不思議に思ったところを全部挙げて調べるよう心がけました。
ROPにおいてスタックポインタの減算とレジスタのデクリメントでループを表現してるのは結構面白いです。
あとasciiで機械語を直打ちすることを思いついたのはちょっと褒めてほしい。

問題:

以下のダンプはあるプログラムのobjdumpの結果である。このプログラムが行っていることを調べ、その結果を記述してください。完全には分からなくても構いませんので、理解できたところまでの情報や調査の過程で使ったツール、感じたこと等について記述してください。
==
$ objdump -d challenge00

challenge00:     ファイル形式 elf64-x86-64

セクション .text の逆アセンブル:

0000000000400080 <.text>:
 400080:    68 19 01 40 00           pushq  $0x400119
 400085:    6a 01                    pushq  $0x1
 400087:    68 06 01 40 00           pushq  $0x400106
 40008c:    68 19 01 40 00           pushq  $0x400119
 400091:    68 29 01 40 00           pushq  $0x400129
 400096:    6a 3c                    pushq  $0x3c
 400098:    68 02 01 40 00           pushq  $0x400102
 40009d:    68 10 01 40 00           pushq  $0x400110
 4000a2:    48 b8 36 15 1b 25 67     movabs $0x63391a67251b1536,%rax
 4000a9:    1a 39 63
 4000ac:    50                       push   %rax
 4000ad:    68 02 01 40 00           pushq  $0x400102
 4000b2:    6a 00                    pushq  $0x0
 4000b4:    68 06 01 40 00           pushq  $0x400106
 4000b9:    68 14 01 40 00           pushq  $0x400114
 4000be:    68 0c 01 40 00           pushq  $0x40010c
 4000c3:    68 02 01 40 00           pushq  $0x400102
 4000c8:    68 26 01 40 00           pushq  $0x400126
 4000cd:    68 14 01 40 00           pushq  $0x400114
 4000d2:    6a 07                    pushq  $0x7
 4000d4:    68 0a 01 40 00           pushq  $0x40010a
 4000d9:    6a e0                    pushq  $0xffffffffffffffe0
 4000db:    68 08 01 40 00           pushq  $0x400108
 4000e0:    68 19 01 40 00           pushq  $0x400119
 4000e5:    6a 08                    pushq  $0x8
 4000e7:    68 04 01 40 00           pushq  $0x400104
 4000ec:    6a 00                    pushq  $0x0
 4000ee:    68 1c 01 40 00           pushq  $0x40011c
 4000f3:    6a 00                    pushq  $0x0
 4000f5:    68 06 01 40 00           pushq  $0x400106
 4000fa:    6a 00                    pushq  $0x0
 4000fc:    68 02 01 40 00           pushq  $0x400102
 400101:    c3                       retq 
 400102:    58                       pop    %rax
 400103:    c3                       retq 
 400104:    5a                       pop    %rdx
 400105:    c3                       retq 
 400106:    5f                       pop    %rdi
 400107:    c3                       retq 
 400108:    5d                       pop    %rbp
 400109:    c3                       retq 
 40010a:    59                       pop    %rcx
 40010b:    c3                       retq 
 40010c:    48 01 ec                 add    %rbp,%rsp
 40010f:    c3                       retq 
 400110:    48 39 06                 cmp    %rax,(%rsi)
 400113:    c3                       retq 
 400114:    80 34 0e 55              xorb   $0x55,(%rsi,%rcx,1)
 400118:    c3                       retq 
 400119:    0f 05                    syscall
 40011b:    c3                       retq 
 40011c:    48 89 e6                 mov    %rsp,%rsi
 40011f:    41 5a                    pop    %r10
 400121:    c3                       retq 
 400122:    48 89 f1                 mov    %rsi,%rcx
 400125:    c3                       retq 
 400126:    48 ff c9                 dec    %rcx
 400129:    75 01                    jne    0x40012c
 40012b:    c3                       retq 
 40012c:    41 5a                    pop    %r10
 40012e:    c3                       retq 
==


回答:

まず、始めにこのアセンブリコードを見た時、

前半はほぼpush(q)命令、後半はpop命令とret命令が目立つ、という感想を抱いた。
また、前半のpushq命令の中で一つだけmovabs命令
4000a2:    48 b8 36 15 1b 25 67     movabs $0x63391a67251b1536,%rax
が存在するがこのとき%raxに入れている値は何だろう、と疑問に思ったが、直後で
4000ac:    50                       push   %rax
としているので、64bitの即値をpushすることはできないが、%raxにmovすることはできるので、一度raxに入れてからpushしているのだろうか、と思った。
しかし、後に
4000d9:    6a e0                    pushq  $0xffffffffffffffe0
とあるのを見て違うと思い、なぜ一度raxに入れたのだろう、と思った。
これについて調べたところ、このような回答(http://stackoverflow.com/questions/13351363/push-on-64bit-intel-osx)を発見することができ、「pushqでは、0によって符号拡張される32bitの正値と1によって符号拡張される32bitの負値しかとることができない」ということを知ることができた。
つまり、$0xffffffffffffffe0は1によって符号拡張された負値であるのでpushqのオペランドになることができるが、 $0x63391a67251b1536は符号拡張された負値でも正値でもないのでpushqのオペランドになることはできない、ということである。
また、movは例外で64bitの即値をとることができる、ということも分かった。

実際に以下のようなアセンブリコードを用意して
-82.s-
text:
pushq $0x63391a67251b1536
pushq $0xffffffffffffffe0
$gcc -nostdlib -o tes  82.s
とアセンブルしたところ、pushq $0x63391a67251b1536をコメントアウトしない場合は82.s:2: Error: operand type mismatch for `push'
というエラーが発生し、コメントアウトした場合は正常にアセンブルすることができた。
結局、行っていることとしては64bitの値をスタックにpushしている、ということなのだが、疑問が解決し、嬉しい気持ちになった。

以上のことから、前半はスタックに値を入れており、後半は多くのpopとretが存在しているということに注目し、私はReturn-oriented Programming(以下ROP)のようなことを行っているのではないか、と考えた。
ROPとは、スタックから値を一つ取り出してレジスタに格納するpop hoge(hogeはレジスタ)とret(スタックから値を一つ取り出してripに格納)という命令を組み合わせてスタックを調整しながらプログラムを進める手法である。
今回はx86-64のバイナリだが、関数の引数をスタックに積むことが多い32bit Linuxにおいては、関数の引数を比較的自由に設定してプログラムを実行できる上に、メモリにロードした実行ファイル中の機械語を実行するため、NXビットが立っているためにスタック上に置いた機械語を実行できない場合の攻撃手段としてよく用いられるものである。
スタックは後入れ先出しのデータ構造であるため、popすると最後にpushしたものが取り出されることを考えると、0x4000fcまでにpushされた値はpushされたのとは逆の順番で出てくる。なので、retやpopによって、0x400102、0x0、0x400106、0x0……というようにpushしたのとは逆順に値が取り出され、処理が進んでいくと考えられる。

ここまで考えたところで、デバッガを使って実行してみることにした。この際、アドレスを即値でスタックにpushしているため、objdumpした時に問題と全く同じ出力が得られる実行ファイルを用意しないとうまく動作しないことが考えられたため、
text:
        .ascii "\x68\x19\x01\x40\x00\x6a\x01\x68\x06\x01\x40\x00\x68\x19\x01\x40\x00\x68\x29\x01\x40\x00\x6a\x3c\x68\x02\x01\x40\x00\x68\x10\x01\x40\x00\x48\xb8\x36\x15\x1b\x25\x67\x1a\x39\x63\x50\x68\x02\x01\x40\x00\x6a\x00\x68\x06\x01\x40\x00\x68\x14\x01\x40\x00\x68\x0c\x01\x40\x00\x68\x02\x01\x40\x00\x68\x26\x01\x40\x00\x68\x14\x01\x40\x00\x6a\x07\x68\x0a\x01\x40\x00\x6a\xe0\x68\x08\x01\x40\x00\x68\x19\x01\x40\x00\x6a\x08\x68\x04\x01\x40\x00\x6a\x00\x68\x1c\x01\x40\x00\x6a\x00\x68\x06\x01\x40\x00\x6a\x00\x68\x02\x01\x40\x00\xc3\x58\xc3\x5a\xc3\x5f\xc3\x5d\xc3\x59\xc3\x48\x01\xec\xc3\x48\x39\x06\xc3\x80\x34\x0e\x55\xc3\x0f\x05\xc3\x48\x89\xe6\x41\x5a\xc3\x48\x89\xf1\xc3\x48\xff\xc9\x75\x01\xc3\x41\x5a\xc3"
以上のようなアセンブリコードを用意し、gcc -nostdlib -Wl,-Ttext-segment=0x3fffac 81.sでエントリポイントまでしっかり合うようにアセンブルした。環境はLinux Mint 17.1 64bitを使用した。
機械語を.asciiで直打ちした理由は、与えられたアセンブリ言語をgccでアセンブルすると、0x400129番地の機械語が
400129:0f 85 fd ff ff ff    jne    40012c <text+0xac>
と、命令は同じだが問題とは違う機械語になってしまい、それ以降の命令のアドレスがずれてしまいうまく動作しなかったためである。
以降にデバッガ(gdb)で実際に動作させながら動作を解析した結果を記す。以下はすべてのソースコードを示すのではなく、アルゴリズムとして重要な部分のみ抜粋することとする。
また、以下のアセンブリ言語については、私が普段使っているintel記法で議論する。

0x4000fcのpush  0x400102が終わった直後のretにおいて、スタックの一番上には$0x400102が入っているため、後半は0x400102に飛ぶ(retする)所から処理が始まる。
その後、
400102:pop    rax
400106:pop    rdi
40011c:mov    rsi,rsp
40011f:pop    r10
400104:pop    rdx
400119:syscall
というように(retは省略している)スタックから値を取り出しレジスタに格納(mov rsi,rspはスタックポインタをrsiに格納)、スタックからretによる戻り先を取り出してそこにジャンプする、ということを繰り返しながらプログラムが進み、一回目のsyscallが呼ばれる。
この時、rax=0x0,rdi=0x0,rsi=0x7fffffffdfc8,rdx=0x8となっており、このサイト(http://www.mztn.org/lxasm64/x86_x64_table.html)に基づいてC言語に直すと、システムコールの0番はreadであることを考えて、
read(0,buf,8)ただし、buf=0x7fffffffdfc8(これはスタック上を指している)
となる。つまり、標準入力から最大8バイトを0x7fffffffdfc8に読み込むというプログラムになる。
さらに処理を追っていくと、rbpにスタックから0xffffffffffffffe0を、rcxにスタックから0x7をポップし、
0x400114:xor    BYTE PTR [rsi+rcx*1],0x55
0x400126:dec    rcx
0x400129:jne    0x40012c <text+172>
0x40012c:pop    r10
0x40010c:add    rsp,rbp

を繰り返すことで、入力された文字を一文字ずつ(rcxが0になるまで)0x55とXORしていく、ということが分かる。(rsiには入力された文字列のアドレスが入っている)
このとき、add    rsp,rbpによってスタックポインタ(スタックの一番上、次に出てくるデータを指す)に0xffffffffffffffe0(これは2の補数表現の-0x20である)を足すことでrspから0x20を引き、xor    BYTE PTR [rsi+rcx*1],0x55以降の一連の処理で変化したスタックポインタをxorを行う直前の値まで戻し、その後retすることでループを実現している。

rcxが0になり、
0x400129:jne    0x40012c <text+172>
のジャンプが発生しないと、
0x40012b:ret
により
0x400102:pop    rax(このpop raxはうまく0x400114にretするためにスタックを調整するものだと思われる)
0x400114:xor    BYTE PTR [rsi+rcx*1],0x55
で8回目の(最後の)xorが行われ、
入力文字列を0x55とXORする処理が終わったのち、
0x400106 <text+134>:pop    rdi
でrdiに0x0がスタックから格納され、
0x400102:pop    rax
でraxに0x63391a67251b1536がスタックから格納され、
0x400110:cmp    QWORD PTR [rsi],rax
で先ほど入力文字列を一文字ずつXORしていった値と比較される
その比較結果は、
0x400129:jne    0x40012c <text+172>
で使われ、比較結果が一致ならば
0x40012b:ret
により
0x400119:    syscallへ、
そうでないなら
0x40012c:pop    r10へジャンプする。
このとき、raxには0x3bが入っており、これはexitのシステムコール番号である。一致ならば第一引数であるrdiはこの時点で0x0が入っているのでexit(0)が呼ばれ、プログラムは正常終了する。
一致しない場合、その後に(pop    r10によるスタックの調整を経て)到達する
0x400106:pop    rdi
により0x1がrdiに入り、その後システムコールが呼ばれexit(1)となり異常終了となる。
では、どのような文字列を入れれば正常終了するのだろうか。
XORの「同じ数ともう一度XORすると元の数に戻る」という性質を考えると、0x63391a67251b1536について、数字二つずつ0x55とXORしてみれば良さそうである。
また、エンディアンを考えて、逆順にすることも考えると、pythonを使って
>>> s="63391a67251b1536"
>>> cy= [(i+j) for (i,j) in zip(s[::2],s[1::2])]
>>> pl=map(lambda x: int(x,16)^0x55,cy)
>>> pl
[54, 108, 79, 50, 112, 78, 64, 99]
>>> pl.reverse()
>>> "".join(map(chr ,pl))
'c@Np2Ol6'
より、「c@Np2Ol6」と入力すれば終了コード0で終了するとわかる。
実際、gdbでc@Np2Ol6と入力したときとそうでない時を比べると、終了コードが異なっていることがわかる。

まとめると、
・このプログラムはreadで8バイトの入力を受け付け、それが"c@Np2Ol6"と一致している時のみ正常終了するプログラムである。
・ただし、比較文字列は0x55とXORされた値がプログラムの中に入っており、入力文字列を一文字ずつ0x55とXORしてから比較している。
ということである。
ここで、比較文字列が0x55とXORされている、というのは、実行ファイルをバイナリエディタなどで見られた時に文字列が見られてしまわないようにするためなのだろうか、と思った。