PRINCE密码算法的差分−线性分析

刘正斌

PRINCE密码算法的差分−线性分析

刘正斌

（保密通信重点实验室，四川 成都 610041）

PRINCE是一个低时延轻量级分组密码算法，广泛应用于各种资源受限设备。PRINCE使用FX结构，其核心部件是PRINCEcore。差分−线性分析是一种经典分析方法，它将差分分析和线性分析结合起来，使用短的高概率差分特征和线性特征来攻击密码算法。研究了PRINCEcore的差分−线性分析，使用2轮差分−线性区分器攻击4轮PRINCEcore，需要26个选择明文，时间复杂度为214.58次4轮加密。对于6轮和7轮PRINCEcore的差分−线性分析，数据复杂度分别为212.84和229.02个选择明文，时间复杂度分别为225.58和241.53。

轻量级分组密码；PRINCE；差分−线性分析

1 引言

PRINCE算法[1]是Borgho等在ASIACRYPT2012年会上提出的轻量级分组密码，它具有非常低的硬件实现代价，可以广泛应用于各种资源受限环境。PRINCE算法的重要特性是时延非常低，它能够在一个时钟周期内完成一次加密或解密运算，是专门为低时延应用而设计的分组密码。

PRINCE算法采用FX结构[2]，由一个核心算法PRINCEcore和两个白化密钥组成，其安全性主要依赖于PRINCEcore的安全性。PRINCEcore是一个SPN型分组密码，它采用对称结构，具有加解密相似性，将加密密钥异或常数α，使用该密钥进行加密即可实现解密过程（α反射性质）。

自PRINCE算法被提出以后，其就受到了密码学界和工业界的广泛关注，目前学术界发表了许多分析PRINCE算法安全性的文章。在FSE 2013年会上，Jean等[3]首次给出了对PRINCE算法的第三方分析结果，他们提出了对约减轮数的PRINCE版本的积分攻击以及对PRINCE全轮的相关密钥攻击和时间−存储−数据折中攻击。2013年，Soleimany等[4]研究了PRINCE的α反射性质，以及α的取值对PRINCE安全性的影响，对于某些特定的α值，他们提出了对PRINCE全轮的密钥恢复攻击。在CRYPTO 2013年会上，Canteaut等[5]使用Sieve-in-the-Middle技术攻击了8轮PRINCE。在FSE 2014年会上，Canteaut等[6]利用多差分分析方法攻击了10轮PRINCE，他们同时研究了PRINCE算法族中S盒的选择对于安全性的影响。在FSE 2015年会上，Derbez等[7]使用中间相遇攻击分析10轮PRINCE。

虽然理论分析能够加深人们对于PRINCE算法的安全性和设计原理的理解，但来自工业界的研究人员和工程师更关注PRINCE的实际攻击。为了鼓励密码学者对PRINCE算法开展实际攻击，算法设计者在2014年发起了PRINCE挑战[8]（PRINCE challenge），该挑战共包含3轮，第三轮评估在2016年结束。PRINCE挑战提供了两种场景：选择明文和已知明文。选择明文场景提供220个选择明/密文，已知明文场景提供230个已知明文，要求分析者使用尽可能少的选择或已知明文对算法进行攻击。对于每一种场景，根据攻击的轮数，设计者分别设置了5项挑战，最终的分析结果公布在其网站上[8]。

本文研究PRINCE算法在差分−线性攻击模型下的安全性，给出了对4轮、6轮和7轮PRINCEcore的实际攻击，攻击的数据复杂度分别为26、212.84和229.02，时间复杂度分别为214.58、225.58和241.53。本文的分析结果与公开文献的对比如表1所示[9-14]。

2 差分−线性分析

差分分析和线性分析是两种最有效的密码分析技术，它们给出了许多分组密码目前已知的最优分析结果。因此，抵抗差分分析和线性分析已经成为分组密码的一个基本设计准则。

差分分析是Biham和Shamir[15]在1990年提出的一种分析方法，它研究一个特定的明文差分在整个加密过程中的传播特性。差分分析使用一条高概率的差分（或差分特征）将分组密码和随机置换区分开，并在此基础上进行密钥恢复。差分概率的定义如下。

线性分析是Matsui[16]在1993年的欧洲密码学年会上提出的，它研究一组明文比特和密文比特之间的线性近似关系。线性分析使用一条高偏差的线性近似来区分分组密码和随机置换，并在此基础上恢复密钥。线性近似的偏差定义如下。

差分分析和线性分析成功的关键是寻找一条长的高概率的差分（差分特征）和高偏差的线性近似（线性特征），因此，只要保证分组密码中不存在这种长的差分和线性近似，就能保证其抵抗差分分析和线性分析。在很多情况下，短的差分和线性近似仍然可以用于攻击分组密码。

