设为首页 加入收藏

1. 引言

文献[1]设计了一种AES候选算法，该算法被学术界用文献[1]作者的名字命名为Crypton算法。该算法中密码采用分组长度为128 bit，密钥长度可变且最多为256 bit的SPN型结构。文献[1]指出，Crypton对差分密码分析和线性密码分析是安全的，但是其密钥扩展算法相对比较简单。文献[2]对其进行了改进，得到Crypton v1.0。由于Crypton具有加密过程严格一致、结构高度灵活、并且可并行运算等特点，使其倍受密码分析者的关注。目前人们所做的工作主要有：H’Halluin等在FSE1999上提出了对6轮Crypton算法修正的Square攻击^[3]，2009年王兵等分别对5，6轮的Crypton算法实施了新的积分攻击^[4]，2010年Mala等找到了Crypton算法的4轮不可能差分，给出了7轮算法的两个攻击^[5]，2011年魏悦川等构造了一系列6轮相关密钥不可能差分，并提出了对9轮Crypton算法的两个攻击^[6]。

中间相遇攻击由Dilfie和Hellman针对Two-DES分析时提出的一种时空折中的攻击方法^[7]，其实质是用存储复杂度来换取时间复杂度。与其他的分析方法相比，在攻击相同轮数的情况下，该方法所需的数据量相对较少。其基本思想是：首先找到一种区分器，然后猜测相应的密钥对特定的明文和密文分别向下加密和向上解密若干轮，最后与区分器的首尾相接，构成完整的攻击线路。如果上述对接能够成功，则说明猜测的密钥是正确的，需要保留，否则是错误的，于是将其淘汰。由此可知当所有的错误密钥都被淘汰后，剩下的密钥即为正确密钥。这种方法尽管有大量的预计算复杂度和存储复杂度，但预计算只需进行一次，而且可以降低攻击时的时间复杂度，所以还是比较有效的。截止到目前，这种方法已被广泛应用于许多分组密码的分析中，如见文献[8-11]。

中间相遇攻击中的“多重集”^[12]概念最初是由Dunkelman和Shamir在分析AES时引入的，后来文献[13]又将其引入到了与AES有着相似结构的ARIA算法的分析中。

本文将借助多重集的概念，研究Crypton算法抵抗中间相遇攻击的能力。通过对Crypton算法的结构特点的分析，设计出该算法的两类4/5轮区分器，并用于分别对7/8/9轮的Crypton实施攻击。

2. 预备知识：Crypton算法简介

Crypton密码采用SPN结构，标准加密轮数为12轮。它的分组长度为128 bit，密钥长度可变且最多为256 bit。对于128 bit的分组数据可表示为

 

Crypton密码的轮函数由4种变换组成：

1) 字节代替变换：将数据每一字节操作非线性变换(S盒)，其中和分别作用于奇数轮和偶数轮。

2) 列混合变换：将状态矩阵中的每一列分别与已知字节作用。其中用于奇数轮的定义为，用于偶数轮的定义为。这里，，，。而且容易验证矩阵和都是自逆的，即，。

3) 字节对称变换：将在位置上的字节变换到位置，即，明显地有。

4) 轮密钥加变换：将128比特的轮密钥直接与数据按比特位异或。

令为第i轮的轮密钥，它是通过主密钥K经过密钥扩展算法得到的，于是完整的Crypton算法可描述为：。

其中奇数轮：，偶数轮：，而线性变换为作用在最后一轮之后的末变换，当最后一轮为奇数轮时，相应的变换定义为。

另外，在一些情况下，可以将轮函数写成其等价形式，，相应地密钥K也替换为等价密钥，其中。由于密钥扩展算法和S盒具体的构造与本文分析无关，可将两个版本的算法Crypton和Crypton v1.0统称为Crypton。

3. Crypton多重集与区分器的设计

本节利用Crypton算法的结构特点，首先给出Crypton的4/5轮多重集，然后设计相应的4/5轮中间相遇区分器。

3.1. Crypton的多重集

3.1.1. Crypton的4轮多重集

首先考虑集^[12]的第0字节为活跃字节时进行4轮加密的情况(其他位置的字节情况类似)。我们用分别表示经过运算后的中间输出状态。

今从低轮开始推导。在第u轮时，差分是已知的，因为这些正是第0字节的256种可能的差分值(其他15个字节都相等，没有差分)。我们只关心多重集而不关心差分顺序。由于、和都是线性变换，所以经过上面的操作就得到了差分的值。由于集的活跃字节是第0字节，所以上述差分的活跃字节为，其他字节均为非活跃的。

