International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.

Details

Markku-Juhani Olavi Saarinen (#260)
Name Markku-Juhani Olavi Saarinen
Personal Homepage http://www.mjos.fi
Topic of his/her doctorate. Cryptanalysis of Dedicated Hash Functions
Category secret-key cryptography
Keywords Hash function cryptanalysis, FSB, Fast Syndrome Based Hash, FORK-256, VSH, Very Smooth Hash, LASH, Lattice Hash, d-Monomial Test
Ph.D. Supervisor(s) Keith Martin
Year of completion 2009
Abstract

In this thesis we study the security of a number of dedicated cryptographic hash functions against cryptanalytic attacks.

We begin with an introduction to what cryptographic hash functions are and what they are used for. This is followed by strict definitions of the security properties often required from cryptographic hash functions.

FSB hashes are a class of hash functions derived from a coding theory problem. We attack FSB by modeling the compression function of the hash by a matrix in GF(2). We show that collisions and preimages can easily be found in FSB with the proposed security parameters.

We describe a meet-in-the-middle attack against the FORK-256 hash function. The attack requires 2^112.8 operations to find a collision, which is a 38000-fold improvement over the expected 2^128 operations.

We then present a method for finding slid pairs for the compression function of SHA-1; pairs of inputs and messages that produce closely related outputs in the compression function. We also cryptanalyse two block ciphers based on the compression function of MD5, MDC-MD5 and the Kaliski-Robshaw "Crab" encryption algorithm.

VSH is a hash function based on problems in number theory that are believed to be hard. The original proposal only claims collision resistance; we demonstrate that VSH does not meet the other hash function requirements of preimage resistance, one-wayness, and collision resistance of truncated variants.

To explore more general cryptanalytic attacks, we discuss the d-Monomial test, a statistical test that has been found to be effective in distinguishing iterated Boolean circuits from real random functions. The test is applied to the SHA and MD5 hash functions.

We present a new hash function proposal, LASH, and its initial cryptanalysis.The LASH design is based on a simple underlying primitive, and some of its security can be shown to be related to lattice problems.

E-Mail Address mjos (at) iki.fi
Last Change 2011-03-09 15:13:22
To provide an update on this entry, please click .

Contact: phds (at) iacr.org

[ IACR home page ] [ IACR PhDs page ] © IACR