Cryptographic hash functions are an important primitive deployed in many applications and protocols for secure communication. Their main objective is to provide data (or message) integrity. The computation of a hash function over a particular message yields a message digest, sometimes referred to as the hash value or hash code. A message is said to be of no integrity if the hash value of the message after transmission does not match the hash value of the message before transmission. Thus, the integrity of the original message can be verified from the hash value of the message itself. In principle, a hash function is a function H that accepts a message of arbitrary length * and produces a message of fixed length n via a compression function f, H: [0, 1]*→[0, 1]n. Cryptographic hash functions are not the same as the common hash function used in a look-up table for passwords. In principle, cryptographic hash functions must fulfill three basic cryptographic properties: preimage resistance, second preimage resistance and collision resistance. These properties are explained as follows.
||Preimage resistance: Given any hash value y, it is
infeasible to find its corresponding message m. This property is also known
as one-wayness. The hash function is considered to be preimage resistant
if the complexity of finding the corresponding message is equal to or greater
||Second preimage resistance: Given a message m and its corresponding
hash value H(m), it is infeasible to find another message m', where m ≠
m', such that H(m) = H(m'). Suppose that second preimage resistance also
implies preimage resistance; therefore, the complexity of finding a message
m' through a brute force attack is also 2n
||Collision resistance: Given a hash value H(m), it is infeasible
to find any two random messages m and m', where m ≠ m', such that H(m)
= H(m'). For a collision-resistant hash function, the fastest way to find
m and m' is with a birthday attack which has a complexity of 2n/2
In the past, most cryptographic applications used MD-family hash functions,
such as MD4 (Rivest, 1992a) and MD5 (Rivest,
1992b), SHA-family hash functions, such as SHA-0 (NIST,
1993) and SHA-1 (NIST, 1995), RIPEMD (Bosselaers
and Preneel, 1995) and HAVAL (Zheng et al., 1993).
These hash functions survived for more than a decade until, in 2004. A powerful
techniques based on differential attack to find a pair of colliding messages
was presented by Wang and Yu (2005) and Wang
et al. (2005a-c). However, RIPEMD-128/160
and SHA-2 (NIST, 2002) family hash functions are still
secure and resistant against Wang et al.s attacks.
RIPEMD-128/160 has different structures than that of MD and SHA family hash
functions. The compression function consists of two parallel branches having
the same step operations of MD5 and SHA algorithm. However, this structure results
in its efficiency was degenerated almost half of them. This is described by
and they introduced FORK-256 Hong et al. (2006)
to overcome the problem in RIPEMD. FORK-256 has four parallel branches as compared
to two in RIPEMD-128/160, but with less number of step operations in each branch.
However, the memory requirement in FORK-256 is bigger than that of RIPEMD-320.
Furthermore, Matusiewiez et al. (2006) and Matusiewiez
et al. (2007) showed that a near-collision can be constructed for
a complete version of FORK-256 with a complexity of 2125 hash computation.
Using Matusiewiezs technique, Contini et al.
(2007) showed that it can be extended to find full collisions for a complete
version of FORK-256.
From the weaknesses found in MD-4/5, SHA-0/1, RIPEMD and FORK-256 hash functions,
we proposed a dedicated cryptographic hash function, STITCH-256. It was designed
with more careful observations in all of its components. We also carefully selected
cryptographically strong Boolean functions from a set of one dimensional Cellular
Automata (CA) rules and used them in STITCH-256 step operations. Recent research
on cryptography based on CA can be found (Ayanzadeh et
al., 2009; Ayanzadeh et al., 2012; Jaberi
et al., 2012). We analyzed the security of all of the components
of STITCH-256 and compared with the other hash functions discussed earlier.
DESCRIPTIONS OF MD-4/5, SHA-0/1/2, RIPEMD AND FORK-256
Here, we briefly describe the widely used hash functions such as MD-4/5, SHA-0/1/2 and RIPEMD and recently introduced hash function, FORK-256. The notation used throughout this study is given in Table 1.
MD-4/5: MD-4 was born in 1990 and performed excellently on 32-bit software
architecture. The design was novel and was expected to provide high security.
However, it was less than a year after its born, found that the security
level of MD4 was not up to the expectation. collisions for reduced versions
of the algorithm (Den Boer and Bosseleras, 1991; Dobbertin,
||The structure of MD4 hash function (Martin and Oswald, 2006)
MD-5 was born a year after MD4, introduced to be the improved version of MD4.
Both MD-4 and MD-5 process 512-bit input message and produce 128-bit output
message. MD-4 and MD-5 have 3 and 4 rounds for a single iteration, respectively.
The step operation in MD4 is depicted in Fig. 1. The followings
are the Boolean functions used in MD-4:
F(X, Y, Z) = X∧Y∨~X∧Z
G(X, Y, Z) = X∧Y∨X∧Z∨Y∧Z
H(X, Y, Z) = X⊕Y⊕Z
where, ∧, ∨ and ⊕ are bitwise AND, OR and XOR operations, respectively.
Functions F, G and H are used in different round. MD-5 is slightly different
in that it has four Boolean functions used in different round. The step operation
in MD-5 adds in a unique additive constant and the rotation constant values
are different for the 64 rounds in the full algorithm. The details of MD-4/5
can be found in (Rivest, 1992a, b).
SHA-0/1/2: SHA family hash functions were designed by NSA and published by NIST as federal standard FIPS.
||The step operation of functions SHA-0 and SHA-1
The design principle of SHA-0 was not disclosed but it was similar to that
of MD-4. SHA-1 is the improvement to SHA-0. SHA-2 family hash functions were
introduced in 2002 offering a longer hash value to increase the security level
of the algorithms against birthday attacks. The step operation for SHA-1 is
depicted in Fig. 2. SHA family hash functions are interesting
as they used recursive functions for their message expansion. The details of
SHA-0/1/2 can be found in NIST (1993, 1995,
RIPEMD: The designs of RIPEMD family hash functions are based on MD-4,
in which the only difference is RIPEMD has two parallel branches in its compression
function. Both parallel branches have similar step operation of MD-4. The step
operation for RIPEMD is depicted in Fig. 3 and the details
of RIPEMD hash functions (Preneel et al., 1997).
FORK-256: FORK-256 maps 256 bits of state and 512 bits of message to
256 bits of hash value. The compression function of FORK-256 consists of four
parallel branches as illustrated in Fig. 4. FORK-256 employs
fewer operations as compared to SHA-256 to maintain the efficiency of the algorithm.
Note that a major difference in FORK-256, as compared to the other hash functions,
is several words impact more than one word in a step operation. The details
of FORK-256 can be found by Hong et al. (2006)
and the step operation of FORK-256 is illustrated in Fig. 5.
The cryptanalysis shows that these hash functions have several weaknesses.
||The compression function of RIPEMD
We outline the weaknesses as follows:
||Some of the message expansion procedures in these hash functions
are linear functions which lead to poor diffusion
||Certain mathematical operations have unexpected security problems. This
could probably due the weakness exposed by the Boolean functions used in
the compression function
||Similar message expansion procedure (i.e., close distance for two message
words) for parallel branches (for RIPEMD hash function) leads to similar
patterns for differential characteristics
||Light step operations and similar constants are used in different round
in step operations. This leads to poor bit propagation and differential
characteristics can be constructed easily
||As in the MD, SHA and RIPEMD family hash functions, the output from Boolean
functions that takes three words only affects one word in every single round.
This leads several input words to be controllable by the attacker to produce
a particular output word. In other word, the output words of Boolean function
are used to update only one chaining variable
Observing the weaknesses above, we propose a dedicated cryptographic hash function, STITCH-256, to overcome the problems raised in these hash functions.
DESCRIPTION OF STITCH-256
STITCH-256 is a cryptographic hash function that accepts a message of arbitrary length and produces one of fixed size. It has four main components, namely padding, message expansion, compression function and step operation. In the first component, the arbitrary input message is first padded by a single bit 1 next to the least significant bit of the message, followed by zero as many as possible until the length of the message is 448 modulo 512. At least one bit and at most 512 bits are appended to the message. This is then followed by a 64-bit unsigned big-endian representation of message length modulo 264 to the message. This procedure ensures that the length of the padded message is a multiple of 512. Padding for STITCH-256 can be represented as:
M ← m || 10000
This is also known as MD-strengthening (Merkle, 1989;
Damgard, 1989) which allows the function to be resistant
against fixed point and message expansion attacks.
Every message block M is then expanded into several 32-bit message words in a procedure called message expansion.
Message expansion of STITCH-256: To proceed to the iterated hash, each successive 512-bit message block M is expanded into thirty two 32-bit message words Wi according to the following formulas:
Wt = Mt for 0≤t≤15
Wt = ROT11 (s0(Wi-16, Wi-15, Wi-14, Wi-13)+s1(Wi-12, Wi-11, Wi-10, Wi-9)⊕SV0)+ROT13(s0(Wi-8, Wi-7, Wi-6, Wi-5)+s1(Wi-4, Wi-3, Wi-2, Wi -1)⊕SV1) for 16≤t≤32
where, σ0(w, x, y, z) is w⊕x⊕y⊕z and σ1(w, x, y, z) is w+x+y+z.
We use two salt values to support message expansion in STITCH-256, namely SV0 = 67452301 and SV1 = 41083726.
The process of message expansion in STITCH-256 is illustrated in Fig. 6.
Note that the output from message expansion in STITCH-256 is thirty-two 32-bit
message words Wi. We then re-arrange the ordering of the message
words Wi according to Table 2 and we extract out
eight different message orderings where each ordering consists of sixteen 32-bit
|| Boolean functions used in the STITCH-256 compression function
|| Compression function of STITCH-256
All the eight different message orderings are used in the compression function
Compression function of STITCH-256: The compression function of STITCH-256
is inspired by the design of parallel processing as this makes any cryptographic
algorithm ready for futures architecture that would solve current speed
problem and open cryptography to a whole new range of uses. RIPEMD family hash
function is one of the examples that runs in parallel of two branches in its
compression function. However, as the step operation in both of the branches
are similar, this causes the efficiency of RIPEMD is degenerated almost half
of them. STITCH-256 has four parallel branches, B1, B2, B3 and B4 in its compression
function, as illustrated in Fig. 7.
Cvi is a 256-bit chaining variable at ith iteration, is made up of eight 32-bit word registers A, B, C, D, E, F, G and H. The initial values or the chaining variable at i=0 of STITCH-256 are the same as that used in SHA-224:
A = C1059ED8,B = 367CD507
C = 3070DD17,D = F70E5939
E = FFC00B31,F = 68581511
G = 64F98FA7,H = BEFA4FA4
Each branch processes different message orderings through the step operations. This gives eight different message orderings for the whole STITCH-256 function, two for each branch. The intermediate chaining variable CVi is updated to CVi+1 through the following process:
CVi+1 = [ CVi+B1 (CVi, Σ1(M))+B2
(CVi, Σ2(M)) ] ⊕ [CVi+B4 (CVi,
Σ4(M))+B3 (CVi, Σ3(M)) ]+CVi
where, Σj(M) is the sixteen message words of different ordering in each branch j.
|| Message expansion in STITCH-256
|| A single step transformation in STITCH-256
Each of the branches has similar step operation.
Step operation in the compression function of STITCH-256: The compression function of STITCH-256 has two wings which we simply name the left and right wings. Each wing has different step operations, different Boolean functions and different constants. We divide the step operations in STITCH-256 into two phases; the first phase serves as a heavy step operation and the second phase involves only permutation. We will use the notation of left and right wings throughout this chapter.
In the step operations of the right and left wings, two distinct Boolean functions are used in the right wing and one Boolean function is used in the left wing. In the right wing, the registers and message words are processed through seven steps, whereas for the left wing the registers are processed through six steps prior to the stitching permutation. For example, registers Ai, Bi, Ci and Di are processed in the left wing during the first phase. The processed Ai, Bi, Ci and Di are then rearranged using the stitching permutation and are processed in the right wings first phase. This means the registers are processed in two non-overlapping step operations. After being processed in the right wing, registers Ai, Bi, Ci and Di are permuted in the second phase and used to update the values of Ei+1, Fi+1, Gi+1 and Hi+1. This process occurs vice versa and in parallel, for registers Ei, Fi, Gi and Hi.
Let the outputs for the first stage (before stitching) be as follows:
Ai = D+fi((A+B), C, D)
Bi = Ci,j+fi((A+B), C, D)
Ci = B+fi((A+B), C, D)
Di = C+fi((A+B), C, D)
Ei = ROT7(Ci,j+f2(Ei,
Wi, f3(Fi, Gi, Hi)))
Fi = Ei+f2(Ei, Wi,
f3(Fi, Gi, Hi))
Gi = Fi+f2(Ei, Wi,
f3(Fi, Gi, Hi))
Hi = Gi+f2(Ei, Wi,
f3(Fi, Gi, Hi))
A single step operation in each wing updates the registers by producing the following outputs:
Ai+1 = f1((Ei+Fi),
Bi+1 = ca+f1((Ei+Fi),
Ci+1 = f1((Ei+Fi), Gi,
Di+1 = f1((Ei+Fi), Gi,
Ei+1 = ROT7(Ci,j,+f2(Ai,
Wi, f3(Bi, Ci, Di)))
Fi+1 = Ai+f2(Ai, Wi,
f3(Bi, Ci, Di))
Gi+1 = Bi+f2(Ai, Wi,
f3(Bi, Ci, Di))
Hi+1 = Ci+f2(Ai, Wi,
f3(Bi, Ci, Di))
Each wing in a branch processes sixteen message words and this makes each branch in the compression function of STITCH-256 to have only sixteen rounds of step operation. The step operation of STITCH-256 is illustrated in Fig. 8.
The stitching permutation is designed to maximize the propagation of intermediate chaining variables, thus lower the probability to construct differential characteristics. The stitching permutation is illustrated in Fig. 9.
As described earlier, in the stitching permutation, the intermediate values Ivi, 0≤i≤7, from the right wing are permuted to the left wing and vice versa.
The Boolean functions used in the STITCHx-256 step transformation are shown
in Table 2. These functions are selected from balanced Cellular
Automata (CA) rules which exhibit strong cryptographic properties (Jamil
et al., 2011). Each branch uses two Boolean functions (CA rules)
and one diffusion function fd. The orderings of Boolean functions
used in the compression function of STITCH-256 are shown in Table
The step operation in each branch uses two different constants, one for each wing, derived from the first digit of π. Table 3 shows the eight different constants used in the compression function of STITCH-256.
Each of the components in STITCH-256 is designed to maximize the diffusion property of the function and to resist known generic attacks with efficient implementation in mind. To achieve these objectives, the design strategy for each of the component is described in the following chapter.
Message expansion in STITCH-256: The principle behind the design of
the message expansion process in STITCH- 256 is this: we want to involve the
previous 16 message words to get a new value for the expanded message word.
|| Stitching permutation
||Boolean functions used in the compression function of STITCH-256
We choose the rotation that maximizes the diffusion in the STITCH-256 message
expansion. The motivation for high diffusion in message expansion comes from
the fact that the larger the minimum weight introduced in the message expansion,
the more difficult it is to construct a collision path (Wang
et al., 2005c).
Though the step operation in the right wing is not the reverse process of step
operation in the left wing, we believe that the message differences that appear
in the right wing can still be cancelled by a disturbance-correction strategy
(Chabaud and Joux, 1998) with non-negligible probability.
To avoid this from happening, each wing in a branch accepts a different message
ordering to prevent an attacker from constructing a collision path with a high
probability of success. This gives a total of eight message orderings in the
compression function of STITCH-256 and each ordering consists of sixteen 32-bit
message words. The message orderings are designed based on the following design
||Each ordering has a different arrangement of message words,
such that the sum of every element in a column is 60 and the sum of every
element in a row is 120
||For a single step transformation, two different message orderings are
used simultaneously in each branch
Table 4 shows the message orderings in STITCH-256. The number with 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 forth and so on.
With this arrangement, we confuse the attacker who aims at constructing a differential characteristic with high probability (Table 5).
Compression function of STITCH-256: The compression function of STITCH-256
is designed to have parallel branches with fewer operations and rounds to cater
both security and speed.
|| Message orderings (MO) for four branches
|| Constants used in each branch
The choice of four parallel branches comes from the result of our experiment
that shows less than four parallel branches having similar step operations such
as that in four branches do not maximize the functions diffusion.
Step operation: The strategies for step operation are as follows:
||The output from a single Boolean function is distributed to
all of the registers. This is to maximize the bit propagation of intermediate
||Double permutations are introduced to maximize the bit propagation in
a single round
||Only cryptographically strong Boolean functions are used in the step operation
to confuse the attacker who aims at constructing the relationship between
in the input and the output bits. One diffusion function fd is
introduced in each branch, fd = x⊕y⊕z
||Diffusion is also maximized by a proper selection of bit rotations and
the arrangement of addition modulo 232
||Different constants are used in every branch to randomize the pattern
of message differences
SECURITY ANALYSIS OF STITCH-256
Here, we analyze all the components in STITCH-256 to show that STITCH-256 is collision resistant against known generic attacks.
Message expansion: In the message expansion of STITCH-256, every 16
message words are taken into account to form the (i-16)th message word. This
maximizes bit propagation in the message expansion of STITCH-256. The bit rotations
in this message expansion method are carefully selected to increase the diffusion
of the whole message expansion. The strength of the message expansion can be
measured by the effect of a single bit difference in a factor of 2-2.5
(Jutla and Patthak, 2009). It means that each weight
in the expanded message words lowers the probability of successful collision
characteristics by, on average, a factor of 2-2.5. In the message
expansion of STITCH-256, the effect from a single bit difference has caused
an average of 215 bits in the expanded message words to change. Furthermore,
the lowest minimum weight found by a single bit difference in a full 32 rounds
of message expansion in STITCH-256 is 171. This gives a probability of 2-2.5x171
for an attacker to successfully construct a collision characteristic in the
message expansion of STITCHx-256. This tells that it is infeasible to construct
a collision characteristic in the message expansion of STITCH-256 with a high
The main objective of having message orderings in the compression function of STITCH-256 is to make the effort of an attacker to construct collision characteristics in the compression function of STITCH-256 becomes useless. This is because, in order for an attacker to construct one, he needs to construct similar characteristics for all the branches having different message orderings. This seems to be impossible because the probability to find a collision in one branch is already 2.2-128, as one branch has two wings taking different message orderings.
Compression function: Assume that the attacker inserts a message difference Δm = m-m, to the i-th branch and suppose the output difference Δi is produced. The attacker expects that a collision might occur if the following event is satisfied:
Say the attacker simplify the operation by denoting (CV+Δ1) as α and (CV+Δ4+Δ3) as β. There are several strategies that the attacker can take to fulfill this event. For every strategy, we provide the arguments on how to defeat the strategies
||The attacker constructs α+Δ2 = -(β+Δ3+CV)
to have a collision to occur. He can also reduce the complexity by constructing
Δ2 = -Δ3 and α = -(β+CV). However differential pattern
of the message words Δ2 = -Δ3 is difficult to achieve because
the output of each branch is random. Therefore the probability to construct
the differential pattern to occur with high probability is close to 2-128.
||The attacker constructs two distinct differential characteristics and
expects that α = - Δ2 and β = -Δ3. However, this is
also difficult to construct since both α and β contain random
output differential Δ in branch 1 and 4. Message reordering and bit
propagation in a stitching way increase the probability for an attacker
to construct differential characteristics with low probability.
Step operation: The step operation of STITCH-256 is analyzed from the perspective of differential attack since this is the most successful attacks to break the hash functions so far. In other words, we analyze only the property of collision resistance of STITCH-256.
To break a hash function using a differential attack, an attacker first aims to construct a collision path in each nonlinear component satisfying certain conditions. The whole collision path can be constructed when certain conditions hold for the message difference, intermediate values difference and output difference. We want to show that the probability of constructing a collision path in the step transformation of STITCH-256 is very small and the conditions to be fulfilled are large which in turn makes the attackers efforts useless.
To show this, we first linearized the step transformation of STITCH-256. For this purpose, we replaced all the Boolean functions with addition modulo 232 and rotation as the identity function. We also omitted the stitching permutation. We found a set of conditions that need to be fulfilled by applying the correction-disturbance strategy and then constructed a collision path for a linearized version of STITCH-256 by determining the number of steps where the difference between intermediate values is zero. This is also referred to as inner collision.
To do this, we introduced a disturbance in bit i = 1 of message words Wi, where 0≤ i ≤31. The pattern of differences that we obtained for the left wing is listed in Table 6.
From Table 6, we can see that the difference becomes bigger as s increases. The condition for the left wing is complex and the disturbance cannot be corrected because the difference grows exponentially with the increasing number of steps. We introduced the same disturbance to the right wing and present the pattern of differences in Table 7.
||Correcting a single disturbance Δi introduced
in step s in a linearized variant of STITCH-256 (left wing step transformation)
||Correcting a single disturbance Δi introduced
in step s in a linearized variant of STITCH-256 (right wing step transformation)
From Table 7, it is easy to see that the disturbance cannot be corrected because the pattern is simply repeating up to step i+5. In other words, there is no way to correct the disturbance unless the attacker can find a more intelligent way to cancel it beyond step i+5. For both the left and right wing step transformations, no appropriate conditions can be built.
We first discuss the advantage of each the strengthened components as follows:
Message expansion: As the formula to expand the message in STITCH-256 is inspired by a nonlinear recursive function in SHA-256, Table 8 shows the comparison between the message expansion of STITCH-256 and SHA-256 in terms of number of operations used in the algorithms. It shows that the total number of operations used in STITCH-256 is less than that of SHA-256. Having a better security with lower number of operations seemed to be a good advantage in the message expansion of STITCH-256.
Compression function: As the security analysis shows that it is infeasible to find colliding messages in the compression function of STITCH-256. It is observed that the mode of operation used is Davies-Meyer which provides one-wayness (preimage resistance) to the function.
Step operation: Preliminary security analysis done on the step transformations of STITCH-256 showed that the compression function of STITCH-256 is collision resistant from the perspective of differential attacks, particularly using the technique used to attack MD and SHA family hash functions. Table 9 shows the number of operations used in the step transformation of STITCH-256. We compare the number of operations with that of SHA-256 and found out that STITCH-256 consumes fewer operations than SHA-256, though STITCH-256 has four parallel branches. This is partly due to the fewer number of rounds in the compression function of STITCH-256.
||The number of operations used in the message expansion of
STITCH-256 and SHA-256
|| The number of operations used in the step transformation
of STITCH-256 and SHA-256
In this study, we proposed a dedicated cryptographic hash function known as STITCH-256. The main components include message expansion, message ordering, compression function and step operation. As a result of these components, STITCH-256 became stronger from the perspective of security and was shown to be more collision resistant from the perspective of a differential attack, where no suitable condition could be constructed from the STITCH-256 step operation. Thus, it is very difficult for an attacker to construct collision characteristics during the step operation of STITCH-256. From the security analysis carried out in this study, we believe that STITCH-256 is a good candidate for cryptographic hash functions, especially in applications which collision resistance is the main sought property. However, since it is relatively new hash function, we invite the cryptographic community to further cryptanalyze STITCH-256.
This research work is supported by Ministry of Higher Education Malaysia under a Fundamental Research Grant Scheme Phase II 2010/11.