针对Fruit v2和Fruit-80的差分错误攻击

doi:10.19665/j.issn1001-2400.2022.01.012

摘要/Abstract

摘要：

基于轻量级流密码Sprout,Fruit v2、Fruit-80、Fruit-128和Fruit-F等Fruit族小状态流密码自2016年相继被提出。Fruit族密码与Sprout结构相比,最大的区别在于Fruit族密码中非线性反馈移位寄存器与线性反馈移位寄存器的内部状态没有参与轮密钥函数状态更新,这使得对Fruit族密码的密钥恢复攻击相比于Sprout更加困难。借鉴Maitra等学者对Sprout的差分错误攻击方法和Banik等学者对Grain的差分错误攻击方法,在一个相对宽松的错误模型下,对Fruit v2和Fruit-80进行了差分错误攻击。攻击中,在攻击者能够多次注入时间同步的单比特错误的假设下,首先精确识别了错误注入的位置;随后通过求解利用输出函数的一阶差分性质得到的线性方程组,完整恢复了Fruit v2与Fruit-80的整个内部状态,恢复内部状态所需的时间复杂度为2^16.3(线性反馈移位寄存器)和2^6.3(非线性反馈移位寄存器)。进一步地借助Cryptominisat-2.9.5 SAT解算器,只需要大约10 min即可求解所有密钥,整个故障攻击所需错误个数为2^7.3。精确识别错误位置的复杂度分别为2^6.3(Fruit v2)和2^7.3(Fruit-80)。

关键词: 侧信道攻击, 错误攻击, 差分错误攻击, 流密码, 小状态流密码

Abstract:

Based on lightweight stream cipher Sprout,small state stream cipher such as Fruit v2,Fruit-80,Fruit-128 and Fruit-F have been proposed since 2016.The difference between Fruit and Sprout is that the round key that participates in the internal state update in Fruit does not involve the internal state of NFSR and LFSR,which makes it more difficult to recover the key of Fruit than Sprout.In this paper,based on Maitra's differential fault attack on Sprout and Banik's differential fault attack on Grain,we will describe a differential fault attack(DFA) on Fruit v2 and Fruit-80 under the most relaxed of assumption.We assume that the attacker can inject multiple,time-synchronized,single bit-flipping faults in the same albeit random register location.e first accurately identify the location of the fault injection,and then according to the affine property of the output function,we formulate a sufficient number of linear equations to recover the whole internal state of the cipher.The results show that the time complexity required to determine the internal state of Fruit v2 and Fruit-80 is 2^16.3 (LFSR) and 2^6.3(NFSR).In the part of key recovery,with the help of cryptomanisat-2.9.5 SAT solver,all the equations can be solved in about 10 minutes.According to the statistics,the number of fault needed to attack is 2^7.3.The complexity of identifying the correct fault location is 2^6.3(Fruit v2) and 2^7.3 (Fruit-80),respectively.

Key words: side-channel attack, fault analysis, differential fault attack, stream cipher, small-state stream cipher

中图分类号:

TN918.3

乔青蓝,董丽华. 针对Fruit v2和Fruit-80的差分错误攻击[J]. 西安电子科技大学学报, 2022, 49(1): 121-133.

QIAO Qinglan,DONG Lihua. A differential fault attack of fruit v2 and fruit 80[J]. Journal of Xidian University, 2022, 49(1): 121-133.

图/表 8

表1

图1

图2

图3

图4

表2

表3

表4

参考文献 52

