JIS  Vol.4 No.3 , July 2013
Diffusion Analysis of Message Expansion in STITCH-256

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.

Cite this paper: N. Jamil, R. Mahmod, M. Z’aba, N. Udzir and Z. Zukarnain, "Diffusion Analysis of Message Expansion in STITCH-256," Journal of Information Security, Vol. 4 No. 3, 2013, pp. 129-137. doi: 10.4236/jis.2013.43015.

[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.

[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.

[11]   M. Stevens, “Single-Block Collision Attack on MD5,” 2012.

[12]   T. Xie and D. Feng, “Construct MD5 Collisions Using Just a Single Block of Message,” 2010.

[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.