差分情報を利用したRC4 PRGA内部状態復元アルゴリズムの改良

摘要

RC4は1987年に開発されたストリーム暗号である．現在もWEP （Wired Equivalent Privacy），WPA （Wi-Fi Protected Access），SSL等様々なアプリケーションで使用されており，未だに現実的な時間内において脅威となる解読法は見つかっていない．RC4はKey Scheduling Algorithm（以下KSA）とPseudo Random Generation Algorithm（以下PRGA）に分類できる．KSAは鍵と初期値を入力とLPRGAの初期内部状態を生成するアルゴリズム，PRGAは初期内部状態を用いて疑似乱数を出力するアルゴリズムである．2009年，宮地らにより2バイトのみ異なる2つのPRGA初期内部状態に対し，初期差分位置が与えられた際の内部状態遷移解析が行われた．これは，2つのPRGAから得られる出力の差分に着目し，差分位置の遷移が起こったかどうかを判定することにより，内部状態を推測するという解析方法であった．また，著者らはにおいて，与えられた初期差分位置を元に，状態遷移後の差分位置を推測することにより内部状態復元アルゴリズムを提案した．本稿では，2バイトのみ異なる2つのPRGA初期内部状態に対し，初期差分位置が与えられたという条件において，出力差分を解析することにより，一部の内部状態をランダムに推測するよりも最大32.27％高い確率で推測するとともに，差分位置を特定することが内部状態を特定することにつながることを示した．よって，にて得られた差分位置推測の結果を元に，内部状態復元アルゴリズムを提案した．