RC4加密算法逆向分析

简介

RC4 是一种流加密算法，密钥长度可变。它加解密使用相同的密钥，因此也属于对称加密算法。RC4 是有线等效加密（WEP）中采用的加密算法，也曾经是 TLS 可采用的算法之一。

加解密原理

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

加密流程

  1. 先初始化状态向量S（256 个字节，用来作为密钥生成的种子）按照升序，给每个字节赋值。

  2. 初始密钥（由用户输入），长度任意，如果输入长度小于 256 个字节，则进行轮转，直到填满。例如填入密钥的是1 2 3 4 5 ，那么填入的是1，2，3，4，5，1，3，4，5，1，2，3，4，5 由上述轮转过程得到 256 个字节的向量T（用来作为密钥流生成的种子）

  3. 最后是根据向量S和T生成T生成密钥流与明文进行加密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//1.初始化S和T

for(int i=0;i<255;i++){
	S[i]=i;
	T[i]=K[i%keylen]
}

//2.初始排列S
j=0;
for(int i=0;i<255;i++){
	j=(j+S[i]+T[i])%256;
	swap(S[i],S[j]); //交换S[i]和S[j]
}

//3.产生密钥流，利用密钥流和明文进行加密
i,j=0;
for(int r=0;r<len;r++){
	i=(i+1)%256;
	j=(j+S[i])%256;
	swap(S[i],S[j]);//swap交换
	t=(S[i]+S[j])%256;
	k[r]=S[t];
	data[r]^=k[r];
}

C代码表示

几个基本变量：

  • S-Box也就是所谓的S盒，是一个 256 长度的char型数组，每个单元都是一个字节，算法运行的任何时候，S都包括0-255的8比特数的排列组合，只不过值的位置发生了变换。
  • 密钥char key[256]密钥的长度keylen与明文长度、密钥流的长度没有必然关系。
  • 临时向量k长度也为 256，每个单元也是一个字节。如果密钥的长度是 256 字节，就直接把密钥的值赋给 k，否则，轮转地将密钥的每个字节赋给k。

初始化部分

  • 参数 1 是一个 256 长度的char型数组，定义为：unsigned char sBox[256]
  • 参数 2 是密钥，其内容可以随便定义：char key[256]
  • 参数 3 是密钥的长度，Len=strlen(key)

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*初始化函数*/
void rc4_init(unsigned char*s,unsigned char*key, unsigned long Len)
{
    int i=0,j=0;
    char k[256]={0};
    unsigned char tmp=0;
    for(i=0;i<256;i++) {
        s[i]=i;  //0-255赋值给s
        k[i]=key[i%Len];  //将k重新计算
    }
    for(i=0;i<256;i++) {  //对s进行初始置换
        j=(j+s[i]+k[i])%256; //给j赋值
        tmp=s[i];
        s[i]=s[j]; //交换s[i]和s[j]
        s[j]=tmp;
    }
}

初始化长度为 256 的S盒。第一个for循环将 0 到 255 的互不重复的元素装入S盒。第二个for循环根据密钥打乱S盒，i确保 S-box 的每个元素都得到处理，j保证 S-box 的搅乱是随机的。而不同的 S-box 在经过伪随机子密码生成算法的处理后可以得到不同的子密钥序列，将 S-box 和明文进行xor运算，得到密文，解密过程也完全相同。

加密部分

  • 参数1 是上边rc4_init函数中，被搅乱的 S-box
  • 参数2 是需要加密的数据data
  • 参数3 是 data 的长度

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*加解密*/
void rc4_crypt(unsigned char*s,unsigned char*data,unsigned long len)
{
    int i=0,j=0,t=0;
    unsigned long k=0;
    unsigned char tmp;
    for(k=0;k<len;k++)
    {
        i=(i+1)%256;  //固定方式生成的i
        j=(j+s[i])%256;  //固定方式生成的j
        tmp=s[i];
        s[i]=s[j];  //交换s[x]和s[y]，第二次置换
        s[j]=tmp;
        t=(s[i]+s[j])%256;  //固定方式生成的t
        data[k]^=s[t];  //异或运算
    }
}

每收到一个字节，就进行循环。通过一定的算法定位S盒中的一个元素，并与输入字节异或，得到k。循环中还改变了S盒。如果输入的是明文，输出的就是密文；如果输入的是密文，输出的就是明文。

