CTF流密码之RC4

CTF流密码之RC4基础

在CTF中 Re和Crypto方向中会经常遇到RC4加密，本篇将对CTF密码学中RC4的考点进行解析分享，笔者水平有限，文中若有疏漏或不当之处，欢迎各位读者批评指正，交流探讨。

RC4简介

RC4算法，是一种对称加密算法，属于流密码的一种形式，流密码逐字节操作数据流。对称密码算法的工作方式有四种：电子密码本(ECB)方式、密码分组链接(CBC)方式、密文反馈(CFB)方式、输出反馈(OFB)方式。

RC4算法采用的是输出反馈工作方式，所以可以用一个短的密钥产生一个相对较长的密钥序列。

RC4流密码是使用最广泛的流密码之一，通过算法一次一字节地加密消息，算法简单，运行速度快。

算法中变量

密钥流：RC4算法的关键就是根据明文和密钥生成对应的密钥流，密钥流的长度和明文的长度相对应， Cipher[i] = Message[i]^密钥流[i]。

状态向量S（S盒）： 长度为256 每个单元都是一个字节。

临时变量T：长度为256 如果密钥长度为256个字节，俺们将把密钥的值赋给T，否则轮转的将密钥的每个字节赋给T。

密钥K：长度 1-256字节，与明文长度 密钥流长度无必然关系。

算法原理与加密过程

假设定义RC4运算过程为 rc4(key,data)，那么密文C = rc4(key, M)，明文M = rc4(key, C)。

C算法实现

void rc4_init(unsigned char *s, unsigned char *key, unsigned long Len) //初始化函数 根据key定义s盒
{
    int i =0, j = 0;
    char k[256] = {0};
    unsigned char tmp = 0;
    for (i=0;i<256;i++) {
        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[i]和s[j] 生成新s盒
        s[j] = tmp;
    }
 }

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;
        j=(j+s[i])%256;
        tmp = s[i];
        s[i] = s[j]; //交换s[x]和s[y]
        s[j] = tmp;
        t=(s[i]+s[j])%256;
        Data[k] ^= s[t];
     }
} 

加密过程

RC4由伪随机数生成器和异或运算组成，主要包含两块内容 初始化算法(KSA) 、伪随机子密码生成算法(PRGA)。

1.初始化算法（KSA）

KSA(The key-scheduling algorithm)算法初始化长度为256的S盒，将0-255 互不重复的元素装入S盒，在根据密钥打乱S盒。

j = 0
for i in range(256):
  j = (j+s[i]+key[i]) % 256
  s[i],s[j] = s[j],s[i]

2.伪随机子密码生成算法(PRGA)、加密阶段

for i in range(len(message))
    i=(i+1)%256;
    j=(j+s[i])%256;
    s[i],s[j] = s[j],s[i]
    t = (s[i] + s[j])%256
    cipher += message[i]^s[t]

伪随机的子密码的生成只受初始化后的S盒的影响，要加密的明文并不会影响密钥。只要得到初始化后的s盒，那么秘钥也是固定的。

明文流与密钥流异或得到密文流，密文流与密钥流异或得到明文流。

题目解析

[SEETF 2023]BabyRC4

题目描述

from Crypto.Cipher import ARC4
from os import urandom
key = urandom(16)
flag = b'SEE{?????????????????????????????????}'[::-1]

def enc(ptxt):
    cipher = ARC4.new(key)
    return cipher.encrypt(ptxt)

print(f"c0 = bytes.fromhex('{enc(flag).hex()}')")
print(f"c1 = bytes.fromhex('{enc(b'a'*36).hex()}')")

"""
c0 = bytes.fromhex('b99665ef4329b168cc1d672dd51081b719e640286e1b0fb124403cb59ddb3cc74bda4fd85dfc')
c1 = bytes.fromhex('a5c237b6102db668ce467579c702d5af4bec7e7d4c0831e3707438a6a3c818d019d555fc')
"""

题目分析

使用同一个key 对 反转后的flag和明文进行rc4加密

c0 = rc4(key,flag) c1 = rc4(key,m0) 计算出数据流keystream

c0 = flag_rev ^ keystream ，c1 = a36 ^ keystream

c0 ^ c1 = flag_rev ^ a36

进而求得 反转后的flag

WP

c0 = bytes.fromhex('b99665ef4329b168cc1d672dd51081b719e640286e1b0fb124403cb59ddb3cc74bda4fd85dfc')
c1 = bytes.fromhex('a5c237b6102db668ce467579c702d5af4bec7e7d4c0831e3707438a6a3c818d019d555fc')

