International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Some Observations on Indifferentiability

Ewan Fleischmann
Michael Gorski
Stefan Lucks
Search ePrint
Search Google
Abstract: At Crypto 2005, Coron et al. introduced a formalism to study the presence or absence of structural flaws in iterated hash functions: If one cannot differentiate a hash function using ideal primitives from a random oracle, it is considered structurally sound, while the ability to differentiate it from a random oracle indicates a structural weakness. This model was devised as a tool to see subtle real world weaknesses while in the random oracle world. In this paper we take in a practical point of view. We show, using well known examples like NMAC and the Mix-Compress-Mix (MCM) construction, how we can prove a hash construction secure and insecure at the same time in the indifferentiability setting. These constructions do not differ in their implementation but only on an abstract level. Naturally, this gives rise to the question what to conclude for the implemented hash function. Our results cast doubts about the notion of “indifferentiability from a random oracle” to be a mandatory, practically relevant criterion (as e.g., proposed by Knudsen [16] for the SHA-3 competition) to separate good hash structures from bad ones.
  title={Some Observations on Indifferentiability},
  booktitle={IACR Eprint archive},
  keywords={foundations /},
  note={an extended abstract will appear in the ACISP 2010 proceedings, this is the full version 14719 received 20 Apr 2010},
  author={Ewan Fleischmann and Michael Gorski and Stefan Lucks},