[1]	HELL M, JOHANSSON T, MEIER W. Grain:A Stream Cipher for Constrained Environments[J]. International Journal of Wireless and Mobile Computing, 2007, 2(1):86-93. doi: 10.1504/IJWMC.2007.013798
[2]	AGREN M, HELL M, JOHANSSON T, et al. Grain-128a:A New Version of Grain-128 with Optional Authentication[J]. International Journal of Wireless and Mobile Computing, 2011, 5(1):48-59. doi: 10.1504/IJWMC.2011.044106
[3]	CD CANNIERE. Trivium:A Stream Cipher Construction Inspired by Block Cipher Design Principles[C]// International Conference on Information Security. Berlin: Springer, 2006, 4176:171-186.
[4]	BABBAGE S, DODD M. The MICKEY Stream Ciphers[J]. New Stream Cipher Designs, 2008, 4986:191-209.
[5]	BARKAN E, BIHAM E, SHAMIR A. Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs[C]// Annual International Cryptology Conference. Berlin: Springer, 2006:1-21.
[6]	BIRYUKOV A, SHAMIR A. Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers[C]// International Conference On the Theory and Application of Cryptology and Information Security.Berlin:Springer, 2000:1-13.
[7]	ARMKNECHT F, MIKHALEV V. On Lightweight Stream Ciphers with Shorter Internal States[C]// International Workshop on Fast Software Encryption.Berlin:Springer, 2015:451-470.
[8]	MAITRA S, SARKAR S, BAKSI A, et al. Key Recovery from State Information of Sprout:Application To Cryptanalysis and Fault Attack[EB/OL]. [2015-03-12]http://eprint.iacr.org/2015/236. .
[9]	BANIK S. Some Results on Sprout[C]// International Conference in Cryptology in India.Cham:Springer, 2015:124-139.
[10]	ESGIN M F, KARA O. Practical Cryptanalysis of Full Sprout with TMD Tradeoff Attacks[C]// International Conference on Selected Areas in Cryptography.Cham:Springer, 2015:67-85.
[11]	HAO Y. A Related-Key Chosen-IV Distinguishing Attack on Full Sprout Stream Cipher[EB/OL]. [2015-03-15]https://eprint.iacr.org/2015/231.pdf.
[12]	LALLEMAND V, NAYA-PLASENCIA M. Cryptanalysis of Full Sprout[C]// Advances in Cryptology-CRYPTO 2015.Berlin:Springer, 2015:663-682.
[13]	ZHANG B, GONG X. Another Tradeoff Attack on Sprout-Like Stream Ciphers[C]// International Conference on the Theory and Application of Cryptology and Information Security.Berlin:Springer, 2015:561-585.
[14]	MIKHALEV V, ARMKNECHT F, MULLER C. On Ciphers That Continuously Access the Non-volatile Key[J]. IACR Transactions on Symmetric Cryptology, 2016:52-79.
[15]	MAITRA S, SIDDHANTI A, SARKAR S. A Differential Fault Attack on Plantlet[J]. IEEE Transactions on Computers, 2017, 66(10):1804-1808. doi: 10.1109/TC.2017.2700469
[16]	HAMANN M, KRAUSE M, MEIER W. LIZARD-A Lightweight Stream Cipher for Power-constrained Devices[J]. IACR Transactions on Symmetric Cryptology, 2017, 1:45-79.
[17]	GHAFARI V A, HU H, CHEN Y. Fruit-v2:Uultra-Lightweight Stream Cipher with Shorter Internal State[EB/OL]. [2017-07-23]https://eprint.iacr.org/2016/355.
[18]	GHAFARI V A, HU H. Fruit-80:A Secure Ultra-Lightweight Stream Cipher for Constrained Environments[J]. Entropy, 2018, 20(3):1-13. doi: 10.3390/e20010001
[19]	AMIN GHAFARI GHAREHSHIRAN. 轻量级流密码的设计及选择初始向量统计分析[D]. 合肥: 中国科学技术大学, 2018.
[20]	GHAFARI V A, LIN F. A New Idea in Response to Fast Correlation Attacks on Small-state Stream Ciphers[EB/OL]. [2020-11-8]https://eprint.iacr.org/2020/1061 https://eprint.iacr.org/2020/1061
[21]	GHAFARI V A, HU H, XIE C. Fruit:Ultralightweight Stream Cipher with Shorter Internal State[EB/OL]. [2017-07-23]https://eprint.iacr.org/2016/355.pdf https://eprint.iacr.org/2016/355.pdf
[22]	ZHANG B, GONG X, MEIER W. Fast Correlation Attacks on Grain-Like Small State Stream Ciphers[J]. IACR Transactions on Symmetric Cryptology, 2017:58-81.
[23]	HAMANN M, KRAUSE M, MEIER W, et al. Design and Analysis of Small-state Grain-Like Stream Ciphers[J]. Cryptography & Communications, 2017, 10(5):803-834.
[24]	WANG S, LIU M, LIN D, et al. Fast Correlation Attacks on Grain-Like Small State Stream Ciphers and Cryptanalysis Of Plantlet,Fruit-v2 And Fruit-80[EB/OL]. [2019-07-03]https://eprint.iacr.org/2019/763.pdf
[25]	DEY S, ROY T, SARKAR S. Some Results on Fruit[J]. Designs,Codes and Cryptography, 2019, 87:349-364. doi: 10.1007/s10623-018-0533-y
[26]	TODO Y, MEIER W, AOKI K. On The Data Limitation of Small-State Stream Ciphers:Correlation Attacks on Fruit-80 and Plantlet[C]// International Conference on Selected Areas in Cryptography.Cham:Springer, 2019:365-392.
[27]	POGUE T E, NICOLICI N. Incremental Fault Analysis:Relaxing the Fault Model of Differential Fault Attacks[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2020, 99:1-14.
[28]	FARHADY GHALATY N. Fault Attacks on Cryptosystems:Novel Threat Models,Countermeasures and Evaluation Metrics[D]. Virginia Tech, 2016.
[29]	REN-JIE Z. Study on SM 4 Differential Fault Attack Under Extended Fault Injection Range[J]. Computer ence, 2019.
[30]	BONEH D, DEMILLO R A, LIPTON R J. On the Importance of Checking Cryptographic Protocols for Faults[C]// International Conference on the Theory and Applications of Cryptographic Techniques.Berlin:Springer, 1997.
[31]	YUAN Q J, ZHANG X C, GAO Y, et al. Differential Fault Attack on the Lightweight Block Cipher PUFFIN[J]. Journal of Electronics and Information Technology, 2020, 42(6):1519-1525.
[32]	CHEN W J, ZHAO S Y, ZOU R J, et al. The Differential Fault Attack of PRESENT Cipher[J]. Journal of the University of Electronic Science and Technology of China, 2019, 48:865-869.
[33]	GAO Y, WANG Y, YUAN Q, et al. Improvement of Differential Fault Attack Based on Lightweight Ciphers with GFN Structure[M]// Artificial Intelligence and Security. 2019.
[34]	LE D P, YEO S L, KHOO K. Algebraic Differential Fault Analysis on SIMON Block Cipher[J]. IEEE Transactions on Computers, 2019, 68(11):1561-1572. doi: 10.1109/TC.2019.2926081
[35]	ZHANG J, WU N, ZHOU F, et al. A Novel Differential Fault Analysis on the Key Schedule of SIMON Family[J]. Electronics, 2019, 8(1):93. doi: 10.3390/electronics8010093
[36]	GRUBER M, SELMKE B. Differential Fault Attacks on KLEIN[C]// International Workshop on Constructive Side-Channel 6Analysis and Secure Design.Cham:Springer, 2019:80-95.
[37]	DONG L, ZHANG H, ZHU L, et al. Analysis of an Optimal Fault Attack on the LED-64 Lightweight Cryptosystem[J]. IEEE Access, 2019:31656-31662.
[38]	BEIERLE C, LEANDER G, TODO Y. Improved Differential-Linear Attacks with Applications to ARX Ciphers[C]// Annual International Cryptology Conference.Cham:Springer, 2020:329-358.
[39]	LIU F, ISOBE T, MEIER W. Automatic Verification of Differential Characteristics:Application to Reduced Gimli[C]// Advances in Cryptology-CRYPTO 2020.Cham:Springer, 2020:219-248.
[40]	SOOS M, NOHI K, CASTELLUCCIA C. Extending SAT Solvers to Cryptographic Problems[C]// Theory and Applications of Satisfiability Testing-SAT 2009.Berlin:Springer, 2009:244-257.
[41]	HOCH J J, SHAMIR A. Fault Analysis of Stream Ciphers[C]// Cryptographic Hardware and Embedded Systems-CHES 2004.Berlin:Springer, 2004:240-253.
[42]	HOJSIK M, RUDOLF B. Differential Fault Analysis of Trivium[C]// International Workshop on Fast Software Encryption.Berlin:Springer, 2008:158-172.
[43]	HOJSIK M, RUDOLF B. Floating Fault Analysis of Trivium[C]// International Conference on Cryptology in India.Berlin:Springer, 2008:239-250.
[44]	BERZATI A, CANOVAS C, CASTAGNOS G, et al. Fault Analysis of GRAIN-128[EB/OL]. [2009-01-03]https://www.researchgate.net/publication/224584884.
[45]	KARMAKAR S, CHOWDHURY D R. Fault Analysis of Grain-128 By Targeting NFSR[C]// International Conference on Cryptology in Africa.Berlin:Springer, 2011:298-315.
[46]	BANIK S, MAITRA S, SARKAR S. A Differential Fault Attack on the Grain Family of Stream Ciphers[C]// International Workshop on Cryptographic Hardware and Embedded Systems.Berlin:Springer, 2012:122-139.
[47]	BANIK S, MAITRA S, SARKAR S. A Differential Fault Attack on the Grain Family Under Reasonable Assumptions[C]// International Conference on Cryptology in India.Berlin:Springer, 2012:191-208.
[48]	HU Y, GAO J, LIU Q, et al. Fault Analysis of Trivium[J]. Designs Codes & Cryptography, 2012, 62(3):289-311.
[49]	BANIK S, MAITRA S. A Differential Fault Attack on MICKEY 2.0[C]// International Conference on Cryptographic Hardware and Embedded Systems.Berlin:Springer, 2013:215-232.
[50]	BANIK S, MAITRA S, SARKAR S. Improved Differential Fault Attack on MICKEY 2.0[J]. Journal of Cryptographic Engineering, 2015, 5(1):13-29. doi: 10.1007/s13389-014-0083-9
[51]	SIDDHANTI A, SARKAR S, MAITRA S, et al. Differential Fault Attack on Grain v1,ACORN v3 and Lizard[C]// International Conference on Security,Privacy,and Applied Cryptography Engineering.Cham:Springer, 2017:247-263.
[52]	SARKAR S, BANIK S, MAITRA S. Differential Fault Attack Against Grain Family with Very Few Faults and Minimal Assumptions[J]. IEEE Transactions on Computers, 2014, 64(6):1647-1657. doi: 10.1109/TC.2014.2339854

密码结构	错误个数	恢复LFSR	恢复NFSR	恢复密钥
Fruit v2	2^7.3	O(2¹⁶^.³)	O(2⁶^.²)	O(2⁶⁰)
Fruit-80	2^7.3	O(2¹⁶^.³)	O(2⁶^.²)	O(2⁷⁷)

密码结构	最大时间(Max)	平均时间(Avg)	最小时间(Min)
Fruit v2	409.6	146.2	38.53
Fruit-80	409.6	146.2	38.53

密码结构复杂度	密钥恢复攻击		快速相关攻击		差分错误攻击
密码结构复杂度	时间	空间	时间	空间	时间	空间
Fruit v2	2^72.63	2^42.38	2^55.62	2^55.34	2⁶⁰	2^26.5
Fruit-80	*	*	2^64.47	2^62.82	2⁷⁷	2^26.5