2024年熵密杯 Flag1 精讲

2024年熵密杯 Flag1 精讲 自定义口令加密算法逆向 AND 密钥暴力破解阅读指引本文是熵密杯2024年真题精析密码系统系列的第一篇。Flag1 考察的是自定义分组密码的逆向与密钥暴力枚举——题目实现了一个16轮迭代型对称加密算法使用4字节(32位)种子通过递增方式派生轮密钥。本文先完整推导解密函数的构造流程逐一逆向四个操作再基于解密函数实现密钥暴力枚举。由于密钥空间仅 2³² ≈ 43 亿且口令固定以pwd:开头攻击者在构造出解密函数后即可通过枚举全部可能密钥恢复口令明文 目录题目场景还原加密算法完整剖析2.1 算法参数2.2 加密流程总览2.3 操作一比特逆序2.4 操作二S盒替换2.5 操作三跨字节左移2.6 操作四轮密钥加2.7 轮密钥派生解密函数构造逐操作逆向推导3.1 总原则逆序 逆操作3.2 逆操作一轮密钥加的逆3.3 逆操作二跨字节左移的逆3.4 逆操作三S盒替换的逆3.5 逆操作四比特逆序的逆3.6 拼装完整的 decrypt 函数密钥暴力枚举基于解密函数的攻击搜索范围分析攻击原理总结与防御1. 题目场景还原题目描述某系统使用自定义的口令加密算法保护用户口令。口令固定以pwd:开头通过16轮迭代加密后存储。已知加密算法源码和目标密文请恢复原始口令明文。┌──────────────────────────────────────────────────────────┐ │ 自定义口令加密系统架构 │ │ │ │ 口令 (16 bytes) │ │ e.g. pwd:0123456789ab │ │ │ │ │ ▼ │ │ ┌──────────────────────────────────────────┐ │ │ │ 16 轮加密 (每轮 4 个操作) │ │ │ │ │ │ │ │ ① 比特逆序 reverse_bits │ │ │ │ ② S盒替换 sbox_4bit │ │ │ │ ③ 字节左移 left_shift_bytes │ │ │ │ ④ 轮密钥加 add_round_key │ │ │ └──────────────────────────────────────────┘ │ │ │ │ │ ▼ │ │ 密文 (16 bytes) │ │ │ │ 轮密钥: 从 4 字节种子 key 连续递增生成 │ │ 攻击链路: 加密算法 → 构造解密函数 → 枚举key → 前缀验证 │ └──────────────────────────────────────────────────────────┘2. 加密算法完整剖析2.1 算法参数参数值说明分组大小128 bits (16 bytes)固定长度密钥长度32 bits (4 bytes)一个int型整数轮数16迭代次数S盒4位×4位 (16项)非线性混淆层轮密钥总量256 bytes (16轮×16B)从4B种子递增派生2.2 加密流程总览加密是一个16轮的迭代过程每轮依次执行四个独立操作。用伪代码表示state plaintext # 初始状态 16字节明文 for round 0, 1, 2, ..., 15: # 共16轮 state reverse_bits(state) # ① 比特逆序 state sbox_transform(state) # ② S盒替换 state left_shift_bytes(state) # ③ 跨字节左移 state add_round_key(state, round) # ④ 轮密钥加 ciphertext state # 最终状态 密文接下来逐一解剖这四个操作的具体实现。2.3 操作一比特逆序它同时做了两种逆序① 字节内部: bit0 ↔ bit7, bit1 ↔ bit6, bit2 ↔ bit5, bit3 ↔ bit4 ② 字节之间: byte0 ↔ byte15, byte1 ↔ byte14, ..., byte7 ↔ byte8defreverse_bits(state):temp[0]*16foriinrange(16):byte0forjinrange(8):bit(state[i]j)1# 取第 j 位byte|bit(7-j)# 放到第 (7-j) 位temp[15-i]byte# 字节位置也逆序state[:]temp关键性质reverse_bits是对合运算involution——执行两次等于什么都不做。这意味着reverse_bits(reverse_bits(x))x# 逆操作 正操作2.4 操作二S盒替换本题使用一个4位→4位的S盒16项每个半字节独立查表intsBox[16]{2,10,4,12,1,3,9,14,7,11,8,6,5,0,15,13};S盒的直观表现输入: 0 1 2 3 4 5 6 7 8 9 A B C D E F 输出: 2 A 4 C 1 3 9 E 7 B 8 6 5 0 F D对于每个字节高低半字节分别查表后拼接hex两个一组前后各映射一次defsbox_transform(state):foriinrange(16):loSBOX[state[i]0x0F]# 低4位 → S盒 → 新低4位hiSBOX[state[i]4]# 高4位 → S盒 → 新高4位state[i](hi4)|lo# 拼接回一个字节S盒是可逆的输入空间等于输出空间16→16且映射是一一对应的双射。构造逆S盒只需交换键值inv_sbox[0]*16foriinrange(16):inv_sbox[SBOX[i]]i# 结果: [13, 4, 0, 5, 2, 12, 11, 8, 10, 6, 1, 9, 3, 15, 7, 14]2.5 操作三跨字节左移这个操作将16字节分成4组每组4字节内部做3位循环左移defleft_shift_bytes(state):temp[0]*16foriinrange(0,16,4):# 每组4字节temp[i0](state[i2]5)|((state[i1]3)0xFF)temp[i1](state[i3]5)|((state[i2]3)0xFF)temp[i2](state[i0]5)|((state[i3]3)0xFF)temp[i3](state[i1]5)|((state[i0]3)0xFF)state[:]temp用图来理解每组内部的数据流动——把4个字节排成一个32位的环整体左旋3位原始: [byte0][byte1][byte2][byte3] ↓ ↓ ↓ ↓ 结果: byte2的低5位 byte1的高3位 → temp[0] byte3的低5位 byte2的高3位 → temp[1] byte0的低5位 byte3的高3位 → temp[2] byte1的低5位 byte0的高3位 → temp[3]本质是跨字节的位级置换没有密钥参与完全可逆。2.6 操作四轮密钥加四个操作中最简单的一个——逐字节异或defadd_round_key(state,round_keys,round_idx):baseround_idx*16foriinrange(16):state[i]^round_keys[basei]XOR异或是自逆运算a XOR k XOR k a。解密时只需再次异或相同的轮密钥即可取消加密时的效果。2.7 轮密钥派生轮密钥派生机制是这个算法安全性最薄弱的地方之一。从4字节种子出发连续递增生成256字节voidderive_round_key(unsignedintkey,unsignedchar*round_key,intlength){unsignedinttmpkey;for(inti0;ilength/16;i){memcpy(round_keyi*160,tmp,4);tmp;memcpy(round_keyi*164,tmp,4);tmp;memcpy(round_keyi*168,tmp,4);tmp;memcpy(round_keyi*1612,tmp,4);tmp;}}转换关系从种子key开始每次取4字节后递增共64个4字节块 256字节 16轮×16B。第 0 轮密钥: [key, key1, key2, key3 ] 第 1 轮密钥: [key4, key5, key6, key7 ] ... 第15轮密钥: [key60, key61, key62, key63]Python 等价实现defderive_round_keys(key:int)-bytes:round_keysbytearray(16*16)tmpkey0xFFFFFFFFforiinrange(64):# 64个4字节块struct.pack_into(I,round_keys,i*4,tmp)tmp(tmp1)0xFFFFFFFFreturnbytes(round_keys)致命缺陷密钥空间仅 2³²。轮密钥派生完全确定性——给定 key 即可完全重建全部256字节轮密钥。3. 解密函数构造逐操作逆向推导有了加密算法四个操作的完整理解之后就可以开始构造解密函数了。这是从理解算法到能写攻击代码的关键一步。3.1 总原则逆序 逆操作解密是加密的完全逆过程遵循两条规则规则1逆序加密是 Round 0 → Round 1 → … → Round 15解密必须是 Round 15 → Round 14 → … → Round 0。规则2逆操作加密每轮内部是 ①→②→③→④解密每轮内部必须是 ④⁻¹→③⁻¹→②⁻¹→①⁻¹。加密: 解密: state plaintext state ciphertext ↓ Round 0: ①→②→③→④ Round 15: ④⁻¹→③⁻¹→②⁻¹→①⁻¹ Round 1: ①→②→③→④ Round 14: ④⁻¹→③⁻¹→②⁻¹→①⁻¹ ... ... Round 15: ①→②→③→④ Round 0: ④⁻¹→③⁻¹→②⁻¹→①⁻¹ ↓ ↓ ciphertext state plaintext state接下来逐操作推导每个逆操作的具体实现。3.2 逆操作一轮密钥加的逆加密state[i] state[i] XOR round_key[i]解密再次异或相同值即可还原——XOR是自逆运算。( a ⊕ k ) ⊕ k a (a \oplus k) \oplus k a(a⊕k)⊕ka逆操作代码与正向完全一致defadd_round_key(state,round_keys,round_idx):baseround_idx*16foriinrange(16):state[i]^round_keys[basei]# 正向和逆向是同一个函数!在解密循环中add_round_key出现在每轮的第一步forrndinrange(15,-1,-1):# 逆序!add_round_key(state,round_keys,rnd)# ④⁻¹ 再次异或# ... 随后是 ③⁻¹, ②⁻¹, ①⁻¹ ...3.3 逆操作二跨字节左移的逆加密每组4字节整体左旋3位。解密需要右旋3位——即左旋效果的反向。从数学上看每组内部的数据流动完全可逆加密时temp[2]的生成依赖state[0]的低5位解密时就需要反过来让state[0]从temp[2]的高5位和temp[3]的低3位重建。把加密的4个等式反解得到解密版本defleft_shift_bytes_inv(state):跨字节左移的逆操作 — 等价于3位右旋temp[0]*16foriinrange(0,16,4):temp[i0](state[i2]5)|(state[i3]3)temp[i1](state[i3]5)|(state[i0]3)temp[i2](state[i0]5)|(state[i1]3)temp[i3](state[i1]5)|(state[i2]3)foriinrange(16):state[i]temp[i]0xFF与正向的对应关系加密取哪些位拼到temp[j]解密取哪些位拼回state[j]temp[0] (state[2]5) | (state[1]3)state[0] (temp[2]5) | (temp[3]3)temp[1] (state[3]5) | (state[2]3)state[1] (temp[3]5) | (temp[0]3)temp[2] (state[0]5) | (state[3]3)state[2] (temp[0]5) | (temp[1]3)temp[3] (state[1]5) | (state[0]3)state[3] (temp[1]5) | (temp[2]3)本质上就是操作方向反转和索引置换的逆映射。3.4 逆操作三S盒替换的逆加密每个半字节通过S盒映射到新的半字节。解密使用逆S盒将半字节映射回原始值。第2.4节已给出逆S盒的构造方法# 构造逆S盒只需做一次inv_sbox[0]*16foriinrange(16):inv_sbox[SBOX[i]]i# inv_sbox [13, 4, 0, 5, 2, 12, 11, 8, 10, 6, 1, 9, 3, 15, 7, 14]逆S盒查表逻辑与正向完全相同只是查的表换了defsbox_transform_inv(state):foriinrange(16):loinv_sbox[state[i]0x0F]# 低4位 → 逆S盒hiinv_sbox[state[i]4]# 高4位 → 逆S盒state[i](hi4)|lo验证sbox_transform_inv(sbox_transform(x)) x✓3.5 逆操作四比特逆序的逆这是最简单的逆操作——得益于reverse_bits的对合性质reverse_bits(reverse_bits(x))x# 做两次 不做逆操作就是再做一次正操作代码无需任何修改直接复用# 解密中直接调用正向函数即可reverse_bits(state)# 逆操作 正操作3.6 拼装完整的 decrypt 函数将以上四个逆操作按逆序串联得到完整的解密函数defdecrypt(ciphertext:bytes,key:int)-bytes: 完整的口令解密函数。 加密是: Round 0..15, 每轮 ①→②→③→④ 解密是: Round 15..0, 每轮 ④⁻¹→③⁻¹→②⁻¹→①⁻¹ assertlen(ciphertext)16# 1. 从key重建全部256字节轮密钥 (与加密完全一致)round_keysderive_round_keys(key)# 2. 初始化状态 密文statebytearray(ciphertext)# 3. 16轮解密 (逆序!)forrndinrange(15,-1,-1):add_round_key(state,round_keys,rnd)# ④⁻¹ 再次异或left_shift_bytes_inv(state)# ③⁻¹ 右旋3位sbox_transform_inv(state)# ②⁻¹ 逆S盒reverse_bits(state)# ①⁻¹ 再做一次 (对合)returnbytes(state)逐轮追踪以第15轮为例输入: state 第15轮加密后的输出 ── ④⁻¹ add_round_key(state, rk, 15) → 消去第15轮的轮密钥 ── ③⁻¹ left_shift_bytes_inv(state) → 还原第15轮的跨字节移位 ── ②⁻¹ sbox_transform_inv(state) → 还原第15轮的S盒替换 ── ①⁻¹ reverse_bits(state) → 还原第15轮的比特逆序 输出: state 第14轮加密后的输出 第15轮加密前的输入 ✓至此解密函数构造完毕。下一步利用它进行密钥暴力枚举。4. 密钥暴力枚举基于解密函数的攻击在第3节中我们完成了decrypt(ciphertext, key)函数的构造。现在有了它暴力枚举就成了一个简单的循环对每个候选key用 decrypt 解密密文检查解密结果的前4字节。4.1 原题C代码的爆破逻辑这是竞赛中实际使用的爆破代码——清晰、高效展示了decrypt函数构造之后的攻击全貌// 目标密文 (16 bytes)memcpy(ciphertext,\x99\xF2\x98\x0A\xAB\x4B\xE8\x64\x0D\x8F\x32\x21\x47\xCB\xA4\x09,16);// 搜索范围: 0xf0000000 → 0x00000000 (覆盖到0xFFFFFFFF后自然回绕)unsignedints0xf0000000;unsignedinte0x00000000;for(unsignedintkeys;key!e;key){// 每 2^14 (16384) 次打印进度if((key((114)-1))0){printf(key %x (%.2lf%%)\n,key,(key-s)*100./(e-s));}// ★ 核心: 用上一步构造好的 decrypt 函数解密,// 然后只检查前4字节是否为 pwd:decrypt(ciphertext,key,passback);if(passback[0]ppassback[1]wpassback[2]dpassback[3]:){printf(%x\n,key);// 找到正确密钥!printf(%16s\n,passback);// 打印完整口令明文break;}}为什么用 decrypt 而不是 encrypt?方案操作需要的信息验证方式C代码实际方案decrypt(ct, key)仅需密文 4字节前缀pwd:passback[:4] pwd:等价替代方案encrypt(known_pt, key)需要完整16字节明文enc_result target_ct解密方案只需要知道固定前缀pwd:4字节即可开始爆破——你不需要提前知道完整口令是什么这也正是你要恢复的目标。搜索范围分析搜索轨迹: 0xF0000000 → 0xF0000001 → ... → 0xFFFFFFFF → 0x00000000 → 0x00000001 → ... ↑ 32位无符号整数自然溢出回绕原题从0xf0000000开始而非0x00000000意味着参赛者可能已通过其他渠道如部分密钥泄露、已知明文攻击、或侧信道信息锁定了key的大致范围在0xf0..附近将实际搜索空间从 2³² 缩小到了约 2²⁸。攻击原理总结与防御完整攻击链路回顾步骤1: 分析加密算法 正向: plaintext → [①reverse_bits → ②sbox → ③left_shift → ④add_rk] × 16 → ciphertext 步骤2: 构造解密函数 (本文第3节) 逆向: 逐个推导 ④⁻¹, ③⁻¹, ②⁻¹, ①⁻¹ → 按逆序拼装出完整的 decrypt() 步骤3: 编写密钥枚举循环 (本文第5节) for key in 0x00000000..0xFFFFFFFF: if decrypt(ciphertext, key)[:4] bpwd: → 找到正确密钥 步骤4: 恢复完整口令 password decrypt(ciphertext, found_key)核心教训永远不要使用小于128位的密钥。32位密钥 42.9亿种可能 现代计算能力下形同虚设不要自定义密码算法。即使结构看起来复杂16轮、4个操作交错密钥空间小到可暴力枚举意味着所有混淆都是徒劳轮密钥派生需要单向性。从种子线性递增生成轮密钥意味着恢复种子即可重建一切不要依赖算法保密性Kerckhoffs原则算法的安全性必须仅依赖于密钥的保密性而非算法结构防御建议措施说明使用标准算法SM4 (128-bit key) 或 AES-256 (256-bit key)安全的密钥派生PBKDF2 / Argon2 从口令派生密钥带盐值和迭代密钥长度标准至少128位推荐256位不硬编码密钥密钥应从安全存储/HSM获取相关博客23年自定义加密算法逆向下一篇Flag2 — SM2协同签名 k3k2 漏洞恢复服务端私钥