Hacking the Xbox 日本語訳

Appearance

第7章　セキュリティ入門 ​

前の章で体験したように、Xboxをハックするには、ハードウェアとファームウェアのハッキングに加えて、セキュリティハッキングの知識も必要だ。本章では、まず洗練されたセキュリティを家庭用ゲーム機というありふれた製品に組み込む動機を探り、Xboxのセキュリティメカニズムを理解・評価するために必要な基本原理とアルゴリズムを解説する。

セキュリティって本当に必要なの？ ​

ビデオゲームコンソールは、大多数の人にとってはただのおもちゃだ——低価格の家庭用電子機器にすぎない。それなのに、なぜMicrosoftはシステムをこれほど手厚く守ろうとしたのだろうか？ セキュリティハッキングのゲームでは、守る側の動機を理解することが、突くべき弱点を見つける鍵になることが多い。

暗号技術それ自体はセキュリティではない。セキュリティを実現するための手段にすぎない。本当のセキュリティは、エンドユーザーを含めたシステムアーキテクチャ全体を対象にする。Kevin Mitnickが最近のSlashdotインタビューで語ったように、「……セキュリティとは棚から買ってこられる製品ではなく、ポリシー、人、プロセス、テクノロジーで構成されるものだ」1。セキュリティとは本質的に社会的な概念だと僕は思っている。実際の生活でも、窓を開けたまま玄関のドアに鍵をかけておけば、人々はわざわざ窓から入ったり錠前を壊したりしない——どちらも技術的には難しくないのに。施錠されたドアと開いた窓が機能するのは、ドアの鍵が主にシンボリックな意味を持つからだ。侵入者は意識的な違反行為に踏み出す必要があり、それだけで犯罪者と善良な人々を分けるのに十分だ。SonyのPlayStationはこのフロントドアロック型セキュリティの好例だ。

ゲームのコピープロテクションに使われているメカニズムはシンプルで、暗号技術は一切使われておらず、安価なハードウェア改造で簡単に回避できる。それでも、販売数のデータを見れば、PlayStationゲームを購入する習慣は廃れていない——フロントドアロックはちゃんと機能しているのだ。

MicrosoftもフロントドアロックのバリエーションをXboxに採用している。Xboxのゲームソフトは、（今のところ）コピー不可能なDVD-9フォーマット——片面2層のメディア規格——で配布されている。一方、ユーザーが書き込めるDVDは常にDVD-5フォーマット、つまり片面1層だ。一方の層に書き込む際にもう一方の層の記録面を傷めずに済む書き込みシステムを作ることが難しいため、DVD-9対応バーナーが近い将来登場する可能性は低い。セキュリティデータをDVD-9ディスクの2層に分散させ、ゲームの実行ファイルをDVD-9メディアからのみ起動できるよう要求することで、Microsoftはかなり効果的なフロントドアロックを実現している。DVD-9フォーマットを要件として課すことで、潜在的なゲームコピーの試みをハードウェア改造が必要な領域に追い込んでいるわけだ。

では、なぜMicrosoftはXboxにこれほど複雑なセキュリティスキームを投資するリスクを冒したのだろうか？ Xboxセキュリティシステムの残りの部分——セキュアブートセクタ、署名された実行ファイル、トラスト関係、暗号化・認証されたネットワークプロトコル——の主目的は、著作権侵害対策ではない可能性がある。

動機の一つとして、Xboxコンソールをゲーム以外の用途に使えないようにすることが考えられる。Xboxコンソールはほぼ100%普通のPCという特異な立ち位置にある。GameCubeやPlayStation 2とは違い、適切なBIOSさえあればXboxでそのまま動きそうなソフトウェアが山ほど存在する。さらに厄介なことに、Microsoftはコンソールのハードウェアで競合他社よりはるかに大きな損失を出している。最新の小売価格199ドルを前提にすると、その損失は1台あたり200ドルに達するという試算もある。だから、補助金を投じたGNU/Linuxボックスを売っているだけにならないよう努めたいわけだ。しかし、これさえもおそらくMicrosoftの主目的ではない。XboxはRAMが64MB、キーボードもマウスも付属せず、当時の基準でもプロセッサが比較的遅い。2002年末にWalmartで200ドルで買えたMicrotel PCより魅力的とは言いがたい。さらにMicrosoftには潤沢な資金がある。XboxがSonyのPlayStation 2を超える市場支配を確立できれば、数十億ドルの先行投資損失は——手元に積み上がる約400億ドルの現金と比べれば——相対的に小さい。だから、Xboxセキュリティの重要な使命は、コンソールの代替用途を防いだり海賊版を阻止したりすることではないのかもしれない。

