1. Introduction
Recent advances in the cryptanalysis of hash functions [1-12], to name a few, have led to the unexpected failure of some popular algorithms, such as MD4, MD5, SHA-0, SHA-1, HAVAL-128, and RIPEMD. From this cryptanalysis, we understand that these broken hash functions can have two distinct messages yielding the same hash value, known as a collision. The new cryptanalysis techniques introduced by Wang et al. [13-16] provided this breakthrough in cryptography, finding collisions for MD4, MD5, SHA-0, SHA-1, HAVAL-128, and RIPEMD. It was found that the most successful attack on these hash functions is a differential attack, whereby a difference in the messages leads to zero difference in the output of the hash function. In other words, the collision is obtained by constructing a collision path, or characteristic, that fulfills certain conditions with respect to the message differences. In SHA-0, SHA-1, and the MD-family of hash functions, a message with a small difference in the expanded keys is first obtained. This is then used to construct a collision path in the step transformation. This paper focuses only on the first part, which is the message expansion.
Briefly, message expansion in the SHA-family is performed by recursive expansion. In SHA-1, for example, the message expansion accepts a 512-bit input that is divided into sixteen 32-bit words
. Sixty-four additional expanded message words are generated as follows:
Message expansion in SHA-1 differs from that of SHA-0 only in the rotation of one bit to the left. The 80 words can be considered to constitute a linear code over F2. Due to the quasi-cyclic nature of message expansion in SHA-0 and SHA-1, the full collision path can easily be constructed, as in the attack by Wang et al. This can be seen, for example, in SHA-0 message expansion, where differential characteristics with a probability of 1 can easily be constructed in the first 16 steps, as a single bit difference affects fewer than 28 bits in the output. In SHA-1, the code gives a minimum weight of no more than 44 for the full rounds. These traits were exploited by Wang et al. in order to find a collision path for the whole hash function with a complexity of 269 hash operations [14].
As a consequence of the work by Wang et al., the MD-family and SHA-0/1 hash functions are no longer suitable for secure communications. SHA-256 has now become the recommended hash function for many applications that require secure communication. The message expansion in SHA-256 is slightly different from its predecessors. It is the first hash function to use nonlinear modular addition in its message expansion, and successfully increases the minimum Hamming weight of the output bits from 44 (in a full round of SHA-1 message expansion) to 507 for a single-bit difference over a full round. To the best of our knowledge, no optimal lower bound on the minimum weight of the output bits has yet been found by the cryptographic community. However, it is important to have a high minimum weight for a single-bit difference over a full round of message expansion to prevent an attacker from constructing a collision path. This is because of a useful heuristic, often used in the analysis of SHA-0 and SHA-1, suggests that each weight of the output bits lowers the probability of successful collision characteristics by, on average, a factor of 2−2.5 [6].
STITCH-256 [17] is a dedicated cryptographic hash function that also employs message expansion as a source of diffusion. In this paper, we describe the message expansion process in STITCH-256 and compare it with that in SHA-256. This paper is organized as follows: In Sections 2 and 3, we briefly describe the message expansion methods of SHA-256 and STITCH-256, respectively. We then analyze the diffusion property of the two message expansion procedures in Section 4, and show that the minimum weight of the STITCH-256 output bits is higher than the minimum weight of the SHA-256 output bits. Finally, we offer some concluding remarks in Section 5.
2. Message Expansion of SHA-256
In this section, we briefly describe the message expansion process of SHA-256. We use the notation shown in Table 1 throughout this paper.
In SHA-256, the pre-processing involves padding followed by message expansion. A message of arbitrary length is first padded to form multiple 512-bit message blocks. Each of the message blocks is denoted by a row vector m represented by sixteen 32-bit words,
. The input message is then expanded to sixty four 32-bit words by the message expansion process, and this can be considered as a 2048-bit expanded message row vector w. The message words Wt are defined as follows:
where 
and
.
In total, there are 144 addition (modulo 32) operations and 192 XOR, rotation, and shift operations used in the message expansion of SHA-256.
3. Message Expansion of STITCH-256
In this section, we describe the message expansion procedure of STITCH-256. We use the notation in Table 1. In STITCH-256, the pre-processing again involves padding, whereby the arbitrary length message is extended to an exact multiple of 512-bits. This is followed by the message expansion, which works as follows:
where
and 
We use two salt values to support the message expansion of STITCH-256, where SV0 = 67452301 and SV1 = 41083726. In the message expansion of STITCH-256, every sixteen message words are taken into account to form the (i-16)-th message word. This is to maximize the bit propagation in the message expansion of STITCH-256. The bit rotations in the message expansion of STITCH-256 are carefully selected to increase the diffusion to the whole message expansion. The message expansion of STITCH-256 is illustrated as in Figure 1.
In STITCH-256, the 512-bit message input is expanded to thirty-two 32-bit message words. This gives the output of message expansion as 1024 bits. All the message words 
are then reordered to cater to
Figure 1. Message expansion in STITCH-256.
different message ordering in each line. The compression function of STITCH-256 requires eight 
for the whole function as described earlier and the orderings are depicted in Figure 2.
Figure 2 shows the input order of message words 
applied to Bj (1 £ j £ 4) branches. The number with an asterisk denotes the message words Wi for 16 £ i £ 31. This means 1’ refers to message words W16, 2’ refers to message word W17, so on and so forth.