logo

SCIENCE CHINA Information Sciences, Volume 59, Issue 5: 052110(2016) https://doi.org/10.1007/s11432-015-5389-4

Evaluate the security margins of SHA-512, SHA-256 and DHA-256 against the boomerang attack

More info
  • ReceivedOct 14, 2015
  • AcceptedDec 19, 2015
  • PublishedMar 10, 2016

Abstract

For an $n$-bit random permutation, there are three types of boomerang distinguishers, denoted as Type I, II and III, with generic complexities $2^{n}$, $2^{n/3}$ and $2^{n/2}$ respectively. in this paper, we try to evaluate the security margins of three hash functions namely SHA-512, SHA-256 and DHA-256 against the boomerang attack. firstly, we give a boomerang attack on 48-step SHA-512 with a practical complexity of $2^{51}$. the correctness of this attack is verified by providing a Type III boomerang quartet. then, we extend the existing differential characteristics of the three hash functions to more rounds. we deduce the sufficient conditions and give thorough evaluations to the security margins as follows: type I boomerang method can attack 54-step SHA-512, 51-step SHA-256 and 46-step DHA-256 with complexities $2^{480}$, $2^{218}$ and $2^{236}$ respectively. type II boomerang method can attack 51-step SHA-512, 49-step SHA-256 and 43-step DHA-256 with complexities $2^{158.50}$, $2^{72.91}$ and $2^{74.50}$ respectively. type III boomerang method can attack 52-step SHA-512, 50-step SHA-256 and 44-step DHA-256 with complexities $2^{223.80}$, $2^{123.63}$ and $2^{99.85}$ respectively.


Funded by

national Basic Research Program of China(973 Program)

(2013CB834205)

National Natural Science Foundation of China(61133013)

National Natural Science Foundation of China(61373142)


Acknowledgment

Acknowledgments

This work was supported by national Basic Research Program of China (973 Program) (Grant No. 2013CB834205) and National Natural Science Foundation of China (Grant Nos. 61133013, 61373142).


References

[1] Wang X Y, Yu H B. How to break {MD5} and other hash functions. In: Proceedings of 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, 2005. 19--35. Google Scholar

[2] Wang X Y, Yin Y L, Yu H B. {Finding collisions in the full {SHA-1}}. In: Proceedings of 25th Annual International Cryptology Conference, Santa Barbara, 2005. 17--36. Google Scholar

[3] Kayser R F. Federal Register, 2007, {72}: 62 Google Scholar

[4] Isobe T, Shibutani K. {Preimage attacks on reduced Tiger and {SHA-2}}. In: Proceedings of 16th International Workshop on Fast Software Encryption, Leuven, 2009. 139--155. Google Scholar

[5] Guo J, Ling S, Rechberger C, et al. {Advanced meet-in-the-middle preimage attacks: first results on full Tiger, and improved results on {MD4} and {SHA-2}}. In: Proceedings of 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 2010. 56--75. Google Scholar

[6] Khovratovich D, Rechberger C, Savelieva A. {Bicliques for preimages: attacks on Skein-512 and the {SHA-2} Family}. In: Proceedings of 19th International Workshop on Fast Software Encryption, Washington, DC, 2012. 244--263. Google Scholar

[7] Mendel F, Pramstaller N, Rechberger C, et al. {Analysis of step-reduced {SHA-256}}. In: Proceedings of 13th International Workshop on Fast Software Encryption, Graz, 2006. 126--143. Google Scholar

[8] Sanadhya S K, Sarkar P. {New collision attacks against up to 24-step {SHA-2}}. In: Proceedings of 9th International Conference on Cryptology in India, Kharagpur, 2008. 91--103. Google Scholar

[9] Nikolic I, Biryukov A. {Collisions for step-reduced {SHA-256}}. In: Proceedings of 15th International Workshop on Fast Software Encryption, Lausanne, 2008. 1--15. Google Scholar

[10] Indesteege S, Mendel F, Preneel B, et al. {Collisions and other non-random properties for step-reduced {SHA-256}}. In: Proceedings of 15th International Workshop on Selected Areas in Cryptography, Sackville, 2008. 276--293. Google Scholar

[11] Mendel F, Nad T, Schl{ä}ffer M. {Finding {SHA-2} characteristics: searching through a minefield of contradictions}. In: Proceedings of 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, 2011. 288--307. Google Scholar

