RC4加密算法


RC4

在密码学中,RC4(来自Rivest Cipher 4的缩写)是一种流加密算法,密钥长度可变。它加解密使用相同的密钥,因此也属于对称加密算法。RC4是有线等效加密(WEP)中采用的加密算法,也曾经是TLS可采用的算法之一。曾经广泛分布和使用的主要因素是它不可思议的简单和速度,不管是软件还是硬件,实现起来都十分容易.

由美国密码学家罗纳德·李维斯特(Ronald Rivest)在1987年设计的。由于RC4算法存在弱点,2015年2月所发布的 RFC 7465 规定禁止在TLS中使用RC4加密算法。

RC4由伪随机数生成器和异或运算组成。RC4的密钥长度可变,范围是[1,255]。RC4一个字节一个字节地加解密。给定一个密钥,伪随机数生成器接受密钥并产生一个S盒。S盒用来加密数据,而且在加密过程中S盒会变化。

关键变量:

1、密钥流:RC4算法的关键是根据明文和密钥生成相应的密钥流,密钥流的长度和明文的长度是对应的,也就是说明文的长度是500字节,那么密钥流也是500字节。当然,加密生成的密文也是500字节,因为密文第i字节=明文第i字节^密钥流第i字节;

2、状态向量S:长度为256,S[0],S[1].....S[255]。每个单元都是一个字节,算法运行的任何时候,S都包括0-255的8比特数的排列组合,只不过值的位置发生了变换;

3、临时向量T:长度也为256,每个单元也是一个字节。如果密钥的长度是256字节,就直接把密钥的值赋给T,否则,轮转地将密钥的每个字节赋给T;

4、密钥K:长度为1-256字节,注意密钥的长度keylen与明文长度、密钥流的长度没有必然关系,通常密钥的长度趣味16字节(128比特)。

RC4的原理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1、初始化S和T
for i=0 to 255 do
S[i]=i;
T[i]=K[ imodkeylen ];

2、初始排列S
j=0;
for i=0 to 255 do
j= ( j+S[i]+T[i])mod256;
swap(S[i],S[j]);

3、产生密钥流
i,j=0;
for r=0 to len do //r为明文长度,r字节
i=(i+1) mod 256;
j=(j+S[i])mod 256;
swap(S[i],S[j]);
t=(S[i]+S[j])mod 256;
k[r]=S[t];

由于异或运算的对合性,RC4加密解密使用同一套算法。

伪代码

初始化长度为256的S盒。第一个for循环将0到255的互不重复的元素装入S盒。第二个for循环根据密钥打乱S盒。

1
2
3
4
5
6
7
8
for i from 0 to 255
S[i] := i
endfor
j := 0
for( i=0 ; i<256 ; i++)
j := (j + S[i] + key[i mod keylength]) % 256
swap values of S[i] and S[j]
endfor

下面i,j是两个指针。每收到一个字节,就进行while循环。通过一定的算法((a),(b))定位S盒中的一个元素,并与输入字节异或,得到k。循环中还改变了S盒((c))。如果输入的是明文,输出的就是密文;如果输入的是密文,输出的就是明文。

1
2
3
4
5
6
7
8
9
i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256 //a
j := (j + S[i]) mod 256 //b
swap values of S[i] and S[j] //c
k := inputByte ^ S[(S[i] + S[j]) % 256]
output K
endwhile

破解:

2015年,比利时鲁汶大学的研究人员Mathy Vanhoef及Frank Piessens,公布了针对RC4加密算法的新型攻击程式,可在75小时内取得cookie的内容。

When you visit a website, and the browser’s address bar contains a lock icon , the HTTPS protocol is used to protect your communication with this website (providing security and privacy). HTTPS supports several encryption techniques, one of them being the famous RC4 algorithm. At one point RC4 was used 50% of the time, with the estime around Februari 2015 being 30%. Our RC4 NOMORE attack exposes weaknesses in this RC4 encryption algorithm. More precisely, in most situations where RC4 is used, these weaknesses can be used to reveal information which was previously thought to be safely encrypted.

The research behind the attack has been presented at USENIX Security. Summarized, an attacker can decrypt a cookie within 75 hours. In contrast to previous attacks, this short execution time allows us to perform the attack in practice. When we tested the attack against real devices, it took merely 52 hours to successfully perform the attack. The attack consists of three steps:
RC4
When the victim visits an unencrypted website, the attacker inserts malicious JavaScript code inside the website. This code will induce the victim to transmit encrypted requests which contain the victim’s web cookie. By monitoring numerous of these encrypted requests, a list of likely cookie values can be recovered. All cookies in this list are tested until the correct one is found.


参考文献:

https://en.wikipedia.org/wiki/RC4
http://www.rc4nomore.com RC4 NOMORE
http://blog.csdn.net/lc_910927/article/details/37599161

sign bman

-------------本文结束感谢浏览-------------