8轮PRINCE的快速密钥恢复攻击

密码学报 ISSN 2095-7025 CN 10-1195/TN E-m a i l:j c r@c a c r n e t.o r g.c n Journal of Cryptologic Research^ 2021, 8(1): 113 h t t p://w w w.j c r.c a c r n e t.o r g.c n ©《密码学报》编辑部版权所有. T e l/Fax: +86-10-82789618

8轮P R IN C E的快速密钥恢复攻击#

段春晖\谭林'戚文峰夂2

1.中国人K解放军战略支援部队信息工程大学，郑州450001

2.数学工程与先进it算国家重点实验室，郑州450001

通信作者：谭林，E-mail:*****************

摘要：P R I N C E算法是J.Borghoff等在2012年亚密会上提出的一个轻量级分组密码算法，它糢仿 A E S并采用a-反射结构设计，具有加解密相似的特点.2014年，设计者发起了针对P R I N C E实际攻击的公开挑战，使得该算法的安全性成为研究的热点.目前对P R I N C E攻击的最长轮數是10轮，其中P. Derbez等利用中间相遇技术攻击的数据和时间复杂度的乘枳D x 了 = 2125,A.Canteaut等利用多重差分技术攻击的复杂度D x T= 2118'5，并且两种方法的时间复杂度都超过了 257.本文将A.Canteaut等给出的多重差分技术稍作改变，通过考4输入差分为固定值，输出差分为选定的集合，给出了目前轮数最长

的7轮P R I N C E区分器，并应用该区分器对8轮P R I N C E进行了密钥恢复攻击.本文的7轮PRINCE 差分区分器的概率为2_56'89, 8轮P R I N C E的密钥恢复攻击所需的数据复杂度为261'89个选择明文，时间复杂度为219'68次8轮加密，存储复杂度为215'21个16比特计数器.相比目前已知的8轮PRINCE 密钥恢复攻击的结果，包括将A.Canteaut等给出的10轮攻击方案减少到8轮，本文给出的攻击方案的时间复杂度和Z3 x T复杂度都是最低的.

关键词：分组密码；PRINCE；差分分析

中图分类号：T N918.1 文献标识码：A DOI: 10.13868/j.c n k i.j c r.000415

中文引用格式：段春晖.谭林，戚文峰.8轮PRINCE的快速密钥恢复攻击p j.密码学报.2021, 8(1): 113. [DOI: 10.13868/j.c n k i.j c r.000415]傣族舞蹈音乐

英文引用格式：DUAN C H,TAN L.Q I W F.F a s t e r k e y r e c o v e r y a t t a c k o n 8-r o u i i(l PRINCE[J].J o u r n a l o f C r y p t o l o g i c R e s e a r c h, 2021, 8(1): 1-13. [DOI: 10.13868/j.c n k i.j c r.000415]

F a s te r K ey R eco v e ry A tta c k o n8-R o u n d P R I N C E

D U A N Chun-Hni1,TAN L i n1'2,QI Wen-Fe ng1'2

1.P L A Strategic Support Force Information Engineering University, Zhengzhou 450001, China

2.State K e y Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China Corresponding author: T A N Lin, E-mail: *****************

Abstract:PRINCE i s a l i g h t w e i g h t b l o c k c i p h e r p r o p o s e d b y J.B o r g h o f F e t a l.a t ASIACRYPT2012.

I m i t a t i n g AES and u s i n g a-r e f l e c t i o n d e s i g n,i t p o s s e s s e s t h e s i m i l a r i t y o f e n c r y p t i o n and d e c r y p t i o n.

我的八十年代I n 2014, t h e d e s i g n e r s l a u n c h e d a p u b l i c c h a l l e n g e on f i n d i n g p r a c t i c a l a t t a c k s o n PRINCE.C u r r e n t l y,

a t t a c k s o n PRINCE c a n r e a c h up t o 10 e n c r y p t i o n r o u n d s.P.D e r

b ez e t a l.u s e d meet-i n-t h e-m i d d l e

*基金项目：国家自然科学基金（61521003)；国家密码发展基金（MMJJ20170103, MMJJ20180204) Foundation: National Natural Science Foundation of China (61521003); National Cryptography Development Fund (MMJJ20170103, MMJJ20180204)

收稿日期：2020-01-07 定稿日期：2020-05-09