おそらくXboxの複雑なセキュリティの本当の理由は、MicrosoftのオンラインゲームサービスであるXbox Liveの成功を保証することにある。Microsoftのマーケティングとプレスリリースは、ハードウェア販売の起爆剤としてXbox Liveの成功に賭けていることを示している。さらに、Xbox Liveはサブスクリプションサービスで、ローンチから1年後にはユーザーが月額料金を払う必要がある。Xbox Liveでユーザーを虜にできれば、ハードウェアでかなりの損失を出しても、一気にXboxビジネスは十分な収益性を持つように見えてくる。「オンラインゲームのディズニーランド」とも形容されるXbox Liveの目標は、公平で洗練されたゲーム体験を提供することだ。そのサービス価値の核心は「チーターがいない」ことだ。誰もズルをしていないと保証するには、ユーザーをXbox Liveが管理するレジストリに対して認証させ、ゲームの状態を安全かつ改ざん不可能に保つ必要がある。さらに、ゲームソフトにはパッチが当たっていないことも求められる。もっと切実なのは、ほんの一握りのチーターが大勢のユーザーのゲーム体験を台無しにするという事実だ。そうなると、DVD-9フォーマットが提供するフロントドアセキュリティだけでは不十分に見えてくる。コンピュータにそこそこ詳しい20代の男性ゲーマーが何百万人も存在する状況で、彼らの倫理観と誠実さに事業の成功を賭けるのは分が悪い。ハードウェアは信頼できなければならず、ネットワーク接続は安全でなければならず、実行ファイルは署名・封印されていなければならない。

ハードウェアは信頼できなければならない——この一文は繰り返す価値がある。信頼できないユーザーを相手にするとき、クライアントとの信頼関係を築く唯一の方法は、すべてのハードウェアの内部に「信頼の種」が存在することだ。だからこそMicrosoftは、すべてのクライアントに改ざん耐性（耐タンパー性）のあるハードウェアを組み込み、アテステーション——特定のデータ（例えばプレイヤーの識別情報やゲーム状態）が、確かに汚染されていないソフトウェアとハードウェアから生成されたことを証明する機能——を可能にする必要があった。耐タンパーハードウェアはアテステーション機能を直接実装する必要はないが、少なくとも認証前にシステムが信頼できる状態にあることを保証しなければならない。

ハードウェアの信頼性を確保する方法はいくつかある。最も力技なのは、ハードウェア全体を物理的に保護することだ。現金自動預払機（ATM）は物理的に安全なハードウェアの典型例だ。厚い鉄板で密封し、侵入センサーを張り巡らせたATMを物理的に破って改造するのは難しい。ただ、効果的ではあっても、ビデオゲームコンソールに適用するには現実的でなく、コストも高すぎる。

より経済的な解決策は、システムの残りの部分を「計測」できる小さな耐タンパーハードウェアを使うことだ。この種の計測には通常、暗号学的ハッシュ関数が使われる。すべての信頼計測値が期待値と一致すれば、システム全体が信頼できると結論づけられるかもしれない。

「かもしれない」と言ったのは、このスキームが依然として中間者攻撃（man-in-the-middle attack）に対して脆弱だからだ。中間者攻撃とは、攻撃者が2者間でやり取りされる情報を自由に改ざん・制御できる攻撃の総称だ。計測クエリに対して偽の正常データを送り込まれてしまう。この中間者攻撃の弱点があるため、システム計測に極めて高度な耐タンパーモジュールを使うことに意味はない。パッケージ化されたシリコンチップ1個で十分だ——プリント基板上を流れる計測データを傍受・偽装する方が、チップのエポキシパッケージを物理的に破って回路を改造するよりも一般的に簡単だからだ。

信頼計測システムは「一度だけ計測する」アプローチで実装できる。プロセッサのコールドブートシーケンスから始めて、実行前にすべてのコードを信頼性について計測する。プロセッサが一切の信頼されないコードを実行しないなら、信頼できないものは何もないはずだ。このスキームに必要な耐タンパーハードウェアはごくシンプルでよい——コールドブートコード、つまり「信頼の種」を格納する耐タンパーROMだ。計測と検証のプロセスで使われる暗号方式は、通常ハッシュと公開鍵暗号の組み合わせだ。公開鍵暗号がこの用途に好まれるのは、正当なコードセグメントを生成するために必要な秘密鍵が、ハードウェアベンダーだけが知るシークレットだからだ。このスキームも多種多様な中間者攻撃、純粋な暗号解析攻撃、システム実装上の攻撃に対して脆弱であることには変わりない。

暗号技術入門 ​

暗号（cipher）（名詞）: 1 a: ゼロ　b: 重さ・価値・影響力が皆無の存在：無名の人。2 a: 意味を隠すためにテキストを変換する方法——「CODE」の第2定義と対比せよ2

暗号はそれ自体では何のセキュリティも提供しない。正確に言えば、暗号がセキュリティを提供できるのは、鍵が安全で、アルゴリズムが強固で、システムにバックドアがない場合だけだ。強力な暗号で暗号化されたCD-ROMを手渡され、スーパーコンピュータと共に密室に閉じ込められたとしよう——おそらく太陽が超新星爆発を起こす前にCD-ROMを復号することはできない。一方、CD-ROMを暗号化しているマシンの動作を観察・調査できる状況なら、暗号化などほぼ無意味だ。キーボードを盗み聞きして暗号化鍵を入手できる。あるいは、コンピュータのメモリをダンプして、鍵を知らなくても平文を得られる。

Xboxもこれによく似た後者の状況に置かれている。最終的には、Xboxは正規ディスクに収録されたプログラムにアクセスして実行しなければならない。さらに、XboxのPentium CPUは、正規の命令と不正な命令を区別できない。おまけに、ユーザーはXboxのハードウェアを自由に調査・改造できる。だから、Xboxが強力な暗号を使っていても、鍵のセキュリティには疑問符が付き、システムへのバックドアが存在する可能性もある。

本節では、Xboxで使われている暗号アルゴリズムの種類を簡単に説明する。実装上の観点や実際の運用上の問題に焦点を当てる。Xboxのセキュリティシステムに対する攻撃手法を理解・評価するために、これらのアルゴリズムを知っておく必要がある。

NOTE

暗号技術の理論的な側面については、僕の能力と本書の範囲を超えているため扱わない。暗号に興味のある読者は、Bruce Schneierの名著 Applied Cryptography（John Wiley & Sons）をぜひ参照してほしい——僕の暗号知識のほとんどはその本から来ている。暗号に精通している読者は、本章の残りの部分をざっと眺めるかスキップしても構わない。

暗号アルゴリズムの種類 ​

Xboxで使われている主要な暗号アルゴリズムの種類は以下のとおりだ。

  • ハッシュ（Hash）
  • 共通鍵暗号（Symmetric cipher）
  • 公開鍵暗号（Public key cipher）

ハッシュにはいくつかの種類がある。暗号学的なハッシュは、大量のデータを「要約」あるいは「ダイジェスト」するために使われる。要約結果は固定長の数値で、通常100〜200ビット程度。一方、元のデータはほぼ任意のサイズで構わない。ハッシュの最も重要な特性は、一方向計算だということだ。つまり、ハッシュの計算は簡単だが、同一のハッシュダイジェストを持つデータ列を見つけたり、ハッシュから元データを逆算したりすることは非常に難しい（「非常に難しい」の意味については、コラム「とてつもなく難しい問題」を参照）。

同一のハッシュ値を生成する2つのデータ列を見つけることへのハッシュの耐性を「衝突耐性（collision resistance）」と呼ぶ。一般に、優れたnビットのハッシュが衝突を引き起こすには、約2n/2個のランダムなデータ列をハッシュして比較する必要がある。ハッシュは計算が非常に高速で衝突耐性も高いため、大量のセキュアなデータ領域でビットが変化していないかを検出するために頻繁に使われる。多くの用途では、メッセージ全体を暗号化する計算コストをかける代わりに、暗号化されたメッセージのハッシュだけを付加する方式で十分だ。

共通鍵暗号は、暗号化と復号の鍵が互いに簡単に導出できるアルゴリズムだ。多くの場合、暗号化鍵と復号鍵は同じだ。共通鍵暗号は、鍵スケジュール（key schedule）と暗号関数で処理されたデータを組み合わせる混合関数（mixing function）を使う。この混合は、ブロック暗号のように1ブロックのデータに対して複数回繰り返されることもあれば、ストリーム暗号のように1回だけ行われることもある。共通鍵暗号の基本的な演算はどれも計算上シンプルなので、大量データを暗号化する際の優先的な方法として使われる。

混合関数の典型的な例は、XOR、剰余加算、剰余乗算だ。最もシンプルなXOR演算には「任意の数とそれ自身をXORするとゼロになる」という性質がある。XOR演算は記号⊕で表され、通常の算術の性質（交換法則、結合法則、分配法則など）をすべて持つ。

(A ⊕ B) ⊕ B = A ⊕ (B ⊕ B) = A ⊕ 0 = A

つまり、AがメッセージでBが鍵なら、(A ⊕ B) が暗号文となり、再びBとXORするだけで平文に戻せる。

鍵スケジュールは、比較的短い鍵を取り、その情報を長いビット列に展開するアルゴリズムだ。鍵スケジュールは、鍵データをより大きなデータブロックに拡散させ、暗号文と鍵の関係を不明瞭にするために使われる。

📦 コラム：とてつもなく難しい問題

暗号関数はすべて、すべての演算子が与えられれば結果を計算するのは簡単だが、結果だけが与えられた場合に演算子を求めることが非常に難しい数学的アルゴリズムに基づいている。暗号関数のセキュリティとは、まさにこの「結果だけから演算子を求めることの難しさ」そのものだ。「非常に難しい」とはどういうことか、少し考えてみよう。

共通鍵暗号のAES（Advanced Encryption Standard）を例に取ろう。128ビット鍵を使い、差分暗号解析や線形暗号解析など現在知られているすべての解析的暗号解析攻撃に対して強固だとされている。「解析Xに対して強固」とは、ブルートフォースで鍵や平文を回復するために必要な演算回数以上の演算が解析Xでも必要になる、という意味だ。ブルートフォース探索とは、非常に高速なコンピュータで2128通りすべての鍵を試して元のデータを回復しようとすることだ。

今日広く使われている暗号アルゴリズムのほとんどは、すべての既知の暗号解析技術に対して強固なので、重要な指標はブルートフォース攻撃の強度だ。

少し古い56ビット暗号のDES（Data Encryption Standard）は「とてつもなく難しい問題」とは言えない。FPGA（Field Programmable Gate Array、現場でプログラム可能なゲートアレイ）を使ったマシンを構築すれば、約222鍵/秒/ドル（222は約400万）というコスト効率で鍵を解読できる。この数字はムーアの法則に従い時間とともに増加する。現在、1週間ほど待つ覚悟があれば、高級車1台分の価格でDES鍵を回復できる。銀行がDESでアカウントデータを暗号化していないことを祈るばかりだ！

