「Trusting Trust」攻撃に対抗する

シュナイアーさんによるblogエントリ( https://www.schneier.com/blog/archives/2006/01/countering_trus.html )は、もう10年も前ですので、その世界では特に新しい話題というわけではないようですが、私が知ったのは今年のはじめのことでしたので*1、この機会に紹介する文章を書いてみたいと思います。

Unixを作ったケン・トンプソンさんがチューリング賞を受賞された際の講演「信用を信用することができるだろうか」( Reflections on Trusting Trust )は、その暴露的な部分(UNIXのloginコマンドにバックドアがあった、とする)の真偽はさておき、もしコンパイラのバイナリが「信用できない」ものだったら、という場合における、潜在的な脅威の可能性を否定することの難しさの指摘でした。*2

以下で述べる話題は、直接的な「コンパイラのバイナリを精読する」といった手段と比べると、大幅に省力的で、また、そのような可能性に対してある種の「相対的」安全性という考え方を示すものにもなっています。

詳細は、デイヴィッド・ホイーラーさん*3D論 Fully Countering Trusting Trust through Diverse Double-Compiling( http://www.dwheeler.com/trusting-trust/dissertation/html/wheeler-trusting-trust-ddc.html )となっていて、だいぶ大部ですが(私も全部は追いきれていません)、基本的なアイディアのスケッチは、けっこう以前からUSENETで議論されていたという程度には、簡単なものです。

まず基本的な問題について確認

トンプソンさんの講演の詳細を知っている方は、この節は飛ばして問題ありません。

しばしば、オープンソースのプロダクトは、たくさんの目でソースコードがチェックされているのだから安心だ、と主張されます。その当否はともかくとして、その大前提に、コンパイラは絶対に信用できるものだ、という仮定があります。

しかし、本当にコンパイラは信用できるのでしょうか? 噂では、性能比較に使われるベンチマークプログラムはその目的上、共通のものが広く公開されているので、そのパターンを検出して特別な最適化を掛ける、というチートが仕込まれていたコンパイラがあった、といいます。もしそれが単なる最適化ではなく、対象にバックドアを仕込むようなものだったら?

コンパイラだってオープンソースコンパイラなんだから大丈夫! でもそのコンパイラコンパイルするコンパイラに何か仕込まれていたら? 理屈では、一種の自己再生プログラム(いわゆるクワイン)のテクニックを利用して、ソースコードには何の痕跡も残さずに、コンパイラのバイナリから、それによってコンパイルされた、次の世代のコンパイラのバイナリへ、と、悪意を持ったコード片を「感染」させ続けることが可能です(プログラムのテクニック自体としては、一種のパズルのようなものとして知られていたものではあるものの、そのようにセキュリティに対する深刻な脅威として、可能性があると(広く注目されるような場で)示したのが、トンプソンさんのチューリング賞講演でした)*4*5

すぐに思いつく対抗法

コンパイラのバイナリを精読してチェックする(ブラックボックスチェック)、あるいはソースコードとの対応が取れているかチェックする(ホワイトボックスチェック)というあたりが、まず思い浮かぶでしょう。それができればそれに越したことはありませんが、たとえばGCCなど、実際に使われているコンパイラはそれなりに大きく、大変な作業です。プログラムでできないか、と考えるかもしれません。いい着目点ではありますが、やはりそのプログラムは信頼できるのか、ということになります。

あるいは、コンパイラではなくインタプリタを使おう、と思うかもしれません。しかし、そのインタプリタコンパイルするコンパイラが、ということになります。問題の場所は移動しますが、必要な作業はそんなに変わらない、ということになります。

ここで、GCCの昔話を

今では多くのUnixライク環境で、バイナリパッケージによるインストールは当たり前のものとなりました。何らかのプログラミング言語の処理系を「野良ビルド」するにあたり、いわゆるセルフホスティングであったり、そうでなくても自分自身のビルドに自分自身が必要であっても、まずバイナリパッケージを使って簡単に必要な環境を作ることができます。

昔は、なんでも野良ビルドが当然であり、わざわざ「野良」などと付けるようになったのもある時代以降ではなかったか、というような記憶があります。そして、難しさの点で大物*6のひとつが「プロプライエタリUNIX環境へのGCCの導入」でした。

普通のやりかたとしては、GCCのバイナリを、同じ環境を使っている他のユーザからGNUの助け合いの精神にもとづきコピーしてもらってくれば良いわけですが、全く同じ環境というのもなかなか無かったりするわけで、いわゆる「言語処理系のブートストラップ」の一種のような作業で「最初のGCCのバイナリ」を得ることになります。

今でもGCCのビルドの説明には、ステージという表現が使われていますが、この時代には次のような意味がありました。

stage1で得られるのはGCCによるコンパイル結果ではありませんから、バイナリ的にも違ったものなはずです(一種のキメラ的存在と言えるかもしれない)。一方、stage2とstage3は、どちらもGCCによるコンパイル結果ですから、結果は一致するはずです(理論的には一種の「不動点」)。結果が一致しても、必ずしも問題が無いとは言い切れませんが、結果が一致しなければ高い確率で問題が存在するはずです。

ここで注目すべきなのは、このプロセスは「何らかの既存のGCCバイナリ」に依存していない、という点です。これを利用したのが Diverse Double-Compiling による、Trusting Trust 攻撃への対抗だ、ということになります。

図法の導入

伝統的な「T図式」( T diagram )というものもありますが、ここでの議論には少し向いてない面があるので、次のような図法を使います( Fully Countering Trusting Trust through Diverse Double-Compiling の、§4.1 にある図)。

中央の四角がコンパイルプロセスを表現していて、上からの矢印がそのコンパイルに使用するコンパイラのバイナリ、左からの矢印がコンパイル対象のソースコード、右からの矢印がコンパイルオプションなどの「ソースコード以外」のコンパイル結果に影響を与える要素(以下では省略します)、下に出ている矢印がコンパイル結果であるバイナリ生成物、という感じになります。

この図法で、前節で話題にした、プロプラUNIX環境へのGCCの導入をあらわすと、次のようになります。

Diverse Double-Compiling

提案手法では、次の図のような手続きで、調査対象のコンパイラの2種類のバイナリを作ります。

右側は、自分自身をコンパイルできる(セルフホスティングな)コンパイラの、通常のコンパイル手続きです。対称性のために2回コンパイルしていますが、原理を示す上では1回でかまいません(2回とも、同じ結果が得られているはずです。説明のため、ここではGCCとします)。

左側は、GCCの導入において「プロプライエタリUNIX付属のcc」であった部分を「何らかの信頼できるコンパイラ」に変えたもの、という感じになります。最初のコンパイラが信頼できるコンパイラですから、stage1のコンパイラソースコードときちんと対応しているはずです。ですからstage2のコンパイラは、(ソースコードGCCだとすれば)最初の「信頼できるコンパイラ」と「GCCソースコード」を信じられる限りにおいて、信じられるはず、ということになります。

そして、この信じられるコンパイラは、右のほうのプロセスで作られたコンパイラと、バイナリ的に一致するはずです。もし一致しなければ、何らかのおかしな仕掛けが仕込まれている可能性がある、ということになります(もちろん、これまで触れてきませんでしたが、コンパイルされた時刻を埋め込む、などといった特異な要因が無ければ*7*8)。

ここで大事なことは、GCCのような大きなCコンパイラのバイナリコードをチェックする、というような大変な仕事ではなく、「信頼できて、GCCをとにかくコンパイルできれば良い(コンパイルが遅くても、最適化が全く無くても)コンパイラを用意すること」と「2つのファイルの単なるバイナリ比較」という、(比較すればそれなりに)単純な仕事で、問題点の検出が可能になった、ということです。

相対的な信頼性

またこの手法は、LLVM clangでGCC(ここではコンパイラコレクションの意)のCコンパイラをビルドする、あるいはGCCのCコンパイラLLVM clangをビルドする、といったようなプロセスで、「絶対に信頼できるCコンパイラ」が無くても、ある程度相対的には信頼できると確認できる、ということも示しています。

まとめ

現実的には考えにくいとはいえ、その危険性から脅威と考えられる「Trusting Trust」攻撃に対して、(世界的なセキュリティ界隈では以前から知られていたもののようですが)有効な対抗手段があることを紹介しました。

世界にコンパイラの実装が1種類ではまずく、少なくとも2つ以上、できればもっと多数あるべき、という「多様性の善」を示すものにもなっているように思います。また、セルフホスティングができると、自分の非標準なオレオレ拡張を、自分自身の実装に使いたくなるんじゃないか、という気がしますが、それをやってしまうとこのような検証ができなくなる、ということもわかります*9。あと、極小Cコンパイラとして8ccという実装がありますが( https://github.com/rui314/8ccGCCコンパイルできれば、もしかして「最初の信頼できるコンパイラ」として有用だったりしないでしょうか? (これについては全く私は手を付けてません)

*1:追記1: どうも10年前に、こちら http://www.radiumsoftware.com/0603.html#060329 の最後の段落で、話題自体は読んでいたようです。

*2:(2018年8月追記)また、講演録を読むと最後のほうで、クラッカー(特に、今で言ういわゆる「スクリプトキディ」)について、きつい語が並んでいますが、それも背景の説明が必要なようです。受賞は1983年で、その当時は、本格的なパーソナルコンピュータが広まる前である一方、映画『ウォー・ゲーム』が公開された年でもあり、フィクションとないまぜの「コンピュータを操る少年」像がしばしば「神童」的に扱われ、マスコミを賑わしていた、というような背景があります。また、いわゆる「ハッカーはクラッカーじゃない」問題の源流の一つでもあり、講演後に(以下出典未確認)CACM誌でRMSと論争になった、という話もあります。

*3:BW変換のWであるデイヴィッド・ホイーラーさんとは特に無関係のようです。

*4:講演録では、トンプソンさんが知ったネタ元は、Multicsのセキュリティに関する空軍の文書とありますが、その後確認されたところによれば Karger, P.A., and Schell, R.R. Multics Security Evaluation: Vulnerability Analysis. ESD-TR-74-193, Vol II, June 1974, p 52. という文献だとネットの情報にはあります。

*5:余談ですが、Multicsは高水準言語をOSの記述に使おうとしたという点でも先進的でした(言語はPL/I)。日本でその影響を受けて開発されたHITAC 5020 TSSも、PL/IWというPL/IのサブセットをPL/IWで書いて、人力コンパイルでブートストラップしたと伝えられていますから、この記事とも少々関係があります。

*6:現代と違って、昔はC言語処理系の標準準拠もいろいろ怪しかったりすると、けっこう一筋縄ではなかったりした。

*7:あるいは、近年のセキュリティ技術という観点からは、アドレスを決め打ちするような攻撃に対抗するべくランダム化を掛ける手法がありますが、そういうのとも相性が悪いでしょう。

*8:追記2(参): Debianプロジェクトなどによる、ReproducibleBuilds日本語解説)として、バイナリ再現性の重視について推進するプロジェクトがあります。

*9:追記3: これも http://www.radiumsoftware.com/0603.html#060329 で指摘されているのを、どこかで覚えていたようです。