Cube Attacks on Cryptographic Hash Functions

A Master's thesis by Joel Lathrop (joel.lathrop@alum.rit.edu)

Abstract

Cryptographic hash functions are a vital part of our current computer systems. They are a core component of digital signatures, message authentication codes, file checksums, and many other protocols and security schemes. Recent attacks against well established hash functions have led NIST to start an international competition to develop a new hashing standard to be named SHA-3.

In this thesis, we provide cryptanalysis of some of the SHA-3 candidates. We do this using a new cryptanalytical technique introduced a few months ago called cube attacks. In addition to summarizing the technique, we build on it by providing a framework for estimating its potential effectiveness for cases too computationally expensive to test. We then show that cube attacks can not only be applied to keyed cryptosystems but also to hash functions by way of a partial preimage attack. We successfully apply this attack to reduced-round variants of the ESSENCE and Keccak SHA-3 candidates and provide a detailed analysis of how and why the cube attacks succeeded. We also discuss the limits of theoretically extending these attacks to higher rounds. Finally, we provide some preliminary results of applying cube attacks to other SHA-3 candidates.

Committee

Chair: Stanisław Radziszowski
Reader: Christopher Homan
Observer:Edith Hemaspaandra

Defense information

Defense Date:Thursday, 5/21/2009 at 11:00 A.M.
Defense Location:70-1620

Thesis documentation

Proposal
Thesis
Defense announcement
Defense Slides

Related resources

The SHA-3 Zoo
The official SHA-3 competition page at NIST

M.M.J. Stevens. On collisions for MD5. Master's thesis, Eindhoven University of Technology, 2007. [ pdf ]
Itai Dinur and Adi Shamir. Cube attacks on tweakable black box polynomials. Cryptology ePrint Archive, Report 2008/385, 2008. [ pdf ]