RC4 加密算法

1. RC4 加密简介#

RC4 (Rivest Cipher 4) 加密算法是由 Ron Rivest 于 1987 年设计的一种对称密钥流密码 (symmetric key stream cipher)，广泛应用于 SSL/TLS 协议和 WEP/WPA 协议。

在对称密码中，加密者和解密者使用相同的密钥。数据发送方利用密钥将明文经过特殊加密算法处理后，向数据接受方发送复杂的加密密文；接受方收到密文后，需要使用加密所用的密钥和相同加密算法的逆算法对密文进行解密，才能得到可读明文。

RC4 面向字节，算法简单而高效。作为流密码，RC4 的密钥流长度与明文的长度相同。密钥流派生自一个较短的初始密钥，派生算法通常为一个伪随机数生成算法。初始密钥长度是可变的，变化范围为 1-256 bytes (8-2048 bits)。

在现代技术的支持下，当初始密钥长度达到 128 bits 时，用暴力法搜索密钥已经不太可行，因此很长一段时间内，RC4 被应用于 SSL、WPA 等流行的互联网加密协议中。

然而，随着时间的推移，RC4 的弱点也不断暴露出来。各大机构已经不再推荐使用 RC4 算法。¹²

2. RC4 加密流程分析#

完整的 RC4 加密分为三步：初始化算法 (Key Scheduling Algorithm, KSA)、伪随机数生成算法 (Pseudo-random generation Algorithm, PRGA) 和异或加密。前两个步骤生成 RC4 需要的密钥流。

2.1 初始化算法 (KSA)#

初始化一个包含 256 字节的状态向量 S，作为生成密钥流的种子 1。按照升序顺序，依次给每个字节赋值，即 $S_i=i$ ， $i\in[0,255]$ .
```
1
for i = 0 to 255 do
2
    S[i] = i
```

这个向量 S 也有一个专有名词“S 盒”，表示密码加密过程中的混淆过程。

创建一个包含 256 字节的向量 T。由用户输入初始密钥 k，如果 k 的长度等于 256 字节，则直接将 k 赋值给 T；如果小于，则将 k 轮转输入直到填满 T（例如，如果密钥 k 为“1，2，3，4”，那么 T 应为“1，2，3，4，1，2，3，4，1，2，3，4，…”）。填充后的 T 作为生成密钥流的种子 2.
```
1
for i = 0 to 255 do
2
    T[i] = k[i mod keylen]
```

置换向量 S。这一步会引入向量 T.

1
j = 0
2
for i = 0 to 255 do
3
    j = (j + S[i] + T[i]) mod 256
4
    swap (S[i], S[j])

2.2 伪随机数生成算法（PRGA）#

使用 S 生成密钥流 K。

1
i = j = 0
2
for each output message byte
3
    i = (i + 1) (mod 256)
4
    j = (j + S[i]) (mod 256)
5
    swap(S[i], S[j])
6
    t = (S[i] + S[j]) (mod 256)
7
    K[i] = S[t]
8
    print K[i]

2.3 异或运算#

将密钥流 K 与明文 P 一个字节一个字节对应，进行异或算法，生成密文 C。

1
C[i] = P[i] ⊕ K[i]

2.4 C 代码演示#

1
#include <stdio.h>
2

3
// KSA
4
void rc4_init(unsigned char *s, unsigned char *key, unsigned long len_k) {
5
  int i = 0;
6
  int j = 0;
7
  unsigned char k[256] = {0};
8
  unsigned char temp = 0;
9
  for (i = 0; i < 256; i++) {
10
    s[i] = i;
11
    k[i] = key[i % len_k];
12
  }
13
  for (i = 0; i < 256; i++) {
14
    j = (j + s[i] + k[i]) % 256;
15
    temp = s[i];
16
    s[i] = s[j];
17
    s[j] = temp;
18
  }
19
}
20
// PRGA
21
void rc4_crypt(unsigned char *s, unsigned char *p, unsigned long len_p) {
22
  int i = 0, j = 0, t = 0;
23
  unsigned long k = 0;
24
  unsigned char temp;
25
  for (k = 0; k < len_p; k++) {
26
    i = (i + 1) % 256;
27
    j = (j + s[i]) % 256;
28
    temp = s[i];
29
    s[i] = s[j];
30
    s[j] = temp;
31
    t = (s[i] + s[j]) % 256;
32
    p[k] ^= s[t];
33
  }
34
}
35