m1 = b'a'*36
keystream = bytes([a^b for a,b in zip(c1,m1)])

# print(m1)
# print(keystream)

flag_rev = bytes([a^b for a,b in zip(c0,keystream)])
print(flag_rev[::-1])
# b'E{n3vEr_reU53_rC4_k3y5ss5s:cafe2835}'

[hgame-week2] notRC4

题目描述

Oo0o0 It's a reverse game!! 0Oo0o

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from hashlib import md5
from secret import flag
assert flag.startswith(b'hgame) and flag.endswith(b')

class Oo0:
    # s盒初始化
    def __init__(self):
        self.O0 = [0] * 256
        self.Ooo = 0
        self.Ooo0 = [0] * 256
        for i in range(256):
            self.O0[i] = i
        self.oO0 = 0
    # 打乱s盒  oO0（key）
    def OO0(self, oO0):
        l = len(oO0)
        for i in range(256):
            self.Ooo0[i] = oO0[i%l]
        for i in range(256):
            self.oO0 = ( self.oO0 + self.O0[i] + self.Ooo0[i] ) % 256
            self.O0[i], self.O0[self.oO0] = self.O0[self.oO0], self.O0[i]
        self.Ooo = self.oO0 = 0
    
    # 加密算法
    def OO0o(self, length):
        O = []
        for _ in range(length):
            self.Ooo = ( self.Ooo + 1 ) % 256
            self.oO0 = ( self.oO0 + self.O0[self.Ooo] ) % 256
            self.O0[self.Ooo], self.O0[self.oO0] = self.O0[self.oO0], self.O0[self.Ooo]
            t = ( self.O0[self.Ooo] + self.O0[self.oO0] ) % 256
            O.append( self.O0[t] )
        print(self.O0)
        return O

def xor(s1, s2):
    return bytes(map( (lambda x: x[0]^x[1]), zip(s1, s2) ))

def enc(msg):
    # 初始化
    Oo0oO = Oo0()
    # 根据key生成s盒 [KSA]
    Oo0oO.OO0( md5(msg).digest()[:8] )
    # 利用s盒 生成密钥流
    O0O = Oo0oO.OO0o( len(msg) )
    # xor
    return xor(msg, O0O)

print( enc(flag) )

# [157, 28, 118, 120, 251, 242, 69, 178, 165, 137, 115, 84, 250, 152, 56, 196, 191, 16, 71, 158, 1, 58, 233, 175, 214, 181, 42, 151, 255, 228, 38, 48, 186, 139, 201, 24, 30, 134, 162, 86, 187, 176, 121, 206, 153, 111, 161, 163, 26, 27, 14, 188, 96, 3, 52, 207, 57, 8, 145, 154, 238, 221, 85, 204, 66, 141, 143, 237, 113, 53, 218, 29, 177, 150, 87, 94, 183, 130, 200, 12, 182, 166, 205, 93, 252, 44, 77, 76, 55, 81, 208, 128, 6, 109, 156, 129, 103, 59, 105, 25, 75, 31, 164, 232, 132, 209, 159, 2, 194, 131, 116, 32, 19, 36, 4, 125, 108, 212, 170, 171, 248, 236, 126, 195, 174, 65, 215, 160, 91, 64, 172, 167, 13, 169, 68, 92, 20, 10, 142, 106, 23, 192, 67, 88, 253, 202, 184, 22, 249, 122, 62, 107, 123, 45, 148, 51, 100, 245, 190, 231, 220, 241, 213, 50, 70, 219, 39, 244, 82, 189, 37, 72, 119, 40, 234, 224, 80, 235, 18, 61, 198, 90, 60, 98, 95, 179, 54, 254, 74, 226, 180, 230, 211, 99, 239, 83, 144, 240, 34, 199, 35, 7, 210, 149, 112, 41, 101, 225, 168, 33, 63, 216, 79, 243, 17, 138, 97, 147, 11, 229, 222, 0, 9, 78, 49, 21, 155, 124, 135, 193, 197, 223, 5, 110, 246, 247, 104, 203, 89, 117, 140, 114, 136, 185, 15, 46, 173, 102, 73, 47, 217, 43, 146, 133, 127, 227]
# b'\x14\xe3s,\xcbq\xa8\xd1\x86\x12\xba\x9f\x88\xa9J}\xf5\xd8BF\x93x\x94\x8a\xdc\xdb\xa0\xb9O0SeJ^\xc7\xce\xcf\xe3\x1c\x10s\xe2\xb6\xceA\xfd\xd6\x87\x95W'

题目分析

