mirage

Advanced meet-in-the-middle preimage attacks : first results on full Tiger, and improved results on MD4 and SHA-2

DSpace/Manakin Repository

 

Search DR-NTU


Advanced Search Subject Search

Browse

My Account

Advanced meet-in-the-middle preimage attacks : first results on full Tiger, and improved results on MD4 and SHA-2

Show full item record

Title: Advanced meet-in-the-middle preimage attacks : first results on full Tiger, and improved results on MD4 and SHA-2
Author: Guo, Jian; Ling, San; Rechberger, Christian; Wang, Huaxiong
Copyright year: 2010
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 269.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.
Subject: DRNTU::Engineering::Computer science and engineering::Computer applications::Physical sciences and engineering.
Type: Journal Article
Series/ Journal Title: Lecture notes in computer science
School: School of Physical and Mathematical Sciences
Rights: © 2010 International Association for Cryptologic Research.This is the author created version of a work that has been peer reviewed and accepted for publication by Lecture Notes in Computer Science, Springer on behalf of International Association for Cryptologic Research. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: http://dx.doi.org/10.1007/978-3-642-17373-8_4
Version: Accepted version

Files in this item

Files Size Format View
C28. Advanced m ... sults on MD4 and SHA-2.pdf 380.6Kb PDF View/Open
   

DOI Query

- Get published version (via Digital Object Identifier)
   

This item appears in the following Collection(s)

Show full item record

Statistics

Total views

All Items Views
Advanced meet-in-the-middle preimage attacks : first results on full Tiger, and improved results on MD4 and SHA-2 330

Total downloads

All Bitstreams Views
C28. Advanced meet-in-the-middle preimage attacks first results on full Tiger, and improved results on MD4 and SHA-2.pdf 189

Top country downloads

Country Code Views
United States of America 62
China 46
Singapore 16
Unknown Country 8
France 7

Top city downloads

city Views
Mountain View 37
Beijing 20
Singapore 16
Dublin 5
Redwood City 4