DESの後継であるAESは、128・192・256ビット鍵が使えるが、どれも総当たり攻撃には事実上不可能なほど大きい。NIST（米国国立標準技術研究所）が公開したAES Q&A（http://csrc.nist.gov/encryption/aes/aesfact.html）によると、ブルートフォースで1秒に1つのDES鍵を回復できるほど強力なマシンが128ビットのAES鍵を回復するには、149兆年かかる。256ビット鍵に対するブルートフォース攻撃の強度についてBruce Schneierは Applied Cryptography の中で、使用エネルギーの観点から興味深い分析を行っている。熱力学的に理想的なコンピュータを使っても、2192まで数えるだけで太陽の年間エネルギー出力の32倍以上のエネルギーが必要だという。（ただし、以上はすべて最も効率的な攻撃がブルートフォースであるという前提に立つ。誰かがアルゴリズムの弱点を発見し、はるかに効率的な攻撃手法を編み出す可能性はゼロではない。暗号の強度を徐々に削るような新しい解析技術は常に生まれ続けている。）

一方、公開鍵暗号は、素数の乗算や剰余べき乗など、逆算が難しいさまざまな数学的演算に基づいている。その結果、多くの公開鍵暗号では鍵空間が疎になるため、同等のセキュリティを持つ共通鍵暗号より長い鍵が必要になる。例えば、RSA公開鍵暗号の鍵長は通常数千ビットだ。

RSA公開鍵長と共通鍵暗号の鍵長の正確な対応関係は不明だ。RSAのセキュリティは大きな素数の積を因数分解することの難しさだと考えられているが、アルゴリズムにはまだ発見されていない攻撃が存在する可能性もある。大きな素数の積を因数分解する実質的な難しさは、コンピュータ技術の進歩（ムーアの法則）だけでなく、二次ふるい法や一般数体ふるい法の発明・改良といった整数論の進歩によっても低下する。

1999年8月、研究者グループが数体ふるい法を使い、因数分解の実行時間のセットアップを含め、暦上7.4か月で512ビットの素数を因数分解した（http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html）。さらに、量子コンピュータのような新技術は多項式時間での素数因数分解を可能にすると期待されている。ただし、興味深い素数を因数分解するのに十分な量子コンピュータを実際に構築できるかどうかはまだ議論中なので、息をひそめて待つ必要はない。

RSA Security社は現在、ほとんどの企業用途には1024ビット、「極めて貴重な鍵」には2048ビットの鍵長を推奨している（http://www.rsasecurity.com/rsalabs/faq/3-1-5.html）。Bruce Schneierは Applied Cryptography 第2版で、2304ビットの公開鍵は128ビット共通鍵と同等のセキュリティを提供し、1792ビットの公開鍵は約112ビット共通鍵に対応すると推定している。

Xboxのセキュリティスキームを読み進める中で、これらの基本的な指針を念頭に置いておくといい——ブルートフォースでセキュリティを破ることがいかに難しいかを理解するために。ハッキングフォーラムには「なぜこれらの鍵に対して分散鍵探索プロジェクトを始めないのか？」という書き込みが繰り返し投稿される。これで答えがわかっただろう。

一般的な共通鍵ブロック暗号の暗号関数は、精巧に設計された換字・置換・圧縮・拡張の組み合わせとして実装される。これらの関数は平文を「混乱」させ「拡散」させるためのものだ。暗号関数のわずかな変化も、通常は暗号のセキュリティに大きな影響を与える。

共通鍵暗号では暗号化鍵と復号鍵が密接に関係しているため、特定のセキュリティ用途での利用が難しくなる。例えば、暗号化された文書をメーリングリストに配布したい場合、受信者全員が事実上僕の暗号化鍵を知らなければ文書を読めない。また、初めて連絡する相手と通信を開始するのも難しい——どこかの時点で鍵を相手に送る必要があり、その送信を傍受した第三者が鍵を盗んで、その後のすべてのメッセージを読んだり、偽造したり、改ざんしたりできてしまう。

公開鍵暗号は、暗号化と復号に異なる鍵を使うアルゴリズムだ。この理由から非対称暗号（asymmetric cipher）とも呼ばれる。公開鍵暗号の最大の利点は、一方の鍵を秘密にできることだ。これにより、信頼できないユーザーとデータをやり取りしても、そのユーザーが他の保護されたコンテンツを偽造したり読んだりできないようにできる。公開鍵アルゴリズムの欠点は、一般的に計算が複雑なため共通鍵暗号より遅いことと、同等のセキュリティを得るために長い鍵が必要なことだ。そのため、大量データのやり取りが必要な場合、公開鍵暗号は通常、高速な共通鍵暗号のための鍵を暗号化するために使われ、バルクデータ自体は共通鍵暗号で暗号化される。この共通鍵暗号の鍵はトランザクションごとにユニークにできるため、「セッション鍵（session key）」と呼ばれることが多い。

SHA-1ハッシュ ​

SHA-1（Secure Hash Algorithm 1）は、米国政府がFIPS（Federal Information Processing Standard）刊行物180-1（http://www.itl.nist.gov/fipspubs/fip180-1.htm）で推奨している安全なハッシュアルゴリズムだ。NSA（米国国家安全保障局）が考案し、Ronald L. RivestのMD4メッセージダイジェストアルゴリズムをベースにしたSHA-1は、264ビット未満の任意の長さのメッセージを処理して160ビットの出力を生成する。

