Preimage Attacks against PKC98-Hash and HAS-V - Information Security and Cryptology-ICISC 2010 - page 68

Preimage Attacks against
PKC98-Hash and HAS-V

Yu Sasaki 1 , Florian Mendel 2 , ,andKazumaroAoki 1 , 2

1 NTT, 3-9-11 Midoricho, Musashino-shi, Tokyo 180-8585 Japan
2 Institute for Applied Information Processing and Communications (IAIK),
Graz University of Technology, Inffeldgasse 16a, A-8010 Graz, Austria

Abstract. We propose preimage attacks against PKC98-Hash and
HAS-V. PKC98-Hash is a 160-bit hash function proposed at PKC 1998,
and HAS-V, a hash function proposed at SAC 2000, can produce hash
values of 128 + 32 k ( k =0 , 1 ,..., 6) bits. These hash functions adopt the
Merkle-Damg ard and Davies-Meyer constructions. One unique charac-
teristic of these hash functions is that their step functions are not injec-
tive with a fixed message. We utilize this property to mount preimage
attacks against these hash functions. Note that these attacks can work
for an arbitrary number of steps. The best proposed attacks generate
preimages of PKC98-Hash and HAS-V-320 in 2 96 and 2 256 compression
function computations with negligible memory, respectively. This is the
first preimage attack against the full PKC98-Hash function.

Keywords: PKC98-Hash, HAS-V, preimage, Davies-Meyer, non-injective
step function.

1 Introduction

Cryptographic hash functions (hereafter, simply referred to as hash functions)
are indispensable in achieving secure systems such as digital signatures and
cryptographic protocols. However, since collisions were found [1] for the widely
used hash function MD5 [2], analytic methods against hash functions have been
greatly improved and the security of existing hash functions has become doubt-
ful. The security of hash functions is usually evaluated by demonstrating crypt-
analysis. Therefore, it is important to analyze hash functions using various struc-
tures to understand the security of the existing hash functions and to design
secure hash functions.
There are many security requirements for hash functions depending on the us-
age. Specifically, the following three properties are the most important: collision
resistance, second preimage resistance, and preimage resistance.
A hash function was proposed at PKC 1998 [3] without a specific name, and
we call it PKC98-Hash as it was referred to in [4]. The hash function adopts spe-
cial features such as a message-dependent rotation. However, the most unique

The work in this paper has been supported by the Austrian Science Fund (FWF),
project P21936.