Security Proofs for the MD6 Hash Function Mode of Operation

In recent years there have been a series of serious and alarming cryptanalytic attacks on several commonly-used hash functions, such as MD4, MD5, SHA-0, and SHA-1 [13, 38]. These culminated with the celebrated work of Wang, Yin, and Yu from 2005, which demonstrated relatively efficient methods for finding collisions in the SHA-1 hash function [37]. Although there are several cryptographic hash functions- such as the SHA-2 family [28]- that have not yet succumbed to such attacks, the U.S. National Institute of Standards and Technology (NIST) put out a call in 2007 for candidate proposals for a new cryptographic hash function family, to be dubbed SHA-3 [29]. Hash functions are algorithms for converting an arbitrarily large input into a fixed-length message digest. They are typically composed of a compression function or block cipher that operate on fixed-length pieces of the input and a mode of operation that governs how apply the compression function or block cipher repeatedly on these pieces in order to allow for arbitrary-length inputs. Cryptographic hash functions are furthermore required to have several important and stringent security properties