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

摘要

RC4 は1987年に開発されたストリーム暗号である．現在もWEP（WEP(Wired Equivalent Privacy），WPA（Wi-FiProtected Access），SSL等様々なアプリケーションで使用されており．未だに現実的な時間内において脅威となる解読法は見つかっていない．RC4 はKey Scheduling Algorithm（以下KSA）とPseudo Random Generation Algorithm（以 下PRGA）に分類できる．KSAは鍵と初期値を入力としPRGAの初期内部状態を生成するアルゴリズム，PRGAは初期内部状態を用いて疑似乱数を出力するアルゴリズムである．2009年，宮地らにより2／ミイトのみ異なる2つのPRGA初期内部状態に対し，初期差分位置が与えられた際の内部状態遷移解析が行われた【1】，【10】．これは，2つのPRGAから得られる出力の差分に着目し，差分位置の遷移が起こったかどうかを判定することにより，内部状態を推測するという解析方法であった．また，著者らは【9】において，与えられた初期差分位置を元に，状態遷移後の差分位置を推測することにより内部状態復元アルゴリズムを提案した．本稿では，2バイトのみ異なる2つのPRGA初期内部状態に対し，初期差分位置が与えられたという条件において，出力差分を解析することにより，一部の内部状態をランダムに推測するよりも最大32．27％高い確率で推測するとともに，差分位置を特定することが内部状態を特定することにつながることを示した．よって，【9】にて得られた差分位置推測の結果を元に．内部状態復元アルゴリズムを提案した．%RC4 was developed by Rivest in 1987. It is used in various applications, for example WEP (Wired Equivalent Privacy), WPA (Wi-Fi Protected Access), SSL and so on. The cryptanalysis of RC4 had been proposed many times. But no method of cryptanalysis can get the message in realistic time. RC4 algorithm is divided into Key Scheduling Algorithm (KSA) and Pseudo Random Generation Algorithm (PRGA). KSA is given a secret key and generates the internal state S, which is an input of PRGA. PRGA is given the internal state S and generates pseude-random output and updates the internal state. In 2009, Miyaji, Sukegawa, Ajiro analysed the correlation between two bytes internal state with two differences in the initial round [1], [10]. Miyaji et al focused on the relationship between the difference of two state outputs and the positions where differences exist in the initial round. By the relationship they guessed the internal state. In this study, we analysed the following based on the correlation between two internal states with two bytes differences in the initial round. We estimates the PRGA internal state, 32.27% more effctively than random guessing. And we proposed the internal state restoring algorithm using [9].