Finding near-Optimum message scheduling settings for SHA-256 variants using genetic algorithms

Tunghai University Institutional Repository > 工學院 > 資訊工程學系所 > 期刊論文 > Item 310901/24833

Please use this identifier to cite or link to this item: http://140.128.103.80:8080/handle/310901/24833

Title:	Finding near-Optimum message scheduling settings for SHA-256 variants using genetic algorithms
Authors:	Lin, C.-H.;Lee, C.-Y.;Kavi, K.M.;Chen, D.-J.;Yeh, Y.-S.
Contributors:	Department of Computer Science, Tunghai University
Keywords:	Cryptography;Genetic algorithms;Message scheduling;Optimisation;Secure hash algorithm
Date:	2013
Issue Date:	2014-05-30T03:07:55Z (UTC)
Abstract:	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 264 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 (Wt) involves more message blocks (Mi) 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 239 and 269, 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 W27 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.
Relation:	Journal of Information Science and Engineering,Vol.29,Issue5,P.889-905
Appears in Collections:	[資訊工程學系所] 期刊論文

Files in This Item:

There are no files associated with this item.

Loading...