Hash functions are one of the ubiquitous cryptographicfunctions used widely for various applications such as digitalsignatures, data integrity, authentication protocols, MAC algorithms,RNGs, etc. Hash functions are supposed to be one-way, i.e., preimageresistant. One interesting property of hash functions is that theyprocess arbitrary-length messages into fixed-length outputs. Ingeneral, this can be achieved mostly by applying compression functionsonto the message blocks of fixed length, recursively. The length ofthe message is incorporated as padding in the last block prior to thehash, a procedure called the Merkle-Damgard strengthening. Inthis paper, we introduce a new way to find preimages on a hashfunction by using a rainbow table of its compression function even ifthe hash function utilizes the Merkle-Damgard (MD) strengtheningas a padding procedure. To overcome the MD strengthening, we identifythe column functions as representatives of certain set of preimages,unlike conventional usage of rainbow tables or Hellman tables toinvert one-way functions. As a different approach, we use theposition of the given value in the table to invert it. The workloadof finding a preimage of a given arbitrary digest value is 2^{2n/3}steps by using 2^{2n/3} memory, where n is both the digest size andthe length of the chaining value. We give some extensions of thepreimage attack on certain improved variants of MD constructions suchas using output functions, incorporating the length of message blocksor using random salt values. Moreover, we introduce the notion of``near-preimage'' and mount an attack to find near-preimages. Wegeneralize the attack when the digest size is not equal to the lengthof chaining value. We have verified the results experimentally, inwhich we could find a preimage in one minute for the 40-bit hashfunction, whereas the exhaustive search took roughly one week on astandard PC.
展开▼
