ソフトウェアプロテクションに関するメモ

Copyright (c) Akito Monden 2001-2004
hits since 2003.10.17 _

2004.11.8 ソフトウェアプロテクションのサーベイ論文

この分野のサーベイとして,古くは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.


2004.3.20 難読化によって隠蔽したいもの

難読化によって隠蔽したいと思われるものは, (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]


2004.3.15 プログラムの暗号化とSecure Processor/Coprocessor

プログラムを難読化したとしても,プログラム中の秘密を完全に隠せるわけではない. プログラムを暗号化する方が強力である. ただし, 復号ルーチンをソフトウェアで実装した場合には, その部分が解析されると暗号化が破られてしまう(復号後のプログラムを得られてしまう)ことになる. 解析を困難するための技術(難読化など)を併用した暗号化方式がいくつか提案されてはいるが[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によるプログラム保護が今後主流に なっていくと思うので,これからも注目していきたい.


2004.3.14 動的解析について

ソフトウェアの難読化の論文の大部分は,静的解析による攻撃しか想定していない. 動的解析に強い難読化法というのがそもそもほとんど存在しないので,仕方のない面もあるのだが. 動的解析に言及している論文としては,以下の文献[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]


2004.3.13 最近の難読化技術の動向(理論的側面)(2) (2004.3.20 追記)

Barakは 完全な難読化は実現不可能である という論文を書いたおかげで一躍有名になったが, 私は未だにあの難読化の定義(Virtual Black Box)には納得がいかない.というよりvirtual black boxは実現不可能であるという証明に意味があるのかどうかが疑問である. この「難読化は実現不可能」というショッキングな論文のタイトルだけはよく知られているので, 私や私の周りの人たちが論文を国際会議へ投稿するたびに,査読者から「Barakの論文を引用せよ」と言われてしまう.「難読化に関するあらゆる論文はBarakの論文を引用しなければならない」と言う人もいるくらいだ. しかし,Barakの論文の中身の式は非常に難解で,完全に理解している人間などほとんどいないだろう(暴言:-)). もちろん私も理解していない.

最近,Barakに続く理論系の論文がいくつか出てきたので,ここで改めて,Barakの難読化の定義について検討したいと思う.

上記の定義は,まさに「暗号化」の定義といえる.Barak以下の共著者は暗号分野の大物ばかりだから,暗号化にあてはめて考えているのかもしれない.仮に,これが暗号化の話だとして, プログラムPを暗号化関数O()により暗号化してO(P)を得た場合,O(P)は単なるホワイトノイズであるから,何も有用な情報が得られない.だからO(P)がvirtual black boxとなるのは自明である. 一方,難読化の場合,難読化ツールO()によってP難読化して得られるO(P)はプログラムであるから,O(P)を読めば,あらゆる情報が得られてしまう.変数の名前,型,演算式,...なんでも得られる.これらの変数や型や演算式といった情報は,当然のことながらPを実行しただけでは得られない.だから,あらゆるO(P)はvirtual black box性を満たすことはありえない.しかし,そんなことは,いちいち証明しなくても自明なのでわかりきってることである.どんなにプログラムを難読化しても,暗号化じゃないんだから,プログラム中の個々の文が隠蔽されているわけはないのだ. うーん,"anything"の解釈が間違ってるのかもしれないが....

さて,Barakらの延長上の研究として,最近,次の論文が登場した.

が,難読化の定義は,依然としてBarakのと同じだったので,読む気をなくした...

(2004.3.20 追記)
上のLynnらの論文は,パスワードチェックプログラム (2003.8.17に書いたもの) においては完全な難読化が可能だと証明しているようだ.一方向性関数が存在すると仮定できるならば証明するまでもなく自明な気はするが... 実は似たようなことを言ってる論文はもう1個ある.

こちらは,また違う定義を行っているようだ(Obfuscator(難読化ツール)の定義を行っている). 暗号化を応用した新たな難読化技術を提案したと言っているが,パスワードチェックに一方向関数を使うというだけでそこまで強気に出るほどのことでもないでしょう. 恐らくこれは多くの人が知ってる事実だし,実用上はパスワードチェックそのものを無効化するという攻撃が行えてしまうので難読化の効果は弱いわけだし.

難読化の目的=仕様(入出力の関係)を隠蔽する,であるならば, Barakの定義でも仕方がないのかなとも思う("anything"がどこまで含むかが問題だけど). 難読化の目的=アルゴリズムを隠蔽する,という定義があり得るかどうかだけど, 改めて考えてみると,仕様は隠蔽しなくてもいいけどアルゴリズムは隠蔽したいというケースが果たしてあり得るのだろうか? 実はあんまりないような気もしてきた. 例えば,クイックソートのアルゴリズムを隠蔽したいときにバブルソートに変換すれば完璧に隠蔽できるけれども,それだと実行効率が落ちるのであんまり意味なさそうだ. また,逆に,実行効率のよいアルゴリズムに変換した場合は,そもそも最初の(実行効率の悪い)アルゴリズムを隠蔽する意味などないような気がするし. いずれにしても,難読化を行う者にとっては「隠蔽したいもの」がまずありきなので, 何を隠蔽したいかによって様々な定義が考えられそうだ.


2004.3.12 Apple社の特許

最近,アップルコンピュータ社が難読化の特許を取得した.

パッと見た感じでは, 基本的には命令列を分割して混ぜてるだけなので,新しい方法とは思えないのだが. Cohenの頃の難読化技術と大差ないような気がする. とはいえ,この特許が有効か否かは,裁判になってみないと分からないかもしれない.