SHA-1ハッシュアルゴリズムは確定的な160ビットのシード状態から始まる。この状態は512ビットのメッセージデータブロックと4ラウンドかけて混合される。各ラウンドは一連の非線形関数、ローテーション、シフト、XORで構成される。あるラウンドの結果が次のラウンドの計算のシードになる。一般に、同一のハッシュ値（つまりハッシュの衝突）を持つ2つのメッセージを見つけるには、280個のランダムなメッセージを生成してハッシュし「同時に」比較する必要がある。この「同一ハッシュを持つ2つのランダムなメッセージを見つける」ことは「誕生日攻撃（birthday attack）」と呼ばれ、「誕生日のパラドックス」という確率論的現象にちなんでいる——23人がいる部屋で2人が同じ誕生日を共有する確率は50%を超える、という現象だ。一方、特定のメッセージと同じハッシュ値を持つメッセージを見つけるには、2160個のランダムなメッセージを生成・比較する必要がある。このように、ハッシュ関数の強度はその使われ方に大きく依存する。

TEA ​

TEA（Tiny Encryption Algorithm、タイニー暗号化アルゴリズム）は、ケンブリッジ大学コンピュータ研究所のDavid WheelerとRoger Needhamが開発した。（開発者のTEAのウェブページは http://vader.brad.ac.uk/tea/tea.shtml にある。本節の内容の多くはそのページから引いている。）

c
void encipher(unsigned long *const v, unsigned long *const w,
    const unsigned long *const k)
{
    register unsigned long
        y=v[0], z=v[1], sum=0, delta=0x9E3779B9,
        a=k[0], b=k[1], c=k[2], d=k[3], n=32;
    while(n-->0) {
        sum += delta;
        y += (z << 4)+a ^ z+sum ^ (z >> 5)+b;
        z += (y << 4)+c ^ y+sum ^ (y >> 5)+d;
    }
    w[0]=y; w[1]=z;
}

リスト 7-1：ANSI CによるTEAアルゴリズム3

その名のとおり、TEAはリアルタイムデータストリームの暗号化や、プロセッサ性能とストレージが限られた組み込みアプリケーションに適したコンパクトで高速な暗号アルゴリズムだ。128ビット鍵を使い、64ビットのデータを1回の処理単位として扱い、32ラウンドそれぞれでシフト、XOR、加算だけを使う。（リスト 7-1と図7-2に示したアルゴリズムは、32ビット汎用プロセッサへの実装に最適化されている。）

Figure 7-1：TEA暗号の使用シナリオ

図7-1（上）：TEA暗号の使用シナリオ。 TEAを暗号として使う場合（128ビット鍵で64ビットブロックを暗号化）と、ハッシュ関数として使う場合（前の出力を次のTEA演算の鍵入力として連鎖させる）を示している。

Figure 7-2：TEAの内部構造

図7-2（下）：TEAの内部構造。 TEAの1ラウンドを示す図で、完全な暗号では32回繰り返される。右側のボックスに、暗号としての使用とハッシュ関数としての使用それぞれの鍵スケジュールを示している。

この小型のTEAアルゴリズムは、データの暗号化・復号に使うと十分に安全だと考えられている。ただし、XboxではTEAは暗号化には使われていない。実際には改変されたデービーズ・マイヤーモード（Davies-Meyer mode）で動作させることで、ハッシュ関数として使われている。ハッシュ対象の領域は64ビットのブロックに分割される。これらのソースデータブロックがTEAへの鍵入力の半分として使われる。もう半分の鍵入力は前のTEA演算の結果から得られ、最初のTEA演算にはマジックナンバーが使われる。

結果は図7-1に示す64ビットのハッシュ関数となる。TEAの計算効率が高いことから、このハッシュは誕生日攻撃に対して脆弱で、衝突を見つけるのに平均で232個のメッセージペアをテストすれば十分だ。Xboxの使用シナリオでは誕生日攻撃は適用できないものの、Xboxはハッシュを2回実行し、それぞれ異なるマジックナンバーシードを使って結果を連結し、128ビットのハッシュ値を生成している——おそらくブルートフォース攻撃を無効化しようとする試みだろう。

残念ながら、TEAには鍵スケジュールに弱点がある。すべてのTEA鍵には4つの関連鍵が存在する。つまり、どの鍵についても、同じ入力データで同じ暗号文を生成する3つの別の鍵を生成できてしまう。関連鍵の生成は、鍵ビットのペア（ビット31と63が1つのペア、ビット95と127がもう1つのペア）を反転するだけだ。これにより、TEAはハッシュ関数としての使用には適さない。この弱点は、CRYPTO 1996で発表されたJohn Kelsey、Bruce Schneier、David Wagnerによる論文「Key-schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and triple-DES」に詳しく記載されており、後にAndy Greenが率いるチームがこの弱点を利用してXboxセキュリティスキームの第2バージョンを破ることになった。

RC-4 ​

RC-4（Ron's Code 4またはRivest Cipher 4）は、Ron Rivestによる可変長鍵のストリーム暗号だ。RC-4の核心は鍵ストリームジェネレータで、暗号学的な擬似乱数生成器（CPRNG：Cryptographic Pseudo-Random Number Generator）と考えることができる。CPRNGの出力は平文ストリームと1バイトずつXORされ、暗号文が生成される。復号も同様に行われる。大まかに言うと、ジェネレータは最大256バイト（2048ビット）の値（鍵）で「シード」される。鍵が256バイトより短い場合は、シードとして使う前に256バイトになるまで繰り返される——これにより可変長鍵が使える。Xboxでは鍵は16バイト（128ビット）で、この暗号は「RC-4/128」と呼ばれる。