主函数

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int main()
{
    unsigned char s[256] = { 0 }, s2[256] = { 0 };//S-box
    char key[256] = { "justfortest" };
    char pData[512] = "这是一个用来加密的数据Data";
    unsigned long len = strlen(pData);
    int i;

    printf("pData=%s\n", pData);
    printf("key=%s,length=%d\n\n", key, strlen(key));
    rc4_init(s, (unsigned char*)key, strlen(key)); //已经完成了初始化
    printf("完成对S[i]的初始化，如下：\n\n");
    for (i = 0; i<256; i++)
    {
        printf("%02X", s[i]);
        if (i && (i + 1) % 16 == 0)putchar('\n');
    }
    printf("\n\n");
    for (i = 0; i<256; i++)           //用s2[i]暂时保留经过初始化的s[i]，很重要的！！！
    {
        s2[i] = s[i];
    }
    printf("已经初始化，现在加密:\n\n");
    rc4_crypt(s, (unsigned char*)pData, len);//加密
    printf("pData=%s\n\n", pData);
    printf("已经加密，现在解密:\n\n");
    //rc4_init(s,(unsignedchar*)key,strlen(key));//初始化密钥
    rc4_crypt(s2, (unsigned char*)pData, len);//解密
    printf("pData=%s\n\n", pData);
    return 0;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <string.h>

void rc4_init(unsigned char *s,unsigned char *key,unsigned long len){
  unsigned char tmp=0;
  int i=0,j=0;
  char k[256]={0};
  for (i=0;i<256;i++) {
  //初始化s盒
    s[i]=i;
    k[i]=key[i%len];
  }
  for (i=0;i<256;i++) {
    j=(j+s[i]+k[i])%256;
    tmp=s[i];
    s[i]=s[j];
    s[j]=tmp;
  }

void crypto(unsigned char *s,unsigned char *data,unsigned long len){
    int i=0,j=0,t=0;
    unsigned long k=0;
    unsigned char tmp;
    for (k=0;k<len;k++) {
      i=(i+1)%256;
      j=(j+s[i])%256;
      tmp=s[i];
      s[i]=s[j];
      s[j]=tmp;
      t=(s[i]+s[j])%256;
      data[k]^=s[t];
    }
  }
}

int main(){
    unsigned char s[256] = {0};
    char key[256] = {0x74, 0x61, 0x6C, 0x6C, 0x6D, 0x65, 0x77, 0x68, 0x79};
    unsigned char data[512]= {0xf5, 0x8c, 0x8d, 0xe4, 0x9f, 0xa5, 0x28, 0x65, 0x30, 0xf4, 0xeb, 0xd3, 0x24, 0xa9, 0x91, 0x1a, 0x6f, 0xd4, 0x6a, 0xd7, 0xb, 0x8d, 0xe8, 0xb8, 0x83, 0x4a, 0x5a, 0x6e, 0xbe, 0xcb, 0xf4, 0x4b, 0x99, 0xd6, 0xe6, 0x54, 0x7a, 0x4f, 0x50, 0x14, 0xe5, 0xec};
    unsigned long key_len = strlen(key);
    rc4_init(s,(unsigned char*)key,key_len);//初始化得到s
    rc4_crypt(s,(unsigned char*)data,42);//解密
    for(int i=0;i<42;i++)
    {
        printf("%c",(data[i])&0xff);
    }
	return 0;
}

逆向分析

特征识别

RC4 算法主要通过加密算法特征来进行识别。

  1. 反编译后可以看见多个循环次数为 256 的循环，以及存在一些%256的运算。

  2. 最后处理输入数据的是异或。

动态调试解RC4

由于 RC4 是对称加密，加密和解密用的是一套算法。也就是说我们如果将加密后的密文重新利用算法进行再次加密就可以得到明文。

所以对于标准的 RC4 算法我们可以进行对密文再次加密来获取明文。

首先我们要确定加密算法是否为对称加密

然后我们要获取密文，将密文深入进行再次加密

魔改RC4

RC4常见的魔改方法：

  1. 魔改初始化算法，可以将s盒初始化值并不设置成 0-255，也可以设置成其它的，也可以在s的初始置换过程中添加可逆运算。

  2. 由于最后加密 flag 是利用密钥流来单字节加密的，也有人会在这个地方添加一些可逆运算来进行魔改。

例：

总之算法需要遵循对称加密性质。

  • enc_data=RC4(flag)
  • flag=RC4(enc_data)

例题

标准RC4

2024Moectf RC4

1

动态调试解RC4

2024极客大挑战

魔改RC4

YLCTF xorplus

2024极客大挑战

后言

参考：RC4加密算法与逆向方法分析

≡