36
int main(void){
37
    unsigned char s[256] = {0};
38
    unsigned char key[] = "Your key"; // 在此处输入密钥
39
    unsigned char p[] = {"Your data"}; // 在此处输入明文/密文
40
    unsigned long len_k = sizeof(key) - 1;
41
    unsigned long len_p = sizeof(p);
42
    rc4_init(s, key, len_k);
43
    rc4_crypt(s, p, len_p);
44
    printf("RC4 data: %s\n", p);
45
    return 0;
46
}

2.5 RC4 解密#

解密通过使用相同的密钥生成相同的密钥流，并将其与密文进行异或运算以恢复明文：

1
P[i] = C[i] ⊕ K[i]

换句话说，解密时，把密文当明文走一遍加密流程，那么输出的密文就是明文。这就是“对称密码”的性质。

3. RC4 特征分析#

RC4 通常是使用加密过程的特征去识别的。

次数为 256 的循环，以及 % 256 的运算。
最后处理输入数据的是异或运算。

4. RC4 加密的处理#

RC4 加密的处理思路为：enc_data = RC4(flag); flag = RC4(enc_data)

对于一般的 RC4 加密，通过逆向找到密文和初始密钥，然后重走一遍加密流程就好了。这个加密流程既可以自己重写，也可以通过修改内存，让目标程序处理密文。

Tip

众所周知，RC4 是出了名的不统一，各个语言的 RC4 结果基本上都不一样，所以碰到 RC4 的逆向题一般只能写代码去解密。

——Wankko Ree’s Blog

Note

RC4 属于互逆密码 (Reciprocal cipher)，可以将密文输入到系统中的相同位置以获得明文。

接下来，我们介绍一些魔改的 RC4 加密算法：

魔改初始化算法。可以随意指定 S 的初始值（不一定为 $S_i=i$ ，也不一定在 0-255）；也可以在 S 的置换过程中加入可逆的运算。
魔改异或算法。密钥流不和原文进行异或。
数据重加密。在异或加密后添加其他可逆运算。

5. 习题示例#

BUUCTF [第五章 CTF 之 RE 章]BabyAlgorithm 1

拖进 DIE 看看信息

64 位，没有壳。

拖进 IDA，找 main 函数

1
__int64 __fastcall main(int a1, char **a2, char **a3)
2
{
3
  int i; // [rsp+Ch] [rbp-E4h]
4
  char v5[16]; // [rsp+10h] [rbp-E0h] BYREF
5
  char s[64]; // [rsp+20h] [rbp-D0h] BYREF
6
  char v7[64]; // [rsp+60h] [rbp-90h] BYREF
7
  char v8[72]; // [rsp+A0h] [rbp-50h] BYREF
8
  unsigned __int64 v9; // [rsp+E8h] [rbp-8h]
9

10
  v9 = __readfsqword(0x28u);
11
  memset(v8, 0, 0x40uLL);
12
  v8[0] = -58;
13
  v8[1] = 33;
14
  v8[2] = -54;
15
  v8[3] = -65;
16
  v8[4] = 81;
17
  v8[5] = 67;
18
  v8[6] = 55;
19
  v8[7] = 49;
20
  v8[8] = 117;
21
  v8[9] = -28;
22
  v8[10] = -114;
23
  v8[11] = -64;
24
  v8[12] = 84;
25
  v8[13] = 111;
26
  v8[14] = -113;
27
  v8[15] = -18;
28
  v8[16] = -8;
29
  v8[17] = 90;
30
  v8[18] = -94;
31
  v8[19] = -63;
32
  v8[20] = -21;
33
  v8[21] = -91;
34
  v8[22] = 52;
35
  v8[23] = 109;
36
  v8[24] = 113;
37
  v8[25] = 85;
38
  v8[26] = 8;
39
  v8[27] = 7;
40
  v8[28] = -78;
41
  v8[29] = -88;
42
  v8[30] = 47;
43
  v8[31] = -12;
44
  v8[32] = 81;
45
  v8[33] = -114;
46
  v8[34] = 12;
47
  v8[35] = -52;
48
  qmemcpy(&v8[36], "3S1", 3);
49
  v8[40] = 64;
50
  v8[41] = -42;
51
  v8[42] = -54;
52
  v8[43] = -20;
53
  v8[44] = -44;
54
  puts("Input flag: ");
55
  __isoc99_scanf("%63s", s);
56
  if ( strlen(s) == 45 )
57
  {
58
    strcpy(v5, "Nu1Lctf233");
59
    sub_400874(v5, s, v7);
60
    for ( i = 0; i <= 44; ++i )
61
    {
62
      if ( v7[i] != v8[i] )
63
      {
64
        puts("GG!");
65
        return 0LL;
66
      }
67
    }
68
    puts("Congratulations!");
69
    return 0LL;
70
  }
71
  else
72
  {
73
    puts("GG!");
74
    return 0LL;
75
  }
76
}

