共通鍵暗号の安全性に関する研究

近年のインターネットの急速な普及により，多量の情報がネットワークを流れるようになった．ネットワーク社会においては情報の盗聴，改竄，不正アクセスなどの脅威が潜んでおり、これに対する情報セキュリティの問題が重要なウェイトを占めるようになった．暗号技術は秘匿，完全性を実現する情報セキュリティの中でも根幹をなす技術である．
暗号は大きく分けて共通鍵暗号と公開鍵暗号の2つに分類される．共通鍵暗号は送信者と受信者で共通の鍵を用意する．この共通の鍵を用いて単純な論理演算，算術演算で構成された暗号化関数を繰り返すことにより秘匿したい情報（平文）を攪拌する暗号である．暗号化関数の繰り返し回数をラウンドと呼ぶ．数論に基づく公開鍵暗号と比べて高速な動作とコンパクトな実装が可能となっており，大量のデータの暗号化やICカード，携帯電話などの低速なCPUの機器での暗号化にも利用可能である．
共通鍵暗号はさらにブロック暗号とストリーム暗号に分類される．ブロック暗号は平文をブロックと呼ぶ単位毎に攪拌を行う．ブロック暗号の安全性は全数探索より効率的に鍵の推定が可能となるラウンド数で評価される．一方，ストリーム暗号は擬似乱数を生成し，この擬似乱数を平文とビットごとに排他的論理をとることにより暗号化を行う．ストリーム暗号の安全性は全数探索より効率的に鍵の推定が可能となる擬似乱数の量によって評価される．共通鍵暗号では様々な種類のアルゴリズムが提案されているが，本研究ではブロック暗号としてRC6，ストリーム暗号としてRC4について安全性の評価を行う．

RC6はRivestらによって提案された算術演算とビットシフトからなるソフトウェア実装向きの共通鍵ブロック暗号である．次世代暗号化標準規格（AES）の候補では最速のソフトウェア処理が実現できた．ワード長wビット，ラウンド数r，bバイト鍵のRC6は一般にRC6-w/r/bのように記述される．r=20, w=32, b=16, 24, 32が推奨される値である．なお，RC6-32は単にRC6と表す．また，post-whiteningなしのRC6をRC6Pと呼ぶ．
RC6に対する効果的な攻撃方法としてはχ^2攻撃が挙げられる．χ^2攻撃は入出力に現れる統計的偏りをχ^2統計量（χ^2値）を用いて計ることにより鍵を推定する攻撃手法である．Knudsenらは第1ラウンドでのF関数による巡回シフトが0になるようにとることで鍵を推測する攻撃法を提案した．武中らは，遷移行列を用いて理論的にχ^2値を求め，Knudsenらの攻撃法の理論的評価を行った．磯貝らはRC6Pの最終ラウンドから1ラウンド復号したときのχ^2値を利用するχ^2攻撃を提案し，その成功確率をDisinguishの結果を用いて理論的に導出する方法を示した．高野らは，磯貝らのアルゴリズムをRC6に対して拡張し，RC6/16/24，RC6/16/32において総当り攻撃よりも効率よく解読可能であることを示した．しかし，このアルゴリズムは64ビットの最終拡大鍵を同時に推定するため，計算量・メモリ量共に大きく128bit-key RC6では8ラウンドが限界である．なお，128bit RC6はχ^2値の実験値より12ラウンドまで解読可能であると見積もられている．樋上らは検定ビット位置と鍵を非対称に扱う非対称χ^2検定攻撃を提案し，192bit以上の鍵については16ラウンドRC6の解読に必要な計算量を2181から2158に削減した．樋上らは誤鍵でのχ^2値の分布について仮定をおき，これに基づいた成功確率の理論値を求めている．しかし，高野らの攻撃と比べて非対称χ^2検定攻撃は攻撃成功確率の実験値と理論値が大きく異なっている．
RC4はRon Rivestによって1987年に開発されたストリーム暗号である．SSLやWEPなどで広く用いられている．そのアルゴリズムはRSA Data Securityが保持しており，公開されていない．しかし，1994年にインターネットを通じてアルゴリズムが漏洩し公知のものとなって以後，様々な解析が行われている．FluhrerとMcGrewは連続した2つの出力（digraph）の出現確率の偏差を用いることにより，RC4の出力と真の乱数列とを識別するdistinguishの手法を示した．また，内部状態のa個の要素のみが連続するa個の出力に影響するFortuitous状態について解析を行った．PaulらはFortuitous状態の考え方を拡張し，内部状態のa個の要素のみが不連続なa個の出力に影響するNon-Fortuitous状態について解析を行っている．Mantinは同一のdigraphが現れる場合での内部状態の遷移を解析し，繰り返し現れるdigraphを用いたdistinguishの手法について示した．RC4のdigraphに関する状態遷移についてはFluhrerらによって数例が示されているが，多くは明らかにされていない．

本研究ではRC6に対する非対称χ^2検定攻撃理論値を求める上での誤鍵でのχ^2値の分布についての仮定を細分化することによって，厳密な理論値を求めた．また，RC4については連続した同じ値が出たdigraphに着目し，その様なdigraphが現れた場合の内部状態について解析を行った．