英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
Skipjack的密码分析-用不可能的微分将其缩减为31轮
Eli Biham 1，Alex Biryukov 2和Adi Shamir 3
一以色列理工学院计算机科学系，海法32000，以色列，biham@cs.Technon.ac.il，http：/www.cs.Technon.ac.il/sim;biham/
二以色列理工学院应用数学系，海法32000，以色列，albi@cs.tech on.ac.il
三应用数学和计算机科学系，魏茨曼科学研究所，Rehovot 76100，以色列，Shamir@wisdom.weizmann.ac.il.
摘要。本文提出了一种基于不可能微分的密码分析技术。我们使用它来表明，Skipjack的恢复键从32次减少到31次，比穷举搜索更快。我们还描述了Yoyo游戏(一种可以用来对付缩减轮Skipjack的工具)以及Skipjack的其他属性。
关键词。Skipjack，密码分析，差分密码分析，不可能的不同级别，Yoyo游戏，自适应攻击。
1导言
差分密码分析[6]传统上考虑特征或差异-具有较高概率的效价，并利用它们来区分正确的从错误的钥匙未知的钥匙。当正确的密钥被用于解密最后几轮的密文，预计会有不同之处。当使用错误的键时，由差异预测的情况经常出现。这种差异发生的频率较低。
本文描述了一种新的差分密码分析变体差异预测不应发生特殊的差异(即它们的差异)。)，因此正确的密钥永远无法解密一对密文的区别。因此，如果一对被解密为此差异在某个试用密钥下，那么这个试用密钥肯定不是正确的密钥。这是一种筛选攻击，它通过消除所有其他键来找到正确的键。导致矛盾。
我们称之为概率为零的不可能微分，并且这种密码分析方法具有不可能的差别。
我们应该强调的是，利用不可能发生的事情来隐晦地说-姐姐不是新来的。众所周知，[7]英国对德国的密码分析在第二次世界大战中，谜使用了几个这样的想法(例如，一个明文字母不能被加密到自己，因此一个错误猜测的明文可以。)容易被丢弃)。不可能事件在微分中的首次应用在[6]中提到密码分析，其中差分分布中的零项-在计数阶段之前，使用tion表来丢弃错误的对。更多Biham描述了最近基于不可能事件的密码分析攻击。在1995年的梯形DES密码分析中，一种使用DES的4轮Feistel密码。作为F函数。这一密码分析发表在[3]中，并基于事实是，碰撞不能由置换产生。类似的技术他在描述交易[8]，一个六轮费斯特尔时使用了后者。用DES作为F函数的密码。虽然使用不可能的事件的想法这种类型的密码在只有几发子弹的Feistel密码中是自然的。以排列为圆函数，没有一般的方法论。将不可能事件与差分密码分析技术相结合，产生不可能的差异，有大量的回合。
在本文中，我们证明了不可能微分的密码分析是非常重要的。强大的对抗许多具有不同结构的密码。我们描述一个不可能的Skipjack的微分[15]，它确保所有的键都没有对的属性有特殊差异的输入，在24轮加密输出还有其他一些特殊的区别。这个微分可用于(1)攻击Skipjack，减少到31发(即从Skipjack到Skipjack)。只有第一轮或最后一轮被移除)，略快于详尽无遗搜索(使用2 34选择明文和2 64内存)，(2)攻击较短的变体和(3)区分黑匣子是否应用24轮变体。或者随机排列。在一篇相关的论文[5]中，我们描述了这类密码分析在IDEA[10]和Khufu[12]中的应用改进了对这些方案的最知名攻击。
对弹跳的常规密码分析我们请读者参阅[4]和[9]。
本文的结构如下：对Skipjack的描述第2款。Skipjack的24轮不可能微分在证券交易委员会中被描述-运动3。在第4节中，我们描述了我们对Skipjack攻击的一个简单变体。减少到25发和26发，在第5节中我们描述了我们的主要攻击AP-与Skipjack的对抗减少到31发。最后，在第六节中，我们讨论了为什么这次攻击不直接适用于32回合的Skipjack，总括来说-把报纸整理一下。在附录中，我们描述了一种自动查找不可能的差别。
2 Skipjack简介
SKIPJACK是一个具有32轮两种类型的迭代分组密码，称为规则A规则B.每一轮都以线性反馈移位寄存器的形式描述。具有附加的非线性键控G置换。规则B基本上是相反的。规则A的位置差异很小。跳过八轮规则A，接着是八轮规则B，接着是另八轮规则A，然后是另八轮规则B。图1给出了规则A和规则B的原始定义，其中计数器是整数。(在1到32的范围内)，其中G是一个四轮Feistel置换，其F函数定义为一个8x8位S盒(称为F表)，每一轮G的键由八位键组成。Skipjack的键调度需要一个10字节的密钥，每次使用其中的四个来键入每个G置换。前四个字节用于键入第一个G置换，并且每个额外的字节G置换是由接下来的四个字节周期性地进行的，周期为五轮。
如果我们展开巡查，保持四个，描述就变得更简单了。移位寄存器中的元素是固定的。图2描述了这种表示形式。Skipjack(32轮中只有前16轮被列出；接下来的16轮是除计数器值外相同)。第八轮之后的不寻常结构(和在第24轮之后)是简化两个连续的XOR操作的结果在规则A和规则B之间的边界。
3 24圈概率为零的微分
我们专注于24轮的Skipjack，从第5轮开始，最后结束。在第28轮(即没有前四轮和最后四轮)。为为了清晰起见，我们使用了完整Skipjack的原始整数，即，从5到28，而不是从1到24。给出了只在第五轮输入的第二个词，即形式不同(0，a，0，0)，第28轮后的差额不能为任何非零的形式(b，0，0，0)。a和b.
这种微分具有零概率的原因可以解释为概率为1的两个12轮微分的中间组合中的遗漏：正如瓦格纳在[17]中所观察到的，第五轮的第二个输入词不影响第四字后第16轮，并给出一个输入差(0，a，0，0)的差。在12轮之后，对于一些非零的c，d，e，和e的形式是(c，d，e，0).在另一方面，我们可以从第16轮之后的产出差异来预测数据。第28轮，即考虑向后方向的微分。类似对于带概率1的12轮微分，有一个向后的12轮。与概率1的微分。它在第28轮之后有差(b，0，0，0)，它预测第16轮后的数据必须是形式(f，g，0，h)。对于一些非零的f，g，h，结合这两个微分，我们得出了第4轮后有差(0，a，0，0)和差(b，0，0，0)的任何对。后第28轮必须有形式的差异(c，d，e，0)=(f，g，0，h)后对于一些非零的c，d，e，f，g和h，作为e和h是非零的，我们得到一个矛盾，这样就不可能有这样的差异。第4轮和第28轮。
这种差异的一个应用可能是区分加密黑匣子是24轮Skipjack(从第5轮到第28轮)，还是随机排列。标识只需要给黑匣子提供2 48对alpha;。(对于某些alpha;)与表单(0，a，0，0)有差异，并验证输出差异是否为表单(b，0，0，0)。如果对于某些对，输出差是形式(b，0，0，0)，则黑匣子肯定不会应用这个Skipjack变体。另一方面，如果黑匣子实现随机排列，则只有eminus;alpha;的概率，即2 48个alpha;对中没有一个有差异(b，0，0，0，0)。例如，给定2 52对，被错误识别为Skipjack变体的黑匣子的概率仅为eminus;16asymp;10minus;7。这对黑匣子可以使用组成2 31对的2 16条明文的结构进行有效包装。在这些结构中，所有明文都是相等的，除了第二个单词，它的范围超过所有可能的216个值。使用这些结构，仅需2 33alpha;加密就可获得相同的区别结果。
4 对Skipjack的攻击减少到25-26发
在本节中，我们描述了Skipjack变体的最简单的密码分析，只有一到两个回合(在24轮不可能差分本身之上)。从第5轮到第29轮，对25轮Skipjack的攻击如下所示。选择只有第二个单词不同的216个明文的结构，其中包含所有可能的值。这些结构提出了约2 31对明文。给定222个这类结构(238个明文)，收集所有仅在密文前两个单词上不同的对；按跳过第28轮后，只有这些对可能是与之不同的对(b，0，0，0)产生的。平均来说，只有一半的结构提出这样的对，因此只有大约2对21对。用(C1，C2，C3，C4)和(Clowast;1，Clowast;2，C3，C4)表示该对的密文。只有当最后一轮G置换的C1和Clowast;1的解密值相差C2=C2oplus;Clowast;2时，该对在最后一轮前的形式(b，0，0，0)可能有差异。正如我们所知，这样的差别是不可能的，每一个提出这种差别的关键都是错误的。对于每一对，我们尝试上一轮的子项的所有232个可能的值，并验证。由最后G置换解密的值是否有c 02的差异(这个过程可以在大约2 16步中有效地完成)。预计大约有216个值提出了这一差异，因此我们可以保证[2]16值不是上一轮的正确子项。在对2 2 1对进行分析后，仅剩下2 32·(1minus;2minus;16)2 2 1=2 32·eminus;32asymp;2minus;14的上一轮子键错误值。因此，预计只保留一个值，并且该值必须是正确的子键。恢复这个32位子键的时间复杂度约为2.17·2.21=2.38G置换计算。由于每个加密包含大约2 5个G的应用程序，因此这个时间复杂度相当于大约233个加密。的直接实现攻击需要一个2 32位的数组来保存已经识别的错误密钥的信息。更有效的实现平均只需要2 32 G计算，即大约2 27加密，使用2 16位的记忆。
本质上，同样的攻击对第4轮到第29轮的26轮变体有效.在这个变体中，第一轮和最后一轮使用相同的子项。攻击方式如下：选择2 32条明文中的2 6种结构，其中只有不同之处。在前两个单词中，得到这两个单词的所有232个值。找到只在密文的前两个单词中不同的对。预计约为2 6·2 6 3/2 32=2 37对。这些对平均提出一个错误的子键值，因此，在对所有对进行分析后，只有正确的第一个/最后一个子键保留的概率很高。这种攻击的时间复杂度是2 48，使用的是2 16位的数组。其余的关键位可以通过对2 48个键的彻底搜索或更有效的辅助技术来找到。
5. Skipjack密码分析减少到31轮
对于Skipjack的密码分析，我们再次使用了24轮不可能的差分。我们首先分析由前31轮Skipjack组成的变体，然后分析由Skipjack最后31轮组成的变体。
在我们描述攻击的全部细节之前，我们要强调几个微妙的问题。我们观察到，在前四轮(差异之前)使用完整的80位键，在最后三轮(后)也使用完整的80位键。差异)。因此，关键消除过程应该丢弃80位。候选钥匙。假设对280个密钥中的每一个进行验证的费用为至少一个G计算，而作为一个G计算大约快31倍超过一次加密，我们最终得到的攻击的时间复杂度至少是2 80/31asymp;2 75加密。这个下限仅略小于穷尽搜索，因此攻击不会超过几个G操作验证每个密钥，并且不能尝试每个密钥超过几次。
接下来我们观察到，如果不可能的微分在某些对中成立，那么明文第三词和密文第三、第四词有零的差异，而另一个词有非零的差异。给出与这样的差异成对，假设微分成立，我们得到三个16位限制在第1，4和29轮。因此，我们认为在2minus;48密钥中，大约有2 32密钥将明文对加密到输入。第4轮后差分的差异，并将密文对解密到第29轮前差速器的输出差。一旦确认，这些密钥都被丢弃了。这2 32键必须以不高于2 32键的复杂度丢弃。[32]正如我们前面提到的。因此，我们不能尝试每对的所有280个键，相反，我们设计了一种有效的算法来计算2 32键。
因此，攻击的一般结构如下：我们生成一个大的选择明文结构，并选择满足所需差异的对。我们分析这些对，每一个丢弃大约2个32个键。经2对48对分析，约2～80（不一定区别）。密钥被丢弃。我们预计，由于碰撞，约1 / E的密钥仍然不丢弃。额外的对的分析减少了未丢弃的密钥的数量，直到大约2个48 LN2 80times;2 48·2 6对之后，只有正确的密钥仍然存在。然而，这种攻击的复杂性高于穷举搜索的复杂性。
因此，我们只分析了2 49对，留下约2 80/e 2asymp;2 77键波动-经过梳理，然后尝试其余的钥匙穷尽。我们强调分析丢弃导致有效部分加密和解密的密钥。配对以匹配不可能的微分的形式。因此，我们假设在攻击由不可能的差别所提出的分歧确实成立，和丢弃确认此错误假设的所有键。
我们现在准备描述这次袭击。我们选择第三个单词相等的241个明文。给定密文，我们根据它们的第三个和第四个单词对它们进行排序(或散列)，并选择在这些单词上碰撞的对。预计约(2 41)2/22 32=2 49对。
每个选定的对都经过以下四个阶段的分析。在第一阶段，我们分析了第一轮。我们知道G置换的两个输入，以及它的输出差。这个G置换由32位键组成，大约有216个可能的子键导致预期的差异。这可以通过猜测子键的前两个字节，并通过差分密码分析技术计算另外两个字节，在2 16步内完成。由于第一轮和最后一轮的子键是相同的，我们可以为每个可能的子键剥离最后一轮。
然后我们分析第4轮。我们知道第四轮G置换的输入和输出的差异。由于G置换的互补性质[4]1，我们可以假定输入被固定在任意一对值上，并找到了约2 16个对应于这些值的候选子键。这一分析的复杂性为2 16。然后，我们可以使用互补属性完成所有可能的输入和子键组合。第29轮的分析类似。我们现在观察到，在第4轮和第29轮中使用了相同的子键。第4轮和第29轮可能的子键通过使用互补属性有效地保持，因此我们不能直接保留。搜索两个相等的子键值。相反，我们观察到前两个子键字节与另外两个子键字节的XOR值是独立于互补的，我们使用这个XOR值作为公共值，用于连接两个回合的两个子键列表。通过适当的互补，我们得到了一个约有216元组的子键、第4轮的输入和第29轮的输出的列表。这一分析的复杂性约为2 16步。这个列表仍然可以受互补属性的约束，从而得到所有(约为2.32)可能的组合。
第三阶段将这两个列表连接成大约232个表格条目(cv 0，hellip;，cv 5，x3，x30)，其中cv 0
全文共10726字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11726]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