2<7owma/ 〇/Crypb/c^c Hesearc/i 密码学报 Vol.8，No.1，Feb.2021

t e c h n i q u e t o a t t a c k PRINCE w i t h t h e d a t a c o m p l e x i t y and t i m e c o m p l e x i t y s a t i s f y i n g D x T= 2125, and A.C a n t e a u t e t a l.u s e d m u l t i p l e d i f f e r e n t i a l c r y p t a n a l y s L s t o a t t a c k PRINCE w i t h t h e d a t a c o m p l e x i t y and t i m e c o m p l e x i t y s a t i s f y i n g D x T — 2118 5.The t i m e c o m p l e x i t y o f b o t h t h e t w o a t t a c k s e x c e e d s 257.T h i s p a p e r s l i g h t l y c h a n g e s t h e m u l t i p l e d i f f e r e n t i a l c r y p t a n a l y s i s g i v e n b y A. Canteaut.By c o n s i d e r i n g t h e c a s e when t h e i n p u t d i f f e r e n c e i s a f i x e d v a l u e and t h e o u t p u t d i f f e r e n c e f a l l s i n t o a s e l e c t e d s e t,a d i s t i n g u i s h e r on7-r o u n d PRINCE w i t h t h e l o n g e s t number o f r o u n d s i s g i v e n, wh i c h ca n be u s e d t o l u n c h a k e y r e c o v e r y a t t a c k on8-r o u n d PRINCE.The d i f f e r e n t i a l p r o b a b i l i t y o f 7-r o u n d PRINCE d i f f e r e n t i a l d i s t i n g u i s h e r d e s i g n e d i n t h i s p a p e r i s 2 —56 89.The k e y r e c o v e r y a t t a c k on8-r o u n d PRINCE i s g i v e n w i t h d a t a c o m p l e x i t y b e i n g261 89 c h o s e n p l a i n t e x t,t i m e c o m p l e x i t y b e i n g 21908 8-r o u n d PRINCE e n c r y p t i o n,and memory c o m p l e x i t y b e i n g21521o f16-b i t c o u n t e r s.Compared w i t h t h e r e s u l t s o f k e y r e c o v e r y a t t a c k s o n 8-r o u n d PRIN

CE,i n c l u d i n g r e d u c i n g t h e 10-r o u n d a t t a c k g i v e n b y A.C a n t e a u t e t a l.t o8-round,t h e t i m e c o m p l e x i t y and D x T c o m p l e x i t y g i v e n i n t h i s p a p e r a r e b o t h t h e l o w e s t.

Key words:b l o c k c i p h e r;PRINCE;d i f f e r e n t i a l c r y p t a n a l y s i s

i引言

随着移动通信和物联网的发展，射频识别系统（RFID)和智能卡等设备的加密被广泛应用，海量信息加密和有限资源处理间的矛盾日益突显，传统的加密算法无法适用于资源受限的环境，密码算法的轻量化越来越受到关注.PRESENT W,S I M O N和S P E C K等M轻量级密码算法先后被提出，它们使用小规模的密码组件，在硬件实现方面有着明显的优势.PRINCE |3i密码算法是J.Bo rghoff等在2012年的亚密会上提出的一个轻量级分组密码，它基于F X结构W设计，具有a-反射性质，解密过程可以通过稍微改变密钥进行加密来实现.这种特性使P R I N C E在硬件实现上具有优势，但也使得其安全性受到担忧，H. Soleimany等15]针对某些特定的a值在相关密钥模式下可以攻击全轮的P R I N C E变种，但这里不包括 P R I N C E算法的a值.

学者们对P R I N C E算法的安全性进行了大量分析，表1罗列了目前在单密钥模式下对P R I N C E算法不同轮数版本的主要分析结果.J.Jean等给出了 4轮和6轮P R I N C E的积分攻击王小云团队使用中

