fbpx
维基百科

差分密码分析

十月 05, 2023

差分密码分析是一种密码分析的方法，主要用于破解分组加密，但也适用于流加密和加密哈希函数。广义上讲，其研究的是信息输入上的差别对输出结果变化的影响。对于分组密码，其指的是利用差异来获取密钥的技术，包括跟踪变换网络中的差异，以及寻找加密中的非随机行为等。

历史 编辑

1980年代后期，诶利·比哈姆（英语：Eli_Biham）和阿迪·萨莫尔发表了一系列针对多个块加密和哈希函数的攻击，包括对資料加密標準（DES）理论弱点的运用。因此，二者通常被认为是在公开领域中发现差分密码分析的元勋，然而NSA在更早之前已发现该方法，但并未公开。比哈姆和萨莫尔表示，DES在抗差分密码分析方面表现意外的好，不过只要对加密算法稍加修改就能大幅减弱其抗攻击能力。[1]

1994年，IBM DES初始团队的成员唐·库帕史密斯（英语：Don_Coppersmith）发表论文称，IBM早在1974年就发现了差分密码分析法，并早已将抗差分分析纳入算法的设计目标中。[2]作家史蒂芬·列维表示，IBM的确独立发现了差分密码分析方法，显然NSA也知道这项技术。[3]对于IBM选择保密的原因，库帕史密斯解释道：“IBM与NSA商讨后，认为若公布加密算法中抗差分密码分析的设计，那么差分密码分析这种能攻击多种加密算法的强力技术就会被暴露，这将削弱美国在密码学领域的领先优势。[2]IBM内部把差分分析称为“T-attack”[2]或“Tickle attack”。[4]

与内建抗差分密码分析的DES相比，同期其它加密算法在这方面被证实是脆弱的。FEAL（英语：FEAL）是本分析方法的早期攻击目标。原始的4轮版本（FEAL-4）可以在仅利用八个选择明文的情况下被破解，且31轮版本的FEAL的抗攻击性也不尽人意。相比之下，差分分析在使用247数量级的选择明文后才能破解DES算法。

攻击原理 编辑

差分密码分析通常是选择明文攻击，意思是攻击者可以自行选取一部分明文并取得相应密文。不过，一些扩展也能让此方法用在已知明文攻击，甚至是唯密文攻击上。差分分析的基本方法，是运用若干对有着常量差异的明文；差异可以用数种方法定义，最常见的是逻辑异或（XOR）。然后，攻击者计算相应密文的差异，尝试找出差异分布的统计特征。明文差异和密文差异所组成的差异对被称为差分，其统计性质由加密所使用的S盒决定。也就是说，对于S盒子S，攻击者分析差分(ΔX, ΔY)，其中ΔY = S(X ⊕ ΔX) ⊕ S(X)（⊕表示异或）。在初等攻击中，攻击者希望某个密文差异出现的频率非常高，这样就能将加密和随机过程区分开来。更复杂的变体攻击能做到比穷举更快地破解出密钥。

最基本的差分密码分析密钥破解形式中，攻击者首先取得大量明文对的密文，并假设差分在至少r − 1轮后有效，r即加密算法的总轮数。攻击者在倒数第二轮与最后一轮之间差异固定的假设下，去推测可能的轮密钥。如果轮密钥比较短，那么只需举可能的轮密钥，直到最后一轮运算结果和差异的密文对一致即可。当一个轮密钥看起来明显比其他密钥常出现时，其会被假设是正确的轮密钥。

针对特定的加密算法，输入差异要经过精心挑选才能使攻击成功。这需要研究算法的内部过程；标准的方法是在加密的不同阶段，跟踪一个高频差异经过的路径，术语上将这点称为差分特征。

自从差分密码分析进入公众视野，其就成了加密设计者的基本考量。新的加密设计通常需要举证其算法可以抗此类攻击。包括AES在内的许多算法都被证明在差分分析攻击下是安全的。[來源請求]

攻击细则 编辑

