-
-
[原创] RC4加密算法流程剖析结合CTF逆向签到
-
发表于: 2024-8-4 14:20
-
流密码（Stream Cipher）属于对称密码，加解密使用与明文长度相同的同一个密钥流。这个密钥流通常是某一个确定状态的伪随机数发生器所产生的比特流，双方将伪随机数生成器的种子作为密钥。明文流通常通过和密钥流进行异或得到密文流。由异或操作可知，密文流和密钥流再进行异或也就得到了明文流。
RC4是对称加密中特殊的流加密算法，主要有三个操作：
下面进行一个初步的解释，
对照ascii码表对比应该不难理解，下一步便是密钥调度KSA
首先是计算key的长度和初始化一个S数组，通常称为S盒或S向量
然后就是使用密钥打乱状态数组，根据密钥的值，对状态数组进行置换。这个置换过程确保状态数组S与密钥相关联。
以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是RC4算法生成伪随机字节流的部分。它使用KSA生成的状态数组S作为种子来生成伪随机字节流
同样以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的简单使用
yield关键字用于定义生成器函数。一个带有yield关键字的函数会返回一个生成器对象，而不是一个普通的函数返回值。当生成器函数被调用时，函数体中的代码不会立即执行，而是返回一个生成器对象。每次调用生成器对象的__next__()方法（通常使用内置的next()函数），函数会执行到下一个yield语句并返回yield语句后的值。函数的状态（包括局部变量的值）会被保留，以便下一次继续执行。
next函数用于从生成器或迭代器中获取下一个值。当你调用next()时，生成器函数执行到下一个yield语句并返回该语句后的值。如果生成器没有更多值要生成，它会引发StopIteration异常。
通过yield和next关键字我们知道keystream每次会生成一个k值
% 是格式化操作符。
02 表示格式化结果至少为两位，不足两位时前面补零。
x 表示将数字格式化为小写的十六进制。
同样，依然只解释第一个操作，ord(char)=ord(w)=119，由前文可知第一次生成的k=231，则
结果为144，转为两位十六进制的结果为90，RC4加密后的结果是904fc1ff4dc92eed7555acfcbbbfad161b8f6313bb8fc3602c8c7108de3f可见，90确实是前两位十六进制数。
至此RC4的解密流程便已经理清了
我们已经知道904fc1ff4dc92eed7555acfcbbbfad161b8f6313bb8fc3602c8c7108de3f我们依然取我们熟悉的90，我们只需要直到k的值也就是231，那么
此时我们便知道了第一个字母就是w了，也就是说我们只需要知道密钥流便可以通过密文流得到明文流，而密钥流的生成只需要知道密钥即可。
签到题，简单的加密，抓个特征就好
扔进IDA分析，结合题目表述：签到题，简单的加密，抓个特征就好
由猜测是RC4加密，并且key为woodpecker，加密后的结果为904fc1ff4dc92eed7555acfcbbbfad161b8f6313bb8fc3602c8c7108de3f所以解题脚本为
当然也可以用刚才的python脚本，只需要简单修改一下RC4函数的部分即可
完整的脚本如下
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}")
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}")
key = [ord(c) for c in key] # key为：woodpecker
# 将字符串转为十进制数组# [119, 111, 111, 100, 112, 101, 99, 107, 101, 114]key = [ord(c) for c in key] # key为：woodpecker
# 将字符串转为十进制数组# [119, 111, 111, 100, 112, 101, 99, 107, 101, 114]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 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_length = len(key)
S = list(range(256))
key_length = len(key)
S = list(range(256))
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
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
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
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
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异常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异常gen = simple_generator()
print(next(gen)) # 输出: 1
print(next(gen)) # 输出: 2
print(next(gen)) # 输出: 3
# print(next(gen)) # 如果再调用一次，将会引发StopIteration异常gen = simple_generator()
print(next(gen)) # 输出: 1
print(next(gen)) # 输出: 2
print(next(gen)) # 输出: 3
# print(next(gen)) # 如果再调用一次，将会引发StopIteration异常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(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)
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}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} 0111 0111
^ 1110 0111
-----------
1001 0000 = 144
9 0
0111 0111
^ 1110 0111
-----------
1001 0000 = 144
9 0
1110 0111
^ 1001 0000
-----------
0111 0111 = 119 = w
1110 0111
^ 1001 0000
-----------
0111 0111 = 119 = w
#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;
}#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;
} [培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
