@InProceedings{DRRS09,
author = { Yevgeniy Dodis and Leonid Reyzin and Ronald L. Rivest and Emily Shen },
title = { Indifferentiability of Permutation-Based Compression Functions and
Tree-Based Modes of Operation, with Applications to {MD6} },
pages = { 104--121 },
OPTurl = { http://dx.doi.org/10.1007/978-3-642-03317-9_7 },
doi = { 10.1007/978-3-642-03317-9_7 },
booktitle = { Proceedings of Fast Software Encryption 2009 },
date = { 2009 },
editor = { Orr Dunkelman },
publisher = { Springer },
isbn = { 978-3-642-03316-2 },
series = { Lecture Notes in Computer Science },
volume = { 5665 },
OPTyear = { 2009 },
OPTmonth = { February 22-25, },
eventdate = { 2009-02-22/2009-02-25 },
eventtitle = { FSE '09 },
venue = { Leuven, Belgium },
organization = { IACR },
abstract = {
MD6 [17] is one of the earliest announced SHA-3 candidates,
presented by Rivest at CRYPTO'08 [16]. Since then, MD6 has received
a fair share of attention and has resisted several initial cryptanalytic
attempts [1,11].
\par
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. [13] (also see [9]).
\par
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.
\par
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.
\par
Both proofs are rather general and apply not only to MD6 but also
to other sufficiently similar hash functions.
\par
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.
},