通过阅读伪代码，可知 flag 长度应为 45，其密文存储在 v8 中。用户输入存储在 s 中。

我们感兴趣的是 58、59 这两行。58 行将一个字符串存入 v5 中，59 行的 sub_400874 将 v5 和 s 进行某种处理，然后存入 v7.

查看 sub_400874 的伪代码

1
__int64 __fastcall sub_400874(__int64 a1, __int64 a2, __int64 a3)
2
{
3
  char v5[264]; // [rsp+20h] [rbp-110h] BYREF
4
  unsigned __int64 v6; // [rsp+128h] [rbp-8h]
5

6
  v6 = __readfsqword(0x28u);
7
  sub_40067A(a1, v5);
8
  sub_400753(v5, a2, a3);
9
  return 0LL;
10
}

又发现两个未知函数 sub_40067A 和 sub_400753。

先查看 sub_40067A

1
__int64 __fastcall sub_40067A(const char *a1, __int64 a2)
2
{
3
  int v3; // [rsp+10h] [rbp-10h]
4
  int i; // [rsp+14h] [rbp-Ch]
5
  int j; // [rsp+18h] [rbp-8h]
6
  int v6; // [rsp+1Ch] [rbp-4h]
7

8
  v6 = strlen(a1);
9
  v3 = 0;
10
  for ( i = 0; i <= 255; ++i )
11
    *(_BYTE *)(i + a2) = i;
12
  for ( j = 0; j <= 255; ++j )
13
  {
14
    v3 = (*(unsigned __int8 *)(j + a2) + v3 + a1[j % v6]) % 256;
15
    sub_400646(j + a2, a2 + v3);
16
  }
17
  return 0LL;
18
}

发现几个次数 256 的循环以及 % 256 操作。很明显的 RC4 特征。

再看 sub_400753

1
__int64 __fastcall sub_400753(__int64 a1, const char *a2, __int64 a3)
2
{
3
  int v5; // [rsp+24h] [rbp-1Ch]
4
  int v6; // [rsp+28h] [rbp-18h]
5
  size_t v7; // [rsp+30h] [rbp-10h]
6
  size_t v8; // [rsp+38h] [rbp-8h]
7

8
  v5 = 0;
9
  v6 = 0;
10
  v7 = 0LL;
11
  v8 = strlen(a2);
12
  while ( v7 < v8 )
13
  {
14
    v5 = (v5 + 1) % 256;
15
    v6 = (v6 + *(unsigned __int8 *)(v5 + a1)) % 256;
16
    sub_400646(v5 + a1, a1 + v6);
17
    *(_BYTE *)(a3 + v7) = a2[v7] ^ *(_BYTE *)((unsigned __int8)(*(_BYTE *)(v5 + a1) + *(_BYTE *)(v6 + a1)) + a1);
18
    ++v7;
19
  }
20
  return 0LL;
21
}

