RC4原理和实现

发表于 更新于 Valine： 本文字数： 6.4k 阅读时长 ≈ 6 分钟

RC4

基本原理

RC4属于对称密码算法中的流密码加密算法

密钥长度可变，面向字节操作

以一个足够大的S表为基础，对表进行非线性变换，产生密钥流

两次交换过程是为了增加随机性

加密过程

初始化S表

1、对S表进行先行填充，一般为256字节，且为unsigned类型

2、用种子密钥填充另一个256字节的K表

如果种子密钥长度不为256，将循环使用种子密钥对K表进行填充

3、用 K表对S表进行初始置换

样例展示

这里我们假设S表和K表都是7个字节的，密钥为345，填充结果如下

使用K表对S表进行置换

1
2
3
4
5
6
int j = 0;
	for (int i = 0; i < 7; ++i)
	{
		j = (j + S[i] + K[i]) % 7;
		Swap(S[i], S[j]);
	}

得到被置换后的S表

生成密钥流

作用：为每个待价密的字节生成一个伪随机数，用来异或

注：S表完成初始化之后，种子密钥将不会再被使用

使用置换后的S表生成密钥流

1
2
3
4
5
6
7
8
9
int i, j = 0;
for (int k = 0; k < strlen(raw); ++k)
{
	i = (i + 1) % 7;
	j = (j + S[i]) % 7;
	Swap(S[i], S[j]);
	int t = (S[i] + S[j]) % 7;
	K[k] = S[t];
}

加密过程

密钥流和明文进行异或得到密文

最终代码

加密部分的j是用来打乱的，实现伪随机

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
49
50
51
52
53
54
55
#include<stdio.h>
#include <string.h>
void Rc4_init(unsigned char* S, unsigned char*K,unsigned char* key, unsigned long len)
{
	unsigned char  tmp = 0;
	for (int i = 0; i < 256; ++i)
	{
		S[i] = i;
		K[i] = key[i % len];
	}
	int j = 0;
	for (int i = 0; i < 256; ++i)
	{
		j = (j + S[i] + K[i]) % 256;
		tmp = S[i];
		S[i] = S[j];
		S[j] = tmp;
	}
	return;
}
void Rc4_encrypt(unsigned char* S, unsigned  char* flag,int len)
{
	int i = 0, j = 0,t = 0 ;
	unsigned char key_liu[len] = { 0 };
	unsigned char tmp = 0;
	for (unsigned long 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;
		key_liu[k] = S[t];
	}
	for (int i = 0; i < len; ++i)
	{
		flag[i] ^= key_liu[i];
	}
}
int main()
{
	unsigned char S[256] = { 0 };
	unsigned char K[256] = { 0 };
	char flag[512] = { 0xB6, 0x94, 0xFA, 0x8F, 0x3D, 0x5F, 0xB2, 0xE0,
	0xEA, 0x0F, 0xD2, 0x66, 0x98, 0x6C, 0x9D, 0xE7,
	0x1B, 0x08, 0x40, 0x71, 0xC5, 0xBE, 0x6F, 0x6D,
	0x7C, 0x7B, 0x09, 0x8D, 0xA8, 0xBD, 0xF3, 0xF6};
	char key[] = "w0wy0ugot1t";
	unsigned long Len = strlen(flag);
	Rc4_init(S, K,(unsigned char*)key, strlen(key));
	Rc4_encrypt(S, (unsigned char*)flag, Len);
	printf("%s", flag);
	return 0;
}

可以不保存密钥流，直接进行异或，逆向的时候我们可以动调得到密钥流，再与密文进行异或就可以得到明文了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Rc4_encrypt(unsigned char* S, unsigned  char* flag,char*flag1)
{
	int len = strlen(flag1);
	int i = 0, j = 0,t = 0 ;
	unsigned char tmp = 0;
	for (unsigned long 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;
		flag[k] ^= S[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
25
26
27
28
29
30
31
32
__int64 __fastcall Rc4_encrypt(unsigned __int8 *a1, unsigned __int8 *a2, char *a3)
{
  unsigned int v3; // eax
  unsigned __int8 v4; // ST2B_1
  __int64 result; // rax
  unsigned int v6; // [rsp+30h] [rbp-10h]
  unsigned int i; // [rsp+34h] [rbp-Ch]
  int v8; // [rsp+38h] [rbp-8h]
  signed int v9; // [rsp+3Ch] [rbp-4h]
  unsigned __int8 *v10; // [rsp+50h] [rbp+10h]
  unsigned __int8 *v11; // [rsp+58h] [rbp+18h]

  v10 = a1;
  v11 = a2;
  v6 = strlen(a3);
  v9 = 0;
  v8 = 0;
  for ( i = 0; ; ++i )
  {
    result = v6;
    if ( v6 <= i )
      break;
    v9 = (unsigned __int8)(((unsigned int)((v9 + 1) >> 31) >> 24) + v9 + 1) - ((unsigned int)((v9 + 1) >> 31) >> 24);
    v3 = (unsigned int)((v8 + v10[v9]) >> 31) >> 24;
    v8 = (unsigned __int8)(v3 + v8 + v10[v9]) - v3;
    v4 = v10[v9];
    v10[v9] = v10[v8];
    v10[v8] = v4;
    v11[i] ^= v10[(unsigned __int8)(v10[v9] + v10[v8])];
  }
  return result;
}

先保存再异或

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
49
50
__int64 __fastcall Rc4_encrypt(unsigned __int8 *a1, unsigned __int8 *a2, signed int a3)
{
  void *v3; // rsp
  char *v4; // rax
  signed __int64 i; // rdx
  unsigned int v6; // eax
  __int64 result; // rax
  __int64 v8; // [rsp+0h] [rbp-30h]
  __int64 *v9; // [rsp+8h] [rbp-28h]
  __int64 v10; // [rsp+10h] [rbp-20h]
  int v11; // [rsp+1Ch] [rbp-14h]
  unsigned int k; // [rsp+20h] [rbp-10h]
  unsigned int j; // [rsp+24h] [rbp-Ch]
  unsigned int v14; // [rsp+28h] [rbp-8h]
  unsigned int v15; // [rsp+2Ch] [rbp-4h]
  unsigned __int8 *v16; // [rsp+58h] [rbp+28h]

  v16 = a2;
  v15 = 0;
  v14 = 0;
  v11 = 0;
  v10 = a3 - 1i64;
  v3 = alloca(16 * ((unsigned __int64)(a3 + 15i64) >> 4));
  v9 = &v8;
  LOBYTE(v8) = 0;
  v4 = (char *)&v8 + 1;
  for ( i = a3 - 2i64; i != -1; --i )
    *v4++ = 0;
  HIBYTE(v8) = 0;
  for ( j = 0; a3 > j; ++j )
  {
    v15 = (unsigned __int8)(((unsigned int)((signed int)(v15 + 1) >> 31) >> 24) + v15 + 1)
        - ((unsigned int)((signed int)(v15 + 1) >> 31) >> 24);
    v6 = (unsigned int)((signed int)(v14 + a1[v15]) >> 31) >> 24;
    v14 = (unsigned __int8)(v6 + v14 + a1[v15]) - v6;
    HIBYTE(v8) = a1[v15];
    a1[v15] = a1[v14];
    a1[v14] = HIBYTE(v8);
    v11 = (unsigned __int8)(a1[v15] + a1[v14]);
    *((_BYTE *)v9 + j) = a1[v11];
  }
  for ( k = 0; ; ++k )
  {
    result = k;
    if ( (signed int)k >= a3 )
      break;
    v16[k] ^= *((_BYTE *)v9 + (signed int)k);
  }
  return result;
}

可以看到密钥流存储在v9，动调之后可以直接提取

Vs2022生成的exe文件反编译

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
__int64 __fastcall sub_140015E30(__int64 a1, __int64 a2, char *a3)
{
  __int64 result; // rax
  __int64 v4; // kr00_8
  unsigned __int8 v5; // dl
  char v6; // STA4_1
  int v7; // edx
  unsigned int v8; // [rsp+24h] [rbp+4h]
  int v9; // [rsp+44h] [rbp+24h]
  int v10; // [rsp+64h] [rbp+44h]
  unsigned int i; // [rsp+C4h] [rbp+A4h]
  __int64 v12; // [rsp+1C0h] [rbp+1A0h]
  __int64 v13; // [rsp+1C8h] [rbp+1A8h]
  const char *Str; // [rsp+1D0h] [rbp+1B0h]

  Str = a3;
  v13 = a2;
  v12 = a1;
  sub_140011361(&unk_14002200E);
  v8 = j_strlen(Str);
  v9 = 0;
  v10 = 0;
  for ( i = 0; ; ++i )
  {
    result = v8;
    if ( i >= v8 )
      break;
    v4 = v9 + 1;
    v9 = (BYTE4(v4) + v9 + 1) - BYTE4(v4);
    v5 = (*(v12 + v9) + v10) >> 31;
    v10 = (v5 + *(v12 + v9) + v10) - v5;
    v6 = *(v12 + v9);
    *(v12 + v9) = *(v12 + v10);
    *(v12 + v10) = v6;
    v7 = (*(v12 + v10) + *(v12 + v9)) >> 31;
    *(v13 + i) ^= *(v12 + (v7 + *(v12 + v10) + *(v12 + v9)) - v7);
  }
  return result;
}

看着跟别的不一样

题目——BUU-[GUET-CTF2019]encrypt

拖进ida，对一些变量和函数名进行识别和改名

点进加密函数进行查看

整体就是先RC4，然后将加密后的三个字符变为四个字符

逆向过来先将四个字符转为三个字符，然后直接将转换后的结果和密钥流进行异或得到明文

密钥流可以通过动调得到

脚本

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
#include<stdio.h>
#include<string.h>

int main()
{
	char raw[52]={0x5a,
    0x60, 0x54, 0x7A, 0x7A, 0x54, 0x72, 0x44, 0x7C, 0x66, 0x51, 0x50, 0x5B, 0x5F, 0x56, 0x56, 0x4C,
    0x7C, 0x79, 0x6E, 0x65, 0x55, 0x52, 0x79, 0x55, 0x6D, 0x46, 0x6B, 0x6C, 0x56, 0x4A, 0x67, 0x4C,
    0x61, 0x73, 0x4A, 0x72, 0x6F, 0x5A, 0x70, 0x48, 0x52, 0x78, 0x49, 0x55, 0x6C, 0x48, 0x5C, 0x76,
    0x5A, 0x45, 0x3D};
	char decode[39]={0};
	for(int i=0;i<52;++i)
	{
		raw[i]-=61;
	}
	for(int i=0,i_=0;i<52;i+=4,i_+=3)
	{
		decode[i_]=((raw[i])<<2)|((raw[i+1])>>4);
		decode[i_+1]=((raw[i+1]&0xf)<<4)|((raw[i+2]&0x3c)>>2);
		decode[i_+2]=((raw[i+2]&0xF)<<6)|(raw[i+3]);
	}
	char v[90]={0x10,0x59,0x9C,0x92,0x06,0x22,0xCF,0xA5,
	0x72,0x1E,0x45,0x6A,0x06,0xCB,0x08,0xC3,
	0xE4,0x49,0x5A,0x63,0x0C,0xDF,0xF6,0x5F,
	0x08,0x28,0xBD,0xE2,0x10,0x15,0x1F,0x6E,
	0xAA,0x5A,0xCA,0xEC,0x80,0xAF,0x9B,0x16,
	0xBB,0x3D,0x13,0x2F,0x6A,0xA4,0xC7,0x2E,
	0xBC,0x4B,0x60,0x9A,0xAF,0xE9,0xCE,0xDA,
	0x67,0x39,0xBA,0x3B,0x85,0xEB,0xD2,0x6B,
	0xAB,0x06,0x6B,0x10,0x57,0x2C,0x88,0x70,
	0xF7,0x4F,0xAA,0x7F,0x12,0x47,0xD6,0xDE,
	0x74,0xB2,0x1D,0xA4,0xD7,0x76,0x9A,0xE0
	};
	for(int i=0;i<39;++i)
	{
		decode[i]^=v[i];
	}
	printf("%s",decode);
	return 0;
}