Diffusion Analysis of Message Expansion in STITCH-256
- 1 College of Information Technology, Universiti Tenaga Nasional, Kajang, Malaysia
- 2 Faculty of Computer Science and Information Technology, Universiti Putra Malaysia, Seri Kembangan, Malaysia
- 3 Cryptography Lab, MIMOS Berhad, Technology Park Malaysia, Bukit Jalil, Malaysia
- 4 Faculty of Computer Science and Information Technology, Universiti Putra Malaysia, Seri Kembangan, Malaysia
- 5 Faculty of Computer Science and Information Technology, Universiti Putra Malaysia, Seri Kembangan, Malaysia
Abstract
Cryptographic hash functions are built up from individual components, namely pre-processing, step transformation, and final processing. Some of the hash functions, such as SHA-256 and STITCH-256, employ non-linear message expan sion in their pre-processing stage. However, STITCH-256 was claimed to produce high diffusion in its message expan sion. In a cryptographic algorithm, high diffusion is desirable as it helps prevent an attacker finding collision-producing differences, which would allow one to find collisions of the whole function without resorting to a brute force search. In this paper, we analyze d the diffusion property of message expansion of STITCH-256 by observing the effect of a single bit difference over the output bits, and compare the result with that of SHA-256. We repeated the same procedure in 3 experiments of different round. The results from the experiments showed that the minimal weight in the message ex pansion of STITCH-256 is very much lower than that in the message expansion of SHA-256, i.e. message expansion of STITCH-256 produce high diffusion. Significantly, we showed that the probability to construct differential characteris tic in the message expansion of STITCH-256 is reduced.
- K. Aoki, J. Guo, K. Matusiewicz, Y. Sasaki and L. Wang, “Preimages for Step-Reduced SHA-2,” In: M. Mitsuri, Ed., Advances in Cryptology—ASIACRYPT 2009, Springer, Berlin, 2009, pp. 578-597. doi:10.1007/978-3-642-10366-7_34
- E. Biham and R. Chen, “Near-Collisions of SHA-0,” In: M. Franklin, Ed., Advances in Cryptology—Crypto 2004, Springer, Berlin, 2004, pp. 290-305. doi:10.1007/978-3-540-28628-8_18
- E. Biham and R. Chen, “New Results on SHA-0 and SHA-1,” 2004.
- A. Biryukov, M. Lamberger, F. Mendel and I. Nikolic, “Second-Order Differential Collisions for Reduced SHA-256,” In: D. H. Lee and X. Y. Wang, Eds., Advances in Cryptology—ASIACRYPT 2011, Springer, Berlin, 2011, pp. 270-287. doi:10.1007/978-3-642-25385-0_15
- F. Chabaud and A. Joux, “Differential Collisions in SHA0,” In: H. Krawczyk, Advances in Cryptology—Crypto’ 98, Springer, Berlin, 1998, pp. 56-71. doi:10.1007/BFb0055720
- E. Grechnikov, “Collisions for 72-Step and 73-Step SHA-1: Improvements in the Method of Characteristics,” 2010. http://eprint. iacr.org.
- V. Rijmen and E. Oswald, “Update on SHA-1,” In: A. J. Menezes, Ed., Topics in Cryptology—CTRSA 2005, Springer, Berlin, 2005, pp. 58-71. doi:10.1007/978-3-540-30574-3_6
- K. Matusiewicz and J. Pieprzyk, “Finding Good Differential Patterns for Attacks on SHA-1,” In: ?. Ytrehus, Ed., Coding and Cryptography, Springer, Berlin, 2006, pp. 164-177. doi:10.1007/11779360_14
- S. Manuel and T. Peyrin, “Collisions on SHA-0 in one Hour,” In: K. Nyberg, Ed., Fast Software Encryption, Springer, Berlin, 2008, pp. 16-35. doi:10.1007/978-3-540-71039-4_2
- Y. Sasaki, L. Wang and K. Aoki, “Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512,” 2009. http://eprint.iacr.org/2009/479.pdf
- M. Stevens, “Single-Block Collision Attack on MD5,” 2012. http://eprint.iacr.org/2012/040.pdf
- T. Xie and D. Feng, “Construct MD5 Collisions Using Just a Single Block of Message,” 2010. http://eprint.iacr.org/2010/643.pdf
- X. Wang, D. Feng, X. Lai and H. Yu, “Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD,’ 2004.
- X. Wang, Y. Yin and H. Yu, “Finding Collisions in the Full SHA-1,” In: V. Shoup, Ed., Advances in Cryptology—Crypto 2005, Springer, Berlin, 2005, pp. 17-36. doi:10.1007/11535218_2
- X. Wang, H. Yu and Y. Yin, “Efficient Collision Search Attacks on SHA-0,” In: V. Shoup, Ed., Advances in Cryptology—Crypto 2005, Springer, Berlin, 2005, pp. 1-16. doi:10.1007/11535218_1