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

　共通鍵暗号とは暗号化と復号に同じ鍵を用いる暗号方式である．共通鍵暗号はさらにストリーム暗号とブロック暗号に区別されるが，本研究で対象とするのは後者の暗号方式の1つであるRC6[RRSY98]である．共通鍵暗号の特徴としては，高速に実行可能という点がある．これは，WEBや携帯電話，VPNなど，スループットが重要となる通信形態でも用いられるからである．このように幅広いサービスで用いられる共通鍵暗号の安全性を正しく，正確に評価することは社会的にも重要なテーマであると言える．ところが共通鍵暗号では公開鍵暗号と違い，安全性の評価においては理論的に評価することが難しく，本研究の対象とする攻撃方法においても，その安全性はこれまで実験値を用いた推測でしか求められていなかった．本研究ではこの安全性の評価を理論的に行うといったことについても，主眼を置いている．
　RC6はRivestらによって提案された共通鍵ブロック暗号方式であり， AESの最終候補の1つであった．その構成は単純な算術演算とビットシフトのみとなっており，ソフトウェア実装向きの仕様となっている． RC6は1ワードwビットとして4ワード単位で暗号化と復号を行う． RC6-w/r/bと表記され，wは1ワードのビット数，rはラウンド数， bは鍵のバイト数である．推奨はRC6-32/20/{16,24,32}となっている．ここで，RC6暗号化アルゴリズムの最初と最終段の加算が無いバージョンをRC6W，最終段の加算が無いバージョンをRC6Pと表記する．
　RC6に対する最も有効な攻撃手法の一つとして\chi^2[KM00]攻撃が知られている． \chi^2攻撃にはDistinguish攻撃とそれを利用するKey Recovery攻撃がある． Distinguish攻撃とは暗号文と乱数列を区別する攻撃であり，本研究で対象とする$chi^2攻撃の場合，統計学で適合度検定として用いられる\chi^2検定を用いて乱数列と区別する． Key Recovery攻撃とは実際に鍵(の一部)を導出する攻撃である．
　\chi^2攻撃を用いたDistinguish攻撃の理論的な解析手法は[TSK04]で示された． [TSK04]ではRC6の暗号文出力である下位10ビットの出現確率を理論的に導出し，Distinguish攻撃における$chi^2値の平均値を理論的に導出可能なことが示された．また[MMT04]ではRC6Pに対するKey Recovery攻撃の成功確率をDistinguish攻撃の結果を用いて導出する方法が示された．本報告では[TSK04, MMT04]の結果を用いて，RC6Pに対するKey Recovery攻撃の成功確率を理論的に導出することに成功した．その結果，Key Recovery攻撃の成功確率が95%以上となるのに必要な平文数の近似式は
log_2(#texts) = 8.01 r - 11.33
となり[IMM03]で示されている実験結果とほぼ一致した．
　さらに本報告では[IMM03]に示されているRC6Pに対するKey Recovery攻撃を拡張し，RC6に対してもKey Recoveryを行えるように改良を行い，成功確率を理論的に導出した． [IMM03]の拡張として，まず初めにRC6Pに対する攻撃を単純に拡張したアルゴリズム~3を示す．アルゴリズム~4はアルゴリズム~3を拡張し，利用可能な平文数が2^{128}までとなるようにした．アルゴリズム~5では，アルゴリズム~4をさらに改良し，メモリ，計算量的により効率のよいアルゴリズムを考案した． [KM00]では 192, 256bit鍵のRC6に対してそれぞれ14, 15段まで全数検索よりも効率良く鍵の導出が可能としていた．対して提案アルゴリズムでは，192, 256bit鍵の場合，全数検索よりも効率的に解読が可能となる段数は16段までとなった．また4ラウンドのRC6-8に対して拡張したKey Recoveryアルゴリズムを適用し，その成功確率の理論値と実験値を計算し比較を行った．その結果，理論値と実験値は近い値となり，理論値は実際の値のよい近似となっていることを示した．さらに，3つのアルゴリズムの比較も行い，計算量とメモリ使用量に関する考察も行った．

【戻る】