TTradeoff tables for compression functions:  how to invert hash values radeoff Tables for Compression Functions: How to Invert Hash Values

Orhun KARA; Adem ATALAY

Article Details

TTradeoff tables for compression functions: how to invert hash values radeoff Tables for Compression Functions: How to Invert Hash Values

Authors:

Orhun KARA | Adem ATALAY

Publisher:

TUBITAK

Journal:

Turkish Journal of Electrical Engineering and Computer Science 2012 Vol.20 Issue 1, pp.57-70

Document Type:

Article

Publication Date:

12/2011

Document Language:

Turkish

Document ID (Org No.):

2000743629

Frequency:

Bimonthly

eISSN:

1303-6203

pISSN:

1300-0632

Abstract:

 

Hash functions are one of the ubiquitous cryptographic  functions used widely for various applications such as digital  signatures, data integrity, authentication protocols, MAC algorithms,  RNGs, etc.  Hash functions are supposed to be one-way, i.e., preimage  resistant.  One interesting property of hash functions is that they  process arbitrary-length messages into fixed-length outputs.  In  general, this can be achieved mostly by applying compression functions  onto the message blocks of fixed length, recursively.  The length of  the message is incorporated as padding in the last block prior to the  hash, a procedure called the Merkle-Damgard strengthening.  In  this paper, we introduce a new way to find preimages on a hash  function by using a rainbow table of its compression function even if  the hash function utilizes the Merkle-Damgard (MD) strengthening  as a padding procedure.  To overcome the MD strengthening, we identify  the column functions as representatives of certain set of preimages,  unlike conventional usage of rainbow tables or Hellman tables to  invert one-way functions.  As a different approach, we use the  position of the given value in the table to invert it.  The workload  of finding a preimage of a given arbitrary digest value is 22n/3  steps by using 22n/3 memory, where n is both the digest size and  the length of the chaining value.  We give some extensions of the  preimage attack on certain improved variants of MD constructions such  as using output functions, incorporating the length of message blocks  or using random salt values.  Moreover, we introduce the notion of  near-preimage'' and mount an attack to find near-preimages.  We  generalize the attack when the digest size is not equal to the length  of chaining value.  We have verified the results experimentally, in  which we could find a preimage in one minute for the 40-bit hash  function, whereas the exhaustive search took roughly one week on a  standard PC.

 

Hash functions are one of the ubiquitous cryptographic  functions used widely for various applications such as digital  signatures, data integrity, authentication protocols, MAC algorithms,  RNGs, etc.  Hash functions are supposed to be one-way, i.e., preimage  resistant.  One interesting property of hash functions is that they  process arbitrary-length messages into fixed-length outputs.  In  general, this can be achieved mostly by applying compression functions  onto the message blocks of fixed length, recursively.  The length of  the message is incorporated as padding in the last block prior to the  hash, a procedure called the Merkle-Damgard strengthening.  In  this paper, we introduce a new way to find preimages on a hash  function by using a rainbow table of its compression function even if  the hash function utilizes the Merkle-Damgard (MD) strengthening  as a padding procedure.  To overcome the MD strengthening, we identify  the column functions as representatives of certain set of preimages,  unlike conventional usage of rainbow tables or Hellman tables to  invert one-way functions.  As a different approach, we use the  position of the given value in the table to invert it.  The workload  of finding a preimage of a given arbitrary digest value is 22n/3  steps by using 22n/3 memory, where n is both the digest size and  the length of the chaining value.  We give some extensions of the  preimage attack on certain improved variants of MD constructions such  as using output functions, incorporating the length of message blocks  or using random salt values.  Moreover, we introduce the notion of  near-preimage'' and mount an attack to find near-preimages.  We  generalize the attack when the digest size is not equal to the length  of chaining value.  We have verified the results experimentally, in  which we could find a preimage in one minute for the 40-bit hash  function, whereas the exhaustive search took roughly one week on a  standard PC.

Article Details

TTradeoff tables for compression functions: how to invert hash values radeoff Tables for Compression Functions: How to Invert Hash Values

Authors: Orhun KARA | Adem ATALAY

Publisher: TUBITAK

Journal: Turkish Journal of Electrical Engineering and Computer Science 2012 Vol.20 Issue 1, pp.57-70

Document Type: Article

Publication Date: 12/2011

Document Language: Turkish

Document ID (Org No.): 2000743629

Frequency: Bimonthly

eISSN: 1303-6203

pISSN: 1300-0632

Issues

Authors:

Orhun KARA | Adem ATALAY

Publisher:

TUBITAK

Journal:

Turkish Journal of Electrical Engineering and Computer Science 2012 Vol.20 Issue 1, pp.57-70

Document Type:

Article

Publication Date:

12/2011

Document Language:

Turkish

Document ID (Org No.):

2000743629

Frequency:

Bimonthly

eISSN:

1303-6203

pISSN:

1300-0632