A collision resistant cryptographic hash function based on cellular automata rules

The subject of this thesis is the study of collision resistant hash function. A cryptographic hash function is one of the cryptographic primitives designed to protect the integrity of data such as that in digital signatures and online business transactions. Popular hash functions are Message Digest 4/5 (MD-4/5), Secure Hashing Algorithm (SHA-0/1) and RIPEMD, which are referred to as MDx-class hash functions due to some commonalities in their design with the MD-family. However, recent advances in cryptanalysis have led to the failure of these hash functions in preserving the strongest property called collision resistance. Factors contributing to the failure are a mathematical weakness found in the Boolean functions used by these cryptographic hash functions, linear message expansion and poor difusion in the step operation. This study proposes a design framework for collision resistant hash function. The framework divides requirements for the design of hash function into three classifications namely design requirements, security requirements for Boolean function and analysis requirements. Following the framework introduced here, a dedicated cryptographic hash function named STITCH-256 was introduced. In STITCH-256 design,an improved formula for message expansion and a step operation that employs a novel permutation technique for better bit propagation, which is called the stitching permutation, are introduced. For the improved formula for message expansion,the study shows that the formula produces higher codewords with minimal weight as compared to the existing formula of message expansion. This leads the effort of attackers to construct differential characteristics with high probability becomes more difficult and challenging. In the step operation that employs a novel stitching permutation, the study shows that the bit propagations are higher and no sufficient condition can be given to construct differential characteristics with high probability. Thus, it is very difficult to and inner collisions in the compression function of STITCH-256. For the second classification in the framework, the study examines the cryptographic properties of 256 one-dimensional Cellular Automata (CA) rules to and cryptographically strong Boolean functions. The study shows that 23 of the rules are cryptographically strong where eight of them are used in our hash function design. Following the third classification of the framework, STITCH-256 is analyzed against all the generic attacks and is measured against its avalanche effect and randomness. The security analysis shows that STITCH-256 is resistant against all the generic attacks and it is very difficult to construct a small list of conditions that gives a successful construction of collision path. The experiments to measure the avalanche effect involved 3000 samples of 512-bit input message and it has been shown that the average avalanche factor for STITCH-256 for these 3000 sequences is 0.5, which is the desired avalanche factor in cryptographic primitives. The 3000 sequences of 256-bit hash values are tested for randomness using NIST Statistical Tests and the results show that the output values from STITCH-256 for these sequences are random. This study also includes a comparison between STITCH-256 and other MDx-class hash functions. The comparison shows that STITCH-256 employs fewer operations which lead to faster computation. From the security analysis carried out in this thesis, we believe that STITCH-256 is a strong collision resistant hash function. This is due to its new non-linear recursive function for message expansion that gives higher codewords with minimal weight,its step operation that employs stitching permutation in a target-heavy Balanced Feistel Network that gives no set of conditions for the construction of collision path using established differential attack being constructed, and cryptographically strong Boolean function used in the compression function of STITCH-256 that gives strong non-linearity and diffusion property.

Preview PDF FSKTM 2013 1R.pdf Download (858kB) | Preview

Actions (login required)

View Item