间相遇攻击方法攻击了 8轮和9轮PRINCE P1.虽然P R I N C E的轮密钥除了首尾白化外都相同，但仍假设差分特征概率等于各轮差分概率的乘积，A.Canteaut等W构造了 5轮和6轮的多重差分区分器，攻击了 9轮和10轮PRINCE；赵光耀等間给出了5轮和6轮的截断差分区分器，并攻击了 7轮PRINCE core.P.Derhez等[1Q1将中间相遇方法和S A T方法相结合，攻击了 10轮PRINCE.P. Morawiecki利用积分和高阶差分分析，给出了 4轮至7轮P R I N C E实际的攻击[111.随后，R.P o s t e u c a 等改进了 6轮P R I N C E的积分攻击，降低了数据量和计算量Ml.利用预存储技术，S.Rasoolzadeh等改进了 4至6轮的积分攻击和7轮的高阶差分攻击I13】.L.Grassi等利用子空间路径给出了只需要8个选择明文的4轮P R I N C E的截断差分攻击

本文将文献间的多重差分技术稍作改变，考虑输入差分为固定值，输出差分为选定的集合，给出了目前轮数最长的7轮P R I N C E区分器，并对8轮P R I N C E进行了密钥恢复攻击.本文给出的7轮差分区分器的概率为2_56+89, 8轮P R I N C E的密钥恢复攻击所需的数据复杂度为26189个选择明文，时间复杂度为219_68次8轮加密，存储复杂度为215'21个16比特计数器.相比目前已知的8轮P R I N C E密钥恢复攻击的结果，包括将A.Canteaut等的10轮攻击方案减到8轮，本文的时间复杂度和D x r复杂度都是最低的.

2 P R I N C E密码算法简介

P R I N C E算法是一个S P N型的分组密码，分组长度为64比特，密钥长度为128比特，迭代轮数为 12轮，算法结构如图1所示.128比特的密钥被分为2个64比特的子密钥和h，其中幻应用于

段春晖等：8轮PRINCE的快速密钥恢复攻击3

表1不同轮數PRINCE算法的攻击结果

T a b l e 1 C r y p t a n a l y s i s r e s u l t s o f d i f f e r e n t r o u n d s PRINCE

轮数数据复杂度1时间复杂度存储复杂度攻击方法参考文献

210_2«227中间相遇分析[10] 423218.3—截断差分分析[14]

2627.4

一积分分析[13]

525

221.4

25积分分析[13] 21321325积分分析[13]

216233.7231.9中间相遇分析[1〇1

213224.6213积分分析[13]

234.6252 1234 6高阶差分分析

[HI

233244.3233高阶差分分析[13]

253260230中间相遇分析[7]

216250.7^3284 9中间相遇分析[1〇] 8216265.7*268.9中间相遇分析[1〇]

216266.3249.9中间相遇分析[10]

261.8921968215.21多重差分分析第5节

246.9251.2252 2多重差分分析

[8]

257264257.3中间相遇分析[1〇]

257.9260.6261.5多重差分分析

[8]

257268*241中间相遇分析[10]

1.数据量均为选择明文

2.—表示复杂度几乎为0

李慧珍好听的歌3. *处标注数值为线上计算的复杂度

核心部件PRINCEcore，知和蜣用于算法输入、输出两端的白化，这里私=(f c〇1)㊉（f c〇》63). PRINCEc^e采用对称结构，中间2轮是对合的，前后5轮除轮常数不同外互为逆变换，轮常数满足 RCi®R C n_i =a，0 <i < 11，这里a是个固定常数.P R I N C E算法可以通过加密操作来实现解密，即^

(f c〇im i|f c l)(*) =^(A:J||fc〇||fc1©a)(-)-

PRIN CE。

%«3尺4«55-1h k\ k\

i l l

%—* "7 ~^ "8%

k x R C〇R C X R C2R C3R C4R C5

R C,k x R C611^7rc8rc9rc10rcu k x

~►[s R'1!~►M,—»|g I~*•

f c】R C,

图1PRINCE算法结构图

F i g u r e 1S t r u c t u r e o f PRINCE

将P R I N C E的64比特状态X看成一个4 x 4的矩阵，每一个块单元为4比特，本文中我们记；为表示X的第Z块，丨€ {0，1，...，15丨，块的顺序如图2所示.算法的轮函数可表示为=A K o A R C o

4Jemma/ 〇/CrypbZo仍c •R esearc/i 密码学报 Vol.8，No.1，Feb.2021 SR〇W〇5•，包括以下5个变换:

04812

15913

261014

371115

图2状态X的16个块标记

F i g u r e2 S t a t e X

S层：16个块同时查询一个4比特的S盒，S盒如表2所示.

表2 PRINCE的S盒

T a b l e 2 S-b o x o f PRINCE

x0123456789A B C D E F S(x)B F32A C916780E5D4

扩散层M'：扩散层对应对角矩阵M' =diagWf'X^AV1，A'P)，作用在状态；C上为

M' -X =(M° ■ XiWM1■ X2\\Ml ■ X3\\M° ■ XA)

李易峰哪里人

这里X，表示X的第i列.1 S i幺4，矩阵M1分别为:

其中

M° =

/M〇Mi m2MA/M i M‘2M3M〇\

Ml m2Ms M o

,M J=

Ah m3M〇Mi

m2M3M o Mi m3M〇Mi m2

\Ms A/〇Mi M2)W

〇Mi m

2m3J

A/〇=

/〇00

〇)

00o\

0100

M i =

0000

00100010

、()00i j\〇001/

/100

°)00

0100

,M3 =

0100

00000010

\〇00V\〇00〇/

行移位SR：与A E S的行移位操作相同，将状态的第i行向左循环移动i个块，〇g i < 3.轮常数加A R C：比特异或一个64比特轮常数R C“0 $i < 11.

密钥加A K：比特异或64比特密钥

3准备工作

设7?是一个S P N型分组密码的轮函数，A in和A m t分别表示其输入差分和输出差分，则经过i?的差分概率；4A^)等于活动S盒的差分概率的乘积.设A i n =心44—>A,._! -> A r = A uut是密码经过r轮的一条差分路径，根据马尔科夫链的假设，该差分特征概率等于各轮差分概率的乘

