Understand Stream Cipher and Implement RC4


 

Understand Stream Cipher and Implement RC4

流密码原理及RC4算法的实现

前言 分组密码每次处理一个输入分组,并为每个输入分组产生一个输出分组。流密码连续处理输入元素,在运行过程中,一次产生一个输出元素。尽管分组密码普遍得多,但对于一些特定的应用,使用流密码更合适。

0x00. 流密码结构

img

    典型的流密码一次加密一个字节的明文,尽管流密码可能设计成一次操作一个比特或者比字节大的单位。图2.7是流密码结构的示意图。在这个结构里,密钥输入到一个伪随机字节生成器,产生一个表面随机的8比特数据流。如果不知道输入密钥,伪随机流就不可预测的,而且它具有表面上随机的性质。这个生成器的输出称为密钥流,使用位异或操作与明文流结合,一次一个字节。例如,如果生成器产生的下一字节是01101100,明文的下一字节是11001100,那么得到的密文字节是: $$11001100 ⊕ 01101100 \ = \ 10100000$$ 解密需要同一伪随机序列: $$10100000 ⊕ 01101100 \ = \ 11001100 $$

[KUMA97]列出了下列设计流密码时需要重要考虑的因素:

  • 加密序列应该有一个长周期。伪随机数生成器使用一个函数产生一个实际上不断重复的确定比特流。这个重复的周期越长,密码破解就越困难。
  • 密钥流应该尽可能地接近真随机数流的性质。例如, 1和0的数目应该近似相等。如果将密钥流视作字节流,那么字节的256种可能值出现的频率应该近似相等。密钥流表现得越随机,密文就越随机化,密码破译就越困难。
  • 图2.6指出了伪随机数生成器的输出受输入密钥值控制。为了抵抗穷举攻击,这个密钥必须非常长。分组密码中的考虑因素在这里同样适用。因此,就当前的科技水平而言,需要至少128比特长度的密钥。

    如果伪随机数生成器设计合理,对同样的密钥长度,流密码和分组密码一样安全。流密码的主要优点是流密码与分组密码相比几乎总是更快,使用更少的代码。本文中的示例RC4能用仅仅几行代码实现。最近几年,随着AES的引进,这个优势己经消失了,因为AES可以用软件方式高效实现。比如,Intel AES指令集含有一轮加解密和密钥产生过程使用的机器指令。使用硬件指令实现AES跟仅使用软件方式相比,速度提高了一个数M级。

    分组密码的优点是可以重复使用密钥。但是如果两个明文使用同一密钥进行流密码加密,密码破译常常会非常容易[DAWS96]。如果将这两个密文流进行异或,结果就是原始明文的异或值。如果明文是文本字符串、信用卡号或者其他己知其性质的字节流,密码破解可能会成功。

    对于需要加密/解密数据流的应用,比如在数据通信信道或者浏览器/网络链路上,流密码也许是更好的选择。对于处理数据分组的应用,比如文件传递、电子邮件和数据库,分组密码可能更合适。但是,这两种密码都可以在几乎所有的应用中使用。

0x01. RC4算法

    RC4是Ron Rivest在1987年为RSA Security公司设计的流密码。它是密钥大小可变的流密码,使用面向字节的操作。这个算法基于随机交换的使用。通过分析指出,这个密码的周期完全可能大于10100[ROBS95a]。每输出一个字节需要8~16个机器操作,并且此密码用软件实现运行速度非常快。为网络浏览器和服务器之间的通信定义的SS17TLS (安全套接字层/传输层安全)标准中使用了RC4。它也被用于属于IEEE 802.11无线LAN标准一部分的WEP (有线等效保密)协议及更新的Wi-Fi保护访问(WPA) 协议 。 RC4原本被RSA Security公司当作商业秘密。1994年9月,RC4算法通过Cypherpunks匿名邮件转发列表匿名地公布在因特网上。

1. 算法细节

    RC4算法非常简单,易于描述。用一个可变长度为1〜256字节(8-2048比特)的密钥来初始化256字节的状态向S,其元素为S[0], S[l] , …, S[255]。从始至终置换后的S包含从0到255的所有8位数。加密和解密时,字节k(见上图)是从S的255个元素中按一种系统的方式选出的。每次k值产生之后,要重新排列S的元素。

img

2. 初始化S

    开始时, S的元素按升序被置为0〜255;即S[0] = 0, S[l] = l, S[255] = 255。同时创建一个临时向量T。如果密钥K的长度为256字节,就把K直接赋给T,否则,对于keylen字节长度的密钥,将K赋值给T的前keylen个元素,并循环重复用K的值赋给T剩下的元素,直到T的所有元素都被赋值。这些预操作可被概括为

