ACM通信
研究突出了
技术角度:从中间解决问题
下面的论文提出了一个优雅的新算法来解决一类广泛的组合优化问题。解剖技术的思想是通过研究DES算法的增强版本而产生的。DES是由美国国家标准局(现为美国国家标准与技术研究所，简称NIST)于1977年提出的一种加密算法，用于保护敏感但非机密的美国政府数据。近30年来，DES一直是全球加密的事实上标准。IBM可能设计了DES，但美国国家安全局(NSA)决定密钥长度应该限制在56位。这是一个有争议的举动，因为它将允许美国国家安全局(而不是其他人)通过搜索密钥空间来破解密码。
增加密钥长度的一种直接方法似乎是加密两次，称为双des或C= DESK1(DESK2(P)),P而且C明文和密文是和K1,K2 .是两个不同的k一些钥匙。1977年，迪菲和海尔曼证明了这种方法没有帮助。让我们假设已知一些密文和相应的明文(这是密码学中的一个标准假设，在实践中经常遇到)。中间相遇攻击的工作原理如下:一个尝试所有2个k第一个键的值K1，计算中间的值一个= DESK1(P)并存储对(K1，一个（K1))在一个表。在第二步中，计算所有键K2 .中间的值为
并搜索值一个在表中。如果找到匹配，则候选对(K1，K2)用附加的明文和密文进行检查。这个算法大约需要2个k加密和2k内存。这就是为什么金融部门已经将单一DES升级为具有三种加密的三重DES。对triple-DES的中间相遇攻击大约需要2个2k加密和2k内存。
这篇论文的作者提出了一个自然的问题:使用四个des是否能获得更好的安全性?乍一看，人们会认为打破四重DES需要22k加密和22k内存。但令人惊讶的答案是，通过应用递归，可以将代价降低到三重des的代价，也就是说，首先猜测中间的值，然后执行两次中间集合攻击。这个想法是由Zhu和Gong为分组密码KATAN提出的，作者受到了Isobe在分组密码GOST方面的工作的启发;然而，作者在Crypto 2012的论文中进一步推进了这些想法，对这种情况下的算法进行优化和推广n的任何值的-fold加密n．此外，他们还表明了解剖技术的广泛应用。
下面这篇论文的作者提出了一个自然的问题:使用四种des能获得更好的安全性吗?
本文以两个实例介绍了解剖过程。首先是魔方的解法。分离解具有与早期算法相同的复杂度，但不使用群论性质。第二个例子是组合划分问题;这个问题的一个变体(背包问题)在密码学中对公钥加密和哈希函数的构造起了非常重要的作用。对于本例，使用了更复杂的策略，将问题划分为不均匀的部分。
解剖技术是了不起的，因为它从一个非常简单的想法开始，中间相遇攻击。作者表明，这个想法可以以一种优雅的方式推广，许多聪明的优化可以将这个想法推向极限。这项工作的一个关键贡献是认识到解剖可以广泛地应用于组合优化问题。最后，所提出的算法减少了对内存的需求，这对算法的实用性至关重要。
数字图书馆是由计算机协会出版的。版权所有©2014 ACM, Inc.
评论
托马斯•琼斯
我在1986年提交给Ravi Sandhu主持的一个会议上发现了一个MitM攻击的缓解方案。他拒绝了我的论文，因为他误解我容易受到MitM的影响，而不是直接解决它。解决办法特别简单。如果存在MitM攻击可能发生的地方，只需在那里插入(伪)随机性。在我的论文中，我创建了一个新的三重des版本称为CCC -或密码/链/密码。在这种情况下，输入用密钥的前56位进行加密(w/或w/o链接-无关)，第二个密钥的OFB版本用中间结果进行x-或d，然后用第三个56位密钥进行加密。这种类型的缓解应该解决MitM的一个弱点。
显示1评论