共通鍵暗号の安全性に関する研究
スマートフォンを始めとする携帯型情報端末の急速な普及に伴い,大容量データを高速に処理できる暗号アルゴリズムの重要性が高まっている.このような背景のもと,共通鍵暗号の一種であるストリーム暗号が注目されている.ストリーム暗号は,秘密鍵を入力して生成される擬似乱数と平文の排他的論理和によって暗号文を出力する方式である.ビット単位もしくはバイト単位で逐次暗号化できるため,高速な暗号通信が可能となる. RC4は1987年にRon Rivestによって設計されたストリーム暗号である.RC4のアルゴリズムは鍵スケジューリングアルゴリズム(KSA)と擬似乱数生成アルゴリズム(PRGA)から構成される.KSAでは可変長の秘密鍵から$N$個の要素の置換で構成される内部状態を生成する.PRGAでは内部状態を更新しながら1ラウンド当たり1バイトの鍵ストリームを生成する.生成された鍵ストリームを擬似乱数として暗号化処理を行う. RC4はLotus NotesやOracle secure SQL等の商用アプリケーション,WEP,WPA,SSL/TLS等の標準プロトコルで利用されているため,RC4に未知の脆弱性が存在した場合,社会に大きな影響を及ぼすこととなる.また,RC4に対する安全性評価が数多く行われているものの,未だ現実的な脅威となる攻撃は報告されていない.したがって,RC4に対する新たな安全性評価を行うことは重要であると考える. RC4に対する代表的な攻撃として,識別攻撃[IOWM13],内部状態復元攻撃[DMPS2011],鍵回復攻撃[SVV11]が挙げられる.識別攻撃は,真性乱数と比較して鍵ストリームに偏り(bias)が存在することを利用した攻撃である.[IOWM13]において,攻撃に利用できる最適なbias setと攻撃手法が示され,[SGPM13]において,未評価なbiasに対する理論的な証明が行われた.内部状態復元攻撃は,鍵ストリームから秘密鍵と等価な内部状態を求める攻撃である.[Jenkinse96,MG13]において,ある条件を満たす鍵ストリームから特定の内部状態にbiasがあることが示された.鍵回復攻撃は,鍵ストリームから秘密鍵を直接求める攻撃である.[SVV11]において,鍵ストリームと秘密鍵間にbiasがあることを利用して効率的に攻撃する手法が理論的に示された.以上より,RC4に対する攻撃ではbiasが重要な鍵となる. 本研究の目的は,RC4の安全性を評価することである.具体的には,攻撃の重要な鍵となるbiasに着目する.実験を通して新しいbiasを探索し,発見したbiasの理論的な証明を行う.最終的に,これらのbiasを用いた攻撃手法について検討する.