abstract

ストリーム暗号は,大容量データを高速に処理するために広く利用されている共通鍵暗号方式の一種である.高度情報化社会の進展に伴い,多くの人々が多種多様な情報をこれまで以上に「高速・大容量」かつ「低遅延」で取り扱うことが可能となっており,ストリーム暗号の重要性が今後もより一層高まるものと考えられる. この博士論文は,ストリーム暗号の統計解析に関する研究成果についてまとめたものであり,特にストリーム暗号の1つであるRC4 を研究対象としている.RC4 に対する安全性評価には,大きく分けて3つのステップがある.まず最初に,RC4 の秘密鍵,内部状態,擬似乱数系列(キーストリーム)に関し,バイアスや相関性と呼ばれる統計的脆弱性について調査することである.次に,発見した新しい統計的脆弱性を平文回復攻撃,鍵回復攻撃,内部状態復元攻撃などに適用し,これらの攻撃の効率性を向上させることである.最後に,暗号化/復号にRC4 を利用しているWPA-TKIP などで統計的脆弱性の発生を抑制するための改善策について提案することである. この博士論文の目的は,RC4 への統計解析を通じてストリーム暗号全体の安全性評価に貢献することである.我々の研究成果は,次のとおりである. 最初に,我々は,キーストリームと内部状態の間における相関性の一種「Glimpse Correlations」に着目する.既存研究では.ポジティブなバイアスを有するGlimpse Correlations しか示されておらず,また,これらのGlimpse Correlations は,特定のラウンドに着目した解析結果が存在しない.そこで,我々は,既存のGlimpse Correlations を2つの観点から詳細に解析する.1つ目の観点として,我々は,既存のGlimpse Correlations に加え,全てのポジティブ又はネガティブなバイアスを有するGlimpse Correlations を解析する.2つ目の観点として,我々は,特定のラウンドに着目してGlimpse Correlations を解析することにより,既存研究で示された結果とは異なる統計的脆弱性の有無を解析する.結果として,我々は,6種類の新しい統計的脆弱性を有するGlimpse Correlations を発見するとともに,これらの事象に関する証明を示した. 次に,我々は,WPA-TKIP で利用されるRC4 の内部状態と秘密鍵の間における相関性,いわゆる「内部状態に関する鍵相関」について解析する.WPA-TKIPには,RC4 秘密鍵の先頭3バイトが公開パラメータから設定されるという特徴があり,我々の解析では,この特徴を利用する.結果として,我々は,内部状態に関する22種類の鍵相関を発見するとともに,これらの鍵相関に関する証明を示した.我々の証明は,RC4 の内部状態に関する鍵相関がTKIP によってどれくらい多く発生するのかを明らかにしている.このような結果を受け,我々は,WPA-TKIP においても,一般的なRC4 のセキュリティレベルを維持できるように,RC4 秘密鍵の設定方法に関する改善策を提案する.実験の結果,提案方法によるRC4 秘密鍵の設定では,WPA-TKIP におけるRC4 秘密鍵の設定方法と比較して,内部状態に関する鍵相関を含む統計的脆弱性の発生を約70%抑制することに成功し,提案方法に有効性があることを示した. また,我々は,2バイトのRC4 秘密鍵とキーストリームの間における相関性を解析する.なお,特定のラウンドごとに2バイトのRC4 秘密鍵ペアが反復して一致することから,このような相関性を「反復性のある鍵相関(Iterated RC4 Key Correlations)」と呼んでいる.結果として,我々は,新しい鍵相関を発見するとともに,これらの鍵相関に関する証明を示した.さらに,我々は,発見した鍵相関をWPA-TKIP に対する既存の平文回復攻撃に適用する.実験の結果,我々は,ブロードキャストセッティングにおいて約2^{30}の暗号文を入手することにより,約90.8%の確率で先頭257バイトの平文を復元することに成功した.この成功確率は,既存攻撃よりも約6.0%高いため,提案手法によって効率性が向上したことを示した. 最後に,我々は,これまで述べてきた我々の研究成果と今後の課題についてまとめることで博士論文を締めくくるとともに,我々の「ストリーム暗号の統計解析に関する研究」成果がストリーム暗号全体の安全性評価に貢献できること,そしてより安全なストリーム暗号の構成に貢献できることを示した.

Top