Skip to content
返回搜索结果

线性密码分析

提出者
Mitsuru Matsui
年份
1993
类型
linear approximation attack
类别
Cryptanalytic technique

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

线性密码分析是一种已知明文攻击,它利用密码的非线性变换的线性近似来恢复秘密密钥比特。该方法由松井充(Mitsuru Matsui)于1993年提出,线性密码分析提供了对DES等密码的实际攻击,其计算复杂度低于暴力破解。该技术分析明文和密文比特的线性组合与密钥比特之间关系的统计偏差,从而以减少的数据需求进行密钥恢复。

方法背后的直觉

线性密码分析找到关联明文比特、密文比特和密钥比特的线性方程。由于密码轮中的混合不完美,这些线性方程以略好于随机的概率成立。通过收集大量的明文-密文对,并观察哪些密钥值使这些方程更频繁地成立,攻击者可以缩小正确密钥的范围。

历史学

线性密码分析由松井于1993年提出,作为对DES的已知明文攻击。1994年,松井使用线性密码分析演示了对DES标准首次进行的实验性密码分析,以2^43个已知明文恢复了密钥。这一突破展示了针对已部署标准的实际攻击,并影响了AES的设计,使其具有可证明的抵抗界限。

何时使用

线性密码分析用于密码分析研究和密码设计评估。它指导密码设计者选择能够抵抗线性近似的S盒和变换。现代密码的设计考虑了线性近似强度的可证明界限。

局限与注意事项

  • 现代密码(如AES)经过精心设计,具有可证明的界限,能够抵抗线性密码分析
  • 需要已知明文-密文对,这在所有场景下可能都不可用
  • 对于设计良好的密码,计算和数据需求可能超出实际可行性
  • 发现现代密码的强线性近似极其困难

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 对DES的实际攻击,需要2^43个明文-密文对和2^39次操作
  • 用于分析近似偏差的良好形式化的数学框架(堆积引理)
  • 补充了差分密码分析,发现了差分分析可能遗漏的弱点
  • 塑造了S盒选择和轮变换的密码设计要求

应用

  • 对分组密码的密码分析,在研究和标准化中评估安全属性
  • 密码设计和S盒选择,以确保足够的线性近似界限
  • 密码标准验证(NIST、ETSI)要求进行线性抵抗分析
  • 遗留密码评估,用于退休和替换决策

使用方式

使用方式

1

寻找线性近似:明文比特、密文比特和密钥比特之间,以显著不同于0.5的概率成立的线性关系。

2

使用轮变换的统计分析来估计每个线性近似的偏差(与0.5的偏差)。

3

对于候选密钥值,计算线性近似在已知明文-密文对中成立的次数。正确的密钥使近似最频繁地成立。

4

通过解密密文并检查正确性来验证恢复的密钥比特。

常见陷阱

  • 假设所有线性近似都可利用;弱近似提供最小优势
  • 低估实际攻击难度,尽管理论数据需求看似合理
  • 忽略密码分析中线性与差分属性之间的相互作用

常见问题

什么是堆积引理?

堆积引理提供了一种通过组合单个轮近似的偏差来计算多轮线性近似偏差的方法。它是线性密码分析的基础。

AES如何抵抗线性密码分析?

AES使用的S盒选择旨在最小化最大线性近似概率,其扩散层确保了线性偏差在各轮之间快速扩散。可证明的界限保证不存在实际可行的线性近似。

线性密码分析与差分密码分析的区别是什么?

差分分析研究输入-输出差异,而线性分析研究线性近似(明文和密文比特的异或)。两者都利用密码的结构弱点。

线性密码分析能破解现代密码吗?

实际上不能。像AES这样的现代密码在理论上对线性近似有界限,使得攻击在计算上不可行。

如何在我的密码设计中评估线性抵抗力?

分析S盒的线性近似表,并使用堆积引理计算跨轮的最大偏差。确保所有可能的线性近似的最大偏差都可以忽略不计。

相关方法

参考文献

  1. Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.

    打开 DOI 文献
    已复制。
  2. Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.

    打开 DOI 文献
    已复制。