Algebraic Fault Attack on the SHA-256 Compression Function

Download Full Text
Author(s):
Ronglin Hao, Bao Li, Bingke Ma, Ling Song
Published Date:
March 05, 2014
Issue:
Volume 4, Issue 2
Page(s):
1 - 9
DOI:
10.7815/ijorcs.42.2014.079
Views:
5016
Downloads:
130

Keywords:
algebraic fault analysis, hmac, sha-256 compression function, sat solver, stp
Citation:
Ronglin Hao, Bao Li, Bingke Ma, Ling Song, "Algebraic Fault Attack on the SHA-256 Compression Function". International Journal of Research in Computer Science, 4 (2): pp. 1-9, March 2014. doi:10.7815/ijorcs.42.2014.079 Other Formats

Abstract

The cryptographic hash function SHA-256 is one member of the SHA-2 hash family, which was proposed in 2000 and was standardized by NIST in 2002 as a successor of SHA-1. Although the differential fault attack on SHA-1compression function has been proposed, it seems hard to be directly adapted to SHA-256. In this paper, an efficient algebraic fault attack on SHA-256 compression function is proposed under the word-oriented random fault model. During the attack, an automatic tool STP is exploited, which constructs binary expressions for the word-based operations in SHA-256 compression function and then invokes a SAT solver to solve the equations. The simulation of the new attack needs about 65 fault injections to recover the chaining value and the input message block with about 200 seconds on average. Moreover, based on the attack on SHA-256 compression function, an almost universal forgery attack on HMAC-SHA-256 is presented. Our algebraic fault analysis is generic, automatic and can be applied to other ARX-based primitives.

  1. M. Bellare, R. Canetti, H. Krawczy, “Keying Hash Functions for Message Authentication”, 16th Annual International Cryptology Conference (CRYPTO’96), Springer Berlin Heidelberg 1996, LNCS 1109, pp. 1-15. doi: 10.1007/3-540-68697-5_1
  2. U.S. Department of Commerce, National Institute of Standards and Technology (2008). Announcing the SECURE HASH STANDARD (Federal Information Processing Standards Publication 180-3). [Online]. Available: http://csrc.nist.gov/publications/fips/fips180- 3/fips180-3_final.pdf
  3. National Institute of Standards and Technology (March 2002). FIPS PUB 198. The Keyed-Hash Message Authentication Code (HMAC)
  4. F. Zhang, X. Zhao, S. Guo, T. Wang, Z. Shi, “Improved Algebraic Fault Analysis: A Case Study on Piccolo and Applications to Other Lightweight Block Ciphers”, 4th International Conference on Constructive Side-Channel Analysis and Secure Design (COSADE’13), Springer Berlin Heidelberg 2013, LNCS 7864, pp. 62-79. doi: 10.1007/978-3-642-40026-1_5
  5. L. Hemme and L. Hoffman, “Differential Fault Analysis on the SHA1 Compression Function”, 2011 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC), 2011, pp 54-62. doi: 10.1109/FDTC.2011.16
  6. D. Boneh, R.A. DeMillo, R.J. Lipton, “On the Importance of Checking Cryptographic Protocols for Faults”, International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’97), Springer Berlin Heidelberg 1997, LNCS 1233, pp. 37-51. doi: 10.1007/3-540-69053-0_4
  7. D. Boneh, R.A. DeMillo, R.J. Lipton, “On the Importance of Eliminating Errors in Cryptgraphic Computations”, Journal of Cryptography, 14(2): pp. 101-119, 2001. doi: 10.1.1.42.7009
  8. E. Biham and A. Shamir, “Differential fault analysis of secret key cryptosystems”, 17th International Cryptology Conference (CRYPTO '97), Springer Berlin Heidelberg 1997, LNCS 1294, pp. 513-525. doi: 10.1007/BFb0052259
  9. M. Hojsik and B. Rudolf, “Differential fault analysis of Trivium”, 15th International Workshop of Fast Software Encryption (FSE’08). Springer Berlin Heidelberg 2008, LNCS 5086, pp. 158-172. doi: 10.1007/978-3-540-71039-4_10
  10. N. Courtois, D. Ware, K. Jackson, “Fault-Algebraic Attacks on Inner Rounds of DES”, European Smart Card Security Conference (eSmart’10), 2010, pp. 22-24.
  11. R. Li, C. Li, C. Gong, “Differential fault analysis on SHACAL-1”, 2009 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC), 2009, pp 120-126. doi: 10.1109/FDTC.2009.41
  12. P. Dusart, G. Letourneux, O. Vivolo, “Differential Fault Analysis on A.E.S.”, 1st International Conference of Applied Cryptography and Network Security (ACNS’03), Springer Berlin Heidelberg 2003, LNCS 2846, pp. 293-306.doi: 10.1007/978-3-540-45203-4_23
  13. J. Hoch and A. Shamir, “Fault Analysis of Stream Ciphers”, 6th International Workshop on Cryptographic Hardware and Embedded Systems (CHES’04), Springer Berlin Heidelberg 2004, LNCS 3156, pp. 41-51. doi: 10.1007/978-3-540-28632-5_18
  14. E. Biham, L. Granboulan, P. Q. Nguyen, “Impossible Fault Analysis of RC4 and Differential Fault Analysis of RC4,” 12th International Workshop of Fast Software Encryption (FSE’05), Springer Berlin Heidelberg 2005, LNCS 3557, pp. 359-367. doi: 10.1007/11502760_24
  15. M. Agoyan, J.-M. Dutertre, D. Naccache, B. Robisson, A. Tria, “When clocks fail: On critical paths and clock faults”, the ninth Smart Card Research and Advanced Application IFIP Conference (CARDIS’10), Springer Berlin Heidelberg 2010, LNCS 6035, pp. 182-193. doi: 10.1007/978-3-642-12510-2_13
  16. H. Bar-El, H. Choukri, D. Naccache, M. Tunstall, C. Whelan, “The Sorcerer’s Apprentice Guide to Fault Attacks”, Proceedings of the IEEE, vol.94, issue.2, pp. 370-382, doi: 10.1109/JPROC.2005.862424
  17. A. Barenghi, L. Breveglieri, I. Koren, D. Naccache, “Fault injection attacks on cryptographic devices: Theory, practice and countermeasures”, Proceedings of the IEEE, vol.100, issue.11, pp. 3056-3076, doi: 10.1109/JPROC.2012.2188769
  18. O. Dunkelman, N. Keller, A. Shamir, “ALRED blues: New attacks on AES-based MACs”, Cryptology ePrint Archive, Report 2011/095. [Online]. Available: http://eprint.iacr.org/2011/095
  19. M. Soos, K. Nohl, C. Castelluccia, “Extending SAT Solvers to Cryptographic Problems”, Twelfth International Conference on Theory and Applications of Satisfiability Testing (SAT’09), Springer Berlin Heidelberg 2009, LNCS 5584, pp. 244-257. doi: 10.1007/978-3-642-02777-2_24
  20. Y. Sasaki, “Cryptanalyses on a Merkle- Damgård Based MAC—Almost Universal Forgery and Distinguishing-H Attacks”, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’12), Springer Berlin Heidelberg 2012, LNCS 7237, pp. 411-427. doi: 10.1007/978-3-642-29011-4_25
  21. J. Kang, K. Jeong, J. Sung, S. Hong, “Differential Fault Analysis on HAS-160 Compression Function”, The 4th FTRA International Conference on Computer Science and its Applications (CSA’12), Springer Berlin Heidelberg 2012, LNEE 203, PP. 97-105. doi: 10.1007/978-94-007-5699-1_11
  22. L. Wei, T. Zhi, G. Dawu, W. Yi, L. Zhiqiang, L. Ya, “Differential Fault Analysis on the MD5 Compression Function”, Journal of Computers, 8(11): pp. 2888-2894, Nov 2013. doi:10.4304/jcp.8.11.2888-2894
  23. M. Hojsik and B. Rudolf, “Floating fault analysis of Trivium”, 9th International Conference on Cryptology in India (INDOCRYPT’08), Springer Berlin Heidelberg 2008, LNCS 5365, pp. 239-250. doi: 10.1007/978-3-540-89754-5_19
  24. L. Song, L. Hu, “Differential Fault Attack on the PRINCE Block Cipher”, Second International Workshop on Lightweight Cryptography for Security and Privacy (LightSec’13), Springer Berlin Heidelberg 2013, LNCS 8162, pp. 43-54. doi: 10.1007/978-3-642-40392-7_4
  25. V. Ganesh and D.L. Dill, “A Decision Procedure for Bit-Vectors and Arrays”, 19th International Conference on Computer Aided Verification (CAV’07), Springer Berlin Heidelberg 2007, LNCS 4590, pp. 519-531. doi: 10.1007/978-3-540-73368-3_52
  26. X. Zhao, S. Guo, F. Zhang, Z. Shi, C. Ma, T. Wang, “Improving and Evaluating Differential Fault Analysis on LED with Algebraic Techniques”, 2013 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC), 2013, pp 120-126. doi: 10.1109/FDTC.2013.14
  27. N. Mouha, and B. Preneel, “Towards Finding Optimal Differential Characteristics for ARX: Application to Salsa20”, Cryptology ePrint Archive, Report 2013/359. [Online]. Available: http://eprint.iacr.org/2013/359.pdf
  28. M. Soos (2013), “CryptoMiniSat2”. [Online]. Available: http://www.msoos.org/cryptominisat2/
  29. M. Mohamed, S. Bulygin, J. Buchmann, “Improved Differential Fault Analysis of Trivium”, Second International Workshop on Constructive Side-Channel Analysis and Secure Design (COSADE’11), 2011, pp. 147-158.
  30. C. Bouillaguet, P. Derbez, P.-A. Fouque, “Automatic Search of Attacks on Round-Reduced AES and Applications”, 31st International Cryptology Conference (CRYPTO’11), Springer Berlin Heidelberg 2011, LNCS 6841, pp. 169-187. doi: 10.1007/978-3-642-22792-9_10
  31. P. Jovanovic, M. Kreuzer, I. Polian, “An Algebraic Fault Attack on the LED Block Cipher”, Cryptology ePrint Archive, Report 2012/400. [Online]. Available: http://eprint.iacr.org/2012/400.pdf
  32. N.T. Courtois, J. Pieprzyk, “Cryptanalysis of Block Ciphers with Overdefined Systems of Equations”, 8th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’02), Springer Berlin Heidelberg 2002, LNCS 2501, pp. 267-287. doi: 10.1007/3-540-36178-2_17
  33. G. Piret, J.-J. Quisquater, “A Differential Fault Attack Technique against SPN Structures, with Application to the AES and KHAZAD”, 5th International Workshop on Cryptographic Hardware and Embedded Systems (CHES’03), Springer Berlin Heidelberg 2003, LNCS 2779, pp. 77-88. doi: 10.1007/978-3-540-45238-6_7
  34. M. Tunstall, D. Mukhopadhyay, S. Ali, “Differential Fault Analysis of the Advanced Encryption Standard Using a Single Fault”, 5th IFIP WG 11.2 International Workshop on Security and Privacy of Mobile Devices in Wireless Communication (WISTP’11), Springer Berlin Heidelberg 2011, LNCS 6633, pp. 224-233. doi: 10.1007/978-3-642-21040-2_15
  35. K. Jeong and C. Lee, “Differential Fault Analysis on Block Cipher LED-64”, 7th FTRA International Conference on Future Information Technology (FutureTech’12), Springer Berlin Heidelberg 2012, LNEE 164, pp. 747-755. doi: 10.1007/978-94-007-4516-2_79
  36. P. Jovanovic, M. Kreuzer, I. Polian, “A Fault Attack on the LED Block Cipher”, 3rd International Conference on Constructive Side-Channel Analysis and Secure Design (COSADE’12), Springer Berlin Heidelberg 2012, LNCS 7275, pp. 120-134. doi: 10.1007/978-3-642-29912-4_10
  37. Jeong, K.: Differential Fault Analysis on Block Cipher Piccolo. Cryptology ePrint Archive, Report 2012/399. [Online]. Available: http://eprint.iacr.org/2012/399.pdf
  38. K. Jeong, Y. Lee, J. Sung, S. Hong, “Security Analysis of HMAC/NMAC by Using Fault Injection”, Journal of Applied Mathematics, 2013(17). doi: 10.1155/ 2013/101907
  39. W. Fischer and C.A. Reuter, “Differential Fault Analysis on Grøstl”, 2012 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC), 2012, pp. 44-54. doi: 10.1109/FDTC.2012.14

    Sorry, there are no citation(s) for this manuscript yet.