c
typedef struct rc4_key {
    unsigned char state[256];
    unsigned char x;
    unsigned char y;
} rc4_key;

void prepare_key(unsigned char *key_data_ptr, int key_data_len,
    rc4_key *key) {
    unsigned char swapByte, index1, index2;
    unsigned char* state;
    short counter;

    state = &key->state[0];
    for(counter = 0; counter < 256; counter++)
        state[counter] = counter;
    key->x = 0; key->y = 0;
    index1 = 0; index2 = 0;
    for(counter = 0; counter < 256; counter++) {
        index2 = (key_data_ptr[index1] + state[counter] +
                  index2) % 256;
        swap_byte(&state[counter], &state[index2]);
        index1 = (index1 + 1) % key_data_len;
    }
}

void rc4(unsigned char *buffer_ptr, int buffer_len, rc4_key *key) {
    unsigned char x, y, xorIndex;
    unsigned char* state;
    short counter;

    x = key->x; y = key->y;
    state = &key->state[0];
    for(counter = 0; counter < buffer_len; counter++) {
        x = (x + 1) % 256;
        y = (state[x] + y) % 256;
        swap_byte(&state[x], &state[y]);
        xorIndex = state[x] + (state[y]) % 256;
        buffer_ptr[counter] ^= state[xorIndex];
    }
    key->x = x; key->y = y;
}

リスト 7-2：UsenetへのオリジナルポストよりCによるRC-4コード4

RC-4は強力な暗号だと考えられているが、WEP（Wired Equivalent Privacy）などの欠陥あるシステムで悪用される鍵スケジュールアルゴリズムの既知の弱点がいくつかある。Scott Fluhrer、Itsik Mantin、Adi Shamirが「Weaknesses in the Key Scheduling Algorithm of RC4」（2001年8月の第8回暗号技術に関する国際ワークショップで発表）でこれらの弱点を詳述している。ただし、これらの弱点はXboxのRC-4実装に対しては適用できない。

ただし、Xboxセキュリティ第1バージョンでのRC-4の使い方に潜在的な問題がある。XboxでRC-4はx86コードのストリームを暗号化するために使われており、復号されたコードの完全性を確保する有意義なチェックが行われていない。これは、暗号文を変更すると、Xboxが実行するコードも変化することを意味する。肝心なのは、意味のあるコード変更を引き起こすような暗号文の変更を特定することだ。RC-4は1バイトずつ暗号化し、x86オペコードは最短で1バイトとして表現できるため、暗号文を変化させることで既知の位置の命令を「ブルートフォース」するのに必要な試行回数は最大でも28 = 256回だ。

どの位置をブルートフォースすべきかを特定するのはやや難しいが、キャッシュがオンになっている状態でも、暗号文ビットを変化させて命令フェッチのパターンに何が起こるかを観察することで、多くの情報が引き出せると思う。目標は、ジャンプオペコードのオペランドの位置を特定し、セキュアなプログラムがセキュアでないメモリ領域にジャンプするようにジャンプ先を変更することだ。古典的なボードゲーム「バトルシップ（海戦ゲーム）」のプロセスに似ている。1キロバイトのコードを推測する作業は最大218回の試行しか必要としないことも念頭に置いてほしい。この推測プロセスは、ロジックアナライザをROMエミュレータとホストコンピュータ上で動くコントロールスクリプトで連携させることで自動化できる。

RC-4の背景は実に興味深い。RC-4は1987年にRon Rivestが発明し、RSA Security社が企業秘密として保持していたが、1994年に匿名でサイファーパンクスメーリングリストに投稿されて公開された（リスト 7-2参照）。シンプルさと堅牢さという美点から、RC-4はWEP、SSL（Secure Sockets Layer）、SQL、CDPDなど多数のアプリケーションで採用されてきた。RC-4のソースコードは広く配布されてよく知られているが、暗号はRSA Securityの知的財産であることに変わりない。商用製品に組み込む前にRSA Securityからライセンスを取得することをお勧めする。

Figure 7-3：RSAとセッション鍵の使用

図7-3：RSAとセッション鍵の使用。 送信側は公開鍵RSAを使ってセッション鍵を暗号化して送り、受信側は秘密鍵でセッション鍵を復号する。その後、両者は高速なAESを使ってバルクデータを暗号化・復号する。

RSA ​

RSAは、1977年にRon Rivest、Adi Shamir、Leonard Adlemanが考案した公開鍵アルゴリズムだ。公開鍵アルゴリズムでは、公開鍵と秘密鍵の2つの異なる鍵が使われる。名前のとおり、秘密鍵は秘密にしなければならないが、公開鍵は自由に配布できる。RSAの数学的背景はコラム「RSAアルゴリズム」で簡単に説明する。XboxのコンテキストでRSAがどう使われるかを把握するために、RSAの数学的詳細を理解する必要はない。

現在、RSAへのブルートフォース攻撃は約1000ビット以上の鍵長では実行不可能だと考えられている。また、RSAを暗号システムに組み込む際に不注意であってはならない。RSAを使ったプロトコルへの攻撃がいくつかあり、例えば秘密鍵の保有者に巧みに細工されたメッセージへの署名をさせ、その署名から秘密鍵を導出するといった手法がある。