% 256 操作和异或运算，也是很浓的 RC4 味道。

因此该程序使用的加密算法大概率为 RC4。s 是明文，v7 是生成的密文，那么 s 就是密钥。

现在我们要获取 flag 的密文。在静态调试时，我们点击 v8，会发现所有的元素都是问号：这些数据本来是存储在main函数的栈段的。所以我们使用远程调试。

有毅力的话也可以试试手动输入……

远程调试时，在汇编窗口框选所需要的数据，使用 Shift+E 或者 LazyIDA 输出数据。

脚本：

1
#include <stdio.h>
2

3
// KSA
4
void rc4_init(unsigned char *s, unsigned char *key, unsigned long len_k) {
5
  int i = 0;
6
  int j = 0;
7
  unsigned char k[256] = {0};
8
  unsigned char temp = 0;
9
  for (i = 0; i < 256; i++) {
10
    s[i] = i;
11
    k[i] = key[i % len_k];
12
  }
13
  for (i = 0; i < 256; i++) {
14
    j = (j + s[i] + k[i]) % 256;
15
    temp = s[i];
16
    s[i] = s[j];
17
    s[j] = temp;
18
  }
19
}
20
// PRGA
21
void rc4_crypt(unsigned char *s, unsigned char *p, unsigned long len_p) {
22
  int i = 0, j = 0, t = 0;
23
  unsigned long k = 0;
24
  unsigned char temp;
25
  for (k = 0; k < len_p; k++) {
26
    i = (i + 1) % 256;
27
    j = (j + s[i]) % 256;
28
    temp = s[i];
29
    s[i] = s[j];
30
    s[j] = temp;
31
    t = (s[i] + s[j]) % 256;
32
    p[k] ^= s[t];
33
  }
34
}
35

36
int main(void) {
37
  unsigned char s[256] = {0};
38
  unsigned char key[] = "Nu1Lctf233"; // 在此处输入密钥
39
  unsigned char p[] = {0xC6, 0x21, 0xCA, 0xBF, 0x51, 0x43, 0x37, 0x31,
40
                       0x75, 0xE4, 0x8E, 0xC0, 0x54, 0x6F, 0x8F, 0xEE,
41
                       0xF8, 0x5A, 0xA2, 0xC1, 0xEB, 0xA5, 0x34, 0x6D,
42
                       0x71, 0x55, 0x08, 0x07, 0xB2, 0xA8, 0x2F, 0xF4,
43
                       0x51, 0x8E, 0x0C, 0xCC, 0x33, 0x53, 0x31, 0x00,
44
                       0x40, 0xD6, 0xCA, 0xEC, 0xD4}; // 在此处输入明文/密文
45
  unsigned long len_k = sizeof(key) - 1;
46
  unsigned long len_p = sizeof(p);
47
  rc4_init(s, key, len_k);
48
  rc4_crypt(s, p, len_p);
49
  printf("Flag: %s\n", p);
50
  return 0;
51
}

得到：

1
Flag: n1book{us1nG_f3atur3s_7o_de7erm1n3_4lg0ri7hm}

音乐

1. RC4 加密简介#

2. RC4 加密流程分析#

2.1 初始化算法 (KSA)#

2.2 伪随机数生成算法（PRGA）#

2.3 异或运算#

2.4 C 代码演示#

2.5 RC4 解密#

3. RC4 特征分析#

4. RC4 加密的处理#

5. 习题示例#

文章分享

评论区

1. RC4 加密简介#

2. RC4 加密流程分析#

2.1 初始化算法 (KSA)#

2.2 伪随机数生成算法（PRGA）#

2.3 异或运算#

2.4 C 代码演示#

2.5 RC4 解密#

3. RC4 特征分析#

4. RC4 加密的处理#

5. 习题示例#

Footnotes#

文章分享

评论区