Search

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. [ABSTRACT FROM AUTHOR]

This paper evaluates the preimage resistance of the Tiger hash function. We will propose a pseudo-preimage attack on its compression function up to 23 steps with a complexity of 2181, which can be converted to a preimage attack on 23-step Tiger hash function with a complexity of 2187.5. The memory requirement of these attacks is 222 words. Our pseudo-preimage attack on the Tiger compression function adopts the meet-in-the-middle approach. We will divide the computation of the Tiger compression function into two independent parts. This enables us to transform the target of finding a pseudo-preimage to another target of finding a collision between two independent sets of some internal state, which will reduce the complexity. In order to maximize the number of the attacked steps, we derived several properties or weaknesses in both the key schedule function and the step function of the Tiger compression function, which gives us more freedom to separate the Tiger compression function. [ABSTRACT FROM AUTHOR]

This paper shows new preimage attacks on reduced Tiger and SHA-2. Indesteege and Preneel presented a preimage attack on Tiger reduced to 13 rounds (out of 24) with a complexity of 2128.5. Our new preimage attack finds a one-block preimage of Tiger reduced to 16 rounds with a complexity of 2161. The proposed attack is based on meet-in-the-middle attacks. It seems difficult to find ˵independent words″ of Tiger at first glance, since its key schedule function is much more complicated than that of MD4 or MD5. However, we developed techniques to find independent words efficiently by controlling its internal variables. Surprisingly, the similar techniques can be applied to SHA-2 including both SHA-256 and SHA-512. We present a one-block preimage attack on SHA-256 and SHA-512 reduced to 24 (out of 64 and 80) steps with a complexity of 2240 and 2480, respectively. To the best of our knowledge, our attack is the best known preimage attack on reduced-round Tiger and our preimage attack on reduced-step SHA-512 is the first result. Furthermore, our preimage attacks can also be extended to second preimage attacks directly, because our attacks can obtain random preimages from an arbitrary IV and an arbitrary target. [ABSTRACT FROM AUTHOR]

The cryptanalysis of the cryptographic hash function Tiger has, until now, focussed on finding collisions. In this paper we describe a preimage attack on the compression function of Tiger-12, i.e., Tiger reduced to 12 rounds out of 24, with a complexity of 263.5 compression function evaluations. We show how this can be used to construct second preimages with complexity 263.5 and first preimages with complexity 264.5 for Tiger-12. These attacks can also be extended to Tiger-13 at the expense of an additional factor of 264 in complexity. [ABSTRACT FROM AUTHOR]