# Tag Info

52

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 ...

11

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 ...

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 ...

6

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

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 ...

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 ...

6

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 ...

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

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 ...

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

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 ...

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

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 ...

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

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 ...

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 ...

3

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 ...

3

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 ...

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

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/)

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 ...

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 ...

2

Firstly, I should clarify: I am just referring to the standard definition of a random oracle. There are other scenario's (better discussed in DrL's answer), but these tend to be explicitly referred to. That is, if you have a standard 'random oracle', this answer should hold. On the other hand, if you have a different type of oracle, this won't hold. A ...

2

Assuming that you insist that $H$ preserve the group operation, that is, if $H(A) \times H(B) = H(A+B)$ for any $A, B \in \mathbb{G}_1$, then it would be difficult to come up with an explicit representation (and in any case, the random oracle model doesn't appear to be a great fit). I'll take the last point first: a random oracle is intended to be something ...

1

Yes. Any public random permutation should suffice. (A public random permutation is like a random oracle, except it is a random permutation rather than a random function.) A public random permutation is automatically length-preserving, and it meets the requirements for an all-or-nothing transform. And, a public random permutation can be constructed in a ...

1

Guillo-Quisquater scheme uses the Fiat-Shamir trick to convert a proof of knowledge into a signature. There is a paper out there about the security of such schemes in the random oracle model here which seems to give what you want.

1

Another approach is to assume that the hash function is collision-resistant, and see if you can prove your protocol is secure under this weaker assumption. For some protocols, it is possible, and then you're good. For others, it's not. (More precisely, you demonstrate that any successful attack on the protocol can be turned into an algorithm that produces ...

1

There's the common random string model (where hash functions can be modeled as having been picked from a family of functions using public coins). There are also "whatever-tractable random oracles", where adversaries also have an oracle that finds a whatever with respect to the random oracle. (Usually 'whatever' is one of ...

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