RSAを使ったメッセージの暗号化は、RSAをメッセージに対して呼び出すだけでシンプルに実現できる。ただし、RSA暗号化が処理できるメッセージブロックは短すぎ、暗号化プロセスも多くのメッセージに対して実用的な速度を出せない。そのため、RSAは通常、AESなどの高速な共通鍵暗号のシングルユースランダム鍵（セッション鍵）を暗号化するために使われ、メッセージのバルク部分はその共通鍵暗号で暗号化される。図7-3にこのプロセスを示す。

RSAは暗号化に加えて、デジタル署名も可能にする。デジタル署名は、安全でない通信路でメッセージを交換する当事者間で、メッセージが偽造されておらず改ざんもされていないことを保証するものだ。メッセージ自体を暗号化する必要はない。典型的なデジタル署名プロトコルは次のように機能する。送信者は送信するメッセージのハッシュを計算する。このハッシュを送信者の秘密鍵で暗号化し、メッセージの平文と一緒に送る。受信者は送信者の公開鍵を使って暗号化されたメッセージハッシュを復号し、受信したメッセージのローカルで計算したハッシュと比較する。復号したハッシュとローカルで計算したハッシュが一致すれば、受信者はメッセージが本物で改ざんされていないと結論づけられる。図7-4にこのプロセスを示す。

Figure 7-4：RSAを使ったデジタル署名

図7-4：RSAを使ったデジタル署名の実装。 送信者は秘密鍵でメッセージのハッシュを暗号化して署名を生成し、受信者は公開鍵で復号してハッシュを比較することでメッセージの真正性と完全性を検証する。

📦 コラム：RSAアルゴリズム

RSAアルゴリズムは1983年にマサチューセッツ工科大学（MIT）が特許を取得し、RSA Data Security社に独占ライセンスされた。RSAアルゴリズムの特許は2000年9月に期限切れとなり、今日ではあらゆるアプリケーションで自由に使用できる。インターネット上にはRSAを使った優れたチュートリアルや教育的な例が多数ある。「RSAアルゴリズム」で検索すればすぐ見つかるだろう。

RSAアルゴリズムは次のとおりだ（http://world.std.com/~franl/crypto/rsa-guts.htmlより引用・改変）。

  1. 2つの大きな（数千ビット長の）素数「P」と「Q」を見つける。
  2. E > 1、E < PQ、かつEが(P-1)(Q-1)と互いに素となるように「E」を選ぶ。Eは素数である必要はないが、奇数でなければならない。EとPQのペアが公開鍵となる。
  3. (DE - 1)が(P-1)(Q-1)で割り切れるように「D」を求める。D = (X(P-1)(Q-1) + 1)/E が整数になるような整数Xを見つけることで実現できる。Dが秘密鍵となる。
  4. 平文「T」は次の関数で暗号化する: C = (TE) mod PQ
  5. 暗号文「C」は次の関数で復号する: T = (CD) mod PQ

ただし、T < PQ である必要がある。PQより大きなメッセージは小さなメッセージの列に分割する必要があり、辞書攻撃などを防ぐため、非常に短いメッセージには慎重に選ばれた値でパディングする必要がある。

このプロトコルが複雑に聞こえるなら、実際にそのとおりだ。うまくいかなくなる箇所はたくさんある。受信者が送信者の公開鍵の偽のコピーを持っている可能性もある。送信者の秘密鍵が漏洩しているかもしれない。ハッシュに弱点があるかもしれない。敵対的な環境でデジタル署名を使うには、システム設計のあらゆるレベルで細心の注意が必要だ。

Xboxでは、デジタル署名はコンソール向けプログラムの配布と販売を管理するために使われている。Microsoftは実質的に、メッセージの送信者（ゲームメーカー）と受信者（Xboxコンソール）の両方を管理下に置いている。受信者——Xboxコンソール——はMicrosoftがデジタル署名したプログラムだけを実行するようプログラムされている。理想的には、Microsoftがコンソール上で実行できるプログラムを最終的に決定し、ハッカーはウイルス、トロイの木馬、バックドアを挿入するためにゲームを改ざんできないことになる。セーブデータも暗号化で封印されており、原則として実行ファイルにパッチを当てたりキャラクターのステータスを書き換えたりしてゲームでズルをすることは不可能だ。

明らかに、Xboxコンソールのハッキングにおいて重要な問題はこのデジタル署名システムの実装だ。XboxはSHA-1ハッシュと2048ビットRSA鍵を組み合わせており、ブルートフォース攻撃が成功する確率は極めて低い。もちろん、試みなければ確率はゼロだが、分が悪いことに変わりはない（コラム「とてつもなく難しい問題」参照）。宝くじで当てる方がまだましだ。これは偶然ではない——秘密鍵が発見されれば、ゲームコピーが簡単になり、デベロッパーはMicrosoftへのロイヤリティを払わずに済む（法的には義務があるかもしれないが、技術的な障壁はなくなる）。この鍵はMicrosoftにとっておそらく数十億ドルの価値を持つため、単一の人間が鍵の全体を知っているとは考えにくい——「ゴムホース（拷問）」や「グリーンペーパー（贈賄）」による暗号解析は人間には非常に効果的だからだ。（極めて貴重な秘密を守ろうとしているなら、リアルな「ブルートフォース」の可能性も軽視しないこと！）BBNのSignAssure™証明書認証管理システムのような製品は、高価値な鍵の物理的なセキュリティを確保し、マシンを起動するために複数の信頼されたユーザーの承認を必要とする秘密分散方式を実装している。