题目中的脚本函数名做了混淆，仍可以看出是 rc4加密。rc4按字节加密，所以明文长度和密文长度是相同的 。

已知明文最后一位为 } ，异或密文最后一位和明文最后一位 可以得到 密钥的最后一位s[t]。

然后在根据给出的s盒 确定t的值 t = (s[i] + s[j]) % 256

s盒确定 i=50、 t已知 就可以推出j j = (j + s[i]) % 256

可以在推出上一个j。得到上一个j ，i也确定 ，

t = (s[i] + s[j]) % 256 这样就可以推出上一个t的值 从而确定s[t] 。

以此类推 最终得到完整的密钥 就可以推出明文。

for i in range(len(message))
    i = (i + 1)%256 
    j = (j + s[i])%256
    s[i],s[j] = s[j],s[i]
    t = (s[i] + s[j])%256
    cipher += message[i]^s[t]

WP

enc = b'\x14\xe3s,\xcbq\xa8\xd1\x86\x12\xba\x9f\x88\xa9J}\xf5\xd8BF\x93x\x94\x8a\xdc\xdb\xa0\xb9O0SeJ^\xc7\xce\xcf\xe3\x1c\x10s\xe2\xb6\xceA\xfd\xd6\x87\x95W'
assert len(enc) == 50
s =  [157, 28, 118, 120, 251, 242, 69, 178, 165, 137, 115, 84, 250, 152, 56, 196, 191, 16, 71, 158, 1, 58, 233, 175, 214, 181, 42, 151, 255, 228, 38, 48, 186, 139, 201, 24, 30, 134, 162, 86, 187, 176, 121, 206, 153, 111, 161, 163, 26, 27, 14, 188, 96, 3, 52, 207, 57, 8, 145, 154, 238, 221, 85, 204, 66, 141, 143, 237, 113, 53, 218, 29, 177, 150, 87, 94, 183, 130, 200, 12, 182, 166, 205, 93, 252, 44, 77, 76, 55, 81, 208, 128, 6, 109, 156, 129, 103, 59, 105, 25, 75, 31, 164, 232, 132, 209, 159, 2, 194, 131, 116, 32, 19, 36, 4, 125, 108, 212, 170, 171, 248, 236, 126, 195, 174, 65, 215, 160, 91, 64, 172, 167, 13, 169, 68, 92, 20, 10, 142, 106, 23, 192, 67, 88, 253, 202, 184, 22, 249, 122, 62, 107, 123, 45, 148, 51, 100, 245, 190, 231, 220, 241, 213, 50, 70, 219, 39, 244, 82, 189, 37, 72, 119, 40, 234, 224, 80, 235, 18, 61, 198, 90, 60, 98, 95, 179, 54, 254, 74, 226, 180, 230, 211, 99, 239, 83, 144, 240, 34, 199, 35, 7, 210, 149, 112, 41, 101, 225, 168, 33, 63, 216, 79, 243, 17, 138, 97, 147, 11, 229, 222, 0, 9, 78, 49, 21, 155, 124, 135, 193, 197, 223, 5, 110, 246, 247, 104, 203, 89, 117, 140, 114, 136, 185, 15, 46, 173, 102, 73, 47, 217, 43, 146, 133, 127, 227]
assert len(s) == 256

# 已知明文最后一位 与密文最后一位异或得到最后一位加密密钥
# 在s盒中找到对应位置
t = s.index( ord('W')^ord('}'))
# print(t)

# 密文长度与明文长度相同
i = len(enc)

sj = (t-s[i]) % 256
j = s.index(sj)
s[i],s[j] = s[j],s[i]
j = (j-s[i])%256
i=i-1
t=(s[i]+s[j])%256

flag = '}'

while i>0:
    flag += (chr(enc[i-1]^s[t]))
    s[i], s[j] = s[j], s[i]
    j = (j - s[i]) % 256
    i = i - 1
    t = (s[i] + s[j]) % 256

print(flag[::-1])
# hgame{O0OOO0O0~-rEvEr5E+ThE~prg4~Of+Rc4__00oooOo0}

References

https://lazzzaro.github.io/2020/11/07/crypto-%E6%B5%81%E5%AF%86%E7%A0%81/index.html

https://jayxv.github.io/2020/01/30/%E5%AF%86%E7%A0%81%E5%AD%A6%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%E4%B9%8BRC4%E4%B8%8ESM4/

http://ronpa.top/2018/11/27/%E7%BB%8F%E5%85%B8%E5%AF%B9%E7%A7%B0%E5%8A%A0%E5%AF%86RC4%E5%88%86%E6%9E%90/