PRINCE密碼算法的差分?線性分析

劉正斌

PRINCE密碼算法的差分?線性分析

劉正斌

（保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041）

PRINCE是一個(gè)低時(shí)延輕量級(jí)分組密碼算法，廣泛應(yīng)用于各種資源受限設(shè)備。PRINCE使用FX結(jié)構(gòu)，其核心部件是PRINCEcore。差分?線性分析是一種經(jīng)典分析方法，它將差分分析和線性分析結(jié)合起來(lái)，使用短的高概率差分特征和線性特征來(lái)攻擊密碼算法。研究了PRINCEcore的差分?線性分析，使用2輪差分?線性區(qū)分器攻擊4輪PRINCEcore，需要26個(gè)選擇明文，時(shí)間復(fù)雜度為214.58次4輪加密。對(duì)于6輪和7輪PRINCEcore的差分?線性分析，數(shù)據(jù)復(fù)雜度分別為212.84和229.02個(gè)選擇明文，時(shí)間復(fù)雜度分別為225.58和241.53。

輕量級(jí)分組密碼；PRINCE；差分?線性分析

1 引言

PRINCE算法[1]是Borgho等在ASIACRYPT2012年會(huì)上提出的輕量級(jí)分組密碼，它具有非常低的硬件實(shí)現(xiàn)代價(jià)，可以廣泛應(yīng)用于各種資源受限環(huán)境。PRINCE算法的重要特性是時(shí)延非常低，它能夠在一個(gè)時(shí)鐘周期內(nèi)完成一次加密或解密運(yùn)算，是專門為低時(shí)延應(yīng)用而設(shè)計(jì)的分組密碼。

PRINCE算法采用FX結(jié)構(gòu)[2]，由一個(gè)核心算法PRINCEcore和兩個(gè)白化密鑰組成，其安全性主要依賴于PRINCEcore的安全性。PRINCEcore是一個(gè)SPN型分組密碼，它采用對(duì)稱結(jié)構(gòu)，具有加解密相似性，將加密密鑰異或常數(shù)α，使用該密鑰進(jìn)行加密即可實(shí)現(xiàn)解密過(guò)程（α反射性質(zhì)）。

自PRINCE算法被提出以后，其就受到了密碼學(xué)界和工業(yè)界的廣泛關(guān)注，目前學(xué)術(shù)界發(fā)表了許多分析PRINCE算法安全性的文章。在FSE 2013年會(huì)上，Jean等[3]首次給出了對(duì)PRINCE算法的第三方分析結(jié)果，他們提出了對(duì)約減輪數(shù)的PRINCE版本的積分攻擊以及對(duì)PRINCE全輪的相關(guān)密鑰攻擊和時(shí)間?存儲(chǔ)?數(shù)據(jù)折中攻擊。2013年，Soleimany等[4]研究了PRINCE的α反射性質(zhì)，以及α的取值對(duì)PRINCE安全性的影響，對(duì)于某些特定的α值，他們提出了對(duì)PRINCE全輪的密鑰恢復(fù)攻擊。在CRYPTO 2013年會(huì)上，Canteaut等[5]使用Sieve-in-the-Middle技術(shù)攻擊了8輪PRINCE。在FSE 2014年會(huì)上，Canteaut等[6]利用多差分分析方法攻擊了10輪PRINCE，他們同時(shí)研究了PRINCE算法族中S盒的選擇對(duì)于安全性的影響。在FSE 2015年會(huì)上，Derbez等[7]使用中間相遇攻擊分析10輪PRINCE。

雖然理論分析能夠加深人們對(duì)于PRINCE算法的安全性和設(shè)計(jì)原理的理解，但來(lái)自工業(yè)界的研究人員和工程師更關(guān)注PRINCE的實(shí)際攻擊。為了鼓勵(lì)密碼學(xué)者對(duì)PRINCE算法開(kāi)展實(shí)際攻擊，算法設(shè)計(jì)者在2014年發(fā)起了PRINCE挑戰(zhàn)[8]（PRINCE challenge），該挑戰(zhàn)共包含3輪，第三輪評(píng)估在2016年結(jié)束。PRINCE挑戰(zhàn)提供了兩種場(chǎng)景：選擇明文和已知明文。選擇明文場(chǎng)景提供220個(gè)選擇明/密文，已知明文場(chǎng)景提供230個(gè)已知明文，要求分析者使用盡可能少的選擇或已知明文對(duì)算法進(jìn)行攻擊。對(duì)于每一種場(chǎng)景，根據(jù)攻擊的輪數(shù)，設(shè)計(jì)者分別設(shè)置了5項(xiàng)挑戰(zhàn)，最終的分析結(jié)果公布在其網(wǎng)站上[8]。

本文研究PRINCE算法在差分?線性攻擊模型下的安全性，給出了對(duì)4輪、6輪和7輪PRINCEcore的實(shí)際攻擊，攻擊的數(shù)據(jù)復(fù)雜度分別為26、212.84和229.02，時(shí)間復(fù)雜度分別為214.58、225.58和241.53。本文的分析結(jié)果與公開(kāi)文獻(xiàn)的對(duì)比如表1所示[9-14]。

2 差分?線性分析

差分分析和線性分析是兩種最有效的密碼分析技術(shù)，它們給出了許多分組密碼目前已知的最優(yōu)分析結(jié)果。因此，抵抗差分分析和線性分析已經(jīng)成為分組密碼的一個(gè)基本設(shè)計(jì)準(zhǔn)則。

