• [原创] RC4加密算法流程剖析结合CTF逆向签到

算法原理

流密码（Stream Cipher）属于对称密码，加解密使用与明文长度相同的同一个密钥流。这个密钥流通常是某一个确定状态的伪随机数发生器所产生的比特流，双方将伪随机数生成器的种子作为密钥。明文流通常通过和密钥流进行异或得到密文流。由异或操作可知，密文流和密钥流再进行异或也就得到了明文流。
RC4是对称加密中特殊的流加密算法，主要有三个操作：

  1. 密钥调度KSA，初始化一个数组，并通过密钥打乱数组
  2. 伪随机字节流生成，使用KSA生成的状态数组S来生成伪随机字节流
  3. 通过伪随机字节流，也就是密钥流来与明文流进行异或
    下面以python为例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def RC4(key, plaintext): 
    """ RC4 encryption/decryption """ 
    key = [ord(c) for c in key] 
    S = KSA(key) 
    keystream = PRGA(S) 
 
    result = [] 
    for char in plaintext: 
        val = ("%02x" % (ord(char) ^ next(keystream)))  # XOR and format as hex 
        result.append(val) 
 
    return ''.join(result) 
 
# 示例 
key = 'woodpecker' 
plaintext = 'woodpecker{this_is_simple_rc4}' 
ciphertext = RC4(key, plaintext) 
print(f"密文: {ciphertext}")

下面进行一个初步的解释，

1
2
3
key = [ord(c) for c in key]  # key为：woodpecker
# 将字符串转为十进制数组
# [119, 111, 111, 100, 112, 101, 99, 107, 101, 114]


对照ascii码表对比应该不难理解，下一步便是密钥调度KSA

密钥调度KSA

1
2
3
4
5
6
7
8
9
10
11
def KSA(key): 
    """ Key Scheduling Algorithm (KSA) """ 
    key_length = len(key) 
    S = list(range(256)) 
    j = 0 
 
    for i in range(256): 
        j = (j + S[i] + key[i % key_length]) % 256 
        S[i], S[j] = S[j], S[i]  # swap 
 
    return S

首先是计算key的长度和初始化一个S数组，通常称为S盒或S向量

1
2
key_length = len(key) 
S = list(range(256))


然后就是使用密钥打乱状态数组，根据密钥的值，对状态数组进行置换。这个置换过程确保状态数组S与密钥相关联。

1
2
3
4
5
j = 0 # j初始值为0
for i in range(256): 
# 第i(0->255)个位置与通过特定公式计算出的位置j进行替换
    j = (j + S[i] + key[i % key_length]) % 256
    S[i], S[j] = S[j], S[i]  # swap 

以i=0为例子，j默认初始值为0，S[i]也就是S[0]此时的值为0，key[i % key_length]也就是key[0 % 10] 为key[0]也就是119，所以最终计算的结果j=119，所以S[0]和S[119]进行置换

后面类似即可，最终生成一个调度后的密钥S

PRGA (Pseudo-Random Generation Algorithm)

PRGA是RC4算法生成伪随机字节流的部分。它使用KSA生成的状态数组S作为种子来生成伪随机字节流

1
2
3
4
5
6
7
8
9
10
11
12
def PRGA(S): 
    """ Pseudo-Random Generation Algorithm (PRGA) """
    # 初始化i，j为0位置
    i = 0 
    j = 0
    # 生成器不断生成密钥流
    while True: 
        i = (i + 1) % 256 
        j = (j + S[i]) % 256 
        S[i], S[j] = S[j], S[i]  # 交换i,j的两个位置 
        K = S[(S[i] + S[j]) % 256] # 取S中的S[i]与S[j]相加%256结果的位置作为密钥流的值
        yield K


同样以i=0,j=0为例子，计算出i=1，j=(0+231)%256=231，

所以交换S[1],S[231]的位置

最后生成K的值，S[1]=0, S[231]=231，所以K的值为S[231]=231

关于yield，next的简单使用

1
2
3
4
5
6
7
8
9
10
11
def simple_generator():
    yield 1
    yield 2
    yield 3
 
gen = simple_generator()  # 创建生成器对象
 
print(next(gen))  # 输出: 1
print(next(gen))  # 输出: 2
print(next(gen))  # 输出: 3
# print(next(gen))  # 如果再调用一次，将会引发StopIteration异常

yield关键字用于定义生成器函数。一个带有yield关键字的函数会返回一个生成器对象，而不是一个普通的函数返回值。当生成器函数被调用时，函数体中的代码不会立即执行，而是返回一个生成器对象。每次调用生成器对象的__next__()方法（通常使用内置的next()函数），函数会执行到下一个yield语句并返回yield语句后的值。函数的状态（包括局部变量的值）会被保留，以便下一次继续执行。

