2009 International Conference on Communication Software and Networks

The Evaluation Report of SHA-256 Crypt Analysis Hash Function

1

A.Arul Lawrence Selvakumar 1 ,C.Suresh Ganandhas 2 Asst. Professor, Department of Computer Science & Engineering, Oxford college of Engineering, Bangalore, India 2 Professor, Department of Computer Science & Engineering, Veltech SRS Engineering College, Chennai, India 1 aarul72@hotmail.com 2 Sureshc_me@yahooo.com

Abstract This paper describes the study of cryptographic

hash functions, one of the most important classes of primitives used in recent techniques in cryptography. The main aim is the development of recent crypt analysis hash function. We present different approaches to defining security properties more formally and present basic attack on hash function. We recall Merkle-Damgard security properties of iterated hash function. The Main aim of this paper is the development of recent techniques applicable to crypt Analysis hash function, mainly from SHA family. Recent proposed attacks an MD5 & SHA motivate a new hash function design. It is designed not only to have higher security but also to be faster than SHA-256. The performance of the new hash function is at least 30% better than that of SHA-256 in software. And it is secure against any known cryptographic attacks on hash functions. Key words: Crypt Analysis, Cryptographic

Many hash functions such as MD4 [12], MD5 [13], HAVAL [19], SHA-family [11], etc., follow that idea. Attacks on hash func tions have been focused on vanishing the dierence of intermediate values caused by the dierence of messages. On the other hand, a hash function has been considered secure if it is computationally hard to vanish such dierence in its compression function. Usually, the lower the probability of the dierential characteristic is, the harder the attack is. Therefore a step function is regarded as a good candidate if it causes a good avalanche eect in the serial structure. A function which has a good diusion property can not be so light in general. However, most step functions have been developed to be light for eciency. This may be why MD4type hash functions including SHA-1 are vulnerable to Wang et al.s collision-nding attack [1518]. RIPEMD-family [9] has somewhat dierent approach for designing a secure hash function. The attacker who tries to break members of RIPEMD-family should aim simultaneously at two ways where the message dierence passes. This design strategy is still successful because so far there is not any eective attack on RIPEMD-family except the rst proposal of RIPEMD. However, RIPEMD-family have heavier compression functions than hash functions with serial structure. For example, the rst proposal of RIPEMD consists of two lines of MD4. Total number of steps is twice as many as that of MD4. Also, the number of steps of RIPEMD-160 is almost twice as many as that of SHA-0. In this paper, we propose a new dedicated hash function FORK-256. According to the above observation, we determined the design goals as follows. It should have a 256-bit output because the security of 128 2 operations is recommended for symmetric key cryptography as the computing power increases. Its structure should be resistant against known attacks including Wang et al.s attack [15, 7, 8, 1418].

1. Introduction For cryptographic hash function, the following properties are required: Preimage resistance: it is computationally infeasible to nd any input which hashes to any pre-specied output.

Second preimage resistance: it is computationally infeasible to nd any second input which has the

same output as any specied input.

Collision resistance: it is computationally infeasible to nd a collision, i.e. two distinct

inputs that hash to the same result.

For an ideal hash function with an m-bit output, nding a m preimage or a second preimage requires about 2 operations and the fastest way to nd a collision is a birthday attack

which needs approximately 2

operations. Most dedicated hash functions which have iterative process use the Merkle-Damgard construction [6, 10] in order to hash inputs of arbitrary length. They work as follows. Let HASH be a hash function. The message X is padded to a multiple of the block length and subsequently divided into t blocks X1,, Xt. Then HASH can be described as follows:
CV0= IV; CVi = COMP (CV , Xi), 1 i t; HASH (X) = CVt,
i1

m/2

- The performance should be as competitive as that of SHA-256 2 Description of Fork-256

In this section, we will describe FORK-256. These are basic notations used in FORK-256.