段春晖等：8轮PR IN C E 的快速密钥恢复攻击5

积，即

r — 1

P (A in —> A i —> • • ■ —^ A,■_i

A 〇ut )=

丄丄 P(^i ~^ A j +i)

i=0

设A in 和Aout 分别表示r 轮的输入差分和输出差分，则r •轮差分概率

f(A in —> A 〇ut ) =〉: ^(Ain —> Al A r-l —> A 〇ut )

这里的求和式是对所有输入差分为A i n 、输出差分为A 。。,，的r 轮差分特征概率求和.由于我们很难穷尽所有的差分特征，所以通常使用部分差分特征概率求和来近似计算如果考虑输出差分不是某个固定值，而是某个集合A ，则输入差分为A i n 、输出差分属于集合A 的概率

P (A in ^ A) = ^ P (A i n $ Aout)

A 〇ut € A

P R IN C E 算法S 盒的差分分布表见附录，记p(a 4 /?)表示S 盒输入差分为a 、输出差分为/?的概率,

例如 p (l 1)=盖=2-2.

下面介绍本文用到的八种差分模式，如图3所示，记作A l ，i e {1,2，...，8}.每个差分模式A 1只有 4个块有差分，其余块差分为0，属于模式的差分由4个非零差分块决定，将其记为其中

a ,6,c ，d 是非零差分块的差分值.

c a 7

a c b

a c T

r a d

a c b

a c J

a c b

A 1

A 2

A 3

A 4

夜曲周杰伦

A 5

A 6

A 7

A 8

图3差分模式A 'i = 1,2，...，82021维也纳新年音乐会

F i g u r e 3 D i f f e r e n c e p a t t e r n A ' i = 1，2,…，8

文献丨9]指出了矩阵M 。和心1具有如下性质：如果5 e {1，4,5丨，则

-(0,<5,0,5)t = (5,0,<5,0)t

M ° • (<5,0,6,0)t = (0,<5,0,<5)t

M 1 ■ (0,5,0,<5)t = (0,^,0,5)t M 1 ■ (6,0,(5,0)t = ((5,0,<S,0)t

如果 <5 e {2,8,10}，

M ° • (0,5,0,5)t = (0,<5,0,(5)t M°-(<5,0,(5,0)t = (J,0,(5,0)t M 1 ■ (0,<5,0,<5)t = (<5,0,<S,0)t M 1 • (<5,0,<5,0)t = (0,<5,0,(5)t

4 7轮P R I N C E 的差分区分器

由于轮密钥加和轮常数加不影响差分，在下面的分析中我们将忽略这两个操作.7轮P R I N C E 可以表示成：

R 7 = R -1 o R -1 o S ^1 〇 M' 〇 S o R o R 〇 R = S '1 〇 R'~l 〇 Fm id o R' 〇 S o R

8轮PRINCE的快速密钥恢复攻击

发布评论取消回复

最近发表

热门文章

标签列表