四轮 DES 非标准 S 盒线性密码分析:PL[19]⊕PR[9]⊕CL[9]⊕CR[19] 偏差猜 K4 子密钥恢复主密钥
ctf/crypto · verified
一句话结论
题目使用四轮 DES 但替换了非标准 S 盒,需要自行寻找线性逼近:对表达式 C = PL[19]⊕PR[9]⊕CL[9]⊕CR[19]⊕F4[9]⊕K1[14]⊕K3[14],若猜测的最后一轮子密钥 K4[0..5] 正确,则从密文逆推的 F4[9] 会使 C 的分布出现明显不均匀;枚举 2^6 个候选子密钥、用 80 组明密文统计偏差即可恢复 K4 相关位,再枚举剩余未知位并用已知明密文验证得到完整密钥。
原理
- 线性密码分析:选择一条涉及明文、密文与轮密钥比特的线性近似,使其成立概率偏离 1/2;数据量足够时,正确密钥猜测会让该表达式的分布呈现可检测的偏差。
- 四轮 DES 结构:DES 的 Feistel 结构使 4 轮近似可以写成
PL[i]⊕PR[j]⊕CL[k]⊕CR[l]⊕F4[m]的形式;F4[9]依赖最后一轮子密钥的若干位,因此把“猜密钥”转化为“猜 K4 的 6 位子密钥块”。 - 本题近似:经文中的表达式为
PL[19]⊕PR[9]⊕CL[9]⊕CR[19]⊕F4[9]⊕K1[14]⊕K3[14];在明文/密文已知时可计算除F4[9]外的部分,剩余未知只与 K4 的 6 位有关。 - 偏差判定:对每个候选
k ∈ [0,63],用密文逆推F4[9],统计C为 0/1 的次数;正确候选的分布明显偏离均匀(原文称出现“很明显的不均匀”,错误候选则接近“fifth-fifth”分布)。 - 数据量与剩余位:只有 80 组数据时大数定律不足,部分密钥位可能无法唯一确定;由于明密文已知,可对未知位做暴力枚举并重新加密验证。
- 自定义 S 盒:S 盒被替换后,标准 DES 的线性逼近表失效,需要用题目 S 盒重新计算每个 S 盒的线性逼近偏差,再拼出 4 轮近似。
触发条件
- 已知加密算法为 4 轮 DES 变体、S 盒/置换表可从题目代码或逆向获得。
- 有足够多的已知明文-密文对(原文 80 组;更少时需枚举更多未知位)。
- 攻击者能离线计算线性逼近表与统计偏差。
利用步骤
- 从题目代码提取 IP、FP、E、P、PC-1/PC-2、SHIFT 与自定义 S 盒,建立与 DES 一致的轮函数。
- 对每个 S 盒计算线性逼近表,寻找偏差最大的输入/输出掩码组合,拼出覆盖 4 轮的线性特征。
- 选定近似
PL[19]⊕PR[9]⊕CL[9]⊕CR[19]⊕F4[9]⊕K1[14]⊕K3[14],确认 K1/K3 相关位可通过密钥调度关联或先忽略。 - 对 K4 的 6 位子密钥块(0..63)逐一尝试:用 CR 与候选密钥逆推
F4[9],统计 80 组数据的C分布。 - 选择分布偏差最大的候选作为正确 K4 子密钥位;若多个候选接近,结合其他 S 盒块/近似交叉验证。
- 由 K4 反推主密钥的部分位;对剩余未知位暴力枚举,用已知明密文加密验证,恢复完整 64 位密钥。
- 用恢复的密钥解密挑战密文或生成 flag。
PoC
无完整脚本(原文贴出了 S 盒、密钥调度与统计代码,但未给最终 flag 求解输出)。核心统计逻辑:
# 对每个候选 6-bit K4 子密钥
for k in range(1 << 6):
count = 0
for PL, PR, CL, CR in pairs:
f4 = substitute(xor(expand(CR), guess_key_bits(k))) # 逆推 F4[9]
count += PR[9] ^ CL[9] ^ PL[19] ^ CR[19] ^ f4[9]
score = min(count, len(pairs) - count) # 偏差越小越可疑
变体与关联
- 变体:增加轮数(6 轮)需要更长的线性特征与更多数据;减少数据量则需枚举更多未知密钥位。
- 变体:若 S 盒偏差小,可改用差分分析或多重线性逼近。
- 关联:单轮 SPN 的线性/差分表选择明文攻击见 [[crypto-implementation-single-round-spn-chosen-plaintext-key-recovery]];算法识别与常量提取见 [[code-analysis-reverse-crypto-encoding-identification-decrypt]]。
- 边界:原文只给 80 组数据与统计思路,未给出完整密钥求解脚本;实际复现需自行实现 S 盒线性逼近表与密钥调度逆推。
检测与防御
- 本题为 CTF 密码题,防御侧无直接对应;真实系统应使用标准算法与足够轮数,避免自定义 S 盒引入可分析的线性/差分特征。
- 检测:大量已知明密文对、针对固定密钥的统计查询。