[12] Mendel F, Nad T, Schl{ä}ffer M. {Improving local collisions: new attacks on reduced {SHA-256}}. In: Proceedings of 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, 2013. 262--278. Google Scholar

[13] Lee J, Chang D, Kim H, et al. {A new 256-bit hash function DHA-256: enhancing the security of SHA-256}. In: Proceedings of Cryptographic Hash Workshop Hosted by NIST, 2005. \url{https://cse.sc.edu/ buell/csce557/NIST_SHA/ChangD_DHA256.pdf}. Google Scholar

[14] Wagner D. {The boomerang attack}. In: Proceedings of 6th International Workshop on Fast Software Encryption, Rome, 1999. 156--170. Google Scholar

[15] Kelsey J, Kohno T, Schneier B. {Amplified boomerang attacks against reduced-round {MARS} and Serpent}. In: Proceedings of 7th International Workshop on Fast Software Encryption, New York, 2000. 75--93. Google Scholar

[16] Biham E, Dunkelman O, Keller N. {The rectangle attack---rectangling the Serpent}. In: Proceeding of International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, 2001. 340--357. Google Scholar

[17] Biham E, Dunkelman O, Keller N. {Related-Key boomerang and rectangle attacks}. In: Proceedings of 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, 2005. 507--525. Google Scholar

[18] Biryukov A, Nikolic I, Roy A. {Boomerang attacks on {BLAKE-32}}. In: Proceedings of 18th International Workshop on Fast Software Encryption, Lyngby, 2011. 218--237. Google Scholar

[19] Lamberger M, Mendel F. {Higher-order differential attack on reduced {SHA-256}}. {IACR} Cryptology ePrint Archive. 2011. 37. \url{https://eprint.iacr.org/2011/037.pdf}. Google Scholar

[20] Biryukov A, Lamberger M, Mendel F, et al. {Second-order differential collisions for reduced {SHA-256}}. In: Proceedings of 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, 2011. 270--287. Google Scholar

[21] Mendel F, Nad T. {Boomerang distinguisher for the {SIMD-512} compression function}. In: Proceedings of 12th International Conference on Cryptology in India, Chennai, 2011. 255--269. Google Scholar

[22] Sasaki Y, Wang L. {Distinguishers beyond three rounds of the {RIPEMD-128/-160} compression functions}. In: Proceedings of 10th International Conference on Applied Cryptography and Network Security, Singapore, 2012. 275--292. Google Scholar

[23] Sasaki Y, Wang L, Takasaki Y, et al. {Boomerang distinguishers for full {HAS-160} compression function}. In: Proceedings of 7th International Workshop on Security, Fukuoka, 2012. 156--169. Google Scholar

[24] Leurent G, Roy A. {Boomerang attacks on hash function using auxiliary differentials}. In: Proceedings of the Cryptographers' Track at the {RSA} Conference, San Francisco, 2012. 215--230. Google Scholar

[25] Yu H B, Chen J Z, Wang X Y. {The boomerang attacks on the round-reduced Skein-512}. In: Proceedings of 19th International Conference on Selected Areas in Cryptography, Windsor, 2012. 287--303. Google Scholar

[26] Kircanski A, Shen Y Z, Wang G L, et al. {Boomerang and slide-rotational analysis of the {SM3} hash function}. In: Proceedings of 19th International Conference on Selected Areas in Cryptography, Windsor, 2012. 304--320. Google Scholar

[27] Bai D X, Yu H B, Wang G L, et al. {Improved boomerang attacks on {SM3}}. In: Proceedings of 18th Australasian Conference on Information Security and Privacy, Brisbane, 2013. 251--266. Google Scholar

[28] Bai D X, Yu H B, Wang G L, et al. IET Inf Secur, 2015, 9: 167-178 Google Scholar

[29] AlTawy R, Kircanski A, Youssef A M. Inf Process Lett, 2013, 113: 764-770 Google Scholar

[30] Menezes A, van Oorschot P C, Vanstone S A. {Handbook of Applied Cryptography}. Boca Raton: {CRC} Press, 1996. Google Scholar

[31] US Department of Commerce. National Bureau of Standards, Secure Hash Algorithm, FIPS PUB 180-3. 2008. Google Scholar

[32] Wagner D. {A generalized birthday problem}. In: Proceedings of 22nd Annual International Cryptology Conference, Santa Barbara, 2002. 288--303. Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号