15

SSL/TLS协议安全系列：再见，RC4 | WooYun知识库

 7 years ago
source link:
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

GoSSIP_SJTU · 2015/10/26 10:28

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盒的状态。

密钥调度算法:

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

伪随机数生成算法:

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

在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

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

实验结果表明其他位置处的密钥字节也存在偏移现象。

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

2. 多字节偏移

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

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次正面向上的概率”

这个概率符合二项分布，每次实验只有两种可能的结果。二项分布的名字来源于其概率公式符合二项展开的公式。

每次实验，两种结果出现的概率分别为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”

更一般的情况是不规则的骰子。这种概率仍然符合多项展开公式

基于概率论的相关公式，我们就可以利用RC4密钥流中的偏移特性，对明文某一字节出现的概率进行计算，从而攻破RC4.

在预处理阶段，通过大量的实验，生成随机的key，统计密钥流中各字节出现的概率，类似求出前面多项展开式中的p1，p2

在获取密文阶段，通过一些手段，不断用RC4加密同样的明文，记录出现的密文.类似求出前面多项展开式中的n1，n2

最后，计算明文各个字节的概率，从概率较高的候选字节中恢复明文。

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

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

对于多字节偏移，还要用到更加复杂的概率公式，在此就不详细介绍了，但总体的思路还是一样的。此外，针对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是一个方便、安全的选择。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK