逆向分析中的密码学---RC4_rc4逆向

0x01 简介

RC4是对称加密算法，通过密钥key和S盒生成密钥流，明文逐字节异或S盒，同时S盒也会发生改变。所以加密与解密使用了相同的函数和密钥K。RC4加密的强度主要来源于密钥的安全性，如果密钥泄露，则能直接解密出明文。

0x02 RC4算法分析

S盒初始化

第一个256循环：初始化为0-255
第二个256循环：根据密钥K，交换密钥盒S

for i=0 to 255 do
	S[i]=i
j=0
for i=0 to 255 do
	j = (j+S[i] + key[i mod keylength]) mod 256
	swap(S[i],S[j])//交换S[i]和S[j]
1
2
3
4
5
6

异或生成密文

虽然是一个循环，但是可以分成两步

1. 根据明文的长度生成相同长度的密钥流
2. 密钥流和明文异或生成密文

i,j=0;
for r=0 to len(明文) do:
	i = (i+1)mod 256
	j = (j+S[i]) mod 256
	swap(S[i],S[j])
	t = (S[i]+S[j]) mod 256
	data[r] ^= S[t]//生成密文
1
2
3
4
5
6
7

0x03 代码实现

从加密与解密书的配套代码中扣了一段下来

#include<stdio.h>
#include<string.h>

struct rc4_state
{
    int x, y, m[256];
}rc4_state;

void rc4_setup( struct rc4_state *s, unsigned char *key,  int length );
void rc4_crypt( struct rc4_state *s, unsigned char *data, int length );

void rc4_setup( struct rc4_state *s, unsigned char *key,  int length )
{
    int i, j, k, *m, a;

    s->x = 0;
    s->y = 0;
    m = s->m;

    for( i = 0; i < 256; i++ )
    {
        m[i] = i;
    }

    j = k = 0;

    for( i = 0; i < 256; i++ )
    {
        a = m[i];
        j = (unsigned char) ( j + a + key[k] );
        m[i] = m[j]; m[j] = a;
        if( ++k >= length ) k = 0;
    }
}

void rc4_crypt( struct rc4_state *s, unsigned char *data, int length )
{ 
    int i, x, y, *m, a, b;

    x = s->x;
    y = s->y;
    m = s->m;

    for( i = 0; i < length; i++ )
    {
        x = (unsigned char) ( x + 1 ); 
        a = m[x];
        y = (unsigned char) ( y + a );
        m[x] = b = m[y];
        m[y] = a;
        data[i] ^= m[(unsigned char) ( a + b )];
    }

    s->x = x;
    s->y = y;
}


int main()
{
    struct rc4_state rc4_ctx;
    char* key = "abelxuabelxu";
    unsigned char content[256] = "0123456789abcdef";
    //encrypt为RC4(content,key)得到的密文
    unsigned char encrpyt[256] = {0x7d,0x71,0x12,0xe2,0x97,0xb1,0x24,0xef,0xc4,0xa9,0xe2,0xe3,0xab,0xf4,0x74,0xd7};
    memset(&rc4_ctx,0,sizeof(rc4_state));
    rc4_setup(&rc4_ctx,key,strlen(key));
    rc4_crypt(&rc4_ctx,content,strlen(content));
    for (int i = 0; i < strlen(content); i++)
        printf("%2.2x", content[i]);
    printf("\n");
    rc4_setup(&rc4_ctx,key,strlen(key));
    rc4_crypt(&rc4_ctx,encrpyt,strlen(encrpyt));
    printf("%s\n");
    printf("\n");
}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

0x04 逆向分析识别RC4算法

使用ida pro中的Findcrypt识别一下，因为没有magicnum和一些特征字符，所以Findcrypt没有识别到rc4

rc4_setup
可以容易的发现两个256循环，第一个循环给s盒赋值，第二个循环根据密钥key对S盒进行swap。根据源码的了解，a2中保存的是密钥key

rc4_crypt
循环中最关键的就是S盒的swap，明文和S盒的异或。其中v6为S盒，a2指向明文和密文。

0x05 总结

虽然工具无法直接识别出RC4算法，但是RC4算法比较简单，主要的3个for循环，前两个256循环为S盒初始化，最后一个循环异或生成密文。可以通过调试初始化代码找到每次RC4的密钥key。

参考
《加密与解密第4版》