Preimages of hash functions through rainbow tables

In this paper, we introduce a natural way of how to find preimages on a hash function by using a rainbow table even if the hash function utilizes the Merkle-Daringmgard (MD) strengthening as a padding procedure. To overcome the MD strengthening, we identify the column functions as representatives of certain set of preimages, unlike conventional usage of rainbow tables or Hellman tables to invert one-way functions. The workload of the precomputation to prepare a table is as much as the workload of brute force as usual. Then, one can find a preimage of a given arbitrary digest value in 2^2n/3 steps by using 2^2n/3 memory where n is both the digest size and the length of the chaining value. The notion of the attack is extended to certain improved variants of the MD construction. We generalized the attack when the digest size is not equal to the length of chaining value. We verified the results experimentally as well.