差分分析是Biham和Shamir[15]在1990年提出的一種分析方法，它研究一個(gè)特定的明文差分在整個(gè)加密過(guò)程中的傳播特性。差分分析使用一條高概率的差分（或差分特征）將分組密碼和隨機(jī)置換區(qū)分開(kāi)，并在此基礎(chǔ)上進(jìn)行密鑰恢復(fù)。差分概率的定義如下。

線性分析是Matsui[16]在1993年的歐洲密碼學(xué)年會(huì)上提出的，它研究一組明文比特和密文比特之間的線性近似關(guān)系。線性分析使用一條高偏差的線性近似來(lái)區(qū)分分組密碼和隨機(jī)置換，并在此基礎(chǔ)上恢復(fù)密鑰。線性近似的偏差定義如下。

差分分析和線性分析成功的關(guān)鍵是尋找一條長(zhǎng)的高概率的差分（差分特征）和高偏差的線性近似（線性特征），因此，只要保證分組密碼中不存在這種長(zhǎng)的差分和線性近似，就能保證其抵抗差分分析和線性分析。在很多情況下，短的差分和線性近似仍然可以用于攻擊分組密碼。

表1 PRINCEcore的分析結(jié)果比較

Bar-on等[24]研究了差分?線性分析中兩個(gè)子密碼之間的依賴性對(duì)于分析結(jié)果的影響，并提出了一個(gè)新的分析工具：差分?線性連接表（DLCT，differential-linear connectivity table）。DLCT考慮了兩個(gè)子密碼之間的依賴性，這使差分?線性分析的效率更高、應(yīng)用范圍更廣。

3 PRINCE密碼算法簡(jiǎn)介

（1）S盒層

S盒層使用16個(gè)完全相同的4 bit S盒，S盒的變換過(guò)程如表2所示。

（2）變換矩陣

其中

（3）行移位SR

圖1 PRINCE的結(jié)構(gòu)

表2 PRINCE的S盒

（4）輪常數(shù)加ARC

（5）輪密鑰加ARK

4 PRINCE算法的差分?線性分析

對(duì)PRINCE進(jìn)行差分?線性分析，首先需要構(gòu)造S盒的差分分布表和線性近似表，然后尋找高概率的差分特征和高偏差的線性特征，通過(guò)DLCT將差分特征和線性特征連接起來(lái)，得到差分?線性區(qū)分器。S盒的差分分布表和線性近似表分別如表3和表4所示。

4.1 4輪PRINCEcore的差分?線性分析

攻擊過(guò)程如下。

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

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

（4）取值最大的計(jì)數(shù)器對(duì)應(yīng)的部分密鑰為正確候選密鑰。通過(guò)構(gòu)造其他列對(duì)應(yīng)的差分?線性區(qū)分器，可以恢復(fù)剩余密鑰。

圖2 4輪PRINCEcore的差分?線性分析

4.2 6輪PRINCEcore的差分?線性分析

攻擊過(guò)程如下。

（4）取值最大的計(jì)數(shù)器對(duì)應(yīng)的部分密鑰為正確候選密鑰。通過(guò)構(gòu)造其他列對(duì)應(yīng)的差分?線性區(qū)分器，可以恢復(fù)剩余密鑰。

圖3 6輪PRINCEcore的差分?線性分析

4.3 7輪PRINCEcore的差分?線性分析

7輪PRINCEcore的差分?線性攻擊過(guò)程與6輪類似，這里不再詳細(xì)描述，下面給出復(fù)雜度分析。

圖4 7輪PRINCEcore的差分-線性分析

5 實(shí)驗(yàn)結(jié)果

6 結(jié)束語(yǔ)

本文研究了PRINCE算法在差分?線性分析下的安全性，給出了4輪、6輪和7輪PRINCEcore的差分?線性攻擊。使用2輪差分?線性區(qū)分器，可以攻擊4輪和6輪PRINCEcore，其數(shù)據(jù)復(fù)雜度分別為26和212.84個(gè)選擇明文，時(shí)間復(fù)雜度分別為212.59和225.58次4輪和6輪加密，存儲(chǔ)復(fù)雜度分別為212和216。7輪PRINCEcore的差分?線性攻擊需要使用3輪區(qū)分器，攻擊的數(shù)據(jù)復(fù)雜度為229.2個(gè)選擇明文，數(shù)據(jù)復(fù)雜度為241.53次7輪加密，存儲(chǔ)復(fù)雜度為216。通過(guò)本文分析可知，差分?線性分析對(duì)于低輪數(shù)的PRINCEcore非常有效，攻擊的復(fù)雜度非常低，是一種實(shí)際的安全威脅。如何擴(kuò)展差分?線性分析的攻擊輪數(shù)，是下一步要研究的問(wèn)題。

[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].信息工程大學(xué)學(xué)報(bào), 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] 魏悅川, 潘曉中, 戎宜生, 等. 對(duì)PRINCE分組密碼的不可能差分攻擊[J]. 西安電子科技大學(xué)學(xué)報(bào), 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] 袁征, 彭真. 輕量級(jí)分組密碼PRINCE算法的Biclique分析[J].密碼學(xué)報(bào), 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

國(guó)家重點(diǎn)研發(fā)計(jì)劃（2017YFB0802000）

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

劉正斌. PRINCE密碼算法的差分?線性分析[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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? ），男，山東青島人，保密通信重點(diǎn)實(shí)驗(yàn)室工程師，主要研究方向?yàn)槊艽a學(xué)理論、對(duì)稱密碼分析。