1
2
3
4
5
6
gen = simple_generator()
 
print(next(gen))  # 输出: 1
print(next(gen))  # 输出: 2
print(next(gen))  # 输出: 3
# print(next(gen))  # 如果再调用一次，将会引发StopIteration异常

next函数用于从生成器或迭代器中获取下一个值。当你调用next()时，生成器函数执行到下一个yield语句并返回该语句后的值。如果生成器没有更多值要生成，它会引发StopIteration异常。

通过密钥流加密明文流

1
2
3
4
5
6
7
8
9
10
11
12
def RC4(key, plaintext): 
    """ RC4 encryption/decryption """ 
    key = [ord(c) for c in key] 
    S = KSA(key) 
    keystream = PRGA(S) 
 
    result = [] 
    for char in plaintext: 
        val = ("%02x" % (ord(char) ^ next(keystream)))  # XOR and format as hex 
        result.append(val) 
 
    return ''.join(result)

通过yield和next关键字我们知道keystream每次会生成一个k值

1
2
3
4
5
6
result = [] 
for char in plaintext: 
    # 取出一个字符，与生成的key进行异或操作
    val = ("%02x" % (ord(char) ^ next(keystream)))  # XOR and format as hex
    result.append(val)
# plaintext为woodpecker{this_is_simple_rc4}

  • % 是格式化操作符。

  • 02 表示格式化结果至少为两位，不足两位时前面补零。

  • x 表示将数字格式化为小写的十六进制。

同样，依然只解释第一个操作，ord(char)=ord(w)=119，由前文可知第一次生成的k=231，则

1
2
3
4
5
  0111 0111
^ 1110 0111
-----------
  1001 0000 = 144
     9    0

结果为144，转为两位十六进制的结果为90，RC4加密后的结果是904fc1ff4dc92eed7555acfcbbbfad161b8f6313bb8fc3602c8c7108de3f可见，90确实是前两位十六进制数。
至此RC4的解密流程便已经理清了

RC4解密流程

我们已经知道904fc1ff4dc92eed7555acfcbbbfad161b8f6313bb8fc3602c8c7108de3f我们依然取我们熟悉的90，我们只需要直到k的值也就是231，那么

1
2
3
4
  1110 0111
^ 1001 0000
-----------
  0111 0111 = 119 = w

此时我们便知道了第一个字母就是w了，也就是说我们只需要知道密钥流便可以通过密文流得到明文流，而密钥流的生成只需要知道密钥即可。

题目描述：

签到题，简单的加密，抓个特征就好

题目源代码：

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
77
78
79
80
81
82
83
84
#include <stdio.h> 
#include <string.h> 
 
#define KEY "woodpecker" 
#define TARGET_ENCRYPTED_FLAG "904fc1ff4dc92eed7555acfcbbbfad161b8f6313bb8fc3602c8c7108de3f" 
 
typedef struct { 
    unsigned char S[256]; 
    int i, j; 
} Crypto_CTX; 
 
void crypto_init(Crypto_CTX *ctx, const unsigned char *key, int keylen) { 
    int i, j = 0, k; 
    unsigned char tmp; 
 
    for (i = 0; i < 256; i++) { 
        ctx->S[i] = i; 
    } 
 
    for (i = 0; i < 256; i++) { 
        j = (j + ctx->S[i] + key[i % keylen]) % 256; 
        tmp = ctx->S[i]; 
        ctx->S[i] = ctx->S[j]; 
        ctx->S[j] = tmp; 
    } 
 
    ctx->i = 0; 
    ctx->j = 0; 
} 
 
void crypto_crypt(Crypto_CTX *ctx, const unsigned char *inbuf, unsigned char *outbuf, int buflen) { 
    int i; 
    unsigned char tmp; 
 
    for (i = 0; i < buflen; i++) { 
        ctx->i = (ctx->i + 1) % 256; 
        ctx->j = (ctx->j + ctx->S[ctx->i]) % 256; 
 
        tmp = ctx->S[ctx->i]; 
        ctx->S[ctx->i] = ctx->S[ctx->j]; 
        ctx->S[ctx->j] = tmp; 
 
        outbuf[i] = inbuf[i] ^ ctx->S[(ctx->S[ctx->i] + ctx->S[ctx->j]) % 256]; 
    } 
} 
 
void encrypt_flag(const char *flag, unsigned char *encrypted_flag) { 
    Crypto_CTX crypto_ctx; 
    crypto_init(&crypto_ctx, (const unsigned char *)KEY, strlen(KEY)); 
    crypto_crypt(&crypto_ctx, (const unsigned char *)flag, encrypted_flag, strlen(flag)); 
} 
 