表1 PRINCEcore的分析结果比较

Bar-on等[24]研究了差分−线性分析中两个子密码之间的依赖性对于分析结果的影响，并提出了一个新的分析工具：差分−线性连接表（DLCT，differential-linear connectivity table）。DLCT考虑了两个子密码之间的依赖性，这使差分−线性分析的效率更高、应用范围更广。

3 PRINCE密码算法简介

（1）S盒层

S盒层使用16个完全相同的4 bit S盒，S盒的变换过程如表2所示。

（2）变换矩阵

其中

（3）行移位SR

图1 PRINCE的结构

表2 PRINCE的S盒

（4）轮常数加ARC

（5）轮密钥加ARK

4 PRINCE算法的差分−线性分析

对PRINCE进行差分−线性分析，首先需要构造S盒的差分分布表和线性近似表，然后寻找高概率的差分特征和高偏差的线性特征，通过DLCT将差分特征和线性特征连接起来，得到差分−线性区分器。S盒的差分分布表和线性近似表分别如表3和表4所示。

4.1 4轮PRINCEcore的差分−线性分析

攻击过程如下。

表3 PRINCE算法S盒的差分分布

表4 PRINCE算法S盒的线性近似表

（4）取值最大的计数器对应的部分密钥为正确候选密钥。通过构造其他列对应的差分−线性区分器，可以恢复剩余密钥。

图2 4轮PRINCEcore的差分−线性分析

4.2 6轮PRINCEcore的差分−线性分析

攻击过程如下。

（4）取值最大的计数器对应的部分密钥为正确候选密钥。通过构造其他列对应的差分−线性区分器，可以恢复剩余密钥。

图3 6轮PRINCEcore的差分−线性分析

4.3 7轮PRINCEcore的差分−线性分析

7轮PRINCEcore的差分−线性攻击过程与6轮类似，这里不再详细描述，下面给出复杂度分析。

图4 7轮PRINCEcore的差分-线性分析

5 实验结果

6 结束语

本文研究了PRINCE算法在差分−线性分析下的安全性，给出了4轮、6轮和7轮PRINCEcore的差分−线性攻击。使用2轮差分−线性区分器，可以攻击4轮和6轮PRINCEcore，其数据复杂度分别为26和212.84个选择明文，时间复杂度分别为212.59和225.58次4轮和6轮加密，存储复杂度分别为212和216。7轮PRINCEcore的差分−线性攻击需要使用3轮区分器，攻击的数据复杂度为229.2个选择明文，数据复杂度为241.53次7轮加密，存储复杂度为216。通过本文分析可知，差分−线性分析对于低轮数的PRINCEcore非常有效，攻击的复杂度非常低，是一种实际的安全威胁。如何扩展差分−线性分析的攻击轮数，是下一步要研究的问题。

[1] BORGHO J, CANTEAUT A, GÜNEYSU T, et al. PRINCE: a low-latency block cipher for pervasive computing applications[C]//ASIACRYPT 2012. 2012: 208-225.

[2] KILIAN J, ROGAWAY P. How to protect DES against exhaustive key search (an analysis of DESX)[J]. Journal of Cryptology, 2021. 14(1): 17-35.

[3] JEAN J, NIKOLIC I, PEYRIN T, et al. Security analysis of PRINCE[C]//International Workshop on Fast Software Encryption (FSE) 2013. 2013: 92-111.

[4] SOLEIMANY H, BLONDEAU C, YU X L, et al. Refection cryptanalysis of PRINCE-like ciphers[C]//International Workshop on Fast Software Encryption (FSE) 2013. 2013: 71-91.

[5] CANTEAUT A, NAYA-PLASENCIA M, VAYSSIERE B. Sieve-in- the-middle improved MITM attacks[C]//Advances in Cryptology - CRYPTO. 2013: 222-240.

[6] CANTEAUT A, FUHR T, GILBERT H, et al. Multiple differential cryptanalysis of round-reduced PRINCE[C]//International Workshop on Fast Software Encryption (FSE). 2014: 591-610.

[7] DERBEZ P, PERRIN L. Meet-in-the-middle attacks and structural analysis of round-reduced PRINCE[C]//International Workshop on Fast Software Encryption(FSE). 2014: 190-216.

[8] THE PRINCE TEAM. PRINCE challenge[R].

[9] 段春晖, 谭林, 戚文峰. 减轮PRINCE的混合差分分析[J].信息工程大学学报, 2019, 20(6): 695-701.