把的0, 1, 2, 3字节值作为参数的一部分，可以得到的0, 1, 2, 3各字节的值，当然也得到了的0, 1, 2, 3字节值。又差分除了0, 1, 2, 3之外的字节全为零，并且，所以可推得的值。

由于变换的线性，所以知道了差分也就知道了差分。如果把的16字节值作为变量的一部分给出，就可以得到的值。

然后由状态 (经过变换作用后)和变量的0, 4, 8, 12的4个字节值，可以得到的0, 4, 8, 12字节的值，通过变换，就得到的第0个字节值，也就得到了差分的值。

综上可得多重集它完全由以下24个字节变量决定：

• 状态的4个字节(当集的活跃字节是第0个字节时，则这4字节即为0, 1, 2, 3)；

• 状态的全部16个字节；

• 轮密钥的4个字节(这4个字节分别为0, 4, 8, 12)，而且最多有2¹⁹²种可能的取值。不过，由于有256种可能选择，每个集对应2⁸个多重集，因此可以通过选择使得，来使变量字节数降为23个(这是可能的，由于状态的第0字节是活跃字节)。这就把可能的多重集数量降到了。

本文中使用多重集，取，，对应的集为。

3.1.2. Crypton的5轮多重集

考虑对集进行5轮加密的情况。对每个，(无序)的多重集完全由以下40个字节变量决定：

• 状态的4个字节(当集的活跃字节是第0个字节时，则这4字节即为0, 1, 2, 3)；

• 状态的全部16个字节；

• 状态的所有16个字节；

• 轮密钥的4个字节(这4字节分别为0, 4, 8, 12)。

分析过程与4轮多重集类似。此外，这一多重集最多只有2³¹²个值。本文使用多重集，取，，对应的集为。

3.2. Crypton基于多重集的区分器

3.2.1. Crypton基于多重集的4轮区分器

区分器1

若集的活跃字节是第0字节，用4轮Crypton加密集，则(无序)的多重集完全由以下24个字节变量决定：

• 状态的4个字节(当集的活跃字节是第0个字节时，则这4个字节即为0, 1, 2, 3)；

• 状态的全部16个字节；

• 轮密钥的4个字节(这4个字节分别为0, 4, 8, 12)。

由此可知，多重集完全由184字节变量决定。这一多重集共有2¹⁸⁴个可能值，所以如果密钥的猜测值使得对应的多重集产生了上述的2¹⁸⁴个值中的一个值，那么猜测的这个密钥就很有可能是正确密钥。

3.2.2. Crypton基于多重集的5轮区分器

区分器2

若集的活跃字节是第0字节，用5轮Crypton加密集，则(无序)的多重集完全由以下40个字节变量决定：

• 状态的4个字节(当集的活跃字节是第0个字节时，则这4个字节即为0, 1, 2, 3)；

• 状态的全部16个字节；

• 状态的所有16个字节；

• 轮密钥的4个字节(这4个字节分别为0, 4, 8, 12)。

同样地，由上可知多重集完全由312字节变量决定。这一多重集共有2³¹²个可能值，所以如果密钥的猜测值使得对应的多重集产生了上述的2³¹²个值中的一个值，那么猜测的这个密钥就很有可能是正确密钥。

3.2.3. Crypton基于多重集的改进的5轮区分器

区分器3

在区分器2的基础上，我们令变量中几个字节取相同的值以便减少变量个数，从而降低预计算复杂度，使攻击9轮的Crypton成为可能。但这样做也降低了区分器的成功率，而且增加了选择明文数量。

方案一：选择

,此时的概率为

方案二：选择

,此时的概率为

这时，多重集就完全由29或31字节变量决定了。此外，多重集最多有2²²⁴或2²⁴⁰个可能值。因此，如果密钥的猜测值使对应的多重集取到上述2²²⁴或2²⁴⁰个值中的一个，那么这一猜测的密钥则就很有可能为正确密钥。

4. 对7/8/9轮Crypton的中间相遇攻击

4.1. 对7轮Crypton的中间相遇攻击

首先定义一个明文结构，它是由2³²个在4字节(0, 4, 8, 12)处取固定值的组成的集合。我们利用区分器1对7轮的Crypton实施中间相遇攻击：在4轮区分器的前边添1轮，后边添2轮，构成7轮攻击线路，如图1所示。在这一攻击中，首先预计算上述区分器中用到的多重集的所有可能值，把它们存储到一个哈希表T中。然后选择并加密足量的合乎条件的明文集。

