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, Huaxiong Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

52 Citations (Scopus)

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 2188.8 for finding preimages, and 2188.2 for second-preimages. Both have memory requirement of order 28, 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 278.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, 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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2010
Subtitle of host publication16th International Conference on the Theory and Application of Cryptology and Information Security Singapore, December 5-9, 2010, Proceedings
EditorsMasayuki Abe
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Pages56-75
Number of pages20
ISBN (Print)3642173721, 9783642173721
DOIs
Publication statusPublished - 2010
Event16th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2010 - Singapore, Singapore
Duration: 5 Dec 20109 Dec 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume6477
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2010
CountrySingapore
CitySingapore
Period5/12/109/12/10

Keywords

  • Cryptanalysis
  • Hash function
  • MD4
  • Preimage
  • SHA-2
  • Tiger

Fingerprint Dive into the research topics of 'Advanced meet-in-the-middle preimage attacks: first results on full tiger, and improved results on MD4 and SHA-2'. Together they form a unique fingerprint.

Cite this