Collision Search of a Hash Function by Using Random Mapping

Hikaru MORITA  Hideki ODAGI  Kazuo OHTA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A   No.1   pp.35-40
Publication Date: 1998/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
hash function,  collision,  pseudo random function,  random mapping,  

Full Text: PDF>>
Buy this Article

This paper proposes to apply random mapping methods of a pseudo random function to find collisions of a hash function. We test a hash function including a block cipher (see ISO/IEC 10118-2) with computers, where users can select its initial vector. In particular, the paper shows that a hash function with multiple stages generates a lot of collision hash values, so our probabilistic consideration of a small model for the hash function well explains the computational results. We show that it's feasible to find collisions between the selected messages in advance for 64-bit-size hash functions with WSs linked via an ordinary LAN (Local Area Network). Thus, it is dangerous to use the hash function -- single block mode -- defined in [6] and [7].