# SSL/TLS协议安全系列：再见，RC4

Author: 乌云历史资料库 (@wooyun_archive)
Published: 2015-10-26T02:28:00Z
Canonical: https://wepostx.com/topics/1133

> 乌云历史资料归档
>
> **原始作者：** GoSSIP_SJTU
> **原始编号：** superkieran-wooyundrops:848
> **原始发布时间：** 2015-10-26 10:28
> **声明：内容仅用于技术研究和个人使用，版权归 wooyun.org。**

---

# 0x00背景

RC4是美国密码学家Ron Rivest在1987年设计的密钥长度可变的流加密算法。它加解密使用相同的密钥，因此也属于对称加密算法。RC4曾被用在有线等效加密（WEP）中，但由于其错误的使用的方式已被有效破解，而如今，它又被TLS协议所放弃。
在2015年2月发布的RFC7465中,RC4密码套件被禁止在TLS各版本的客户端和服务端使用。客户端禁止在ClientHello中包含RC4套件，服务端禁止从ClientHello中提供的密码套件中选择RC4，如果客户端只提供了RC4，服务端必须终止握手。另外，谷歌、微软、Mozilla也宣布将于明年年初在各自的浏览器中停止对RC4的支持。
从1994年RC4被匿名公开在Cypherpunks邮件列表，到如今RC4被TLS协议放弃，安全研究员们做出了很多贡献。

# 0x01 RC4

RC4算法分为两个部分。第一部分是密钥调度算法（key-scheduling algorithm）,根据key初始化S盒，第二部分是伪随机数生成算法(Pseudo-random generation algorithm)，生成密钥流，同时更新S盒的状态。
密钥调度算法:

```text
Input： 密钥K ，K长度Ｌ字节 Output:初始化后的S盒子 For i=0 to 255 do S[i] = i j=0 for i=0 to 255 do j = ( j+S[i]+key[i mod L] )mod 256 Swap(S[i],S[j]) Return S
```
伪随机数生成算法:

```text
Input: S盒 Output：生成的密钥流 i=0 j=0 while GeneratingOuput I = (i+1) mod 256 j = (j+S[i]) mod 256 Swap（S[i],S[j]） Z = S[ (S[i]+S[j]) mod 256] Output z
```
密钥key实际可用的长度最大为256字节，但典型的长度是40-128 bit。

# 0x02 偏移

Rc4的最初若干字节密钥流的非均匀分布

## 1. 单字节偏移
在密钥随机的前提下，如果密钥流是均匀的话，每个字节出现的概率应该是1/256=0.3906%,但从理论分析和实验结果来看，密钥流某些位置上的某些字节出现的概率要明显高于(或低于)其他字节，即偏移（biase）
RC4单字节偏移现象最初由Mantin and Shamir等人发现。他们指出密钥流的第二个字节,Z2=0的概率约为1/128,而不是1/256

![原文图片](/media/2016/06/1424b27bbcfda87d0532ed05fe64bf90)

在S盒初始化结束，生成密钥流的过程中，假设S2=0,S1=X≠2,S[X]=Y,根据伪随机数生成算法，第一轮，S[X]和S1互换，生成的密钥字节是S[X+Y];第二轮，S2和S[X]互换，生成的密钥字节是S[X]=0，即Z2=0。
由条件概率公式，计算出z2=0的概率约为1/128

```text
P[z2 = 0] = P[z2 = 0|S[2]= 0] * P[S[2]= 0] + P[z2 = 0|S[2] ≠ 0] * P[S[2] ≠ 0] ≈ 1*1/256 + 1/256*(1-1/256) ≈ 1/128
```
实验结果表明其他位置处的密钥字节也存在偏移现象。

![原文图片](/media/2016/06/0c6882c983bb0ecfcf52f62bc5c673dc)

![原文图片](/media/2016/06/3e6644c42a357384e8910aea8ed8e84d)

单字节偏移的局限性在于偏移现象只在初始的约256个字节出现。

## 2. 多字节偏移
多字节偏移又称long term biase,一些字节对出现的概率高于其他字节，会在密钥流中周期性的出现，最初由Fluhrer 和McGrew等人发现。

![原文图片](/media/2016/06/b4ac8d49e2ca049b20b08c4ea7b9103d)

## 3. RC4NOMORE
2015年Mathy Vanhoef及Frank Piessens发表了对RC4新的攻击方法，他们发现了新的偏移，只需要约9*2^27个密文就可以使cookie破解成功率达到94%，破解时间为75小时。这是第一个被证实可行的此类攻击。他们的论文《All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS》发表在USENIX Security2015，并被评为Best Student Paper

# 0x03 概率

学过概率与统计课程的同学应该对下面的题目有印象
“随机抛n次硬币，求恰好出现m次正面向上的概率”
这个概率符合二项分布，每次实验只有两种可能的结果。二项分布的名字来源于其概率公式符合二项展开的公式。

![原文图片](/media/2016/06/f09d6536212fe5b8cde0dedd2cd98514)

每次实验，两种结果出现的概率分别为a和b，重复实验n次，展开式中的每一项都是一个独立事件，如n*a^(n-1)*b表示第一种结果发生了n-1次，第二种结果发生了1次，这个现象发生的概率是n*a^(n-1)*b
将两种结果推广到更多的结果，就产生了多项分布。
“随机抛n次正方体骰子，点数1-6出现的次数分别为(x1,x2,x3,x4,x5,x6)的概率是多少,其中x1+x2+x3+x4+x5+x6=n”
更一般的情况是不规则的骰子。这种概率仍然符合多项展开公式

![原文图片](/media/2016/06/3a9e8ca0aafe8ef40a3ebe173897ccd4)

基于概率论的相关公式，我们就可以利用RC4密钥流中的偏移特性，对明文某一字节出现的概率进行计算，从而攻破RC4.
在预处理阶段，通过大量的实验，生成随机的key，统计密钥流中各字节出现的概率，类似求出前面多项展开式中的p1，p2
在获取密文阶段，通过一些手段，不断用RC4加密同样的明文，记录出现的密文.类似求出前面多项展开式中的n1，n2
最后，计算明文各个字节的概率，从概率较高的候选字节中恢复明文。

![原文图片](/media/2016/06/0d4ce611e12925797406ef8975c63c41)

最后给出针对单字节偏移的明文概率估计的整体算法。

![原文图片](/media/2016/06/f15020105070dfc8169fab43f042819b)

实验结果：当搜集的密文数为2^26时，前96个字节恢复的概率均超过50%；当密文数为2^32时，恢复的概率基本为100%。

![原文图片](/media/2016/06/43b1c21a79eed9dc7c4c71b7aef55e1d)

![原文图片](/media/2016/06/004d21eb2f147711293bf64d5df7ab44)

对于多字节偏移，还要用到更加复杂的概率公式，在此就不详细介绍了，但总体的思路还是一样的。此外，针对HTTP cookie，有简化运算的条件，如cookie字段总是以“Cookie:”开头，以换行符结尾，大部分cookie中的字符都是16进制字符。有兴趣的同学可以参考USENIX security2013年的论文《On the Security of RC4 in TLS and WPA》

# 0x04 结语

或许有人会说，“既然密钥流初始的若干字节有偏移问题，抛弃那些字节不就可以继续用了么？”的确，RC4后来也出现了抛弃初始字节的版本RC4-drop N,但有问题的原始版本已经被大范围实现和部署，RC4的速度优势在当今硬件条件下也不是特别重要，因此TLS协议放弃RC4是一个方便、安全的选择。

## Replies