Hash functions based on block ciphers and quaternary codes

We consider constructions for cryptographic hash functions basedon m-bitblockciphers.FirstwepresentanewattackontheLOKI- DBHmode:theattackflndscollisionsin2 3m=4 encryptions,whichshould be compared to 2 m encryptions for a brute force attack. This attack breaks the last remaining subclass in a wide class of e-cient hash func- tions which have been proposed in the literature. We then analyze hash functions based on a collision resistant compression function for which flnding a collision requires at least 2 m encryptions, providing a lower boundofthecomplexityofcollisionsofthehashfunction.Anewclassof constructions is proposed, based on error correcting codes over GF(2 2 ) and a proof of security is given, which relates their security to that of single block hash functions. For example, a compression function is pre- sented which requires about 4 encryptions to hash an m-bit block, and forwhichflndingacollisionrequiresatleast2 m encryptions.Thisscheme has the same hash rate as MDC-4, but better security against collision attacks. Our method can be used to construct compression functions with even higher levels of security at the cost of more internal memory.