攻击主要依赖于一点：给定输入/输出，差异特征仅在特定输入下出现。这种方法通常用于线性结构组成的加密方式，如差表结构或S盒。给定两个已知密文或明文后，观察其输出差异可猜测密钥的可能值。

举个例子，假设有一个差分：输入的最低位的变化时，引起输出最低的变化，记作1 => 1。

变体 编辑

  • 高阶差分分析（英语：Higher-order differential cryptanalysis）
  • 截断差分分析（英语：Truncated differential cryptanalysis）
  • 不可能差分密码分析（英语：Impossible differential cryptanalysis）
  • 回力镖攻击（英语：Boomerang attack）

另见 编辑

  • 密码学
  • 线性密码分析（英语：Linear_cryptanalysis）
  • 密文不可区分性（英语：Ciphertext_indistinguishability）

参考 编辑

  1. ^ Biham and Shamir, 1993, pp. 8-9
  2. ^ 2.0 2.1 2.2 Coppersmith, Don. The Data Encryption Standard (DES) and its strength against attacks (PDF). IBM Journal of Research and Development. May 1994, 38 (3): 243 [2018-07-15]. doi:10.1147/rd.383.0243. （原始内容 (PDF)于2020-11-14）.  (subscription required)
  3. ^ Levy, Steven. Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age. Penguin Books. 2001: 55–56. ISBN 0-14-024432-8. 
  4. ^ Matt Blaze, sci.crypt（英语：sci.crypt）, 15 August 1996, Re: Reverse engineering and the Clipper chip" （页面存档备份，存于互联网档案馆）

外部链接 编辑

  • A tutorial on differential (and linear) cryptanalysis （页面存档备份，存于互联网档案馆）
  • . [2018-07-14]. （原始内容存档于2007-10-19）. 