前述のとおり、RSAに対するいくつかの既知の有効な攻撃があるが、それらがすべてXboxのシナリオに適用できるわけではない——ユーザーグループへの依存や選択暗号文が必要なものもある。また、弱点のリストは広く知られており、ほとんどのデジタル署名実装にはこれらの攻撃に対する適切な対策が施されている。

セキュリティ全体像 ​

効果的なセキュリティシステムには、強力な暗号とハッシュに加えて、優れた鍵管理、強固なプロトコル、そしてXboxの場合には物理的なセキュリティが必要だ。

鍵管理は、セキュリティアーキテクトが直面する最も難しいシステム実装タスクの一つだ。結局のところ、復号鍵はユーザーの手に渡らなければならない。最低限の訓練しか受けていない一般ユーザーが誤って鍵情報を漏洩させないように、ユーザーインターフェースを設計する必要がある。暗号が強力になるにつれ、攻撃の最も簡単な経路はますますユーザー自身になっていく。監視カメラによる盗み見、ソーシャルエンジニアリング、あるいはパスワード入力時のキーボードの音のパターン分析さえも、暗号解析よりも単位労力あたりのパスフレーズ情報量が多いかもしれない。公開鍵暗号は鍵配布の問題を部分的に解決するが、中間者攻撃の可能性を排除するために公開鍵のフィンガープリントは対面で確認すべきだ。また、公開鍵暗号は、クライアントマシンへの物理的なアクセス権を持つ者が復号済み出力を盗み聞きするのを防げない。

また、プロトコル攻撃は、鍵やデータの操作方法、または強力な暗号の使い方における弱点を突く。RC-4に対するWEP攻撃や、Mike BondとRoss AndersonによるIBM 4758暗号プロセッサへの攻撃は、どちらもプロトコル攻撃の例だ。プロトコル攻撃の危険信号は、後方互換性対策を実装しているシステムや、主な職責が暗号セキュリティではないエンジニアによって実装されたシステムだ。

最後に、Xboxのような信頼できるクライアントを確立することを目的とするシステムでは、バックドアとバッファオーバーラン攻撃もマシンの信頼状態に対する有効な攻撃となる。広く使われている商用プロセッサは、命令ストリームやデータタグ内に実行権限を埋め込んでいない。プロセッサは、トランジェントなハードウェア障害によるものであれ、悪意を持って配置されたコードによるものであれ、ジャンプするよう命令された任意のコードを盲目的に実行する。マシン状態の定期的なハッシュによってこの欠陥を補えるが、その状態チェックさえ偽装できる。

本章の冒頭で述べたように、クライアントの信頼状態を確立するには、「信頼の種」を担う耐タンパーハードウェアも必要だ。物理的なセキュリティの強度は、一度セキュリティを破るのを経済的に引き合わないものにするとともに、一つのコンソールのセキュリティが破られても残りのコンソールへの簡単な攻撃につながらないよう強固である必要がある。物理的なセキュリティ設計のトレードオフと、Microsoftがその点でどのような判断を下したかは次章で詳しく述べる。

本章の教訓は、セキュリティには優れたシステム設計が必要だということだ。暗号はブルートフォース攻撃を事実上無意味にするほど強力になったが、システム自体は複雑化している。この複雑さはプロトコル攻撃やバックドア攻撃の成功可能性を高める一方で、古典的な盗み聞き・ゴムホース（拷問）・ユーザーエラー攻撃からユーザーを守る助けにはほとんどならない。

注 ​

  1. http://interviews.slashdot.org/article.pl?sid=03/02/04/2233250&mode=nocomment&tid=103&tid=123&tid=172
  2. Merriam-Webster OnLine Dictionary（http://www.webster.com）
  3. コードは http://vader.brad.ac.uk/tea/source.shtml#ansi より
  4. コードは http://www.cc.jyu.fi/~paasivir/crypt/rciv/rc4article.txt より。1ページに収めるため空白を若干修正。swap_byte 関数の定義は含まれていないが、名前から推測できる。
*原著*: *Hacking the Xbox: An Introduction to Reverse Engineering* © 2003 Xenatera LLC
*著者*: Andrew "bunnie" Huang | *出版*: No Starch Press
*日本語訳・レビュー*: ニコ技深圳コミュニティ / 高須正和（@tks） — [https://takasumasakazu.net](https://takasumasakazu.net) — CC BY-NC-SA 1.0
*注記*: 本翻訳は、原著の Creative Commons ライセンス条件に従って公開する翻訳コントリビューションであり、著者 bunnie からも歓迎のコメントをいただいています。出版社による公式日本語版ではありません。

ニコ技深圳コミュニティ / 高須正和（@tks）による日本語訳コントリビューションです。著者 bunnie からも歓迎のコメントをいただいています。原著は Andrew 'bunnie' Huang および No Starch Press に帰属します。

翻訳テキスト © 翻訳者 | 原著 © 2003 Xenatera LLC (著者: Andrew 'bunnie' Huang) | CC BY-NC-SA 1.0