Colliding Message Pair for 53-Step HAS-160
HAS-160 is an iterated cryptographic hash function that is widely used in Korea. In this article, we present a collision attack on the hash function HAS-160 reduced to 53-steps. The attack has a complexity of about 235 hash computations. It is based on th
- PDF / 1,369,322 Bytes
- 11 Pages / 430 x 659.996 pts Page_size
- 63 Downloads / 159 Views
Abstract. HAS-160 is an iterated cryptographic hash function that is widely used in Korea. In this article, we present a collision attack on the hash function HAS-160 reduced to 53-steps. The attack has a complexity of about 235 hash computations. It is based on the work of Cho et al. presented at ICISC 2006. We improve the attack complexity of Cho et al. by a factor of about 220 using a slightly different strategy for message modification in the first 20 steps of the hash function and present the first actual colliding message pair for 53-step HAS-160. Furthermore, we show how the attack can be extended to 59-step HAS-160 by using a characteristic spanning over two message blocks.
1
Introduction
HAS-160 is an iterated cryptographic hash function that is widely used in Korea and standardized by Korean government (TTAS.KO-12.0011/R1) [1]. It is an iterated cryptographic hash function that produces a 160-bit hash value. The design of HAS-160 is based on design principles of the MD4 family. Recently, weaknesses have been shown for several members of the MD4 family such as MD5 [5] and SHA-1 [6]. These breakthrough results by Wang et al. in the cryptanalysis of hash functions, are the motivation for intensive research in the design and analysis of hash functions. In [4], Yun et al. applied the techniques invented by Wang et al. in the cryptanalysis of MD5 and SHA-1 to the HAS-160 hash function. In their article they show that a collision can be found for HAS-160 reduced to 45 (out of 80) steps with a complexity of about 212 45-step HAS-160 computations. This attack was later extended by Cho et al. to HAS-160 reduced to 53 steps. Their attack has a complexity of about 255 53-step HAS-160 computations. This is not feasible on an ordinary PC in practice. In this article, we show how to improve their attack by using a slightly different message modification technique to fulfill the conditions on the state variables in the first 20 steps of the hash function. With our method, we find a colliding message pair for 53-step HAS-160 with a complexity of about 235 hash computations. This improves the attack complexity of the original attack of Cho et al. by a factor of 220 , which makes the attack feasible in practice. Furthermore, we show how the attack can be extended to 59 steps of HAS-160. The attack has a complexity of about 255 hash computations.
This author is supported by the Austrian Science Fund (FWF), project P18138.
K.-H. Nam and G. Rhee (Eds.): ICISC 2007, LNCS 4817, pp. 324–334, 2007. c Springer-Verlag Berlin Heidelberg 2007
Colliding Message Pair for 53-Step HAS-160
325
The remainder of this article is structured as follows. A description of the hash function is given in Section 2. The collision attack of Cho et al. is described in Section 3. In Section 4, we describe the new improved collision attack. A sample colliding message pair is given in Section 5. Section 6 shows how the attack can be extended to 59 steps of HAS-160 by using a characteristic spanning over two message blocks. Finally, conclusions are prese
Data Loading...
