Statistical Model on CRAFT

WANG Caibing; GUO Hao; YE Dingfeng; WANG Ping

doi:10.1049/cje.2021.00.092

Volume 31 Issue 4

Jul. 2022

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2022 > 31(4): 698-712

WANG Caibing, GUO Hao, YE Dingfeng, et al., “Statistical Model on CRAFT,” Chinese Journal of Electronics, vol. 31, no. 4, pp. 698-712, 2022, doi: 10.1049/cje.2021.00.092

Citation:

WANG Caibing, GUO Hao, YE Dingfeng, et al., “Statistical Model on CRAFT,” Chinese Journal of Electronics, vol. 31, no. 4, pp. 698-712, 2022, doi: 10.1049/cje.2021.00.092

WANG Caibing, GUO Hao, YE Dingfeng, et al., “Statistical Model on CRAFT,” Chinese Journal of Electronics, vol. 31, no. 4, pp. 698-712, 2022, doi: 10.1049/cje.2021.00.092

Citation:

WANG Caibing, GUO Hao, YE Dingfeng, et al., “Statistical Model on CRAFT,” Chinese Journal of Electronics, vol. 31, no. 4, pp. 698-712, 2022, doi: 10.1049/cje.2021.00.092

PDF( 3626 KB)

Statistical Model on CRAFT

doi: 10.1049/cje.2021.00.092

WANG Caibing^{1, 2
,},
GUO Hao^{1, 2
,},
YE Dingfeng^{1, 2
,},
WANG Ping^3
,

1.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100195, China
2.
School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
3.
Tianjin Aerospace Zhongwei Data System Technology Co., Ltd., Tianjin 300301, China

Funds: This work was supported by the National Key R&D Program of China (2018YFA0704704), Natural Science Foundation of China (NSFC) (61772519), and the Chinese Major Program of National Cryptography Development Foundation (MMJJ20180102)

More Information

Author Bio:
(corresponding author) is a Ph.D. candidate of Institute of Information Engineering, University of Chinese Academy of Sciences. Her research interest focuses on symmetric cryptanalysis and design. (Email: wangcaibing@iie.ac.cn)

is a Ph.D. candidate of Institute of Information Engineering, University of Chinese Academy of Sciences. His research interest focuses on symmetric cryptanalysis and design. (Email: guohao@iie.ac.cn)

received the Ph.D. degree in mathematics from Chinese Academy of Sciences in 1996. He is a Professor in Institute of Information Engineering, University of Chinese Academy of Sciences. His research interests include basic theory of applications of pseudorandom sequences and arrays, analysis of cryptographic algorithms, and theoretical cryptography. (Email: yedingfeng@iie.ac.cn)

is a Senior Engineer at Tianjin Aerospace Zhongwei Data System Technology Co., Ltd. His research interests include communication and remote sensing. (Email: 2231961836@qq.com)
Received Date: 2021-03-14
Accepted Date: 2021-05-17

Available Online: 2021-08-20

Publish Date: 2022-07-05

Abstract

Abstract

Many cryptanalytic techniques for symmetric-key primitives rely on specific statistical analysis to extract some secrete key information from a large number of known or chosen plaintext-ciphertext pairs. For example, there is a standard statistical model for differential cryptanalysis that determines the success probability and complexity of the attack given some predefined configurations of the attack. In this work, we investigate the differential attack proposed by Guo et al. at Fast Software Encryption Conference 2020 and find that in this attack, the statistical behavior of the counters for key candidates deviate from standard scenarios, where both the correct key and the correct key xor specific difference are expected to receive the largest number of votes. Based on this bimodal behavior, we give three different statistical models for truncated differential distinguisher on CRAFT (a cryptographic algorithm name) for bimodal phenomena. Then, we provide the formulas about the success probability and data complexity for different models under the condition of a fixed threshold value. Also, we verify the validity of our models for bimodal phenomena by experiments on round-reduced of the versions distinguishers on CRAFT. We find that the success probability of theory and experiment are close when we fix the data complexity and threshold value. Finally, we compare the three models using the mathematical tool Matlab and conclude that Model 3 has better performance.
- Differential cryptanalysis,
- Statistical models,
- Success probability,
- Data complexity,
- Bimodal behavior,
- CRAFT,
- Differential fault analysis (DFA) attacks