最近は難読化の特許が増えてきているので,難読化を採用しようとする企業にとっては 細心の注意が必要であろう. ただ,実際に特許を侵害していたとしても,その事実を証明するのは不可能に近い気がしないでもない.


2004.2.26 Software Differential Analysis

差分攻撃(Differential Attack)は,暗号に対する有力な攻撃手段であるが,ソフトウェアプロテクションに対しても有力である.

ソフトウェア差分解析(Software Differential Analysis)は,ユーザ間で差分を取る方法と,バージョン間で差分を取る方法の二つがある. 前者は,異なるユーザが所有するソフトウェア間で差分を取ることで,各ソフトウェアに固有に施されたプロテクション(電子透かしなど)を特定することである. 後者は,あるバージョンのソフトウェアに対して新しいプロテクションが実装された場合に,古いバージョンとの差分を取ることで,新しいプロテクションが実装されている部分のコードを特定することである.ソフトウェアプロテクションを導入する場合には,これらの攻撃を予め想定し,攻撃を困難にする処置を施しておく必要がある.


2004.2.24 Software Diversity (3)

ソフトウェアに多様性を持たせることで,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]の最後に書かれているような攻撃は可能なので,多様性は依然として必要だとはいえるが,必要性はだいぶ弱くなった感じがする.


2004.2.16 難読化の評価技術 (1)

プログラムの難読化方法を提案した場合,その方法はどのくらいの効果があるのか(プログラムがどのくらい解析しづらくなるのか)何らかの評価が必要となる. プログラムを難読化したい者にとっても,評価がなされていない方法をいきなり採用するのは難しい.

しかしながら,評価を行うのは非常に難しい.なぜならば,

以上の議論から,難読化方法の評価は容易ではないが,だからといって評価しないわけにはいかない. 少なくとも,攻撃者の行動や難読化の目的をはっきりさせておく必要があるといえる. 望ましい評価方法としては,
  1. 攻撃者のモデル(攻撃者が行うことのできる行動,行えない行動),及び,
  2. 攻撃者の目的(攻撃者から隠したい情報,攻撃者のリソースに関する定理,例えば, サイズnのプログラムから情報yを平均O(nlogn)回の試行で取り出すなど), を明確にし,
  3. 1.の攻撃者が2.を達成できないことの証明,を行うことである.
このような評価は,情報セキュリティにおけるあらゆる研究に要求されるが, 難読化の研究ではなかなか難しく,多くの論文では(自分のも含めて)不十分なように思う. まず,1.について,攻撃者のモデルが明確になっていない場合が多く, また,たとえ明確であっても,あまり面白くないモデルとなっていることがある. 現実世界において攻撃者が容易に行えるような行動を「攻撃者が行えない行動」として モデル化するのは望ましくない (攻撃者はデバッガを使わない,と仮定されている論文も多い). 2.についても,攻撃者の目的が明確でないか,あるいは,目的自体が面白くない, という場合がある. また,3.が明確でなかったり,誤りが含まれている場合もある.

とはいえ,難読化の分野では完璧な評価は難しく,現実的な攻撃モデルを想定した場合には, 有効な難読化方法を提案することすらままならない. 暗号化技術と違って,強力な(多くの現実的な攻撃に耐えれるような)難読化技術は未だ 存在しないと思う. 結果として,攻撃モデルや攻撃者の目的を限定したものにせざるを得ないことが多い. 個人的には, 何らかの(形式的な)評価を試みている論文であれば積極的に評価したいと思う. また,実験的な(被験者を使った)評価を行っている論文も評価できる. なお,限定的な攻撃モデルで評価する場合には, 少なくとも,どういう攻撃には弱いかを明示しておいて欲しい (方法の限界を示すべき)とも思う.


2003年のメモ
  1. 2003.12.5 Software Diversity (2)
  2. 2003.11.14 Control Flow Obfuscation(制御フローの難読化)
  3. 2003.11.7 Obfuscated Programming Languages(難読化されたプログラミング言語)>
  4. 2003.10.12 ソフトウェア(コンピュータプログラム)におけるWatermark, Fingerprint, Birthmark, Plagiarism detection, and Code clone
  5. 2003.9.14 Software Diversity (1)
  6. 2003.8.24 Javaの逆コンパイルを防止することは原理的に可能か?
  7. 2003.8.22 研究遂行上,(音楽,映像,プログラム等の)コピープロテクトを外すのは合法か?
  8. 2003.8.17 ソフトウェアプロテクションの古典
  9. 2003.8.11 最近の難読化技術の動向(理論的側面)
  10. 2003.7.28 CD-Rバックアップツール
  11. 2003.7.27 Trusted Computing
  12. 2003.7.14 携帯電話の製造番号,及び,組み込みソフトウェアの難読化・暗号化
  13. 2003.6.11 実行時難読化
  14. 2003.5.8 メディアコンテンツ配信システムにおけるソフトウェアプロテクション
  15. 2003.4.14 ソフトウェアプロテクションとオープンソースソフトウェア
  16. 2003.4.10 .NET逆コンパイラ
  17. 2003.2.12 Java逆コンパイラの現状2

2002年のメモ
  1. 2002.11.16 Java逆コンパイラの現状
  2. 2002.9.29 ソフトウェアプロテクション関係の国内会議
  3. 2002.8.5 Javaクラスファイル用の電子透かしツール"jmark"を半年ぶりに更新した.
  4. 2002.7.23 難読化は悪の技術か?
  5. 2002.7.9 Rレジスタ

2001年のメモ
  1. 2001.12.23 Javaクラスファイル用の電子透かしツールを4年ぶりに更新した.
  2. 2001.12.9 ステガノグラフィーとプログラム
  3. 2001.12.5 時刻を用いたプログラム難読化