差分分析
- 提出者
- Eli Biham
- 年份
- 1990
- 类型
- statistical attack on block ciphers
- 类别
- Cryptanalytic technique
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
差分分析是一种针对对称分组密码的统计攻击技术,它通过分析输入的差分和输出的差分来恢复密钥。该技术由Eli Biham和Adi Shamir于1990年提出,是第一个超越暴力搜索的DES实用攻击方法。差分分析通过研究明文的微小变化在密码轮之间传播的方式,来利用密码变换的非随机特性。在过去三十年里,差分分析对密码设计产生了深远影响。
方法背后的直觉
差分分析通过研究具有特定差分的明文对,并观察这些差分如何通过密码轮演变来工作。如果某些差分以特定方式传播的概率更高,这种非随机性就可以被用来恢复密钥比特。攻击者选择旨在最大化有用输出差分概率的明文对,然后利用观察到的输出差分来缩小候选密钥的范围。
历史学
差分分析由Biham和Shamir于1990年提出,揭示了对DES的实际攻击,需要2^47次操作和2^47个明文-密文对。该攻击表明DES比预期要弱,并促使采用更严格的设计标准。AES和其他现代密码在设计时就考虑了差分抵抗能力,显著提高了此类攻击的门槛。
何时使用
差分分析用于密码分析研究,以评估密码强度。密码设计者使用差分分析来验证对差分攻击的抵抗能力。现代密码包含专门设计用于抵抗差分分析的轮和变换。
局限与注意事项
- 需要大量的已知明文-密文对,通常不切实际
- 现代密码(如AES)经过精心设计,能够抵抗差分分析
- 发动攻击的计算成本可能过高
- 有效性取决于发现强大的差分特征,而对于更长的轮数,这变得更加困难
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 对某些密码的实际攻击,所需操作少于2^64次(优于64位密钥的暴力搜索)
- 良好的数学基础,能够严格分析密码安全性
- 指导密码设计;抵抗差分分析是标准设计目标
- 揭示了密码设计中其他技术可能忽略的结构性弱点
应用
- 密码学研究和学术出版物中对分组密码的密码分析
- 密码设计和评估,确保足够的轮数和变换以抵抗差分攻击
- 标准机构(如NIST、ETSI)的密码验证,要求进行抵抗性分析
- 对遗留密码的安全性评估,识别弱点并指导淘汰决策
使用方式
使用方式
识别差分特征:在密码轮之间具有任意密钥下高发生概率的差分序列。
估计区分密码与随机性并恢复密钥比特所需的明文对数量。
使用具有期望差分的明文-密文对来测试候选密钥值,排除与观察不符的密钥。
分析计算成本和所需数据量。实际攻击需要平衡这些因素与暴力密钥搜索。
常见陷阱
- 低估了发现现代密码特征的难度
- 高估了在理论数据需求量过大时实际攻击的可行性
- 仅考虑抵抗差分分析就认为安全;必须考虑多种攻击向量
常见问题
什么是差分特征?
差分特征是密码每轮的输入和输出差分序列,具有特定的概率。发现高概率特征是发动成功的差分攻击的关键。
AES如何抵抗差分分析?
AES使用变换(替换和混合),确保任何单比特输入差分在仅三轮后至少扩散到25个输出比特。这种快速扩散使得差分攻击不可行。
差分分析能破解现代密码吗?
实际上不能。像AES这样的现代密码需要过量的明文和计算资源,远远超过暴力密钥搜索。
差分分析与线性分析是相同的吗?
不是。差分分析研究输入-输出差分,而线性分析研究线性近似。两者都是重要的攻击类别;密码必须同时抵抗两者。
如何评估密码对差分攻击的抵抗能力?
分析密码的S盒和轮变换的最大差分概率。使用自动化工具和手工分析来寻找特征。在同行评审的场合发布结果以供社区审查。