###
Indifferentiability of Permutation-Based Compression
Functions and Tree-Based Modes of Operation, with Applications to MD6

by Yevgeniy Dodis,
Leonid Reyzin,
Ronald L. Rivest
and Emily Shen

**Abstract**
MD6 is one of the earliest
announced SHA-3 candidates, presented by Rivest at
CRYPTO'08. Since then, MD6
has received a fair share of attention and has
resisted several initial cryptanalytic attempts.

Given the interest in MD6, it
is important to formally verify the soundness of its design from a
theoretical standpoint. In this paper, we do so in two ways: once for the
MD6 compression function and once for the MD6 mode of operation.
Both proofs are based on the indifferentiability framework
of Maurer et al., TCC 2004 (also see Coron et al., Crypto 2005).

The first proof demonstrates that the
"prepend/map/chop" manner in which the MD6 compression function
is constructed yields a compression function that is indifferentiable
from a fixed-input-length (FIL), fixed-output-length random oracle.

The second proof demonstrates that the
tree-based manner in which the MD6 mode of operation is defined
yields a hash function that is indifferentiable from a variable-input-length (VIL),
fixed-output-length random oracle.

Both proofs are rather general and apply not only to MD6 but also to
other sufficiently similar hash functions.

These results may be interpreted as saying that
the MD6 design has no structural flaws that make its input/output behavior
clearly distinguishable from that of a VIL random oracle, even for an
adversary who has access to inner components of the hash function.
It follows that, under plausible assumptions about those inner components,
the MD6 hash function may be
safely plugged into any application proven secure assuming a
monolithic VIL random oracle.

This work is part of the MD6
project.

This work appears in the proceedings of FSE 09 -- International Workshop on Fast Software Encryption 2009, © IACR.