The Ideal-Cipher Model, Revisited:An Uninstantiable Blockcipher-Based HashFunctionJohn BlackDept. of Computer Science, University of Colorado, Boulder CO 80309, USA,[email protected], www.cs.colorado.edu/~jrblackAbstract. The Ideal-Cipher Model of a blockcipher is a well-known andwidely-used model dating back to Shannon [25] and has seen frequent usein proving the security of various cryptographic objects and protocols.But very little discussion has transpired regarding the meaning of proofsconducted in this model or regarding the model’s validity. In this paper,we briefly discuss the implications of proofs done in the ideal-ciphermodel, then show some limitations of the model analogous to recentwork regarding the Random-Oracle Model [2]. In particular, we extendwork by Canetti, Goldreich and Halevi [5], and a recent simplification byMaurer, Renner, and Holenstein [15], to exhibit a blockcipher-based hashfunction that is provably-secure in the ideal-cipher model but triviallyinsecure when instantiated by any blockcipher.Keywords: Ideal-Cipher Model, Information-Theoretic Cryptography,Random-Oracle Model, Uninstantiability1 IntroductionThe Standard Model. Before we can prove the security of a cryptographicsystem or object, we must specify what model we are using. The most commonmodel used in modern cryptography is the so-called “standard model.” Here weuse no special mathematical objects such as infinite random strings or randomoracles [2], and we abstract our communications system typically as a reliable butinsecure channel. We have not been able to achieve most common cryptographicgoals in the standard model without making additional complexity-theoretichardness assumptions, because we still have no proof that any of our standardcryptographic building blocks have computational lower bounds. The commonassumptions are typically that factoring the product of large primes is hard,or that discrete log is intractible in certain sufficiently large groups, or thatAES is a good pseudo-random permutation (PRP) [16]. The standard modelis usually well-accepted in our community despite the fact that proofs done inthis model rest upon unproven assumptions and that already much relevantreal-world context has been abstracted away (timing, power consumption, errormessages, and other real-world effects are typically not included as part of themodel in spite of the demonstrated fact they are often relevant to security).The Random-Oracle Model. When proofs in the standard model are unap-pealing or are provably impossible (eg, see [19]), we often resort to proofs usingan alternative model. By far the best-known is the “Random-Oracle Model.”The random-oracle model was used for some time before being formalized byBellare and Rogaway [2], and continues to see widespread use today (there aremore than a hundred instances; for a few examples see [2, 11, 18, 21, 24]). In therandom-oracle model we have a public random function, accessible to all parties,which typically accepts any string from {0, 1}∗and outputs n bits. For each ele-ment in its domain, the corresponding n-bit output is uniform and independentfrom all other outputs. Proofs conducted in the random-oracle model often admitschemes which are provably-secure and more efficient than schemes which havebeen proven secure in the standard model, and for this reason the random-oraclemodel has been widely-adopted.Of course random oracles do not exist in practice, and if the schemes provensecure in the random-oracle model are going to be put into use, we must choosesome object to implement the random oracle. This step is called “instantiation.”Most often, random oracles are instantiated with cryptographic hash functionssuch as SHA-1 [20]. The following question then arises: now that we have instan-tiated our random oracle with a concrete function, what security guarantees dowe have? Does our proof in the random-oracle model have any bearing on thesecurity of the instantiated system?For quite some time there has been concern in our community that therandom-oracle model should be treated with suspicion, and proofs in the stan-dard model should be preferred. As a recent example, the main selling pointof the Cramer-Shoup cryptosystem [7] is that it is provably-secure in the stan-dard model and still practical (and, as with most proofs in the standard model,comes with an assumption: the Decisional Diffie-Hellman assumption [4]). Fur-ther doubt has been recently cast on the random-oracle model due to a string ofresults exhibiting schemes which are provably-secure in the random-oracle modelbut are completely insecure when instantiated by any hash function [1, 5, 6, 15].Schemes of this type are called “uninstantiable.”It has been noted [2] that proofs done in the random-oracle model do guar-antee one thing: if the adversary treats the instantiated random oracle as a blackbox, promising not to think about its inner workings, promising not to exploitany unnatural behavior related to the fact that we have instantiated with somealgorithm that has a compact description, then the proof remains valid in thestandard model. Of course there is no guarantee that real adversaries would abideby such restrictions, and indeed they would be remiss if they did. Nonetheless,no scheme has thus far been proven secure in the random-oracle model and thenbroken once instantiated, unless this was the goal from the start.The Ideal-Cipher Model. Blockciphers are a common building block forcryptographic protocols. In the standard model the associated assumption forblockciphers is that they are “pseudo-random permutations” (PRPs). By this wemean (informally) that an n-bit blockcipher under a secret randomly-chosen keyis computationally indistinguishable from a randomly-chosen n-bit permutation.Proofs conducted using this assumption typically give reductions showing thatif an adversary breaks some scheme, then there exists an associated adversarythat can efficiently distinguish the underlying blockcipher from random.There are countless examples where the PRP assumption in the standardmodel is sufficient, but there are also plenty of cases where we cannot get aproof to go through. In certain cases it can be shown that blockcipher-basedschemes we believe to be secure cannot have a proof of security using only thePRP assumption in the standard model [26]. In this case we are faced with eitherabandoning attempts at a proof, or using an alternate model.The