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

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.

Anahtar Kelimeler:

Cryptographic hash function; compression function; preimage resistance; trade-off; Hellman table; rainbow table; one-way function

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

Keywords:

Cryptographic hash function; compression function; preimage resistance; trade-off; Hellman table; rainbow table; one-way function,

PDF

___

time complexities and the success rates from the experimental data collected by several tries. It may be argued that rainbow tables can never be suﬃciently eﬀective in practice for large digest sizes. It is simply impossible to prepare a table of size, for instance 2512. On the other hand, not all the hash function applications require large digest sizes. Indeed, rainbow tables can be real threats for some hash functions of small digest sizes to Şnd preimages with workloads within practical bounds.
I. Damg˚ard. A design principle for hash functions. In G. Brassard, editor, Advances in Cryptology, CRYPTO 1989, volume 435 of Lecture Notes in Computer Science, pages 416–427. Springer, 1989.
J. Kelsey and B. Schneier. Second-preimages on n -bit hash functions for much less than 2nwork. In R. Cramer, editor, Advances in Cryptology, EUROCRYPT 2005, volume 3494 of Lecture Notes in Computer Science, pages –490. Springer, 2005.
J. Kelsey and T. Kohno. Herding hash functions and the nostradamus attack. In S. Vaudenay, editor, Advances in Cryptology, EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 183–200. Springer,
A. Joux. Multicollisions in iterated hash functions. In M.K. Franklin, editor, Advances in Cryptology, CRYPTO , volume 3152 of Lecture Notes in Computer Science, pages 306–316. Springer, 2004. NIST. Cryptographic hash algorithm competition, URL http://csrc.nist.gov/groups/ST/hash/sha- /index.html.
P. Oechslin. Making a faster cryptanalytic time-memory trade-oﬀ. In D. Boneh, editor, Advances in Cryptology, CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 617–630. Springer, 2003.
M. E. Hellman. A cryptanalytic time-memory trade-oﬀ. IEEE Trans. on Information Theory, 26(4):401–406, 1980.
C. Paar A. Bogdanov, G. Leander, A. Poschmann, M. J. B. Robshaw, and Y. Seurin. Hash functions and rŞd tags: Mind the gap. In Oswald and P. Rohatgi, editors, CHES 2008, volume 5154 of Lecture Notes in Computer Science, pages 283–299. Springer, 2008.
S. Halevi and H. Krawczyk. Strengthening digital signatures via randomized hashing. In C. Dwork, editor, Advances in Cryptology, CRYPTO 2006, volume 4117 of Lecture Notes in Computer Science, pages 41–49. Springer, 2006.
E. Biham and O. Dunkelman. A framework for iterative hash functions: Haifa. In Second NIST Cryptographic Hash Workshop, 2006.
S. Babbage. Improved exhaustive search attacks on stream ciphers. In European Convention on Security and Detection, number 408 in IEE Conference publication, pages 161–166. IEE, 1995.
J. Goli´c. Cryptanalysis of alleged a5 stream cipher. In W. Fumy, editor, EUROCRYPT’97, volume 1233 of Lecture
Notes in Computer Science, pages 239–255. Springer, 1997.
P. Junod G. Avoine and P. Oechslin. Characterization and improvement of time-memory trade-oﬀ based on perfect tables. ACM Trans. Inf. Syst. Secur., 11(4), 2008. URL http://doi.acm.org/10.1145/1380564.1380565.
R.L. Rivest and A. Shamir. Payword and micromint: Two simple micropayment schemes, 2001. URL http://people.csail.mit.edu/rivest/RivestShamir-mpay.pdf.
M. S. Manasse. Millicent (electronic microcommerce), 1995. URL http://www.research.digital.com/SRC/personal/Mark Manasse/uncommon/ucom.html.
NETBILL. The netbill electronic commerce project, 1995. URL http://www.ini.cmu/NETBILL/home.html.
K. Suzuki M. Ohkubo and S. Kinoshita. Cryptographic approach to “privacy- friendly” tags. In RFID Privacy Workshop, MIT, USA, 2003.
E. Dysli G. Avoine and P. Oechslin. Reducing time complexity in rŞd systems. In B. Preneel and S. Tavares, editors, SAC 2006 Selected Areas in Cryptography, volume 3897 of Lecture Notes in Computer Science, pages –306. Springer, 2006.
S. Lucks. A failure-friendly design principle for hash functions. In B. Roy, editor, Advances in Cryptology, ASI- ACRYPT 2005, volume 3788 of Lecture Notes in Computer Science, pages 474–494. Springer, 2005.