Relaxed Differential Fault Analysis of SHA-3

Document Type: ORIGINAL RESEARCH PAPER

Authors

1 Department of Electrical Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran

2 Iran- Tehran- Rajaee University

3 SRTTU

Abstract

In this paper, we propose a new method of differential fault analysis of SHA-3 which is based on the differential relations of the algorithm. Employing those differential relations in the fault analysis of SHA-3 gives new features to the proposed attacks, e.g., the high probability of fault detection and the possibility of re-checking initial faults and the possibility to recover internal state with 22-53 faults.

We also present two improvements for the above attack which are using differential relations in reverse direction to improve that attack results and using the algebraic relations of the algorithm to provide a second way to recover the internal state of SHA-3. Consequently, we show that with 5-8 faults on average, SHA-3's internal state can be fully recovered.
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

Keywords


[1] Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. Keccak sponge function family main document. Submission to NIST (Round 2), 3(30), 2009.

[2] NF Pub. Draft fips pub 202: Sha-3 standard: Permutation-based hash and extendable-output functions. Federal Information Processing Standards Publication, 2014.

[3] Itai Dinur, Orr Dunkelman, and Adi Shamir. Collision attacks on up to 5 rounds of sha-3 using generalized internal differentials. In International Workshop on Fast Software Encryption, pages 219–240. Springer, 2013.

[4] Sourav Das and Willi Meier. Differential biases in reduced-round keccak. In International Conference on Cryptology in Africa, pages 69–87. Springer, 2014.

[5] Paweł Morawiecki, Josef Pieprzyk, and Marian Srebrny. Rotational cryptanalysis of roundreduced keccak. In International Workshop on Fast Software Encryption, pages 241–262. Springer, 2013.

[6] Donghoon Chang, Arnab Kumar, Pawell Morawiecki,andSomitraKumarSanadhya. 1stand2nd preimage attacks on 7, 8 and 9 rounds of keccak224,256,384,512. In SHA-3 Workshop, 2014. [7] Paweł Morawiecki and Marian Srebrny. A sat-based preimage analysis of reduced keccak hash functions. Information Processing Letters, 113(10-11):392–397, 2013.

[8] Jian Guo, Meicheng Liu, and Ling Song. Linear structures: Applications to cryptanalysis of round-reduced keccak. In International Conference on the Theory and Application of Cryptology and Information Security, pages 249–274. Springer, 2016.

[9] Ling Song, Guohong Liao, and Jian Guo. Nonfull sbox linearization: Applications to collision attacks on round-reduced keccak. In Annual International Cryptology Conference, pages 428– 451. Springer, 2017.

[10] Silvia Mella, Joan Daemen, and Gilles Van Assche. New techniques for trail bounds and application to differential trails in keccak. IACR Transactions on Symmetric Cryptology, 2017(1):329– 357, 2017.

[11] Kexin Qiao, Ling Song, Meicheng Liu, and Jian Guo. New collision attacks on round-reduced keccak. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 216–243. Springer, 2017.

[12] Senyang Huang, Xiaoyun Wang, Guangwu Xu, Meiqin Wang, and Jingyuan Zhao. Conditional cube attack on reduced-round keccak sponge function. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 259–288. Springer, 2017.

[13] Eli Biham and Adi Shamir. Differential fault analysis of secret key cryptosystems. In Annual international cryptology conference, pages 513– 525. Springer, 1997.

[14] Ludger Hemme. A differential fault attack against early rounds of (triple-) des. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 254–267. Springer, 2004.

[15] Michael Tunstall, Debdeep Mukhopadhyay, and Subidh Ali. Differential fault analysis of the advanced encryption standard using a single fault. In IFIP International Workshop on Information Security Theory and Practices, pages 224–233. Springer, 2011.

[16] Navid Vafaei, Nasour Bagheri, Sayandeep Saha, and Debdeep Mukhopadhyay. Differential fault attack on SKINNY block cipher. In Anupam Chattopadhyay, Chester Rebeiro, and Yuval Yarom, editors, Security, Privacy, and Applied Cryptography Engineering - 8th International Conference, SPACE 2018, Kanpur, India, December 15-19, 2018, Proceedings, volume 11348 ofLecture Notes in Computer Science,pages177– 197. Springer, 2018.

[17] Ludger Hemme and Lars Hoffmann. Differential fault analysis on the sha1 compression function. In Fault Diagnosis and Tolerance in Cryptography (FDTC), 2011 Workshop on, pages 54–62. IEEE, 2011.

[18] Wieland Fischer and Christian A Reuter. Differential fault analysis on grøstl. In Fault Diagnosis and Tolerance in Cryptography (FDTC), 2012 Workshop on, pages 44–54. IEEE, 2012.

[19] Nasour Bagheri, Navid Ghaedi, and Somitra Kumar Sanadhya. Differential fault analysis of sha3. In International Conference in Cryptology in India, pages 253–269. Springer, 2015.

[20] Pei Luo, Yunsi Fei, Liwei Zhang, and A Adam Ding. Differential fault analysis of sha3-224 and sha3-256. In Fault Diagnosis and Tolerance in Cryptography (FDTC), 2016 Workshop on, pages 4–15. IEEE, 2016.

[21] Pei Luo, Konstantinos Athanasiou, Yunsi Fei, and Thomas Wahl. Algebraic fault analysis of sha-3. In 2017 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 151–156. IEEE, 2017.

[22] Pei Luo, Konstantinos Athanasiou, Yunsi Fei, and Thomas Wahl. Algebraic fault analysis of sha-3 under relaxed fault models. IEEE Transactions on Information Forensics and Security, 2018.

[23] NIST. Sha-3: a secure hash algorithm. https:// competitions.cr.yp.to/sha3.html. Accessed: 1 May 2018.