where COMP is the compression function of HASH, CVi is the chaining variable between stage i and stage i + 1, and IV denotes the initial value. The most popular method of designing compression functions of dedicated hash functions is a serial successive iteration of a small step function, as like round functions of block ciphers.

A<<<
s

: Addition mod 232 : XOR (eXclusive OR) : s-bit left rotation for a 32-bit string A

978-0-7695-3522-7/09 $25.00 2009 IEEE DOI 10.1109/ICCSN.2009.50

586 588

2.1 Input Block Length and Padding An input message is processed by 512-bit block. FORK-256 pads a message by appending a single bit 1 next to the least signicant bit of the message, followed by zero or more bit 0s until the length of the message is 448 modulo 512, and then appends to the message the 64-bit original message 64 length modulo 2 . 2.2 Structure Of Fork-256 Fig. 1 depicts the outline of the compression function of FORK-256. The name FORK was originated from the gure. The compression function of FORK-256 hashes a 512bit string to a 256-bit string. It consists of four parallel branch functions, BRANCH1, BRANCH2, BRANCH3, and BRANCH4. Let CVi = (A, B, C, D, E, F, G, H) be the chaining variable of the compression function. It is initialized

Fig. 2. Step function of FORK-256, STEPj, k

to IV0which is:
A=6a09e667x B = bb67ae85x C = 3c6ef372x D = a54ff53ax E=510e527fx F= 9b05688cx G = 1f83d9abx H = 5be0cd19x Each successive 512-bit message block M is divided into sixteen 32-bit words M0, M1,, M15 and the following : computation is performed to update CVi to CVi+1
CVi+1 = CVi
{[BRANCH1 (CVi , 1(M))

Input Order of Message Words This table shows the input order of message words M0~ M15applied to BRANCHj

(1j4) functions
Table 1: Ordering rule of message words
T 1(t)
0 0 1 1 2 2 3 3 9 14 8 4 4 8 13 15 5 5 10 2 0 6 6 3 9 12 13 11 7 7 4 8 8 2 11 3 9 9 13 4 10 10 111 10 0 15 9 11 5 8 2 12 12 6 5 7 13 13 7 0 14 14 14 12 1 4

15 15 1 3 6

2(t) 14 3(t) 4(t)

7 5

151 11 6 12 10 1

BRANCH2(CVi,2(M ))]

[BRANCH3 (CVi, 3(M ))

BRANCH4(CVi,4(M ))]}, where j(M ) = (Mj (0),, Mj (15)) is the re-ordering of message words for j = 1, 2, 3, 4, given by Table 1.
2.3 Branch Functions: BRANCH j

Constants The compression function of FORK-256 uses sixteen constants given by the following table:
0 = 428a2f98x 2 = b5c0fbcfx 4 = 3956c25bx 6 = 923f82a4x 8 = d807aa98x 10 = 243185bex 12 = 72be5d74x 14 = 9dbc06a7x 1 = 71374491x 3 = e9b5dba5x 5 = 59f111f1x 7 = ab1c5ed5x 9 = 12835b01x 11 = 550c7dc3x 13 = 80deb1fex 15 = c19bf174x

Each BRANCHj is computed as follows: 1) The chaining variable CVi is copied to initial variables Vj,0 for j-th branch.
2)

At k-th step of each BRANCHj(0 k 7), the step function STEP j,k is computed as follows:
,

Vj,k+1 = STEPj,k(Vj,k, Mj(2k) Mj(2k+1), j,k, j,k), where j,k and j,k are constants.

These constants are applied to each BRANCH j according to the ordering rule of them as follows:
Step k

0 1 2 3 4 5 6 7

1, k 0 2 4 6 8 10 12 14

1,k 1 3 5 7 9 11 13 15

2, k 15 13 11 9 7 5 3 1

2,k 14 12 10 8 6 4 2 0

3, k 1 3 5 7 9 11 13 15

3,k 0 2 4 6 8 10 12 14

4, k 14 12 10 8 6 4 2 0

