从DES子密钥泄露到主密钥逆向：CTF密码学实战解析

1. 项目概述与核心思路拆解最近在复盘一些经典的CTF密码学题目NepCTF的simpleDES这道题给我留下了挺深的印象。它没有用那些花里胡哨的魔改算法而是非常“耿直”地考察了对DES算法核心——密钥调度流程的理解特别是当攻击者掌握部分子密钥信息时如何逆向推导出原始的主密钥。这其实就是典型的“密钥泄露攻击”Key Leakage Attack场景。很多刚接触密码学的朋友学DES时可能只记住了那个16轮的Feistel结构对密钥扩展的具体细节和逆向可能性却一知半解。这道题正好是一个绝佳的切入点能让我们把书本上的算法流程图变成手里实实在在能跑通的破解脚本。简单来说这道题模拟了这样一个场景一个系统使用标准的DES算法进行加密但由于实现上的疏忽比如侧信道攻击、错误配置导致的部分密钥信息输出攻击者意外获取了最后一轮第16轮加密所使用的子密钥。题目会给你一个密文并告诉你“喏这是用某个未知密钥加密的但我把第16轮的子密钥给你了你能把原始明文也就是Flag找出来吗” 这听起来似乎不可能因为DES有56位有效密钥暴力破解需要2^56次尝试计算量巨大。但如果你真正理解了DES的密钥调度算法Key Schedule就会发现从一个子密钥逆向推出主密钥其搜索空间远小于2^56甚至在已知一个子密钥的情况下理论上是可逆的。这就是这道题的精髓所在也是我想带大家手把手复现的核心。我的思路很明确不是去暴力碰撞整个密钥空间而是利用已知的第16轮子密钥48位根据DES密钥扩展的规则反向推导出所有可能的原始56位主密钥其实是64位含校验位。这个过程涉及到对密钥初始置换PC-1、循环左移规则以及压缩置换PC-2的逆向推算。推导出若干候选主密钥后再用它们去尝试解密题目给出的密文哪个能解出有意义的明文通常以flag{或NepCTF{开头哪个就是正确的密钥。下面我们就一步步拆解这个“化不可能为可能”的过程。2. DES密钥调度算法深度解析与逆向原理要完成逆向必须先吃透正向的密钥生成过程。这是所有操作的基础不能有半点含糊。2.1 标准DES密钥调度流程回顾DES的主密钥是64位但其中第8、16、24、...、64位是校验位通常为奇偶校验位实际参与加密的有效密钥是56位。密钥调度的第一步就是通过固定置换PC-1将这56位有效密钥从64位中提取出来并分成两个28位的半密钥C0和D0。注意很多编程语言或库如Python的pycryptodome在接收DES密钥时期望的是8字节64位的字节串。即使你只给了7字节56位它内部也会按照某种方式处理。但在我们进行底层比特位推算时必须严格按照56位有效密钥的视角来思考。PC-1置换后得到了C0和D0。接下来进行16轮迭代。在每一轮ii从1到16中根据轮数i对Ci-1和Di-1进行循环左移Left Circular Shift。左移的位数是固定的对于第1、2、9、16轮左移1位对于其他轮次左移2位。将左移后的Ci和Di拼接成一个56位的中间结果。通过另一个固定置换PC-2从这个56位中间结果中选取48位输出即为该轮的子密钥Ki。这个过程是单向、确定的。正向计算非常容易给定主密钥可以毫无歧义地生成16个子密钥。2.2 从子密钥Ki逆向Ci Di的思路攻击的突破口在于已知一个子密钥Ki比如K16它是通过PC-2置换从(C16, D16)这个56位数据中选出的48位。PC-2是一个压缩置换它丢弃了输入的56位中的8位。这意味着已知48位的K16我们无法唯一确定(C16, D16)因为那8位被丢弃的信息是未知的。但是我们可以枚举那8位所有可能的取值2^8 256种可能性对于每一种猜测都能通过PC-2的逆操作严格说是“逆推”因为PC-2不可逆但可以枚举还原得到一个候选的(C16, D16)。这是逆向推导的第一步也是计算量第一次膨胀的地方从1个K16我们得到了最多256个可能的(C16, D16)对。2.3 从Ci Di逆向推导主密钥的可行性分析得到(C16, D16)后我们需要根据循环左移的规则反向操作。因为C16和D16是由C15和D15左移而来的第16轮左移1位所以我们可以对C16和D16进行循环右移1位来得到(C15, D15)。同理我们可以一步步右移回去直到得到(C0, D0)。而(C0, D0)就是经过PC-1置换后的56位有效主密钥。最后我们再通过PC-1的逆置换将这56位有效密钥还原到64位的原始密钥包含8位校验位。这里有一个非常关键的点循环左移/右移操作是在28位的Ci或Di上进行的。当我们从(C16, D16)右移得到(C15, D15)时结果是唯一的吗是的因为移位数是已知且固定的根据轮数查表28位数据的循环移位是可逆的。所以从一对正确的(C16, D16)开始我们能够唯一地推导出(C0, D0)。那么问题就归结为如何从256个候选的(C16, D16)中找出那个正确的理论上我们可以用每个候选推导出的主密钥去尝试解密一次密文。但256次尝试对于计算机来说微不足道。然而这里还有一个隐藏的“过滤器”密钥调度过程中每一轮产生的Ci和Di都必须是经过前面所有轮次正确左移后得到的结果。换句话说从(C0, D0)开始正向执行1-16轮的左移必须能重新得到我们最初用来推导的那个(C16, D16)。这个一致性检查可以在尝试解密前进行可以提前过滤掉大量不合逻辑的候选密钥进一步提升效率。3. 破解实战环境准备与核心代码实现理论分析完毕我们进入实战环节。我会使用Python进行演示因为它有丰富的位操作支持和密码学库。我们需要用到pycryptodome库中的DES模块以及进行位运算。3.1 环境搭建与依赖安装首先确保你的Python环境已经安装了必要的库。打开终端或命令提示符执行以下命令pip install pycryptodomepycryptodome是pycrypto的一个维护更活跃的分支提供了包括DES在内的多种密码学原语实现。接下来我们准备题目数据。假设题目提供的信息如下实际题目数据需替换密文 (Ciphertext)一段Base64编码或十六进制编码的字符串。第16轮子密钥 K16 (Hex)例如0x123456789ABC(48位12个十六进制字符)。为了演示我构造一组示例数据import base64 from Crypto.Cipher import DES from Crypto.Util.Padding import pad, unpad # 假设的真实密钥和明文我们当然不知道用于生成题目数据 real_key b\x01\x23\x45\x67\x89\xAB\xCD\xEF # 8字节密钥 plaintext bflag{This_Is_A_Test_Flag} # 使用ECB模式加密CTF题中常见简单模式 cipher DES.new(real_key, DES.MODE_ECB) ciphertext cipher.encrypt(pad(plaintext, DES.block_size)) print(密文 (hex):, ciphertext.hex()) print(密文 (base64):, base64.b64encode(ciphertext).decode()) # 我们需要计算并泄露K16。这里需要自己实现DES密钥调度来获取但解题时K16是直接给出的。 # 下面我们会实现一个函数get_K16来模拟“泄露”。3.2 实现DES密钥调度与K16提取为了模拟题目并验证我们的破解算法我们先实现一个标准的DES密钥调度函数并能提取指定轮次的子密钥。# DES常量表 (PC-1, PC-2, 左移表) # 注意这些表通常以1为起始索引我们在Python中用0起始索引需要做减1调整。 PC1 [57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36, 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4] PC2 [14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32] SHIFT_SCHEDULE [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1] # 每轮左移位数 def bit_string_to_int(bit_str): 将比特字符串转换为整数 return int(bit_str, 2) def int_to_bit_string(num, length): 将整数转换为指定位长的比特字符串 return format(num, f0{length}b) def permute(bits, permutation_table, input_len): 根据置换表对比特串进行置换 result [0] * len(permutation_table) for i, pos in enumerate(permutation_table): result[i] bits[pos - 1] # 表是1起始的 return .join(result) def left_shift(bits, n): 对比特串进行循环左移 return bits[n:] bits[:n] def generate_subkeys(key_64bit): 输入8字节64位密钥返回16个48位子密钥整数列表 # 将密钥转换为64位比特串 key_bits .join([int_to_bit_string(b, 8) for b in key_64bit]) # PC-1置换得到56位有效密钥并分成C0, D0 key_pc1 permute(key_bits, PC1, 64) C key_pc1[:28] D key_pc1[28:] subkeys [] for round_num in range(16): # 循环左移 shift SHIFT_SCHEDULE[round_num] C left_shift(C, shift) D left_shift(D, shift) # 拼接并PC-2置换生成48位子密钥 combined C D subkey_bits permute(combined, PC2, 56) subkeys.append(bit_string_to_int(subkey_bits)) return subkeys # 测试密钥调度并获取K16 real_key_bytes b\x01\x23\x45\x67\x89\xAB\xCD\xEF subkeys generate_subkeys(real_key_bytes) K16_leaked subkeys[15] # 第16轮子密钥索引为15 print(f泄露的第16轮子密钥 K16 (hex): {K16_leaked:012X})运行这段代码我们会得到K16_leaked模拟了题目中“泄露”的子密钥。请记下这个值后续破解我们将假装只知道密文和这个K16。3.3 逆向推导主密钥的核心算法这是整个破解流程的引擎。我们需要实现几个关键函数reverse_pc2: 已知48位子密钥Ki枚举所有可能的56位CiDi对。reverse_shifts: 从(Ci, Di)开始逆向循环右移得到(C0, D0)。reverse_pc1: 从56位有效密钥(C0, D0)逆推出64位原始密钥包含所有可能校验位。def reverse_pc2(k48_int): 从48位子密钥整数枚举所有可能的56位C_i D_i比特串 k48_bits int_to_bit_string(k48_int, 48) possible_cd_list [] # PC-2丢弃了原56位中的8位。我们需要枚举这8位所有可能的位置和取值。 # PC-2有56个输入位输出选其中48位。我们可以构建一个“逆映射”表。 # 更直接的方法生成所有56位比特串应用PC-2看结果是否等于k48_bits。 # 但2^56太大。实际上由于PC-2是固定的我们可以预先计算哪些位被丢弃。 # 这里采用一种更清晰的方法确定已知位和未知位。 # PC-2的输出位对应原56位的哪些位置我们需要一个反向查找。 # 构建一个映射对于PC2输出位的位置i(0-47)它来自原56位的位置 PC2[i]-1。 # 那么不在这个映射中的原56位位置就是被丢弃的8位。 original_positions_used set([p-1 for p in PC2]) # 被PC-2选中的位置0-55 all_positions set(range(56)) discarded_positions list(all_positions - original_positions_used) # 被丢弃的8个位置索引 # 现在我们构造一个基础56位串其中被PC-2选中的位设为已知值丢弃的位先设为0。 base_bits [0] * 56 for i, pos in enumerate(PC2): base_bits[pos - 1] k48_bits[i] # 枚举丢弃的8位所有可能取值 (2^8 256) for guess in range(256): cd_bits base_bits.copy() # 将猜测值填入丢弃的位置 guess_bits int_to_bit_string(guess, 8) for i, pos in enumerate(discarded_positions): cd_bits[pos] guess_bits[i] cd_str .join(cd_bits) # 验证对这个候选cd_str应用PC-2应该得到原始的k48_bits。 # 这是一个重要的过滤确保我们的逆向枚举逻辑正确。 if permute(cd_str, PC2, 56) k48_bits: possible_cd_list.append(cd_str) return possible_cd_list def reverse_shifts(cd_bits_round16, target_round0): 从指定轮次默认第16轮的CD比特串逆向右移回目标轮次默认第0轮即C0D0。 输入: cd_bits_round16 (56位字符串), target_round (0-16) 输出: cd_bits_at_target_round (56位字符串) C cd_bits_round16[:28] D cd_bits_round16[28:] current_round 15 # cd_bits_round16 对应第16轮索引15 while current_round target_round: shift SHIFT_SCHEDULE[current_round] # 这一轮正向的左移位数 # 逆向操作循环右移shift位 C C[-shift:] C[:-shift] D D[-shift:] D[:-shift] current_round - 1 return C D def reverse_pc1(cd0_bits): 从56位C0D0比特串逆推出所有可能的64位原始密钥字节串列表 # PC-1是从64位中选56位。我们需要枚举被丢弃的8位校验位的所有可能。 # 首先构建PC-1的逆映射。PC1表定义了56个输出位各自来自64位输入的哪个位置。 # 那么不在PC1表中的那8个输入位位置就是被丢弃的校验位位置。 pc1_input_positions set(PC1) # PC-1使用的输入位1-64 all_input_positions set(range(1, 65)) parity_positions list(all_input_positions - pc1_input_positions) # 校验位位置1-64 # 构建一个基础64位串其中被PC-1选中的位设为C0D0的值校验位先设为0。 base_64bits [0] * 64 for i, pos in enumerate(PC1): base_64bits[pos - 1] cd0_bits[i] possible_keys [] # 枚举8个校验位所有可能取值 (2^8 256) for guess in range(256): key_bits base_64bits.copy() guess_bits int_to_bit_string(guess, 8) for i, pos in enumerate(parity_positions): key_bits[pos - 1] guess_bits[i] key_bit_str .join(key_bits) # 将比特串转换为8字节 key_bytes bytes([int(key_bit_str[i:i8], 2) for i in range(0, 64, 8)]) possible_keys.append(key_bytes) return possible_keys3.4 整合破解流程与主函数现在我们将上述模块组合起来形成完整的破解脚本。思路是枚举所有可能的(C16, D16)- 逆向得到(C0, D0)- 枚举得到所有可能64位密钥 - 用每个密钥尝试解密 - 检查解密结果是否为合理明文。def crack_des_with_round_key(ciphertext, k16_int): 主破解函数 print(f[*] 开始利用泄露的K16进行破解...) print(f[*] 泄露的K16: {k16_int:012X}) # 第一步从K16枚举所有可能的C16D16 possible_cd16_list reverse_pc2(k16_int) print(f[*] 枚举得到 {len(possible_cd16_list)} 个可能的 (C16, D16) 对。) candidate_keys [] for idx, cd16_bits in enumerate(possible_cd16_list): # 第二步从C16D16逆向得到C0D0 cd0_bits reverse_shifts(cd16_bits, 0) # 第三步从C0D0枚举所有可能的64位原始密钥 keys_from_this_cd16 reverse_pc1(cd0_bits) candidate_keys.extend(keys_from_this_cd16) print(f[*] 总共生成 {len(candidate_keys)} 个候选密钥。) # 第四步尝试用每个候选密钥解密 # 通常密文是经过填充的我们使用ECB模式题目常见 for key_bytes in candidate_keys: try: cipher DES.new(key_bytes, DES.MODE_ECB) # 注意需要处理填充。这里假设是PKCS#7填充。 decrypted_padded cipher.decrypt(ciphertext) decrypted unpad(decrypted_padded, DES.block_size) # 检查解密结果是否像flag包含可打印字符且以特定格式开头 # 这里我们检查是否包含flag{或NepCTF{可根据题目调整 decrypted_text decrypted.decode(utf-8, errorsignore) if flag{ in decrypted_text or NepCTF{ in decrypted_text: print(f[] 找到潜在密钥) print(f 密钥 (hex): {key_bytes.hex()}) print(f 解密明文: {decrypted_text}) return key_bytes, decrypted except (ValueError, UnicodeDecodeError) as e: # 解密失败或解填充失败说明密钥不对继续尝试 continue print([-] 未找到正确密钥。) return None, None # 使用模拟数据进行测试 # 假设我们拿到的密文就是之前用真实密钥加密的那个ciphertext # 并且我们通过某种方式“泄露”了K16 (就是之前计算的K16_leaked) print(\n *50) print(模拟破解测试开始) print(*50) found_key, found_plaintext crack_des_with_round_key(ciphertext, K16_leaked) if found_key: print(f\n[成功] 破解完成恢复的密钥与原始密钥一致吗{found_key real_key_bytes})运行这个脚本你应该能看到它成功地从K16和密文中找回了原始密钥和明文。这验证了我们逆向推导算法的正确性。4. 常见问题、优化技巧与实战心得在实际操作和解决类似CTF题目的过程中你可能会遇到一些坑。这里我总结几个关键点和优化技巧。4.1 密钥表示与字节序问题这是最容易出错的地方。DES算法标准中比特和字节的顺序位序Bit Order有特定约定。在我们的代码中int_to_bit_string函数使用Python的format(num, 0nb)它生成的是大端序Most Significant Bit first的二进制字符串。而很多DES的图示和表格描述中位编号1通常指的是最高有效位MSB。我们使用的PC-1、PC-2置换表其索引就是基于这种“位1为MSB”的约定。重要提示当你从题目中拿到一个十六进制表示的K16比如0x123456789ABC并将其转换成48位二进制串时必须确保比特顺序与你的置换表所期望的顺序一致。在我们的实现中int_to_bit_string(0x123456789ABC, 48)得到的字符串最左边的字符对应整数的最高位MSB这与标准DES的位编号约定是兼容的。如果你从其他渠道如某些硬件描述或另类实现获得比特流务必确认顺序。4.2 枚举空间的优化我们的基础算法会生成256 (可能的C16D16) * 256 (可能的校验位) 65536个候选密钥。对于DES解密来说尝试6万多个密钥瞬间就能完成。但在极端情况下或者作为学习我们可以进一步优化校验位过滤DES的校验位是奇偶校验位每个字节的第8位最低有效位被设置为使得该字节有奇数个“1”。我们可以在reverse_pc1函数中枚举校验位后立即检查每个字节是否符合奇偶校验规则不符合的直接丢弃。这可以将256种校验位可能性减少到大约1种理论上每个字节只有一种校验位设置能满足奇偶性。这是最有效的优化能直接将候选密钥数量从6万多降到256左右。中间轮次一致性检查在从C16D16逆向推导到C0D0后我们可以立刻用这个C0D0正向执行密钥调度计算到C16D16看是否与我们开始枚举的那个C16D16一致。如果不一致说明这个C16D16候选本身就是无效的它对应的所有密钥都可以提前丢弃。这个检查可以在reverse_shifts之后、reverse_pc1之前进行。4.3 处理不同的操作模式和填充我们的示例使用了ECB模式和PKCS#7填充。但CTF题目可能会变化模式可能是CBC、CFB等。如果涉及CBC模式你还需要知道初始化向量IV。题目通常会给或者IV是固定的如全零。我们的破解核心是密钥模式只影响解密时的DES.new()调用。填充可能无填充明文长度恰好是8字节倍数或使用其他填充方式如ZeroPadding。如果解密后unpad失败可以尝试直接输出解密后的字节人工判断是否包含可读字符串。在破解脚本中可以放宽检查条件先不解填充直接判断解密结果的前几个字节是否为可打印字符或预期格式。4.4 实战CTF题中的变体simpleDES这道题是标准的教学题。但出题人可能会增加难度泄露的不是K16可能泄露的是其他轮次的子密钥比如K1或K8。破解原理完全一样只需要在reverse_shifts函数中从对应的轮次开始逆向即可。你需要根据题目给出的轮次调整逆向的起始点。泄露多位子密钥如果题目不小心泄露了多个轮次的子密钥比如K15和K16那么逆向的约束条件更强枚举出的候选密钥会急剧减少甚至可能唯一确定。你需要在逆向过程中用多个子密钥同时进行过滤。魔改的S盒或P盒这是更进阶的题目。如果DES的S盒被替换那么即使你恢复了密钥用标准DES库也无法解密。你需要根据题目提供的“魔改”DES算法重新实现加密/解密函数。但密钥调度部分通常不会改我们的逆向方法依然适用。4.5 调试与验证技巧当你写的破解脚本跑不出结果时按以下步骤排查验证密钥调度正向代码用你已知的一个密钥比如\x01\x23\x45\x67\x89\xAB\xCD\xEF运行generate_subkeys将生成的子密钥与网上标准的DES测试向量进行对比。确保你的PC-1、PC-2、移位表完全正确。单步测试逆向函数选择一个候选密钥用你的正向代码生成K16。然后用这个K16作为输入运行reverse_pc2、reverse_shifts、reverse_pc1看是否能恢复出原始的密钥。这是一个完整的“往返测试”能精准定位是哪个逆向环节出了问题。检查比特位顺序打印中间结果的比特串与已知的测试向量每一步的比特串进行比对。比特顺序错误是导致失败最常见的原因。缩小枚举范围在调试时可以先不枚举所有可能性。例如在reverse_pc2中先固定丢弃位的猜测值比如全0只测试一条路径看逆向流程是否能通。最后分享一个我自己的心得理解这类密码学题目最好的方法就是像我们今天做的一样抛开工具自己从零实现一遍算法。哪怕一开始你的代码又慢又笨但这个过程会让你对算法的每一个比特的流动都了然于胸。下次再遇到不管它怎么变你都能一眼看穿本质。DES虽然古老但其Feistel结构和密钥调度思想非常经典吃透它对学习现代分组密码大有裨益。希望这篇详细的复现流程能帮你不仅解出这道题更能真正掌握密钥泄露攻击背后的密码学原理。