搜索特定的密钥字节，对密文进行部分解密，来获得多重集，并检测由解密所得多重集是否在预计算时生成的哈希表中。如果是，则很有可能是正确密钥。

4.1.1. 7轮攻击过程

步骤1 预计算阶段

计算由区分器1定义的4轮多重集的2¹⁸⁴个可能值，并存储在一个哈希表中。

步骤2 在线阶段

由第2部分的分析可知，分别交换第6轮的轮密钥加与列混合变换、字节对称变换的复合变换，及第7轮的轮密钥加与列混合变换、字节对称变换的复合变换的顺序，即可以得到是的等价密钥，是的等价密钥。

步骤2.1. 猜测的1字节(0)值以及的4个字节(0, 4, 8, 12)值。对的256个可能值，我们令。他们组成了-集。我们通过把代入下面状态，得到对应的的值。

其中

其他所有p_i(除0, 4, 8, 12字节位置外)均为常量字节，并且不同的位置不一定相等。

步骤2.2. 猜测第0字节值及4字节(0, 1, 2, 3)值。部分解密对应的密文，得到多重集。

步骤2.3. 检查多重集是否存在于预计算生成的哈希表中。如果没有，就舍弃这一组密钥猜测值。由于一组错误密钥的匹配概率接近，而且猜测的轮密钥一共有个。因此，一旦有一个密钥猜测值能保留下来，则认为它是正确密钥。

步骤2.4. 剩余的密钥字节可以通过穷搜索的方法得到。

4.1.2. 7轮攻击的复杂度分析

7轮攻击所需的数据复杂度为选择明文。预计算的复杂度约为次7轮加密运算(计算一个多重集的复杂度相当于轮加密运算)。完成步骤2.1需要一轮加密运算；在步骤2.2中，为了得到的值，只需知道的第0字节即可。而要得到，需要计算的4个字节。所以这一步需要

一轮运算。因此，总的时间复杂度为次7轮Crypton加密运算。

4.2. 对8轮Crypton的中间相遇攻击

在7轮的基础上，后面再添1轮，构成8轮攻击路径，其攻击的结构类似于图1。不同的是，8轮攻击时还需要猜测K₈全部的16字节值，分析过程也相似。这里只给出8轮攻击复杂度的分析结果。

8轮攻击所需的数据复杂度为选择明文。预计算的复杂度接近次8轮加密运算。总的时间复杂度约为次8轮Crypton加密运算。

4.3. 对9轮Crypton的中间相遇攻击

本节利用区分器3来实施9轮Crypton的中间相遇攻击。在5轮区分器的前面添1轮，后面添3轮，从而构成9轮攻击路径，其攻击结构与类似于7，8轮的攻击，分析过程也相似。

4.3.1. 9轮攻击过程

方案一：

步骤1 预计算阶段

计算由区分器3定义的“特殊”多重集的2²²⁴个可能值，并存储在一个哈希表中。

步骤2 在线阶段

由第2部分的分析可知，分别交换第7轮的轮密钥加K₇与列混合变换、字节对称变换的复合变换，及第8轮的轮密钥加K₈与列混合变换、字节对称变换的复合变换的顺序，即可以得到是K₇的等价密钥，是K₈的等价密钥。

步骤2.1. 选择2⁸⁸个含有2³²个与7轮攻击定义相同的明文结构，并加密这2¹²⁰个明文。

步骤2.2. 同7轮攻击的步骤2.1。

步骤2.3. 猜测第0字节值，第4字节(0, 1, 2, 3)值以及K₉所有16字节值，并部分解密对应的密文，得到多重

。

步骤2.4. 检查多重集的值是否在哈希表中出现。如果没有，就删除对应的密钥猜测值。如果在表中，

图1. 7轮Crypton的中间相遇攻击

则猜测的密钥很可能为正确密钥。原因同7轮攻击。

步骤2.5. 剩余密钥字节可以通过穷搜索的方法得到。

方案二：

步骤1 预计算阶段

计算由区分器3定义的“特殊”多重集的2²⁴⁰个可能值，并存储在一个哈希表中。

步骤2 在线阶段

步骤2.1. 选择2⁷²个含有2³²个上述明文结构[同方案一]，并加密这2¹⁰⁴个明文。

步骤2.2.，2.3.，2.4.，2.5.同方案一。