FullText(HTML)

References(31)

References

[1]	Biham Eli and Adi Shamir, “Differential cryptanalysis of DES-like cryptosystems,” Journal of CRYPTOLOGY, vol.4, no.1, pp.3–72, 1991. doi: 10.1007/BF00630563
[2]	Matsui Mitsuru, “Linear cryptanalysis method for DES cipher,” in Proceedings of Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, pp.386–397, 1993.
[3]	Biham Eli, “New types of cryptanalytic attacks using related keys,” Journal of Cryptology, vol.7, no.4, pp.229–246, 1994. doi: 10.1007/BF00203965
[4]	David Wagner, “The boomerang attack,” in Proceedings of International Workshop on Fast Software Encryption, Berlin, Heidelberg, pp.156–170, 1999.
[5]	Biham Eli, Alex Biryukov, and Adi Shamir, “Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials,” in Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Springer, Berlin, Heidelberg, pp.12–23, 1999.
[6]	L. R. Knudsen, “Truncated and higher order differentials,” in Proc. of International Workshop on Fast Software Encryption, Springer, Berlin, Heidelberg, pp.196–211, 1994.
[7]	Blondeau Céline and Benoît Gérard, “Multiple differential cryptanalysis: Theory and practice,” in Proceedings of International Workshop on Fast Software Encryption, Springer, Berlin, Heidelberg, pp.35–54, 2011.
[8]	Blondeau Céline, Benoît Gérard, and Kaisa Nyberg, “Multiple differential cryptanalysis using LLR and χ² statistics,” in Proceedings of International Conference on Security and Cryptography for Networks, Springer, Amalfi, Italy, pp.343–360, 2012.
[9]	Biryukov Alex, Christophe De Canniere, and Michaël Quisquater, “On multiple linear approximations,” in Proceedings of Annual International Cryptology Conference, New York, USA, pp.1–22, 2004.
[10]	Hermelin Miia, Joo Yeon Cho, and Kaisa Nyberg, “Multidimensional linear cryptanalysis of reduced round Serpent,” in Proceedings of Australasian Conference on Information Security and Privacy, Berlin, Heidelberg, pp.203–215, 2008.
[11]	Hermelin Miia, Joo Yeon Cho, and Kaisa Nyberg, “A new technique for multidimensional linear cryptanalysis with applications on reduced round serpent,” in Proceedings of International Conference on Information Security and Cryptology - ICISC 2008, Seoul, Korea, pp.383–398, 2008.
[12]	Hermelin Miia, Joo Yeon Cho, and Kaisa Nyberg, “Multidimensional extension of Matsui’s algorithm 2,” in Proceedings of International Workshop on Fast Software Encryption, Berlin, Heidelberg, pp.209–227, 2009.
[13]	Ali Aydın Selçuk, “On probability of success in linear and differential cryptanalysis,” Journal of Cryptology, vol.21, no.1, pp.131–147, 2008. doi: 10.1007/s00145-007-9013-7
[14]	Joan Daemen and Vincent Rijmen, “Probability distributions of correlation and differentials in block ciphers,” Journal of Mathematical Cryptology, vol.1, no.3, pp.221–242, 2007. doi: 10.1515/JMC.2007.011
[15]	Céline Blondeau and Benoît Gérard, “Links between theoretical and effective differential probabilities: Experiments on PRESENT,” IACR Cryptol. ePrint Arch, vol.2010, article no.261, 2010.
[16]	Céline Blondeau, Benoît Gérard, and Jean-Pierre Tillich, “Accurate estimates of the data complexity and success probability for various cryptanalyses,” Designs, Codes and Cryptography, vol.59, no.1-3, pp.3–34, 2011. doi: 10.1007/s10623-010-9452-2
[17]	Guo Hao, Sun Siwei, Shi Danping, Sun Ling, et al., “Differential attacks on CRAFT exploiting the involutory S-boxes and tweak additions,” IACR Transactions on Symmetric Cryptology, vol.2020, no.3, pp.119–151, 2020. doi: 10.13154/tosc.v2020.i3.119-151
[18]	Harpes Carlo, Gerhard G. Kramer, and James L. Massey, “A generalization of linear cryptanalysis and the applicability of Matsui’s piling-up lemma,” in Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Saint-Malo, France, pp.24–38, 1995.
[19]	Flórez-Gutiérrez Antonio and María Naya-Plasencia, “Improving key-recovery in linear attacks: Application to 28-round PRESENT,” in Proceedings of 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, pp.221–249, 2020.
[20]	Beierle C, Leander G, Moradi A, et al., “CRAFT: Lightweight tweakable block cipher with efficient protection against DFA attacks,” IACR Transactions on Symmetric Cryptology, vol.2019, no.1, pp.5–45, 2019. doi: 10.13154/tosc.v2019.i1.5-45
[21]	Sun Siwei, Hu Lei, Wang Peng, et al., “Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES (L) and other bit-oriented block ciphers,” in Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security, Part I, Kaoshiung, China, pp.158–178, 2014.
[22]	Mouha N, Wang Q, Gu D, et al., “Differential and linear cryptanalysis using mixed-integer linear programming,” in Proceedings of International Conference on Information Security and Cryptology, Beijing, China, pp.57–76, 2011.
[23]	Sun Siwei, Hu Lei, Wang Meiqin, et al., “Automatic enumeration of (related-key) differential and linear characteristics with predefined properties and its applications,” IACR Cryptol. ePrint Arch., vol.2014, article no.747, 2014
[24]	Seijas-Macías Antonio and Amílcar Oliveira, “An approach to distribution of the product of two normal variables,” Discussiones Mathematicae Probability and Statistics, vol.32, no.1-2, pp.87–99, 2012. doi: 10.7151/dmps.1146
[25]	Adelchi Azzalini, “A class of distributions which includes the normal ones,” Scandinavian Journal of Statistics, vol.12, no.2, pp.171–178, 1986.
[26]	Nadarajah Saralees and Samuel Kotz, “Exact distribution of the max/min of two Gaussian random variables,” IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol.16, no.2, pp.210–212, 2008. doi: 10.1109/TVLSI.2007.912191
[27]	Man Wei, Siwei Sun, Zihao Wei, et al., “Unbalanced sharing: A threshold implementation of SM4,” Sci. China Inf. Sci., vol.64, article no.159102, 2021. doi: 10.1007/s11432-018-9794-6
[28]	S. Banik, A. Bogdanov, T. Isobe, et al., “Midori: A block cipher for low energy,” International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, pp.411–436, 2015.
[29]	Man Wei, Siwei Sun, Zihao Wei, et al., “A small first-order DPA resistant AES implementation with no fresh randomness,” Sci. China Inf. Sci., vol.65, article no.169102, 2022. doi: 10.1007/s11432-019-1469-7
[30]	Hadipour Hosein, Sadegh Sadeghi, Majid M. Niknam, et al., “Comprehensive security analysis of CRAFT,” IACR Trans. Symmetric Cryptol., vol.2019, no.4, pp.290–317, 2019. doi: 10.13154/tosc.v2019.i4.290-317
[31]	Muhammad ElSheikh and Amr M. Youssef, “Related-key differential cryptanalysis of full round CRAFT,” in Proceedings of 9th International Conference on Security, Privacy, and Applied Cryptography Engineering, Gandhinagar, India, pp.50–66, 2019.