十月 05, 2023
差分密码分析, 是一种密码分析的方法, 主要用于破解分组加密, 但也适用于流加密和加密哈希函数, 广义上讲, 其研究的是信息输入上的差别对输出结果变化的影响, 对于分组密码, 其指的是利用差异来获取密钥的技术, 包括跟踪变换网络中的差异, 以及寻找加密中的非随机行为等, 目录, 历史, 攻击原理, 攻击细则, 变体, 另见, 参考, 外部链接历史, 编辑1980年代后期, 诶利, 比哈姆, 英语, biham, 和阿迪, 萨莫尔发表了一系列针对多个块加密和哈希函数的攻击, 包括对資料加密標準, 理论弱点的运用, 因. 差分密码分析是一种密码分析的方法 主要用于破解分组加密 但也适用于流加密和加密哈希函数 广义上讲 其研究的是信息输入上的差别对输出结果变化的影响 对于分组密码 其指的是利用差异来获取密钥的技术 包括跟踪变换网络中的差异 以及寻找加密中的非随机行为等 目录 1 历史 2 攻击原理 3 攻击细则 4 变体 5 另见 6 参考 7 外部链接历史 编辑1980年代后期 诶利 比哈姆 英语 Eli Biham 和阿迪 萨莫尔发表了一系列针对多个块加密和哈希函数的攻击 包括对資料加密標準 DES 理论弱点的运用 因此 二者通常被认为是在公开领域中发现差分密码分析的元勋 然而NSA在更早之前已发现该方法 但并未公开 比哈姆和萨莫尔表示 DES在抗差分密码分析方面表现意外的好 不过只要对加密算法稍加修改就能大幅减弱其抗攻击能力 1 1994年 IBM DES初始团队的成员唐 库帕史密斯 英语 Don Coppersmith 发表论文称 IBM早在1974年就发现了差分密码分析法 并早已将抗差分分析纳入算法的设计目标中 2 作家史蒂芬 列维表示 IBM的确独立发现了差分密码分析方法 显然NSA也知道这项技术 3 对于IBM选择保密的原因 库帕史密斯解释道 IBM与NSA商讨后 认为若公布加密算法中抗差分密码分析的设计 那么差分密码分析这种能攻击多种加密算法的强力技术就会被暴露 这将削弱美国在密码学领域的领先优势 2 IBM内部把差分分析称为 T attack 2 或 Tickle attack 4 与内建抗差分密码分析的DES相比 同期其它加密算法在这方面被证实是脆弱的 FEAL 英语 FEAL 是本分析方法的早期攻击目标 原始的4轮版本 FEAL 4 可以在仅利用八个选择明文的情况下被破解 且31轮版本的FEAL的抗攻击性也不尽人意 相比之下 差分分析在使用247数量级的选择明文后才能破解DES算法 攻击原理 编辑差分密码分析通常是选择明文攻击 意思是攻击者可以自行选取一部分明文并取得相应密文 不过 一些扩展也能让此方法用在已知明文攻击 甚至是唯密文攻击上 差分分析的基本方法 是运用若干对有着常量差异的明文 差异可以用数种方法定义 最常见的是逻辑异或 XOR 然后 攻击者计算相应密文的差异 尝试找出差异分布的统计特征 明文差异和密文差异所组成的差异对被称为差分 其统计性质由加密所使用的S盒决定 也就是说 对于S盒子S 攻击者分析差分 DX DY 其中DY S X DX S X 表示异或 在初等攻击中 攻击者希望某个密文差异出现的频率非常高 这样就能将加密和随机过程区分开来 更复杂的变体攻击能做到比穷举更快地破解出密钥 最基本的差分密码分析密钥破解形式中 攻击者首先取得大量明文对的密文 并假设差分在至少r 1轮后有效 r即加密算法的总轮数 攻击者在倒数第二轮与最后一轮之间差异固定的假设下 去推测可能的轮密钥 如果轮密钥比较短 那么只需举可能的轮密钥 直到最后一轮运算结果和差异的密文对一致即可 当一个轮密钥看起来明显比其他密钥常出现时 其会被假设是正确的轮密钥 针对特定的加密算法 输入差异要经过精心挑选才能使攻击成功 这需要研究算法的内部过程 标准的方法是在加密的不同阶段 跟踪一个高频差异经过的路径 术语上将这点称为差分特征 自从差分密码分析进入公众视野 其就成了加密设计者的基本考量 新的加密设计通常需要举证其算法可以抗此类攻击 包括AES在内的许多算法都被证明在差分分析攻击下是安全的 來源請求 攻击细则 编辑攻击主要依赖于一点 给定输入 输出 差异特征仅在特定输入下出现 这种方法通常用于线性结构组成的加密方式 如差表结构或S盒 给定两个已知密文或明文后 观察其输出差异可猜测密钥的可能值 举个例子 假设有一个差分 输入的最低位的变化时 引起输出最低的变化 记作1 gt 1 此章节需要扩充 变体 编辑高阶差分分析 英语 Higher order differential cryptanalysis 截断差分分析 英语 Truncated differential cryptanalysis 不可能差分密码分析 英语 Impossible differential cryptanalysis 回力镖攻击 英语 Boomerang attack 另见 编辑密码学 线性密码分析 英语 Linear cryptanalysis 密文不可区分性 英语 Ciphertext indistinguishability 参考 编辑 Biham and Shamir 1993 pp 8 9 2 0 2 1 2 2 Coppersmith Don The Data Encryption Standard DES and its strength against attacks PDF IBM Journal of Research and Development May 1994 38 3 243 2018 07 15 doi 10 1147 rd 383 0243 原始内容存档 PDF 于2020 11 14 subscription required Levy Steven Crypto How the Code Rebels Beat the Government Saving Privacy in the Digital Age Penguin Books 2001 55 56 ISBN 0 14 024432 8 Matt Blaze sci crypt 英语 sci crypt 15 August 1996 Re Reverse engineering and the Clipper chip 页面存档备份 存于互联网档案馆 外部链接 编辑A tutorial on differential and linear cryptanalysis 页面存档备份 存于互联网档案馆 Helger Lipmaa s links on differential cryptanalysis A description of the attack applied to DES 2018 07 14 原始内容存档于2007 10 19 取自 https zh wikipedia org w index php title 差分密码分析 amp oldid 76763435, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。