¡@

Journal of Information Science and Engineering, Vol. 29 No.
5, pp. 889-905 (September 2013)

**Finding Near-Optimum Message Scheduling Settings
for SHA-256 Variants Using Genetic Algorithms**

CHU-HSING LIN^{1}, CHEN-YU LEE^{2}, KRISHNA M. KAVI^{3}, DENG-JYI CHEN^{2}
AND YI-SHIUNG YEH^{2}

*
*^{1}Department of Computer Science

Tunghai University

Taichung, 407 Taiwan

^{2}Department of Computer Science

National Chiao-Tung University

Hsinchu, 300 Taiwan

^{3}Department of Computer Science and Engineering

University of North Texas

Denton, TX 76203, USA

One-way hash functions play an important role in modern cryptography. Matusiewicz
et al. proved that the message scheduling is essential for the security of SHA-
256 by showing that it is possible to find collisions with complexity 2^{64} hash operations
for a variant without it. In this article, we first proposed the conjecture that message
scheduling of SHA algorithm has higher security complexity (or fitness value in Genetic
algorithm) if each message word (*W*_{t}) involves more message blocks (*M*_{i}) in each round.
We found some evidence supports the conjecture. Consider the security of SHA-0 and
SHA-1. Since Chabaud and Joux shown that SHA-1 is more secure than SHA-0. Further,
Wang found collisions in full SHA-0 and SHA-1 hash operations with complexities less
than 2^{39} and 2^{69}, respectively. We found it is consistent from the viewpoint of message
blocks (terms) involved in each message word. It clearly shown that the number of terms
involved in SHA-1 is more than that in SHA-0, taking *W*^{27} as an example, 14 and 6, respectively.
Based on the conjecture we proposed a new view of complexity for SHA-
256-XOR functions, a variant of SHA-256, by counting the terms involved in each equation,
instead of analyzing the probability of finding collisions within SHA-256-XOR
hash function. Our experiments shown that the parameter set in each equation of message
schedule is crucial to security fitness. We applied genetic algorithms to find the
near-optimal message schedule parameter sets that enhance the complexity 4 times for
SHA-1 and 1.5 times for SHA-256-XOR, respectively, when compared to original SHA-
1 and SHA-256-XOR functions. The analysis would be interesting for designers on the
security of modular-addition-free hash function which is good for hardware implementation
with lower gate count. And the found message schedule parameter sets would be a
good reference for further improvement of SHA functions.

*
***Keywords:**
genetic algorithms, cryptography, secure hash algorithm, message scheduling,
optimisation

Retrieve PDF document (**201309_06.pdf**)

Received July 8, 2011; revised July 23, 2012; accepted September 11, 2012.

Communicated by Vincent Rijmen.