RC4密钥流序列统计漏洞分析

刘莺迎

【摘要】 在大数据的条件下，利用黑盒统计法对RC4密钥流序列进行统计，寻找密钥流序列的不随机现象。针对不同长度密钥，统计了随机生成密钥和固定位置遍历密钥两种情形下密钥流序列的分布特点。对统计结果作出曲线图，详细分析了RC4密钥流序列的非随即现象。

【关键词】 RC4算法 密钥流序列 统计 偏差

一、RC4算法的相关介绍

序列密码作为一种计算速度快，实现简单的密码，在网络密码系统中得到了广泛的应用，例如RC4、A5、snow、seal等加密算法。尤其是美国密码学家设计的RC4加密算法，凭借其简单、高效的特点，目前仍然在许多领域中被应用，如安全协议标准SSL协议、TLS协议、WEP协议、基于Wi-Fi保护接入中的WPA协议等。RC4算法也被集成于Microsoft Windows、Lotus Notes、Apple AOCE、Oracle Secure SQL中。另外，该算法也被选为蜂窝数字数据包规范的一部分。

二 、预备知识

2.1 RC4算法流程

RC4由密钥调度算法和密钥流序列生成算法两部分组成。RC4的密钥长度可变，变化范围是[1，255]。给定一个密钥，伪随机数生成器接受密钥，混淆用与产生密钥流序列的S盒。在算法的第二部分，S盒也会随着加密过程发生变化。RC4加密算法是按字节产生密钥流序列，并将密钥流序列逐个字节与明文异或，加密得到密文。由于异或运算的对合性，解密过程与加密过程一致。

Z ： 当前时刻输出的密文；

i， j： 指针变量。

RC4算法首先执行密钥调度算法，对长度为256的S盒初始化，将0到255的互不重复的元素依次装入S盒，再利用密钥key将S盒打乱，得到算法第二部分S盒的初始状态。其次执行密钥流序列生成算法，将S打乱，再随机输出盒中某个位置的状态。每输出一个字节的密钥，S盒的状态发生变化。

2.2统计方法

1. 基于大数据的黑盒统计法

关于统计方法，有许多种，如简单统计、复杂统计、简单找重、组合找重等。在本文的统计过程中，使用到的是简单统计法，即在用大量密钥流序列做大量实验的基础上，对单个数值进行频数或者频率等的统计。

2. 漏洞分析方法

在漏洞分析上采用黑盒分析法，即用大量不同的初始密钥产生大量密钥流序列，用不同的统计方法对密钥流序列进行频率和t-值等进行统计，并根据条件和需要做相应图表，观察统计结果，凭借经验等去判断序列的不随机性。

三、RC4密钥流序列的统计偏差寻找

3.1偏差统计的理论基础

在前期的研究工作中，若遍历四字节的初始密钥，数据量为232，即42亿的种子密钥，由每个密钥种子生成密钥流序列的前32或者40个字节。

3.2密钥流序列的非随机性和规律

1.随机选取密钥种子

从上面五种情况的折线图中，在随机选取232个密钥的情况下，有以下五个明显的单字节非随机性：

（1）前40个字节的统计结果中，每个字节从0x00到0xFF的t-值随着该字节取值的变大而波动上升；

（2）前40个字节的每个字节中，取值为0x00的t-值很大，同时0x00出现的频率远大于其随机概率1/256；

（3）第1个字节中，取值为0x00和0x81的t-值偏小，约为-20，且随着取值的变化，t-值不随逐渐增大，而是呈s-型变化的；

（4）第2个字节中，实验数据表明，0x00出现的频率是其理论随机概率的两倍，t值非常高，在数据量为232的基础上，其t-值达到4000多倍；

（5）第3个字节中，取值为0x00和0x83的t-值偏大，

2. 固定32位遍历种子密钥

在本次实验中，仅对密钥长度为128bits和256bis的情况作了研究，可以发现以下几点不随机性：

（1）对于前40个字节的每一个字节，随着各个字节取值的增大，其t-值分布依然有增大的趋势，但不如随机选取密钥的增长趋势明显；

（2）对每个字节，其t-值普遍比随机选取种子密钥时大，在相同数据量的情况下，固定位置遍历密钥的t-值约为随机选取密钥的2倍；

（3）前40个字节的每个字节中，取值为0x00的情况和随机选取密钥一致，t-值很大，同时0x00出现的频率大于其随机概率1/256；

参 考 文 献

[1]Nadhem J.AlFardan，DanielJ.Bernstein，Kenneth G.Paterson，Bertram Poettering，Jacob C.N.Schuldt， On the Security of RC4 in TLS ， 2013；

[2]Scott R. Fluhrer and David A. McGrew，Statistical Analysis of the Alleged RC4 Keystream Generator，170 West Tasman Drive， San Jose， 2000；

[3]Itsik Mantin and Adi Shamir，A Practical Attack on Broadcast RC4，Compute-r Science Department， The Weizmann Institute， 2001；