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 算法。^[1]^[2]

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
2
```
```
for i = 0 to 255 do
    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
2
```
```
for i = 0 to 255 do
    T[i] = k[i mod keylen]
```

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

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

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

使用 S 生成密钥流 K。

i = j = 0
for each output message byte
    i = (i + 1) (mod 256)
    j = (j + S[i]) (mod 256)
    swap(S[i], S[j])
    t = (S[i] + S[j]) (mod 256)
    K[i] = S[t]
    print K[i]

2.3 异或运算

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

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

2.4 C 代码演示

#include <stdio.h>

// KSA
void rc4_init(unsigned char *s, unsigned char *key, unsigned long len_k) {
  int i = 0;
  int j = 0;
  unsigned char k[256] = {0};
  unsigned char temp = 0;
  for (i = 0; i < 256; i++) {
    s[i] = i;
    k[i] = key[i % len_k];
  }
  for (i = 0; i < 256; i++) {
    j = (j + s[i] + k[i]) % 256;
    temp = s[i];
    s[i] = s[j];
    s[j] = temp;
  }
}
// PRGA
void rc4_crypt(unsigned char *s, unsigned char *p, unsigned long len_p) {
  int i = 0, j = 0, t = 0;
  unsigned long k = 0;
  unsigned char temp;
  for (k = 0; k < len_p; k++) {
    i = (i + 1) % 256;
    j = (j + s[i]) % 256;
    temp = s[i];
    s[i] = s[j];
    s[j] = temp;
    t = (s[i] + s[j]) % 256;
    p[k] ^= s[t];
  }
}

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

2.5 RC4 解密

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

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 函数

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

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

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

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

查看 sub_400874 的伪代码

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

  v6 = __readfsqword(0x28u);
  sub_40067A(a1, v5);
  sub_400753(v5, a2, a3);
  return 0LL;
}

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

先查看 sub_40067A

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

  v6 = strlen(a1);
  v3 = 0;
  for ( i = 0; i <= 255; ++i )
    *(_BYTE *)(i + a2) = i;
  for ( j = 0; j <= 255; ++j )
  {
    v3 = (*(unsigned __int8 *)(j + a2) + v3 + a1[j % v6]) % 256;
    sub_400646(j + a2, a2 + v3);
  }
  return 0LL;
}

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

再看 sub_400753

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

  v5 = 0;
  v6 = 0;
  v7 = 0LL;
  v8 = strlen(a2);
  while ( v7 < v8 )
  {
    v5 = (v5 + 1) % 256;
    v6 = (v6 + *(unsigned __int8 *)(v5 + a1)) % 256;
    sub_400646(v5 + a1, a1 + v6);
    *(_BYTE *)(a3 + v7) = a2[v7] ^ *(_BYTE *)((unsigned __int8)(*(_BYTE *)(v5 + a1) + *(_BYTE *)(v6 + a1)) + a1);
    ++v7;
  }
  return 0LL;
}

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

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

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

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

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

脚本：

#include <stdio.h>

// KSA
void rc4_init(unsigned char *s, unsigned char *key, unsigned long len_k) {
  int i = 0;
  int j = 0;
  unsigned char k[256] = {0};
  unsigned char temp = 0;
  for (i = 0; i < 256; i++) {
    s[i] = i;
    k[i] = key[i % len_k];
  }
  for (i = 0; i < 256; i++) {
    j = (j + s[i] + k[i]) % 256;
    temp = s[i];
    s[i] = s[j];
    s[j] = temp;
  }
}
// PRGA
void rc4_crypt(unsigned char *s, unsigned char *p, unsigned long len_p) {
  int i = 0, j = 0, t = 0;
  unsigned long k = 0;
  unsigned char temp;
  for (k = 0; k < len_p; k++) {
    i = (i + 1) % 256;
    j = (j + s[i]) % 256;
    temp = s[i];
    s[i] = s[j];
    s[j] = temp;
    t = (s[i] + s[j]) % 256;
    p[k] ^= s[t];
  }
}

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

得到：

Flag: n1book{us1nG_f3atur3s_7o_de7erm1n3_4lg0ri7hm}