4.3.2. 9轮攻击的复杂度分析

方案一：9轮攻击所需的数据复杂度为2¹²⁰选择明文。预计算的复杂度接近次9轮加密运算(计算一个多重集的复杂度相当于轮加密运算)。步骤2.1需要2¹²⁰次9轮Crypton加密；步骤2.2需要一轮加密运算；步骤2.3需要

一轮加密运算，所以总的时间复杂度为次9轮Crypton加密运算。

方案二：9轮攻击所需的数据复杂度为2¹⁰⁴选择明文。预计算的复杂度接近次9轮加密运算(计算一个多重集的复杂度相当于轮加密运算)。步骤2.1需要2¹⁰⁴次9轮Crypton加密；步骤2.2需要一轮加密运算；步骤2.3需要

一轮加密运算，所以总的时间复杂度为次9轮Crypton加密运算。

表1给出了本文对Crypton算法实施中间相遇攻击及利用其他方法分析时所得的比较结果。通过对比发现：在攻击相同轮数的情况下，中间相遇攻击的计

表1. Crypton算法的分析结果比较

算量有所增加，但有效地降低了攻击所需的数据复杂度。

5. 结束语

本文利用中间相遇攻击的方法，并借助多重集的概念，首次评估了Crypton算法对中间相遇攻击的抵抗能力。通过对Crypton算法的结构进行分析，构造出该算法的两类4/5轮区分器，并由此给出了针对7/8/9轮Crypton的中间相遇攻击。表1给出了一些针对Crypton算法的攻击结果。结果显示9轮的Crypton算法对中间相遇攻击是不免疫的，同现有密码分析方法相比，在攻击相同轮数的情况下，中间相遇攻击的计算量有所增加，但有效地降低了攻击所需的数据复杂度。

参考文献 (References)

[1]       C. Lim. Crypton: A new 128-bit block cipher. The First Advanced Encryption Standard Candidate Conference, 1998.

[2]       C. Lim. A revised version of crypton-crypton v1.0. Rome: Proceedings of Conference on Fast Software Encryption. Berlin: Springer-Verlag, 1999: 31-45.

[3]       G. D’Halluin, G. Bijnens, V. Rijmen, et al. Attack on six rounds of crypton. Rome: Proceedings of Conference on Fast Software Encryption. Berlin: Springer-Verlag, 1999: 46-59.

[4]       H. R. Wei, B. Wang. Integral cryptanalysis of reduced-round crypton block cipher. International Symposium on Computer Network and Multimedia Technology, 2009, 2: 792-795.

[5]       H. Mala, M. Shakiba and M. Dakhilalian. New impossible differential attacks on reduced-round crypton. Computer Standards & Interfaces, 2010, 32(4): 222-227.

[6]       Y. C. Wei, C. Li and B. Sun. Related-key impossible differential cryptanalysis on crypton and crypton v1.0. Xi’ an: IEEE International Conference on Signal Processing, Communications and Computing, 2011: 227-232.

[7]       H. Diffie, M. Hellman. Exhaustive cryptanalysis of the NBS data encryption standard. IEEE Computer, 1977, 10(6):74-84.

[8]       H. Demirci, H. Selcuk. A meet-in-the-middle attack on 8-round AES. Lausanne: Proceedings of Conference on Fast Software Encryption. Springer-Verlag, 2008: 116-126.

[9]       唐学海, 孙兵, 李超. 对8轮CLEFIA算法的一种现实攻击[J]. 电子学报, 2011, 39(7): 1608-1612.

[10]    苏崇茂, 韦永壮, 马春波. 10轮3D分组密码算法的中间相遇攻击[J]. 电子与信息学报, 2012, 34(3): 694-697.

[11]    海昕, 唐学海, 李超. 对Zodiac算法的中间相遇攻击[J]. 电子与信息学报, 2012, 34(9): 2259-2262.

[12]    O. Dunkelman, N. Keller and A. Shanmir. Improved single-key attack on 8-round AES-192 and AES-256. Singapore: Proceedings of Conference on Theory and Application of Cryptology and Information Security, 2010: 158-176.

[13]    杜承航. 分组密码算法ARIA的不可能差分分析和中间相遇攻击[D]. 山东大学, 2011.

NOTES

^*资助信息：内蒙古自治区科技创新引导奖励资金项目(2012)；国家自然科学基金项目(61174209)；信息安全国家重点实验室2011年开放课题(02-04-3)。