DUAN C H, TAN L, QI W F. Mixture differential cryptanalysis on round-reduced PRINCE[J]. Journal of Information Engineering University, 2019, 20(6): 695-701.

[10] ABED F, LIST E, LUCKS S. On the security of the core of prince against Biclique and differential cryptanalysis[R]. 2012.

[11] ZHAO G Y, SUN B, LI C, et al. Truncated differential cryptanalysis of PRINCE[J]. Security and Communication Networks, 2015(8): 2875-2887.

[12] LI L B, JIA K T, WANG X Y. Improved meet-in-the-middle attacks on AES-192 and PRINCE[R].

[13] 魏悦川, 潘晓中, 戎宜生, 等. 对PRINCE分组密码的不可能差分攻击[J]. 西安电子科技大学学报, 2017, 44(1): 119-124.

WEI Y C, PAN X Z, RONG Y S, et al. Impossible differential cryptanalysis on the PRINCE[J]. Journal of Xidian University, 2017, 44(1): 119-124.

[14] 袁征, 彭真. 轻量级分组密码PRINCE算法的Biclique分析[J].密码学报, 2017, 4(6): 517-527.

YUAN Z, PENG Z. Biclique cryptanalysis of lightweight block cipher PRINCE[J]. Journal of Cryptologic Research, 2017, 4(6): 517-527.

[15] BIHAM E, SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[J].Journal of Cryptology, 1991, 4(1): 3-72.

[16] MATSUI M. Linear cryptanalystis method for DES cipher[C]//Advances in Cryptology-Proceedings of EUROCRYPT '93. 1993: 386-397.

[17] LANGFORD S K, HELLMAN M E. Differential-linear Cryptanalysis[C]//Advances in Cryptology-proceedings of CRYPTO '94. 1994: 17-25.

[18] BIHAM E, DUNKELMAN O, KELLER N. Enhancing differential-linear cryptanalysis[C]//Advances in Cryptology-proceedings of ASIACRYPT 2002. 2002: 254-266.

[19] LIU Z Q, GU D W, ZHANG J, et al. Differential-multiple linear cryptanalysis[C]//Proceedings of Information Security and Cryptology (Inscrypt 2009). 2009: 35-49.

[20] LU J Q. A methodology for differential-linear cryptanalysis and its applications[J]. Des Codes Cryptography, 2015, 77(1): 11-48.

[21] BLONDEAU C, LEANDER G, NYBERG K. Differential-linear cryptanalysis revisited[J]. Journal of Cryptology, 2017, 30(3): 859-888.

[22] CHABAUD F, VAUDENAY S. Links between differential and linear cryptanalysis[C]//Advances in Cryptology-Proceedings of EUROCRYPT '94, 1994: 356-365.

[23] BLONDEAU C, NYBERG K. New links between differential and linear cryptanalysis[C]//Advances in Cryptology-Proceedings of EUROCRYPT 2013. 2013: 388-404.

[24] BAR-ON A, DUNKELMAN O, KELLER N, et al. DLCT: a new tool for differential-linear cryptanalysis[C]//EUROCRYPT 2019. 2019: 313-342.

Differential-linear cryptanalysis of PRINCE cipher

LIU Zhengbin

Science and Technology on Communication Security Laboratory, Chengdu 610041, China

PRINCE is a low-latency lightweight block cipher, which is widely used in a lot of resource constrained devices. It is based on the FX construction and the core component is PRINCEcore. Differential-linear cryptanalysis is a classical cryptographic technique, which combines differential cryptanalysis and linear cryptanalysis together. Short differential characteristics and linear characteristics with high-probability were concatenated to break the cipher. Differential-linear cryptanalysis were applied to attack PRINCEcore. Using 2-round differential-linear distinguisher, 4-round PRINCEcorecan be broken with 26chosen plaintext and 214.58encryption. For 6-round and 7-round PRINCEcore, the data complexity is 212.84and 229.02respectively, and the time complexity is 225.58and 241.53.

lightweight block cipher, PRINCE, differential-linear cryptanalysis

TP393

A

10.11959/j.issn.2096−109x.2021072

2020−12−16；

2021−05−18

刘正斌，zhengbinliu@126.com

国家重点研发计划（2017YFB0802000）

The National Key R&D Program of China (2017YFB0802000)

刘正斌. PRINCE密码算法的差分−线性分析[J]. 网络与信息安全学报, 2021, 7(4): 131-140.

LIU Z B. Differential-linear cryptanalysis of PRINCE cipher[J]. Chinese Journal of Network and Information Security, 2021, 7(4): 131-140.

刘正斌（1985− ），男，山东青岛人，保密通信重点实验室工程师，主要研究方向为密码学理论、对称密码分析。