自作Cコンパイラで Ken Thompson のログインハックを再現してみた

UNIX 開発者の一人である Ken Thompson が初期の UNIX にバックドアを仕掛けていたと言われている通称 Thompson hack を自作Cコンパイラで再現してみました。 Thompson hack は UNIX のログイン処理のコンパイル時にバックドアを仕掛けるようなコンパイラを作り、さらにコンパイラのソースコードからその痕跡を消し去るという神業です。

元ネタは Reflections on Trusting Trust という1983年に Ken Thompson が Dennis Ritchie と共にチューリング賞を受賞した際の記念公演です。 Ken Tohmpson はこの細工をしたコンパイラを配布したことはないと主張しているそうですが、このバックドアを利用したと見られる不審なログインがあったという報告もあったとのことで、実際にはベル研究所の外部に配布されていたのではないかとも言われているようです。軽く調べただけなので真偽はわかりません。

今回の再現は GitHub 上で閲覧可能です、詳しく見てみたい方はどうぞ。自作のCコンパイラが Mac では動かないので、実際に試してみたい方は Linux 環境でお願いします。

github.com

再現に用いるCコンパイラ

この再現では随所で自分自身のソースコードをコンパイルする(セルフホスト)を行うので、セルフホストが可能なコンパイラを用いる必要があります。加えて、Cコンパイラの内部的な処理とどういうアセンブリが出力されるのかを十分に理解している必要があります。

というわけで今回はセルフホスト可能な自作のCコンパイラを用いることにします。最初に gcc で正常なコンパイラのソースコードをコンパイルして cc という自作コンパイラの実行ファイルを用意しておきます。このCコンパイラはC言語のプログラムを読んでアセンブリを出力します。アセンブリを実行ファイルに変換する部分では gcc の力を借りています。

# gcc で自作コンパイラをコンパイル
$ make cc

ターゲットとするプログラム

以下のような login.c という簡単なログイン処理を今回はターゲットにします。実際にはこんな簡単なはずはないんですが、そこは今回の本質ではないのでご容赦ください。

/* login.c */

int scanf(char *format, ...);
int printf(char *format, ...);
int strcmp(char *s1, char *s2);

int login(char *password) {
  if (strcmp(password, "my_password") == 0) {
    printf("successfully logined.\n");
  } else {
    printf("failed.\n");
  }
}

int main() {
  char password[32];
  printf("type password: ");
  scanf("%s", password);
  login(password);
}

入力された文字列が my_password であればログイン成功、そうでなければ失敗というプログラムです。このプログラムを正常なコンパイラでコンパイルして my_password でしかログインできないことを確認します。

# cc で login.c をコンパイル
$ make login
$ ./login
# my_password を入力
type password: my_password
successfully logined.
$ ./login
# you_are_hacked を入力
type password: you_are_hacked
failed.

今ログインに失敗した you_are_hacked というパスワードでログインできるようコンパイラに仕掛けをするのが今回のゴールです。

login 関数を別の処理に置き換えるコンパイラを作る

例えば、悪い人が you_are_hacked というパスワードでもログインできるようにするために login 関数を以下のように書き換えたとします (login_evil.c)。

/* login_evil.c */

int login(char *password) {
  if (strcmp(password, "my_password") == 0 ||
      strcmp(password, "you_are_hacked") == 0) {
    printf("successfully logined.\n");
  } else {
    printf("failed.\n");
  }
}

当然これでログインできるようになるわけですが、さすがにソースコードを見れば一発でバレてしまいます。そこでこれををコンパイルしてできるアセンブリ (login_evil.s) をコンパイラのコード生成部分に埋め込んでしまいます。関数定義の生成を行う関数 (gen.c の gen_func_def) を書き換えて login という関数名がきたら login_evil.s の中身を printf で出力するようにします (gen_func_def_evil.c)。

/* gen_func_def_evil.c */

void gen_func_def(Node *node) {

  /* login という関数がきたら */
  /* login_evil.s のアセンブリを吐き出す */
  if (strcmp(node->identifier, "login") == 0) {
    printf(" .text\n.XLC0:\n .string \"my\\137password\\000\"\n.XLC1:\n .string ......");
    return;
  }

  /* 正常なコンパイル処理 */
  ......
}

これと他のソースコードを合わせて gcc でコンパイルし cc_evil という実行ファイルを生成します。 cc_evil は login 関数を不正なアセンブリで置き換え you_are_hacked でのログインを可能にするコンパイラです。

# cc_evil を gcc でコンパイル
$ make cc_evil
# login.c を cc_evil でコンパイル
$ make login_by_evil
$ ./login_by_evil
# you_are_hacked でログインできる
type password: you_are_hacked
successfully logined.

