对RC4算法的明文恢复算法研究

Research on Plaintext Recovery Algorithm of RC4

随着RC4算法输出密钥流偏差规律的不断暴露, RC4算法面临极大的安全挑战. 2013年Al Fardan等学者利用RC4算法输出密钥流偏差规律,提出了一种明文恢复算法.在他们的算法中,利用13·2^(30)个不同种子密钥加密同一明文得到的密文,可以以100%的成功率恢复明文的前256字节.同年,为了恢复经RC4算法加密的明文任意字节, Ohigashi等学者提出了猜测确定攻击算法,利用235个不同种子密钥加密同一明文得到的密文,可以以100%的成功率恢复明文的任意字节.但是当密文量小于2^(35)时,恢复成功率下降明显.本文用t值统计量代替传统概率统计,充分利用现有偏差规律,改进了算法的猜测部分,提出了一种更有效的猜测确定攻击算法.利用2^(34)个不同种子密钥加密同一明文得到的密文,可以以接近100%的概率恢复明文的任意字节,当密文量为2^(33)时,能以超过98%的概率恢复任意字节.

With the exposing biases of the output key streams,RC4 algorithm is confronted with great security challenges.In 2013,Al Fardan et al.proposed a plaintext recovery attack using singlebyte and double-byte biases.Given 13.2^30ciphertexts encrypted by different keys,the first 256bytes can be recovered successfully with probability 1.In the same year,Ohigashi et al.proposed a guess and determine attack to recover the plaintexts encrypted by RC4.Given 2^35ciphertexts encrypted by different keys,any byte of a plaintext can be recovered with probability close to 1.However,when the amount of ciphertexts is less than 2^35,the success probability decreases rapidly.This study proposes a more effective guess and determine attack by using the t value to replace the traditional probability,and the existing bias is fully utilized to modify the guess phase of Ohigashi's algorithm.Given 2^34 ciphertexts encrypted by different keys,any byte of a plaintext can be recovered by the proposed method with probability close to 100%,and given 2^33 ciphertexts encrypted by different keys,any byte of a plaintext can be recovered with probability being above 98%.