DES差分密码分析的贝叶斯系统

© 2013年。出版社：Elsevier B.V.信息工程研究院负责评选和同行评议可在www.sciencedirect.com在线获取ScienceDirectIERI Procedia 7（2014）15 - 202013年应用计算、计算机科学与计算机工程国际会议DES差分密码分析的贝叶斯系统A.德保拉湖加利亚诺湾洛雷阿aUniversità degli Studi di Palermo，Viale delle Scienze，ed. 6，Palermo 90128，Italy摘要本文提出了一种新的形式化的DES（数据加密标准）的差分密码分析的基础上贝叶斯网络（BN），一个人工智能框架，用于推理的不确定性影响的数据。通过所提出的方法，它是可能的分析DES从一个新的角度来看，从而铺平了道路，一类新的密码分析方法的发展。版权所有© 2014作者.出版社：Elsevier B.V. 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究院负责评选和同行评议关键词：密码学; DES;差分密码分析;贝叶斯网络;1. 介绍DES（数据加密标准）是在70年代标准化的用于加密敏感数据的对称密码系统。对DES的研究导致了分组密码的现代设计和几种密码分析技术的设计。由于DES的密钥长度较短，该算法目前被认为不适用于关键应用。然而，最近的分组密码，如AES [1]，已经被设计成使暴力攻击不可行。然而，由于DES仍然用于不太敏感的数据，并且也作为Triple DES的构建块[2]，因此分析其漏洞仍然非常有趣。科学文献中的几项工作已经确定并分析了DES的一些主要漏洞这些作品* 通讯作者。联系电话：+39 091 23862064;传真：+39 091 23860840。电子邮件地址：alessandra.depaola@unipa. it。2212-6678 © 2014作者出版社：Elsevier B.V. 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究所负责的选择和同行评审16A. De Paola等人/ IERI Procedia 7（2014）15导致了新的密码分析技术的发展;其中，最有前途的是线性密码分析[3]和差分密码分析[4]。虽然这些方法从理论的角度来看非常有趣，因为它们有助于识别DES的严重漏洞，但由于所需的大量加密操作，即使它小于暴力攻击，它们也不能用于实际攻击。这项工作提出了实施差分密码分析的可行性研究[4]。相对于经典的方法用于形式化的这种技术，我们建议采用贝叶斯网络（BN），用于处理受不确定性影响的数据的人工智能工具。据我们所知，这种方法在科学文献中是一种新颖的方法。本文的其余部分的结构如下：第2节回顾DES的属性，并讨论了一些相关的工作;第3节描述了所提出的贝叶斯网络建模的攻击S盒，然后扩展所提出的方法来攻击整个DES;最后第4节陈述我们的结论，并讨论了一些未来的工作。2. DES描述和相关工作DES是将64位明文P转换为64位密文T的对称密码系统。64位密钥K，实际上减少到56位密钥，因为8位用作奇偶校验位，参数化变换。DES通过一系列称为轮的变换作用于明文P。每一轮的输入通过DES的Feistel函数的应用进行转换，该函数由一系列排列和替换组成。使用用于子密钥生成的调度算法从K获得的48位子密钥参数化每一轮。图1（a）示出了一般DES方案，图1（b）示出了单轮处理的细节。(a)(b)（c）第（1）款Fig. 1. (a)DES通用块方案。(b)DES的轮处理的块方案。(c)DES的Feistel函数的详细框图。对于每一轮X=2，A. De Paola等人/ IERI Procedia 7（2014）1517RXXLXLXRX1XXX 1（R）X1，SK）（一）即，通过用PX-1的右32位半部分RX-1替换PX-1的左32位半部分LX-1并通过用LX-1和RX-1的非线性组合替换PX-1的右半部分，从PX-1获得PX，所述组合由子密钥SKX参数化。一轮的核心是Feistel函数，它包含DES唯一的非线性组件，S盒。特别地，在图1（c）中展开的映射F定义如下：F（RX）1，SK ）P（S（E（RX1）<$SK））（二）其中E称为扩展函数，S称为S-Box，P称为置换。[5]中详细描述的适当表格定义了此类映射。这些函数的域和余域定义如下：E：132-1482 2S：2018年10月31日（三）2 2P：1001002 2值得注意的是，E和P是线性映射，而S是算法中唯一的非线性部分;它的目标是擦除密钥SK和明文之间的现有关系。S盒是DES的主要安全组件，它的破坏使得整个加密系统容易被破坏。一般来说，S-Box不被分析为唯一块，因为它由八个子映射S：组成，i=我2 2许多文献都是针对S盒进行分析的。[6]和[7]的作者提出了一个分析的S盒的性质，从而在分组密码上下文中的一些可能的设计准则。基于所发现的性质，文献中提出了许多破解S盒的密码分析方法。在[8]中提出了一种代数方法，该方法定义了用于确定非线性代数约束集的标准集，该约束集描述了S盒的I/O关系。利用这组约束，整个密码被描述为一个系统的多元非线性方程。相反，作者[3]提出了一种S盒和整个DES的线性近似，这种近似在一定概率下是有效的，这种方法是对S盒的随机攻击的一个例子。已经表明，如果输入未知，则S盒的输出分布是均匀的，但实验表明I/O差异的分布是不均匀的[4]。对于一个给定的S盒取两个不同的输入，并假设这两个输入被某个已知的差所限制，那么S盒的相应输出之间的差的概率分布是不均匀的;这样的重要性质代表了一个强的系统脆弱性，并且是差分密码分析的基础[4]。作者通过变换来跟踪差异，发现密码在哪里表现出非随机行为，并利用这些属性来恢复密钥。3. 贝叶斯网络差分密码分析贝叶斯网络（BN）[9]是一种基于图论的形式主义，表达随机变量之间的因果关系。在所提出的方法中，我们对[4]中发现的I/O差异的统计分布进行建模，尽管BN允许执行诊断推断以发现钥匙建议的BN，如图所示。 2（a），使用[4]中报道的原始符号：在轮次X，Si EX，Si *EX表示扩展函数的输出的第i个六位块;SiKX是扩展函数的输出的第i个六位块。18A. De Paola等人/ IERI Procedia 7（2014）15IX IXOXEX牛S1、S1*是第i个S-Box的两个输入;S1'是S-Box输入之间的XOR;而S1'是S-Box输出之间的XOR。(a)(b)（c）第（1）款图二、（a）BN用于对第i个S盒的攻击（b）BN用于攻击第i个Feistel函数。（c）BN用于对3轮DES的攻击由于差分密码分析是一种选择明文攻击，因此可以假设知道以下证据： Si，Si*，Si'，Si'（4）因此，搜索关键字相当于最大化以下可能性：p（Si KX | ).（五）通过诊断推断，可以评估等式5。当领导多个攻击时，整个分布与单个分布的乘积成比例;因此，给出以下证据集你好，谢谢你，（六）这种可能性可以评估如下：Mp（Si KX|）|（见附件）。第一章1（七）方程7可以通过微分方法求解。让我们定义EXIXA. De Paola等人/ IERI Procedia 7（2014）1519MIXEXEXIXIXIXIXIX牛IX牛IXXXXXXXXXIXXEXKX你知道吗，（八）1 2那么，p（SiKX| KX（SiKX）|n）p（SiKX|（见附件1）。（九）所提出的BN的概率密度函数，执行概率推断所必需的，表示如下：piEX12，* 六个第九章|S iEX，S iKXS iEXS iS i;p*|Si*，SiSi*Si;KX KX（十）pSi' | Si，Si*Si'Si;IX IXpSi'|Si，Si*Si'SiSiSi*IX IX--其中是Kronecker delta，Si（.） 是第i个S盒。所提出的方法允许将攻击形式化为整个Feistel函数;然而，由于作为扩展函数的输出获得的六位块不是独立的，因此不可能概括图2（a）中所示的BN。图2（b）中示出了遵循相同方法构建的替代BN，其采用以下符号：ZX ，Z*：Feistel函数的输入兹 Z*：输入之间的差异;SKX：48位子密钥;SIX*：输入到S-Box;Y'：来自S-Box的输出之间的差的排列。在选择明文上下文中攻击Feistel函数意味着可以选择两个输入ZX和Z*，利用它可以计算输入XORZ在输出Y通过诊断推断，可以减少关于48位的不确定性。子密钥。BN也可以用于前向推理过程，其从以Z '为条件的Y特别地，可以从48位随机采样开始对Y'进行采样。X x X通过随机数生成器[9]并通过应用以下等式获得的SIX的数字“普赖斯” SSE没关系（十一）采样技术还可以用于在处理两个输入P和P*时推断DES内部的差传播。设P' =（L'，R '）是输入P和P*之间的XOR，显式地分解在其左部分和右部分中，T' =（1 '，r'）是密码输出的XOR，RIX是在第X轮处到Feistel函数的输入的XOR，ROX是在第X轮处来自Feistel函数的输出的XOR。差异的传播可以通过BN来建模，如图2（c）所示，DES减少到三轮。为了攻击N轮DES，需要采用以下算法：Z，SYXIXIX20A. De Paola等人/ IERI Procedia 7（2014）15 通过对连续差分进行采样，得到值I（N-1） 获取值RIN=r 获取值lIN; 通过使用图中的BN攻击最后一轮的S-Box来构建子密钥直方图。 2（a）; 一旦最后一轮被打破，继续前一轮。4. 结论和今后的工作这项工作表明，DES的差分密码分析可以通过一种替代的和新的方法，基于贝叶斯网络实现。该方法建立了一个用于攻击单个S盒的BN模型，并可以扩展到攻击Feistel函数，最终攻击整个DES。在分析明文、密文所需对数和计算复杂度时，该方法与原公式是等价的。尽管如此，所提出的新观点可能为未来有希望的发展铺平道路。最有前途的方向之一似乎是利用不同攻击之间的独立性，并行实现的概率推理。此外，通过执行利用BN的结构的重要性采样，可以改变采样阶段所采用的方法。最后，我们计划评估在贝叶斯网络中执行有效推理的替代方法，例如遗传算法[11]，甚至结合并行化[12]。引用[1] Daemen J，Rijmen V. Rijndael的设计。Springer-Verlag New York，Inc. 2002年。[2] Coppermith D，Johnson DB，Matyas，SM.三重DES加密的一种建议模式。IBM研究与发展杂志。1996;40（2）：253-262.[3] 松井DES密码的线性分析方法。在密码学的进展-EUROPHOTOPT '93;在计算机科学讲义。1994;765：386-397.[4] Biham E，Shamir A.类DES密码系统的差分密码分析。Journal of Cryptology. 1991; 4（1）：3-72.[5] 美国国家标准与技术研究所FIPS PUB 46-3：数据加密标准（DES）。一九九九年。[6] Brickell EF，Moore JH，Purtill，MR. DES的S盒中的结构。密码学进展论文集-美国专利局'86;Springer-Verlag; 1987; 3-8。[7] Dawson MH，Tavares SE.基于信息论的扩展S盒设计准则及其与类差分攻击的关系。在第10届加密技术理论和应用国际年会的会议记录中-EUROPENTIAL PT '91; 1991; Springer-Verlag; 352-367。[8] Courtois NT，Bard GV.数据加密标准的代数密码学分析。密码学与编码;计算机科学讲义;2007; 4887：152-169。[9] 柯勒D，弗里德曼N.概率图模型：原理与技术-自适应计算与机器学习。麻省理工学院出版社; 2009.[10] 作者：Jiangsu G，Jiangsu F，Jiangsu M.无线传感器网络中的安全随机数生成。第四届信息和网络安全国际会议（SIN 2011）; 2011; 175-182。[11] Mengshoel OJ。高效贝叶斯网络推理：遗传算法，随机局部搜索和抽象。1999.技术报告。伊利诺伊大学香槟分校，香槟，伊利诺伊州，美国。[12] Lo Presti G，Lo Re G，Storniolo P，Urso A.求解随机Petri网的一种网格化并行混合遗传算法。计算科学- ICCS 2004;计算机科学讲义。2004; 3036：156-163