この分野のサーベイとして,古くは1989年のGroverの著書[1], 1993年のCohenの論文[2]があり, 近年ではCollbergとThomborson[3],Mainら[4],van Oorschot[5], NaumovichとMemon[6],石間ら[7]の文献がある.
[1] D. Grover (ed),"The protection of computer software - its tech-nology and applications," The British Computer Society Mono-graphs in Informatics, Cambridge University Press, 1989 (Second Edition 1992).
[2] F. Cohen, "Operating system protection through program evolu-tion," Computers and Security, Vol. 12, No. 6, pp. 565-584, 1993.
[3] C. Collberg and C. Thomborson, "Watermarking, tamper-proofing, and obfuscation - Tools for software protection," IEEE Trans. on Software Engineering, Vol. 28, No. 8, pp. 735-746, 2002.
[4] A. Main and P. C. Oorschot, "Software protection and application security: understanding the battleground," Proc. International Course on State of the Art and Evolution of Computer Security and Industrial Cryptography, June 2003.
[5] P. van Oorschot, "Revisiting Software Protection," Information Security (ISC 2003), Lecture Notes in Computer Science, vol. 2851, pp. 1-13, 2003.
[6] G. Naumovich and N. Memon, "Preventing piracy, reverse engi-neering, and tampering," Computer, Vol. 36, No. 7, pp. 64-71, July 2003.
[7] 石間, 亀井, 齊藤, "ソフトウェアの耐タンパー化技術," 情報処理, Vol.44, No.6, 2003.
難読化によって隠蔽したいと思われるものは, (1)プログラム中で用いられてる重要アルゴリズム,もしくは,その実装であるサブルーチン,(2)デバイスIDや復号鍵などの定数,(3)ライセンスチェックのような特定の条件式,(4)メンテ用の隠しモードのような特定の外部インタフェース,などである. (1)については,課金が関係するシステムでは特に重要でしょう. (2)については,アルゴリズムが既知の場合に特に重要となりそうだ.例えばCSSの次の世代のコンテンツ保護方式ではアルゴリズムは公開されているようだから鍵を隠すことが必須でしょう. また,携帯電話の 製造番号(IMEI) のような情報の隠蔽することも必須でしょう. (3)については,長年の課題ですね. (4)については,面白い事例がある.オープンソースにしていたソースコードからメンテ用のバックドア(裏口)がバレたらしい[1].オープンソースの安全性については議論があるが[2][3],バックドア付きのプログラムをオープンソースにするのはさすがにまずいでしょうね.
[1] J. S. Havrilla, "Borland/Inprise Interbase SQL database server contains backdoor superuser account with known password," US-CERT, Vulnerability Note VU#247371, Revision 46, 1 Dec. 2001,[Link]
[2] R. Anderson, "Security in open versus closed systems -- the dance of Boltzmann, Coase and Moore,"
[PDF]
[3] R. Needham, "Security and open source,"
[PDF]
プログラムを難読化したとしても,プログラム中の秘密を完全に隠せるわけではない.
プログラムを暗号化する方が強力である.
ただし,
復号ルーチンをソフトウェアで実装した場合には,
その部分が解析されると暗号化が破られてしまう(復号後のプログラムを得られてしまう)ことになる.
解析を困難するための技術(難読化など)を併用した暗号化方式がいくつか提案されてはいるが[1],
熟練した攻撃者に対しては十分安全とはいえない.
ソフトウェアを暗号化するツールも数多く普及しているが([2][3][4]など),その大部分はクラック可能と思われる.
[1] D. Aucsmith, "Tamper resistant software: An implementation,"
Information Hiding Workshop, RJ Anderson (ed), LNCS 1174, pp. 317-333, 1996.
[2] Obsidium [Link]
[3] ACProtect [Link]
[4] XTREME-PROTECTOR, PE-PROTECTOR [Link]
従って,ハードウェアにより暗号化/復号化を行うことが望ましい.
この場合,プログラムは暗号化して配布され,実行時にハードウェア
(CPUやコプロセッサ)によって復号されるわけであるが,
復号したプログラムをどこに置くかによって二つの方式に分類できる.
一つは,
メインメモリに復号したプログラムを置く方式である.
たとえば,
2003.7.27のメモでも書いたTrusted Computingの方式がこれである.
この方式では,復号したプログラムを置いたメモリ領域に
攻撃者がアクセスできないように,CPU,ブート用ハードウェア(TPM),OSのセキュアカーネル等で保護している.
この方式の利点は,一度復号した後では,プログラムの実行速度は通常のプログラムと変わらないことである.弱点としては,ハードウェア的に(ロジックアナライザなどで)メインメモリを覗き見される恐れがあることと,カーネルにセキュリティホールがあるかもしれないことである.
もう一つの方式は,
CPUキャッシュ内に復号したプログラム(の一部を)を置く方式である.
研究グループとしては,XOM[5],AEGIS[6]などのsecure processorを提案しているところが有名である.他にもCerium[7]などがある.
これらの方式の利点は,メインメモリと比べると,CPU内のキャッシュを覗き見される危険性は低いので,より安全性が高いことである.
弱点としては,キャッシュの容量には限界があるので,データキャッシュがあふれた時にメインメモリへのデータの書き込みが発生し,その際に再暗号化が必要となったり,キャッシュのヒット率が低いと復号処理が増えて実行効率が落ちることである.
実行効率を改善する方式についても論文はいくつか出てはいるが...
[5] D. Lie, C.A. Thekkath, and M. Horowitz, "Implementing an untrusted operating system on trusted hardware," Proc. 19th ACM
Symposium on Operating Systems Principles, Oct. 2003.
[PDF]
[6] G. E. Suh, D. Clarke, B. Gassend, M. van Dijk, S. Devadas, "AEGIS: Architecture for tamper-evident and tamper-resistant
processing," Proc. 17th International Conference on Supercomputing (ICS2003), pp. 160-171, June 2003.
[PDF]
[7] B. Chen and R. Morris, "Certifying program execution with secure processors," Proc 9th Workshop on Hot Topics in Operating
Systems, May. 2003.
[PDF]
将来的にもプログラム難読化の需要はあるとは思うが, 一部のハードウェアでは,このようなsecure processorによるプログラム保護が今後主流に なっていくと思うので,これからも注目していきたい.
ソフトウェアの難読化の論文の大部分は,静的解析による攻撃しか想定していない.
動的解析に強い難読化法というのがそもそもほとんど存在しないので,仕方のない面もあるのだが.
動的解析に言及している論文としては,以下の文献[1]において,Mainとvan Oorschotが
「動的解析は静的解析よりも強力であるかもしれないが,より労力を要するし,
複雑であり,攻撃対象のプラットフォームと同等のプラットフォームを
用意する必要がある」と述べている.
[1] A. Main, P.C. van Oorschot, "Software protection and application security:
understanding the battleground,"
State of the Art and Evolution of Computer Security and Industrial Cryptography,
LNCS, June 2003.
[PDF]
現実には,PC上では動的解析はそれほど難しいことではなく,むしろ主流の攻撃手段といえる. 例えば,ソフトウェアのパスワードチェックを無効化したい場合,プログラムを逐一読む攻撃者なんていないだろう. 攻撃者は, SoftICE などのカーネルモードのデバッガを走らせて,パスワードチェックを行っている部分を特定し, 条件分岐を無条件ジャンプに変更するなどの処理を行うであろう. このような動的解析は,静的解析よりもはるかに容易に行える.
従って,ソフトウェアの難読化は,パスワードチェックルーチンを隠蔽する用途には
いまいち使えないというのが一般的な認識と思う.
近年では,暗号アルゴリズムとか復号鍵を隠蔽するのに用いるのが主流と思われる[2].
この[2]の方式は,鍵を隠蔽するという観点からは,動的解析にも強いと思う(実行時に鍵がメモリ上に現れないと思われる).
ちなみに,アルゴリズムを隠蔽するという面において動的解析にそこそこ強いと私が思う難読化方法は,
2003.11.14のメモでも書いた[3]の方式である.
[2] S. Chow, P. Eisen, H. Johnson, and P.C. van Oorschot, "A white-box DES implementation for DRM applications," Proc. 2nd ACM Workshop on Digital Rights Management (DRM2002), 2002.
[Link]
[3] S. Chow, Y. Gu, H. Johnson, and V. Zakharov, "An approach to the obfuscation of control-flow of sequential computer programs," Information Security Conference (ISC2001), G. I. Davida and Y. Frankel (Eds.), Notes in Computer Science, Vol. 2000, pp. 144-155, 2001.
[PDF]
では,動的解析を防ぐにはどうすればいいのであろうか.
現状では,anti-debugging技術を使うのが一般的だと思われる(例えば[4][5][6]).
しかし,カーネルモードで動作するデバッガに対しては,
攻撃を防ぐのはなかなか難しいのが現状だと思われる.
[4] Anti-Debugging Tricks (Release 5) by Inbar Raz
[Link]
[5] Anti-Cracking Tips&Tricks
[Link]
[6] Anti-Anti-Debugging Tricks by _dose
[Link]
Barakは 完全な難読化は実現不可能である という論文を書いたおかげで一躍有名になったが, 私は未だにあの難読化の定義(Virtual Black Box)には納得がいかない.というよりvirtual black boxは実現不可能であるという証明に意味があるのかどうかが疑問である. この「難読化は実現不可能」というショッキングな論文のタイトルだけはよく知られているので, 私や私の周りの人たちが論文を国際会議へ投稿するたびに,査読者から「Barakの論文を引用せよ」と言われてしまう.「難読化に関するあらゆる論文はBarakの論文を引用しなければならない」と言う人もいるくらいだ. しかし,Barakの論文の中身の式は非常に難解で,完全に理解している人間などほとんどいないだろう(暴言:-)). もちろん私も理解していない.
最近,Barakに続く理論系の論文がいくつか出てきたので,ここで改めて,Barakの難読化の定義について検討したいと思う.
さて,Barakらの延長上の研究として,最近,次の論文が登場した.
(2004.3.20 追記)
上のLynnらの論文は,パスワードチェックプログラム
(2003.8.17に書いたもの)
においては完全な難読化が可能だと証明しているようだ.一方向性関数が存在すると仮定できるならば証明するまでもなく自明な気はするが...
実は似たようなことを言ってる論文はもう1個ある.
難読化の目的=仕様(入出力の関係)を隠蔽する,であるならば, Barakの定義でも仕方がないのかなとも思う("anything"がどこまで含むかが問題だけど). 難読化の目的=アルゴリズムを隠蔽する,という定義があり得るかどうかだけど, 改めて考えてみると,仕様は隠蔽しなくてもいいけどアルゴリズムは隠蔽したいというケースが果たしてあり得るのだろうか? 実はあんまりないような気もしてきた. 例えば,クイックソートのアルゴリズムを隠蔽したいときにバブルソートに変換すれば完璧に隠蔽できるけれども,それだと実行効率が落ちるのであんまり意味なさそうだ. また,逆に,実行効率のよいアルゴリズムに変換した場合は,そもそも最初の(実行効率の悪い)アルゴリズムを隠蔽する意味などないような気がするし. いずれにしても,難読化を行う者にとっては「隠蔽したいもの」がまずありきなので, 何を隠蔽したいかによって様々な定義が考えられそうだ.
最近,アップルコンピュータ社が難読化の特許を取得した.
最近は難読化の特許が増えてきているので,難読化を採用しようとする企業にとっては 細心の注意が必要であろう. ただ,実際に特許を侵害していたとしても,その事実を証明するのは不可能に近い気がしないでもない.
差分攻撃(Differential Attack)は,暗号に対する有力な攻撃手段であるが,ソフトウェアプロテクションに対しても有力である.
ソフトウェア差分解析(Software Differential Analysis)は,ユーザ間で差分を取る方法と,バージョン間で差分を取る方法の二つがある. 前者は,異なるユーザが所有するソフトウェア間で差分を取ることで,各ソフトウェアに固有に施されたプロテクション(電子透かしなど)を特定することである. 後者は,あるバージョンのソフトウェアに対して新しいプロテクションが実装された場合に,古いバージョンとの差分を取ることで,新しいプロテクションが実装されている部分のコードを特定することである.ソフトウェアプロテクションを導入する場合には,これらの攻撃を予め想定し,攻撃を困難にする処置を施しておく必要がある.
ソフトウェアに多様性を持たせることで,code-injection attack(ウィルス,ワーム,トロイの木馬などを含む)を防ぐという話を書いた
(12.5のメモ,9.14のメモ)が,
AMDがMicrosoftと協力して根本的な解決を図るようだ[1][2][3].
[1] A. Ananthaswamy, "
Chips to ease Microsoft's big security nightmare," Feb. 2004.
[2] Slashdot, AMD could profit from buffer-overflow protection, Feb. 2004.
[3] M. Tarsala, AMD grabs key security advantage, Dec. 2003.
Code-injection attackは,多くのソフトウェアにおいてセキュリティホールとなっているbuffer overflowを利用する. この攻撃の目的を一言で言えば,メモリ上のプログラム領域に(トロイの木馬となる)プログラムをどうにかして上書きして,そこに実行を移す,もしくは,データ領域にプログラムを書き込み,どうにかしてそこに実行を移すことである. AMDの新CPUでは,プログラム領域とデータ領域を完全に分離することをCPUレベルで保障しているようだ(詳細不明). 従来も,OpenBSDなどでは, 各セクションはwriteかexecuteのどちらか一方しか許可されない(W^X: Write xor eXecute)のだが, これでは不十分なのだろうか. と思って上記[2]を見ると,Intelはi386時代からすでにW^XをCPUレベルで実現していて, OS側が対応してなかっただけだという書き込みもある. また,システムコールを使って各セクションのW^Xを反転させるという攻撃が可能だという書き込みもある(真偽は不明).
MicrosoftがAMDに協力した理由は,この技術の実現により,buffer overflowに対するセキュリティパッチを作らなくてもよくなる...と考えたからのようだが, なぜ今までこの技術を実現しようと努力しなかったのか不思議である. Windowsを64ビット対応にするのがちょうどよい機会になったのかもしれない. NGSCBとの関連もあるかも.
さらに私が気になる点は,この技術の出現により, ソフトウェアに多様性を持たせる研究をしていた人々は研究ネタがなくなって困るんじゃないかなあということである. ただし,上記の[1]の最後に書かれているような攻撃は可能なので,多様性は依然として必要だとはいえるが,必要性はだいぶ弱くなった感じがする.
プログラムの難読化方法を提案した場合,その方法はどのくらいの効果があるのか(プログラムがどのくらい解析しづらくなるのか)何らかの評価が必要となる. プログラムを難読化したい者にとっても,評価がなされていない方法をいきなり採用するのは難しい.
しかしながら,評価を行うのは非常に難しい.なぜならば,
とはいえ,難読化の分野では完璧な評価は難しく,現実的な攻撃モデルを想定した場合には, 有効な難読化方法を提案することすらままならない. 暗号化技術と違って,強力な(多くの現実的な攻撃に耐えれるような)難読化技術は未だ 存在しないと思う. 結果として,攻撃モデルや攻撃者の目的を限定したものにせざるを得ないことが多い. 個人的には, 何らかの(形式的な)評価を試みている論文であれば積極的に評価したいと思う. また,実験的な(被験者を使った)評価を行っている論文も評価できる. なお,限定的な攻撃モデルで評価する場合には, 少なくとも,どういう攻撃には弱いかを明示しておいて欲しい (方法の限界を示すべき)とも思う.