一石二鳥のセキュリティ:高速で堅牢な新しいコーディング スキーム

今日のデジタル世界には膨大な量の重要なデータが存在します。これらのデータは、伝送中か保存中かに関係なく、予期しないデータ損失やデータ破損が発生しても、安全に利用できるようにする必要があります。ECC(エラー訂正コード)は、低信頼性のネットワークやメディア上で高信頼性のデータ伝送やデータ保存を実現するうえで重要なツールであり、デジタル メディア ブロードキャスト、セルラー ネットワーク、衛星通信から、ハイエンドのRAM、DVD、ディスク、クラウド ストレージに至るまで、実際に幅広く使用されています。

ECCでは、冗長性を付加してデータをエンコードします。データは記号に分割されたメッセージと見なされ、その記号が各種のコード記号に変換されます(多くの場合、追加の記号をメッセージに付加するだけです)。コード記号の一部が変更または削除されても、通常は、それらをデコードして元のメッセージを復元するのに十分な情報が残ります。ほとんどのECCは少数のランダムなエラーから保護できるように設計されていますが、ECCの重要な応用例の中には、甚大な損害を引き起こすように特別に的を絞ったエラーを攻撃者が添加できるものもあります。

こうした敵対的なデータ破損から保護することを目的とした既知のECC(リード ソロモン コードなど)のほとんどは、計算コストが高く、大規模なデコード処理が必要になります。噴水コード(LTコード[1]やRaptorコード[2]など)は、その対極にあるECCです。これらのECCは、新しいコード記号から成る潜在的に無制限のストリームをオン デマンドで生成し、記号が利用可能になったときにデコードすることにより、極めて効率的なメッセージのエンコーディングおよび復元を実現します。RaptorコードはIETFによって標準化(RFC 5053および6330)された最先端の噴水コードで、マルチメディア サービス(MBMS、DVB-H、IP-TVなど)のストリーミング メディアや衛星通信といった幅広い応用分野をサポートするために他の標準でも採用されています。

しかし、このように効率性に優れている反面、品質上の制限があります。設計上、LTコードおよびRaptorコードが確実に動作できるのは、コード記号が偶然に失われたと考えられるランダムな消失が発生した場合だけです。これらのECCは、この穏やかな使用上の設定から逸脱するとすぐに、デコードを確実に行うことができなくなります。的を絞って記号を消去するだけで、デコードの失敗や遅延発生の可能性が高まることもあります。これは、攻撃者がコード構造の弱点を利用することで、メッセージの復元を最大限に妨げるように消去する記号を選択できるためです。

実際、的を絞った消去は簡単に実行できます。たとえば、セキュリティ侵害を受けたルーターが通過する記号を選択的に消去するような場合です。最近、Lopes氏とNeves氏[3]がTFTPアプリケーションに対する攻撃のデモンストレーションを行いました(標準化されたRaptorコードでエンコードしたファイルをTFTPアプリケーションで転送)。彼らは、コードの弱点を利用して、その構造を完全に予測し、最も有害な消去パターンを事前に計算しました。驚くべきことに、消去された記号はデータに依存せず、ほとんどの場合、その構成にはごくわずかなコード記号しか含まれていません。しかも、ほぼ必ず、メッセージは復元できなくなります。攻撃は回線速度で実行可能であり、ごくわずかな記号しか消去されないため、攻撃を検出するのは極めて困難です。しかも、エンコーディングが認証または暗号化されている場合(つまり、TFTPがIPsec/ESP上で実行されている場合)でも、ファイル転送を効果的に妨害することができます。

RSAは最近、上記の問題の解決策を見つけました。共同研究者であるAri Juels氏、James Kelley氏、Roberto Tamassia氏との共同作業において、実用的な効率性と、的を絞ったエラーに対する強力な耐性の両方を備えた、暗号で強化されたコーディング スキームを開発できることを示したのです。Falconコード[4]と呼ばれるRSAのソリューションは、LTコードに基づく認証型のECCに分類され、効率性と消失に対する耐性の両方に優れた品質を実現します。Falconコードはほぼすべてのケースにおいて、標準的なLTコードの主な機能を維持しながら、敵対的な記号破損を訂正することができます。つまり、十分な量の記号が破損せずに残っている限り、コード記号の「噴水」をすばやく生成し、メッセージを迅速に復元できるのです。

この新しい設計は、LTコードを2つの基本的な方法(秘密鍵の使用およびコード構造の保護)で強化します。秘密鍵は、データのエンコーディングとメッセージの復元に使用されます。また、強力な擬似乱数生成器(エンコーディングをランダム化し、予測できないようにする)、オプションの安全な暗号(記号を暗号化し、漏洩を防止する)、偽造不可能なMAC(記号を認証し、エラーの伝播を防止する)の単純な組み合わせにより、コード構造が完全に保護されます。この新しいエンコーディングをデータ ストライピングと注意深く組み合わせると、大きなサイズのメッセージ(たとえば数GB)を処理できる拡張性に優れたバリエーションを作成できます。Falconコードは、核となるLTコーディング レベルにおいて暗号を適切に使用することにより、Raptorコードを安全に拡張しつつ、高効率性(300 MB/秒のスループット速度など)を実現できます。Falconコードは便宜上、通信チャネル(SSHまたはIPsecによるトンネリングなど)によって実現されるセキュリティを利用して、必要なオーバーヘッドをさらに制限することもできます。

悪意のある限定的な破損が存在する場合でもメッセージの迅速な復元を保証する、包括的かつ高速なオンザフライのコード記号生成は、多くの実践的なシナリオにおいてFalconコードの価値を高める魅力的な特性です。Falconコードは、LT/Raptorコードよりもはるかに強力なセキュリティを実現できるうえ、わずかなオーバーヘッドしか発生しないため、優れた実用性を継続的に提供できます。特に、Falconコードは、Lopes氏とNeves氏が行った的を絞った消去攻撃に対して、実証可能な方法でRaptorコードを強化することができます。さらに、リード ソロモン コードなどの攻撃耐性の高い既存のコードに匹敵するセキュリティだけでなく、優れた効率性も提供します。特に、クラウド ストレージのセキュリティ プロトコルで使用される、カスタム設計されたコード(Shi氏など[5])の一時的な代用品として使用する場合、Falconコードによって35%高速化できます。このような設計により、Falconコードはセキュリティと効率性の両方を強化することができます。

[1] M. Luby:「LT Codes」、IEEE Symposium on Foundations of Computer Science 2002:271ページ

[2] A. Shokrollahi:「Raptor codes」、IEEE Transactions on Information Theory 52(6):2551~2567ページ、2006年

[3] J. Lopes、N. Neves:「Stopping a Rapid Tornado with a Puff」、IEEE Symposium on Security and Privacy 2014:509~523ページ

[4] A. Juels、J. Kelley、R. Tamassia、N. Triandopoulos:「Falcon Codes: Fast, Authenticated LT Codes (Or: Making Rapid Tornadoes Unstoppable)」、ACM Conference on Computer and Communications Security 2015:1032~1047ページ

[5] E. Shi、E. Stefanov、C. Papamanthou:「Practical Dynamic Proofs of Retrievability」、ACM Conference on Computer and Communications Security 2013:325~336ページ

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

No Comments