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

Faster Key Recovery Attack on 8-Round PRINCE

PRINCE算法是J.Borghoff等在2012年亚密会上提出的一个轻量级分组密码算法,它模仿AES并采用α-反射结构设计,具有加解密相似的特点.2014年,设计者发起了针对PRINCE实际攻击的公开挑战,使得该算法的安全性成为研究的热点.目前对PRINCE攻击的最长轮数是10轮,其中P.Derbez等利用中间相遇技术攻击的数据和时间复杂度的乘积D×T=2^(125),A.Canteaut等利用多重差分技术攻击的复杂度D×T=2^(118.5),并且两种方法的时间复杂度都超过了257.本文将A.Canteaut等给出的多重差分技术稍作改变,通过考虑输入差分为固定值,输出差分为选定的集合,给出了目前轮数最长的7轮PRINCE区分器,并应用该区分器对8轮PRINCE进行了密钥恢复攻击.本文的7轮PRINCE差分区分器的概率为2^(-56.89),8轮PRINCE的密钥恢复攻击所需的数据复杂度为2^(61.89)个选择明文,时间复杂度为219.68次8轮加密,存储复杂度为2^(15.21)个16比特计数器.相比目前已知的8轮PRINCE密钥恢复攻击的结果,包括将A.Canteaut等给出的10轮攻击方案减少到8轮,本文给出的攻击方案的时间复杂度和D×T复杂度都是最低的.

PRINCE is a lightweight block cipher proposed by J.Borghoff et al.at ASIACRYPT 2012.Imitating AES and usingα-reflection design,it possesses the similarity of encryption and decryption.In 2014,the designers launched a public challenge on finding practical attacks on PRINCE.Currently,attacks on PRINCE can reach up to 10 encryption rounds.P.Derbez et al.used meet-in-the-middle technique to attack PRINCE with the data complexity and time complexity satisfying D×T=2125,and A.Canteaut et al.used multiple differential cryptanalysis to attack PRINCE with the data complexity and time complexity satisfying D×T=2118.5.The time complexity of both the two attacks exceeds 257.This paper slightly changes the multiple differential cryptanalysis given by A.Canteaut.By considering the case when the input difference is a fixed value and the output difference falls into a selected set,a distinguisher on 7-round PRINCE with the longest number of rounds is given,which can be used to lunch a key recovery attack on 8-round PRINCE.The differential probability of7-round PRINCE differential distinguisher designed in this paper is 2-56.89.The key recovery attack on 8-round PRINCE is given with data complexity being 261.89chosen plaintext,time complexity being219.688-round PRINCE encryption,and memory complexity being 215.21of 16-bit counters.Compared with the results of key recovery attacks on 8-round PRINCE,including reducing the 10-round attack given by A.Canteaut et al.to 8-round,the time complexity and D×T complexity given in this paper are both the lowest.