Paper 2010/016

Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2

Jian Guo, San Ling, Christian Rechberger, and Huaxiong Wang

Abstract

We revisit narrow-pipe designs that are in practical use, and their security against preimage attacks. Our results are the best known preimage attacks on Tiger, MD4, and reduced SHA-2, with the result on Tiger being the first cryptanalytic shortcut attack on the full hash function. Our attacks runs in time $2^{188.8}$ for finding preimages, and $2^{188.2}$ for second-preimages. Both have memory requirement of order $2^{8}$, which is much less than in any other recent preimage attacks on reduced Tiger. Using pre-computation techniques, the time complexity for finding a new preimage or second-preimage for MD4 can now be as low as $2^{78.4}$ and $2^{69.4}$ MD4 computations, respectively. The second-preimage attack works for all messages longer than 2 blocks. To obtain these results, we extend the meet-in-the-middle framework recently developed by Aoki and Sasaki in a series of papers. In addition to various algorithm-specific techniques, we use a number of conceptually new ideas that are applicable to a larger class of constructions. Among them are (1) incorporating multi-target scenarios into the MITM framework, leading to faster preimages from pseudo-preimages, (2) a simple precomputation technique that allows for finding new preimages at the cost of a single pseudo-preimage, and (3) probabilistic initial structures, compared with deterministic ones, to enable more neutral words, and hence to reduce the attack time complexity. All the techniques developed await application to other hash functions. To illustrate this, we give as another example improved preimage attacks on SHA-2 members.

Note: An error on the preimage attack against MD4 has been corrected.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. A short version of the paper will appear in ASIACRYPT 2010
Keywords
PreimageMD4TigerSHA-2Hash functionCryptanalysisMeet-in-the-Middle
Contact author(s)
ntu guo @ gmail com
History
2010-09-03: last of 7 revisions
2010-01-12: received
See all versions
Short URL
https://ia.cr/2010/016
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/016,
      author = {Jian Guo and San Ling and Christian Rechberger and Huaxiong Wang},
      title = {Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2},
      howpublished = {Cryptology ePrint Archive, Paper 2010/016},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/016}},
      url = {https://eprint.iacr.org/2010/016}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.