/* 初始化 */
for i = 0 to 255 do
	S[i] = i;
	T[i] = K[i mod keylen];

然后用T产生S的初始置换,从S[0]〜S[255],对每个S[i],根据由T[i]确定的方案,并将S[i]置换为S的另一字节:

/* s的初始置换 */
j = 0;
for i = 0 to 255 do
	j = (j + S[i] + T[i]) mod 256;
	Swap(S[i], S[j]);

因为对S的唯一操作是交换,所以唯一改变的就是置换。 S仍然包含0〜255的所有数。

3. 密钥流产生

    一旦S向fi被初始化,就不再使用输入密钥。密钥流产生过程是,从S[0]〜S[255],对每个S[i],根据S的当前配置,将S[i]与S中的另一字节置换。当S[255]完成置换后,操作继续重复从S[0]开始:

i, j = 0;
while(true)
	i = (i+1) mod 256;
	j = (j + S[i]) mod 256;
	Swap (S[i],  S[j]);
	t = (S[i] + S[j]) mod 256 ;
	k = S [t] ;

加密时,将k值与明文的下一字节做异或。解密时,将k值与密文的下一字节做异或。

4. 算法实现

使用Java实现RC4算法

/**
 * RC4主要逻辑
 *      1. 初始化状态向量
 *      2. 获取流密钥
 *      3. 加/解密
 * @param text 明文或密文
 * @param key 密钥
 * @return 加/解密结果
 */
private String core(String text, String key) {
    // 状态向量
    int[] state = new int[256];

    // 生成的密钥流
    char[] keySchedule = new char[text.length()];

    StringBuilder cipherText = new StringBuilder();

    scheduleKey(state, key);
    genPseudoRandom(state, keySchedule, text.length());

    // 将密钥与明文/密文异或
    for (int i = 0; i < text.length(); i++) {
        cipherText.append((char) (text.charAt(i) ^ keySchedule[i]));
    }
    return cipherText.toString();
}

初始化状态向量S

/**
 * 初始化向量(Key-scheduling algorithm)
 * @param state 状态向量
 * @param key 密钥
 */
private void scheduleKey(int[] state, String key) {
    for (int i = 0; i < 256; i++) {
        state[i] = i;
    }
    for (int j = 0, i = 0; i < 256; i++) {
        j = (j + state[i] + key.charAt(i % key.length())) % 256;
        swap(state, i, j);
    }
}

通过伪随机生成算法获取密钥流

/**
 * 伪随机生成算法(Pseudo-random generation algorithm)
 * @param state 状态向量
 * @param keySchedule 流密钥
 * @param plaintextLength 明文长度
 */
private void genPseudoRandom(int[] state, char[] keySchedule, int plaintextLength) {
    for (int i = 0, j = 0, k = 0; k < plaintextLength; k++) {
        i = (i + 1) % 256;
        j = (j + state[i]) % 256;
        swap(state, i, j);
        keySchedule[k] = (char) (state[(state[i] + state[j]) % 256]);
    }
}

整体加解密逻辑,使用Base64对加密结果进行编码

@Override
public String encrypt(String plaintext, String key) {
    String raw = core(plaintext, key);
    return Base64Util.encode(raw);
}

@Override
public String decrypt(String encryptedText, String key) {
    String raw = Base64Util.decode(encryptedText);
    return core(raw, key);
}

5. RC4的强度

    关于分析RC4的攻击方法有许多公开发表的文献(例如, [KNUD98], [MIST98]、 [FLUH00]、 [MANT01]、 [PUDO02]、 [PAUL03]和[PAUL04])。但是当密钥长度很大时,比如128位,没有哪种攻击方法有效。 [FLUH01]公布了一个更严重的问题。作者证明了WEP协议(此协议将要为802.11无线局域网提供机密性)易受一个特定攻击方法的攻击。本质上,这个问题不在于RC4本身,而在于输入到RC4的密钥的产生方法。这种特殊的攻击方法不适合用于其他使用RC的应用,而且能在WEP中通过改变密钥产生方法来修补。这个问题恰恰说明设计一个安全系统的困难性不仅包括密码函数,还包括协议如何正确的使用这些密码函数。

0x02.参考

  • 《网络安全基础 - 应用与标准》(William Stallings著,第五版,清华大学出版社)
  • Wikipedia: RC4