4, k 15 13 11 9 7 5 3 1

Step Functions: STEP j,k The input register Vj,k of STEPj,,k is divided into eight 32-bit words:

Vj,k= (Aj,k, Bj,k, Cj,k, Dj,k, Ej,k, Fj,k, Gj,k, Hj,k).

STEPj,k takes Vj,k, Mj(2k), Mj(2k+1), j,k and j,k as inputs, and then provides the output as follows (See Fig 2): Aj,k+1=Hj,k g (Ej,k Mj(2k+1)) <<<21 f (Ej,k Mj

j,k) B j, k+1 = Aj,k

(2k+1)

<<<17

Mj(2k) f (Aj,k

j,k, Mj(2k)) g(Aj,kMj (2k) j,k),

Fig.1. Outline of the FORK-256 compression function

Cj,k+1 = Bj,k
587 589

Dj,k+1 = Cj,k

f (Aj,kMj(2k))<<<5 g (Aj,k f (Aj,kMj(2k))<<<17 Mj (2k+1) j,k, Mj(2k+1))

Mj(2k)
j

, j,k)<<<9
<<<21,

Ej,k+1 = Dj,k Fj,k+1=Ej,k

g(Aj,kM (2k)

j,k)

the output one word by adjusting the input several words. The attacks on MD4, MD5, HAVAL, RIPEMD and SHA-0/1 are based on this weakness of Boolean functions. In addition,

