# Tag Info

69

A random oracle is described by the following model: There is a black box. In the box lives a gnome, with a big book and some dice. We can input some data into the box (an arbitrary sequence of bits). Given some input that he did not see beforehand, the gnome uses his dice to generate a new output, uniformly and randomly, in some conventional space (the ...

14

Your second question was about programmability. This hasn't been directly addressed yet by Thomas' answer or the comments, so I'll focus on that question only. Unfortunately I don't know of a simple primitive that is secure in the random oracle model that requires programmability, but I'll use one that is hopefully clear once I explain the background. It's ...

12

A random oracle is an ideal object; see this previous question for some details. What makes a random oracle convenient for proofs is the part about knowing nothing on the output for a given input if you do not try it. For instance, consider the following encryption scheme: $H$ is a random oracle which outputs $n$-bit values. The key is a $K$, a string of $... 12 The one real example out there is RMAC. This was proposed in this NIST standard, and was shown to be broken for some instantiations in practice in the paper Analysis of RMAC by Knudsen and Kohno. The construction is proven secure in the random-oracle model in the paper: On the Security of Randomized CBC–MAC Beyond the Birthday Paradox Limit: A New ... 9 This is very confusing because it seems as it should be something really easy to prove. However, it actually is not, and in fact the proof uses the Borel-Cantelli lemma. Anyway, it was formally proven by Rudich and Impagliazzo in their groundbreaking work on black-box separations. You can find a formal proof in Rudich's thesis, Section 6.2, or in the paper ... 9 This is based on an averaging argument (which is also used in the proof of the Goldreich-Levin hardcore bit). First, I assume that when writing$Pr[A(x,y)=1] \geq \epsilon$, then the probability is taken over a random choice of both$x$and$y$. Now, the claim is that there exists a subset of$x$values of a large enough size'' so that for every$x$in ... 7 The random oracle model is a heuristic that assumes the existence of a truly random function to which all parties involved in a protocol, good and bad alike, have access. Since in reality no such function exists, random oracles are instantiated with hash functions and one heuristically assumes that a hash function behaves good enough to be a replacement for ... 7 For many signature schemes, having two signatures using the same randomness for two different hash values allows recovery of the private key. This is used in many security proofs by showing that an adversary that forges a valid signature can be coerced through replaying into producing two signatures of this form. As a consequence, an forger can be twisted ... 7 The shared secret generated by the Diffie–Hellman key exchange is a random element of the subgroup of the multiplicative group modulo$p$generated by$g$. In particular, for$g$and$p$chosen as specified in RFC 2631 section 2.2, i.e. so that$p = jq+1$, where$q$and$p$are both prime,$j$is a small number (often 2, making$p$as safe prime) and$g$... 6 The answer is "it depends". There are two fairly commonly used sets of assumptions, the so-called standard model, and the random oracle model. In the standard model, hash functions are one-way functions. In the random oracle model they are random oracles. The random oracle model isn't actually true, but it is useful and many protocols inspired by it are in ... 6 Given: The attacker can call PRP() and the inverse function prp() on any message of his choosing. PRP is a pseudorandom permutation indistinguishable to the attacker from a random permutation. Assuming R and K are "sufficiently large", perfectly random, and never leaked to the attacker -- in particular, during a chosen-ciphertext attack, the decryptor only ... 6 A PRP is a keyed primitive, so proving properties of a keyed hash on top of it is often possible. Reducing the security of an unkeyed hash to a keyed primitive on the other hand is rarely possible. For example keyed Skein (a hash) is provably a PRF if Threefish (a block-cipher) is a PRP: PRF, MAC, and KDF. We prove that if Threefish is a tweakable PRP (... 5 My estimate of the entropy after$i$iterations is roughly$128- \lg i$bits (as$i$grows large). I don't have a proof of this, but I'll lay out my rough back-of-the-envelope calculations below. Here is the general problem: Problem 1. Let$F:\{0,1\}^n \to \{0,1\}^n$be a random, i.e., chosen uniformly at random from the set of all functions with ... 5 This scheme is insecure, as anyone with the public key can generate a forgery of an arbitrary message. To do this, the forger would take the message$M$, the public key$y$, pick an arbitrary$z$, and compute$r = y^{-H(M)} g^{z} \bmod p$and output$(r,z)$5 The random oracle model is a way to analyze schemes that need a hash function; essentially, you replace the hash function with some black box (the random oracle) which evaluates a function selected uniformly at random from all functions from its input domain to its output domain. Equivalently, it takes input and gives output like this: If you give it an ... 5 A random oracle is an idealization of a hash function$H$: if hash functions were perfect they would be random oracles. This is why it is always easier to consider a hash function a random oracle when one proves something about a larger scheme. Those are "proofs in the random oracle model". [1] That being said it is still possible to prove things using ... 5 Just wrapping my comment into an answer as it seems to be what you're looking for… CryptoVerif can be used for verification of security against polynomial time adversaries in the computational model. It's available via http://prosecco.gforge.inria.fr/personal/bblanche/cryptoverif/cryptoverifbin.html Related to your "it doesn't work on my computer", here's ... 5 None of the above answers seem to take into account that you apparently want to establish security with respect to the eCK model; the above answers are mostly about tools that verify some (related but different) properties. Afaik, there is current no automatic tool that can give you analysis with respect to the exact eCK model. In the symbolic setting, ... 5 If$H(X)$and$H(Y)$were not evaluated as a part of selecting$X$and$Y$, then yes; the assumption of a random Oracle is that$H(Z)$is an independent and uniformly distributed variable for every new (not previously submitted to the Oracle) value$Z$. If this isn't the case, then this need not hold. One obvious counterexample is:$X := 1; Y := 2 \textit{...

4

If you can show a reduction of a security property of your protocol to the security of a hash function is the standard model, you do not need the random oracle assumption. So a proof in the ROM does not have any general (positive) meaning in the SM; hence why it is controversial. About the only general thing you can say is that some (arguably highly ...

4

I could add to the list (in alphabetical order): Casper (http://www.cs.ox.ac.uk/gavin.lowe/Security/Casper/) Proverif (proverif.di.ens.fr/index.php) Scyther (http://people.inf.ethz.ch/cremersc/scyther/)

4

I can highly recommend AVISPA, a tool for automated verification of cryptographic protocols. It is available as a web service, so you can upload a description of your protocol to their web server and it will give you a security analysis of it. They have detailed documentation of how to use their system and of their specification language for protocols, so ...

4

A family $\mathcal{C}$ of circuits/functions is "learnable with oracle queries" if there is an efficient "learning" algorithm $L$ that, given oracle (or "black box") access to any $C \in \mathcal{C}$, outputs a circuit $C'$ (or other representation) that is equivalent to $C$, i.e., it agrees with $C$ on all inputs. Oracle ("black box") access to $C$ means ...

4

The scheme is secure against chosen-plaintext attacks up to $2^{|R|/2}$ queries. Indeed, given this number of queries, it is likely that every encryption call yields a new value $R$, which has never used as part of the permutation input. However, when this bound is reached, some problems occur. Suppose you encrypt the same message $M$ as many as $T=2^{|R|/2}... 4 Your proof certainly has to work even if the adversary doesn't use the random oracle. One technique that you can try is to begin by proving a separate lemma that if the adversary doesn't ask a certain query first, then it definitely cannot succeed in distinguishing. Then, you proceed to prove the simulation conditioned on it asking this query. However, if ... 3 At some level, there is no essential difference. Certainly, there is no difference in the distribution on the random variable$O$vs$f$. However, there is a potential difference in how the terms are typically used. If we say that$O\$ is a random (bijective) oracle, then we are usually implicitly hinting that it is available to everyone: the legitimate ...

3

As @xagawa mentioned in his comment, it depends on what you mean by "controled". In the case of using a programmable random oracle, yes, the reduction (in particular the simulation of the challenger of the real game) decides about what to return as answer to an oracle query. Thereby, the reduction has to guarantee that the "programmed" answers are ...

3

Yes. The following papers should be exactly what you are looking for. The following paper shows that the answer is "Yes" and provides evidence that 3-key Triple DES is more secure than single DES: Code-Based Game-Playing Proofs and the Security of Triple Encryption. Mihir Bellare, Phillip Rogaway. IACR ePrint 2004/331. (Full version of a paper ...

3

Indeed, this question is answered by What is the "Random Oracle Model" and why is it controversial?. However, I would like to add a few more thoughts on this. (Please read the other answer as well, since I will not repeat the very important things said there.) First and foremost, the random oracle is a model and not an assumption. We do not assume ...

2

A "random oracle" is essentially a perfect hash function. It's a device that takes a message of any length and maps it randomly to a message of a fixed length such that the same input always produces the same output. Random oracles don't exist. For algorithms that require them, cryptographic hash functions are used instead. However, cryptographic hash ...

Only top voted, non community-wiki answers of a minimum length are eligible