Diffusion Analysis of Message Expansion in STITCH-256

Norziana Jamil, Ramlan Mahmod, Muhammad Reza Z’aba, Nur Izura Udzir, Zuriati Ahmad Zukarnain

College of Information Technology, Universiti Tenaga Nasional, Kajang, Malaysia.
Cryptography Lab, MIMOS Berhad, Technology Park Malaysia, Bukit Jalil, Malaysia.
Faculty of Computer Science and Information Technology, Universiti Putra Malaysia, Seri Kembangan, Malaysia.

DOI: 10.4236/jis.2013.43015                

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 expansion in their pre-processing stage. However, STITCH-256 was claimed to produce high diffusion in its message expansion. 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 analyzed 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 expansion 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 characteristic in the message expansion of STITCH-256 is reduced.

Keywords

STITCH-256; Message Expansion; Diffusion; Hash Function

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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
[2]	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
[3]	E. Biham and R. Chen, “New Results on SHA-0 and SHA-1,” 2004.
[4]	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
[5]	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
[6]	E. Grechnikov, “Collisions for 72-Step and 73-Step SHA-1: Improvements in the Method of Characteristics,” 2010. http://eprint. iacr.org.
[7]	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
[8]	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
[9]	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
[10]	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
[11]	M. Stevens, “Single-Block Collision Attack on MD5,” 2012. http://eprint.iacr.org/2012/040.pdf
[12]	T. Xie and D. Feng, “Construct MD5 Collisions Using Just a Single Block of Message,” 2010. http://eprint.iacr.org/2010/643.pdf
[13]	X. Wang, D. Feng, X. Lai and H. Yu, “Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD,’ 2004.
[14]	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
[15]	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
[16]	C. Jutla and A. Patthak, “A Simple and Provably Good Code for SHA Message Expansion,” 2005.
[17]	N. Jamil, R. Mahmod, M. Zaba, N. Udzir and Z. Zukarnain, “STITCH-256: A Dedicated Cryptographic Hash Function,” Journal of Applied Sciences, Vol. 12, 2012, pp. 1526-1536. doi:10.3923/jas.2012.1526.1536
[18]	J. Liu, H. Jiang and S. Huang, “Nonlinear Message Expansion for Hash Function,” Computer Science and Information Technology, 2008, pp. 779-784.