void bytes_to_hex(const unsigned char *bytes, char *hex, int len) { 
    for (int i = 0; i < len; i++) { 
        sprintf(hex + 2 * i, "%02x", bytes[i]); 
    } 
} 
 
int main() { 
    char input_flag[256]; 
    unsigned char encrypted_flag[256]; 
    char encrypted_flag_hex[256 * 2 + 1]; 
 
    printf("Enter the flag: "); 
    fgets(input_flag, sizeof(input_flag), stdin); 
 
    // Remove the newline character from the input if present 
    input_flag[strcspn(input_flag, "\n")] = '\0'; 
 
    // Encrypt the input flag 
    encrypt_flag(input_flag, encrypted_flag); 
 
    // Convert encrypted flag to hex string 
    bytes_to_hex(encrypted_flag, encrypted_flag_hex, strlen(input_flag)); 
 
    // Compare the encrypted flag with the target encrypted flag 
    if (strcmp(encrypted_flag_hex, TARGET_ENCRYPTED_FLAG) == 0) { 
        printf("congratulation\n"); 
    } else { 
        printf("try again\n"); 
    } 
 
    return 0; 
}

解题


扔进IDA分析，结合题目表述：签到题，简单的加密，抓个特征就好



由猜测是RC4加密，并且key为woodpecker，加密后的结果为904fc1ff4dc92eed7555acfcbbbfad161b8f6313bb8fc3602c8c7108de3f所以解题脚本为

1
2
3
import binascii 
from Crypto.Cipher import ARC4 
print(ARC4.new(b"woodpecker").decrypt(binascii.a2b_hex("904fc1ff4dc92eed7555acfcbbbfad161b8f6313bb8fc3602c8c7108de3f")))

当然也可以用刚才的python脚本，只需要简单修改一下RC4函数的部分即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def RC4_decrypt(key, ciphertext_hex): 
    """ RC4 decryption """ 
    key = [ord(c) for c in key] 
    S = KSA(key) 
    keystream = PRGA(S) 
 
    ciphertext_bytes = binascii.a2b_hex(ciphertext_hex) 
    result = [] 
    for byte in ciphertext_bytes: 
        val = chr(byte ^ next(keystream))  # XOR with keystream and convert to char 
        result.append(val) 
 
    return ''.join(result) 
 
# 示例 
key = 'woodpecker' 
plaintext = "904fc1ff4dc92eed7555acfcbbbfad161b8f6313bb8fc3602c8c7108de3f" 
ciphertext = RC4_decrypt(key, plaintext) 
print(f"密文: {ciphertext}")

完整的脚本如下

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
import binascii
 
def KSA(key): 
    """ Key Scheduling Algorithm (KSA) """ 
    key_length = len(key) 
    S = list(range(256)) 
    j = 0 
 
    for i in range(256): 
        j = (j + S[i] + key[i % key_length]) % 256 
        S[i], S[j] = S[j], S[i]  # swap 
 
    return S 
 
def PRGA(S): 
    """ Pseudo-Random Generation Algorithm (PRGA) """ 
    i = 0 
    j = 0 
    while True: 
        i = (i + 1) % 256 
        j = (j + S[i]) % 256 
        S[i], S[j] = S[j], S[i]  # swap 
        K = S[(S[i] + S[j]) % 256] 
        yield K 
 
def RC4(key, plaintext): 
    """ RC4 encryption/decryption """ 
    key = [ord(c) for c in key] 
    S = KSA(key) 
    keystream = PRGA(S) 
 
    result = [] 
    for char in plaintext: 
        val = ("%02x" % (ord(char) ^ next(keystream)))  # XOR and format as hex 
        result.append(val) 
 
    return ''.join(result) 
 
def RC4_decrypt(key, ciphertext_hex): 
    """ RC4 decryption """ 
    key = [ord(c) for c in key] 
    S = KSA(key) 
    keystream = PRGA(S) 
 
    ciphertext_bytes = binascii.a2b_hex(ciphertext_hex) 
    result = [] 
    for byte in ciphertext_bytes: 
        val = chr(byte ^ next(keystream))  # XOR with keystream and convert to char 
        result.append(val) 
 
    return ''.join(result) 
 
# 示例 
key = 'woodpecker' 
plaintext = "904fc1ff4dc92eed7555acfcbbbfad161b8f6313bb8fc3602c8c7108de3f" 
ciphertext = RC4_decrypt(key, plaintext) 
print(f"密文: {ciphertext}")

最新回复：
龙游天下178 2024-08-12 18:41:46
学到了