Gj,k+1 = Fj,k g (Ej,k Hj,k+1=Gj,kg g(Ej,k

f (Ej,k Mj(2k+1))<<<9 f(Ej,k

the output words of f and g functions are used to update

M (2k+1)
j

j,k), j,k)
<<<5,

Mj(2k+1)

other chaining variables. In almost dedicated hash functions output words of boolean functions are used to update only one chaining variable. This weakness is also used to analyze

Where f and g are nonlinear functions as follows: <<< <<< f (x) = x (x 7 x 22), <<< g(x) = x (x 13 x<<<27). 3 Design Strategy

above hash functions. Shift Rotations in Nonlinear Functions If the addition is changed into the bitwise x or operation in f and g,
1 nonlinear functions are generalized as x (x x 2 ). We consider all 465 (=31C2) cases for s1and s2 and want to dene shift rotations satisfying the following 7 conditions. HW(x) denotes the Hamming Weight of x.

<<<s

<<<s

3.1 Motivation For Our Proposal

In Wang et al.s attacks on MD4, MD5, HAVAL, and RIPEMD [15, 16] and SHA-0/1 [17, 18] brought the big
impact on the eld of symmetric key cryptography including hash function. However, RIPEMD-128/160 are the algorithms which are still secure against their attacks. No attacks on them are found so far. They were designed to have two parallel lines, which is dierent from MD4, MD5 and SHA-family. This makes an attacker take into account two lines simultaneously. However, since each line needs almost same operation of MD5 and SHA algorithms, its eciency was degenerated almost half of them. This motivates our design. We use four lines

The branch number of f and g is four. If HW (input word) = 2, then HW(output word) 4. If HW (input word) = 3, then HW (output word) 3. If HW (input word) = 4, then HW (output word) 4. If HW (output word)= 1, then HW (input word) 17. If HW (output word)= 2, then HW (input word) 14. The interval of shift rotations are greater than or equal to 4. By above all conditions, we have dened f and g functions.
Ordering of Message Words We adopt the message word ordering instead of the message word extension. If an attacker constructs an intended dierential characteristics for one branch function, the ordering of message words will cause unintended dierential patterns in the other branch functions. This is the core part of the security in the compression function. When we dene the ordering of message words,

instead of two. In order to overcome disadvantage of

RIPEMD algorithms, we manage to reduce operations for step functions of each line. The message reordering of each branch is deliberately designed to be resistant against Wang et al.s attack and dierential attacks. The function f and g in each step are chosen to have good avalanche eects. 3.2 Design Principle Structure FORK-256 consists of 4 Branches. In the security aspect, we can give the security against known attacks with the dierent message-ordering in branches. For example, RIPEMD, which consists of 2 branches, was fully attacked by Wang et al. because RIPEMD has same message-ordering in 2 branches. On the other hand, in case of RIPEMD-128/160, there is no attack result because RIPEMD-128/160 have dierent message-ordering in branches. In the implementation aspect, FORK-256 can be implemented eciently be cause the message-ordering is simpler than the message expansion such as that of SHA-256. Constants Each BRANCHi uses 16 dierent constants i,j and i,j for j = 0,,7. By using constants we pursue the goal to disturb the attacker who tries to nd a good dierential characteristic with a relatively high probability. So, we prefer the constants which represent the rst thirty-two bits of the fractional parts of the cube roots of the rst sixteen four

following four conditions are considered. Balance of upper (step 0~3) and lower (step 4~7) parts: Each value is applied twice to upper and lower parts, respectively.
Balance of left and right parts: Each value is applied twice to left and right parts, respectively. Balance of sums of input orders Each word is applied four times and is indexed by 0~15. Total sum of indexes is 480. Therefore, the average of sum of indexes applied to each word is 30. We search the ordering so that the sum of indexes corresponding to each word is 25~35.

Conditions which do not have dierential patterns in all branches

same

prime numbers.
Nonlinear Functions Nonlinear functions f and g output one word with one input word. Almost dedicated hash functions use boolean functions which output one word with three words at least. The boolean functions make it easy to control

Specic dierential pattern used at a branch may be applied to other branches. Therefore, except the case of giving a same dierence to all words, we try to nd an ordering such that there is no same dierential patterns in all branches. Shift Rotations and Rank In the step function, 5 and 17, the values of shift rotation, are xed. Then we search all the case and nd candidate values (corresponding to 9 and 21) so that the rank of the linearly-changed step function is maximized. The maximum of the rank is 252. Finally we select 9 and 21 among candidate values so that dierences generated from the

588 590

outputs of f and g functions do not overlap when a message word inputted at a step function has an one-bit dierence.

So, in hash functions with a serial structure it is related to the resistance against collision-nding attack how many times an inner collision can be repeated. Let us
focus on only one branch function, say BRANCH1. We can construct 5-step inner collision pattern easily. Let A, B, ,H denote the dierences of A1,k, B1,k,,H1,k, respectively. ML and MR denote the dierences of M1 (2k) and M1 (2k+1), respectively. We found 5-step inner collision patterns of FORK-256 with the probability 240 as listed in Table 2 and 3. If we apply these patterns to BRANCH1, the 40 output dierence 1will be zero with the probability 2 . As mentioned in the previous subsection, however, it is hard to use the pattern for the attack on FORK-256 because the following events seldom occurs: either that the computation of the output dierences of the other branches is zero or that the other branches have the same dierential pattern in the message words as BRANCH1.

4 Security Analysis of Fork-256

4.1 Collision-Finding Attack

Assume that an attacker inserts the message dierence. Let I be the output dierence of i-th branch BRANCH . Then the attacker expects the following event for nding collisions: (1 2) (3 4) = 0. For this, he can take several strategies: 1. The attacker constructs a dierential characteristic with a high probability for a branch function, say
i

BRANCH1, and then expects that the operation of the output dierences in the other branches, 3 4 2 is equal to 1.

2.

3.

The attacker constructs two distinct dierential characteristics, and expects that 1= 2and 3= 4. The attacker inserts the message dierence which yields same message dierence pattern in four
branches, and expects that same dierential character istic occurs simultaneously in four branches. Then the output dierence of the compression function vanishes if the hamming weight of the output dif ference of each branch is small. This is because the nal output is generated with using and by turns.

Table 2: Case 1. 5-step inner collision pattern of FORK-256: The

numbers in the entries of the table denotes the bits in which the

dierence is 1.
Step A B C D E F G H ML MR Prob.

0 1

31 31 6,12 21,26 31 3,4 1,6 8,11 15,16 21,26 6,12 21,26 31 1,6 15,16 20,23 3,4 8,11 21,26 6,12 21,26 31 2-16

2-10

2-4 1

Let us see the rst strategy. If we assume that the outputs of each branch function are random, the probability of the event is almost close to 2256. It is also dicult for the attacker to mount any attack following the second strategy because he

Table 3: Case 2. 5-step inner collision pattern of FORK-256: The numbers in the entries of the table denotes the bits in which the dierence is 1.
Step 0 1
A B C D E F G H M L MR 31 1,6 15,16 20,23 3,4 8,11 21,26 6,12 21,26 31 31 6,12 21,26 31 3,4 1,6 8,11 15,16 21,26 20,23 6,12 3,4 21,26 8,11 21.26 31 6,12 21,26 31 Prob 2-10 2-16

should nd such dierential pattern of the message words.

Third strategy is relatively easy for the attacker to perform. For example, if he inserts the same dierence to all the message words, then the same message dierence pattern occurs in every branches. However, the message word reordering was designed so that the third strategy is satised only if the attacker inserts the same dierence to all the message words. Under the assumption that every step is independent, we can compute the upper bound of the probability that such kind of dierential characteristic

2-10

3 4

2-4 1

5. Eciency and Performance

occurs, which frustrates the attacker.

4.2 Attacks Using Inner Collision Patterns When the attacker inserts the dierences to the message words, the event that the dierence of the intermediate value becomes zero often occurs. It is called inner collision. We call a dierential characteristic which causes an inner collision with a probability, inner collision pattern. Note that an inner collision is not a real collision, but the notion of inner collision pattern is important in cryptanalysis of hash function because it can be repeatedly used to yield a real collision with a high probability. The main idea of attacks on SHA-0 and SHA-1 is also the repetition of an inner collision pattern.

In this section we compare the total number of operations and the performance of FORK-256 and SHA256. The total number of operations is compared in the Table 4, Implementations were written in C language. We denote the simulation environment as CPU/OS/Compiler. The

performance is environments:

compared

in

the

following

Table 4: Number of operations used in FORK-256 and SHA256 Operation Addition (+) Fork 256 472 SHA-256 600

589 591

Bitwise operation (, ) Shift (<<,>>) Shift rotation (<<<, >>>)

328

1024 96 576

512

P3/WinXP/VC P4/WinXP/VC Where the notations are as follows:

P3: Pentium III, 801 MHz, 192MB RAM P4: Pentium IV, 2.0 GHz, 768MB RAM WinXP : Microsoft Windows XP Professional ver 2002 VC : Microsoft Visual C++ Ver 6.0
Table 5: Performance of FORK-256 and SHA-256 on several environments FORK - 256 Environment P3/WinXP/VC P4/WinXp/VC
Mbps Cycle/Byte

SHA - 256
Mbps Cycle/byte

192.101 521.111

31.413 28.755

132.469 318.721

44.581 46.372

These implementations of FORK-256 are not optimized, so we expect performance can be improved for the optimized version. 6 Conclusion
In this paper we have proposed a recent committed crypt analysis 256-bit hash function FORK 256, which is designed to be not only secure but also fast than SHA-256. The main

features are the followings; Four branches are used in parallel, where as SHA-256 uses four serial rounds. This means
that FORK-256 can be implemented in hardware and it is dicult to analyze all branches

simultaneously.
Unlike other dedicated hash functions, FORK-256 doesnt use boolean functions but uses another nonlinear functions which output one word with one

input word. Especially, FORK-256 updates several words with using one word.

EUROCRYPT 2005, LNCS 3494, Springer-Verlag, pp. 3657, 2005. 3.B.den Boer and A. Bosselaers, An Attack on the Last Two Rounds of MD4, Advances in Cryptology CRYPTO91, LNCS 576, Springer-Verlag, pp. 194203, 1992. 4.B.den Boer and A. Bosselaers, Collisions for the Compression Function of MD5, Advances in Cryptology CRYPTO93, LNCS 765, Springer-Verlag, pp. 293304, 1994. 5.F.Chabaud and A. Joux, Dierential Collisions in SHA-0, Advances in Cryptol ogy CRYPTO98, LNCS 1462, SpringerVerlag, pp. 5671, 1998. 6. I. Damgard, A Design Priciple for Hash Functions, Advances in Cryptology CRYPTO89, LNCS 435, Springer-Verlag, pp. 416427, 1989. 7. H. Dobbertin, RIPEMD with Two-Round Compress Function is Not Collision- Free, Journal of Cryptology 10:1, pp. 5170, 1997. 8.H.Dobbertin, Cryptanalysis of MD4, Journal of Cryptology 11:4, pp. 253271, 1998. 9. H. Dobbertin, A. Bosselaers and B. Preneel, RIPEMD-160, a strengthened version of RIPEMD, FSE96, LNCS 1039, SpringerVerlag, pp. 7182, 1996. 10. R. C. Merkle, One way hash functions and DES, Advances in Cryptology CRYPTO89, LNCS 435, Springer-Verlag, pages 428 446, 1989. 11. NIST/NSA, FIPS 180-2: Secure Hash Standard (SHS), August 2002 (change notice: February 2004). 12.R.L. Rivest, The MD4 Message Digest Algorithm, Advances in Cryptology CRYPTO90, LNCS 537, Springer-Verlag, pp. 303311, 1991. 13.R.L.Rivest, The MD5 Message-Digest Algorithm, IETF Request for Comments, RFC 1321, April 1992. 14.B.Van Rompay, A. Biryukov, B. Preneel and J. Vandewalle, Cryptanalysis of 3- pass HAVAL, Advances in Cryptology ASIACRYPT 2003, LNCS 2894, Springer- Verlag, pp. 228245, 2003. 15. X. Wang, X. Lai, D. Feng, H. Chen and X. Yu, Cryptanalysis of the Hash Func tions MD4 and RIPEMD, Advances in Cryptology EUROCRYPT 2005, LNCS 3494, Springer-Verlag, pp. 118, 2005. 16.X.Wang and H. Yu, How to Break MD5 and Other Hash Functions, Advances in Cryptology EUROCRYPT 2005, LNCS 3494, Springer-Verlag, pp. 1935, 2005. 17.X.Wang, H. Yu and Y. L. Yin, Ecient Collision Search Attacks on SHA-0, Advances in Cryptology CRYPTO 2005, LNCS 3621, Springer-Verlag, pp. 116, 2005. 18.X Wang, Y. L. Yin and H. Yu, Finding Collisions in the Full SHA-1, Advances in Cryptology CRYPTO 2005, LNCS 3621, Springer-Verlag, pp. 17-36, 2005. 19.Y.Zheng, J. Pieprzyk and J. Seberry, HAVAL A One-Way Hashing Algorithm with Variable Length of Output, Advances in Cryptology AUSCRYPT92, LNCS 718, Springer-Verlag, pp. 83 104, 1993.

These properties make it dicult to analyze FORK-256 with known attack methods including Wang et al.s attack. It is believed that FORK-256 is secure against any known attacks on hash functions. However, the extensive analysis of our new hash function is required and also we believe that Fork-512 is highly secured attack are developed latter. We believe that new FORK 512 hash function are launched in future with high security measures.

References
1. E. Biham and R. Chen, Near-Collisions of SHA-0, Advances in Cryptology CRYPTO 2004, LNCS 3152, Springer-Verlag, pp. 290 305, 2004. 2.E. Biham, R. Chen, A. Joux, P. Carribault, C. Lemuet and W. Jalby, Collisions of SHA-0 and Reduced SHA-1, Advances in Cryptology

590 592