当然 login.c にはなんの痕跡も残っていません。 cc_evil をバイナリで配布すればバックドアがバレる可能性は低いでしょう (現代なら普通にバレそうですが実際のところはどうなんでしょう？)。しかし、この cc_evil で元の正常なコンパイラのソースコードをコンパイルして置き換えられると、それ以降はバックドアを仕込めなくなってしまいます。かと言ってコンパイラのソースコードを gen_func_def_evil.c のように書き換えたままでは、ソースコードを読まれていずれバレてしまいます。

さて、ここからが Thompson hack のヤバいところです。 Ken Thompson はこの login 関数を書き換える性質がセルフコンパイル時に受け継がれるような細工を施しソースコードから痕跡を完全に消し去ったのです。

コンパイラのソースコードから痕跡を完全に消し去る

ソースコードから痕跡を完全に消し去るために Ken Thompson が用いたのはクワインです。クワインというのは、自分自身のソースコードと全く同じ文字列を出力するプログラムのことです。 Reflections on Trusting Trust の中では self-reproducing program と呼ばれています。

例えば、C言語でのクワインは以下のようなものがあります。

int main() { char *s = "int main() { char *s = %c%s%c; printf(s, 34, s, 34); }"; printf(s, 34, s, 34); }

クワイン (プログラミング) - Wikipedia より

Thompson hack ではコンパイラ自身のプログラムが現れたら自分自身と全く同じコードを埋め込むという条件付きのクワインを使うことでソースコードから痕跡を消しつつ、セルフホストしても login を書き換える性質を引き継がせる仕組みになっています。

今回の再現ではアセンブリのクワインを書いてこれを実現したいと思います。アセンブリのクワインの基本形は quine.s を参照してください。

まずは gen_func_def_very_evil.c というファイルを作り以下のようなプログラムを書いておきます。

/* gen_func_def_very_evil.c */

void gen_func_def(Node *node) {

  /* login という関数がきたら */
  /* login_evil.s のアセンブリを吐き出す */
  if (strcmp(node->identifier, "login") == 0) {
    printf(" .text\n.XLC0:\n .string \"my\\137password\\000\"\n.XLC1:\n .string ......");
    return;
  }

  /* printf("quine"); */
  /* と書かれているところを */
  /* アセンブリに変換した後で書き換える */
  if (strcmp(node->identifier, "gen_func_def") == 0) {
    printf("quine"); 
    return;
  }

  /* 正常なコンパイル処理 */
  ......
}

そしてこれをコンパイルして出来たアセンブリファイル (gen_func_def_very_evil.s) をクワインになるように書き換えます。 gen_func_def という関数が出てきたら自身と全く同じ文字列を出力するというアセンブリに書き換えたものが gen_func_def_very_evil_quine.s です。あとは他のソースコードと合わせてコンパイルします。これで何度セルフホストしても login 関数を書き換えるような性質が受け継がれる非常に邪悪なコンパイラのバイナリ (cc_very_evil) が手に入ります。

# gen_func_def_very_evil.s と他のソースコードを
# gcc でコンパイルして cc_very_evil を生成
$ make cc_very_evil

実際に cc_very_evil を使って正常なソースコードをコンパイルしてできた実行ファイル (cc_hacked) を使って login.c をコンパイルしてみます。

# cc_very_evil で元の正常なソースコードをコンパイル
$ make cc_hacked
# cc_hacked で login.c をコンパイル
$ make login_by_hacked
$ ./login_by_hacked
# you_are_hacked でログインできる
type password: you_are_hacked
successfully logined.

you_are_hacked でログインに成功しました。さらに cc_hacked でもう一度セルフホストしてできた実行ファイル (cc_hacked_hacked) で login.c をコンパイルしてみます。

# cc_hacked で元の正常なソースコードをコンパイル
$ make cc_hacked_hacked
# cc_hacked_hacked で login.c をコンパイル
$ make login_by_hacked_hacked
$ ./login_by_hacked_hacked
# you_are_hacked でログインできる
type password: you_are_hacked
successfully logined.

セルフホストをしても login.c を不正に書き換える性質が引き継がれているのが確認できます。当然のごとく login.c のソースコードにもコンパイラのソースコードにも痕跡は残っていません。これが Thompson hack です。

このバイナリを配布したら、当時であれば様々な UNIX システムにログインができたかもしれません。実際に Ken Thompson がそれをやっていたかどうかは僕にはわかりません。僕が言えるのはただひとつ、こんなことを思いつく Ken Thompson は明らかに天才だということだけです。

まとめ

Thompson hack はソースコードに痕跡を残さずに特定のプログラムを好きに書き換えられるという驚くベきテクニックです。

もしかしたら既存のコンパイラは全てハックされていて、OSやディスアセンブラのようなセキュリティ的に重要なあらゆるプログラムが書き換えられていたりするのかもしれない............というのはさすがに陰謀論すぎですね。

0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

自作Cコンパイラで Ken Thompson のログインハックを再現してみた

再現に用いるCコンパイラ

ターゲットとするプログラム

login 関数を別の処理に置き換えるコンパイラを作る

コンパイラのソースコードから痕跡を完全に消し去る

まとめ