13

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


12

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


12

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


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


12

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 $\operatorname{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 ...


12

This is due to Luby and Rackoff's proof about Feistel networks. The proof assumes the PRFs are independent. See sections 4.5 and 5 of How to Construct Pseudorandom Permutations from Pseudorandom Functions (paywall). Simply using the same key for four rounds is not secure, but there are other ways to key with fewer than four round keys which are secure, see ...


12

Iterated ciphers need variability between rounds to resist so callad Slide attacks. One common way to thwart this attack is with a key schedule generating different round keys for each round. Slide attacks exploit the repeating rounds of the cipher by finding a collision between one input plaintext and the intermediate value after one round of encryption of ...


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


8

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


7

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


7

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


7

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


7

The bear describes a process for choosing and computing a uniform random function involving gnomes in boxes, but this doesn't really explain what the random oracle model is in the context of proving security reductions. There are three parts: uniform random functions, cryptosystems built out of hash functions, and random oracle proofs. Uniform random ...


7

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


7

What you are asking for is not really a list of security models, but more a list of idealized models (like the ROM), and trust assumptions (like the CRS model). Asking for a list seems a bit off-topic to me, and the question is a bit vague. Anyway, many idealized models and trust models are common in cryptography, and things are in general not as simple as "...


7

The CRS has nothing to do with modeling hash functions. Rather, it is a model where there is a public string that was generated in a trusted manner, and all parties have access to the string. It has two flavors: a common random string (where it is just a uniformly distributed string) and a general common reference string (which may have an arbitrary ...


7

With KDFs, you need domain separation when you use the same initial key material to generate keys for different purposes like using the same initial key material and nonce to generate encryption and signing keys, you provide the KDF some data about the domain (encryption or signing) so it can generate different (private) keys. eg. for HKDF there is an info ...


7

Hash functions we use, e.g. Sha-1, Sha-256, Sha-512, usually don’t have a sufficiently large range. But we can construct full domain hash via repeated application of a hash function $h$: $FDH(m) = h(m||0)||h(m||1)||\cdots $, then take the leading n-bit. This way the hash value is deterministic and the size is arbitrary. This is something like MGF1 defined ...


7

Yes, there are examples where the random oracle model has been first used, then removed, Yes, the proof becomes, in the end, much (much) more complex. But in fact, simplicity of the proof is not the reason why we initially prove security in the ROM. The main reason is that we don't even know what security property our hash function must satisfy! Intuitively,...


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


6

Cyclic group of prime order q such that the DLP is hard A simple technique to form a cyclic group $G$ of prime order $q$ such that the underlying discrete logarithm problem (DLP) is (conjecturally) hard, applicable to large $q$ (in the order of a thousand bits), is to pick $q$ as a random prime of appropriate size such that $p=2q+1$ is prime, and random any ...


6

The obvious way to create such a hash function would be to first define a hash function $H$ (distinct from $H_1$) that generates as output an integer in the range $[2, q]$, and then define $H_2(x) = H(x)^2 \bmod (2q+1)$ (that is, square $H(x)$ modulo $2q+1$). If we treat $H$ as a random oracle, then $H_2(x)$ is a random element (uniformly distributed, other ...


6

Hiding which cipher you are using means violating Kerckhoff's principle. That's actually an extremely common mistake. The problem is that such a cipher becomes very hard to analyze because you have to consider all the options for an attacker to learn parts of the system. In general we don't analyze cipher designs on this website because it is too easy to ...


6

It does not make sense to say that any fixed function $F$ "is a good PRF". A distribution on functions can, however, be pseudorandom (indistinguishable from the uniform distribution over the set of all functions). Therefore, it makes sense to consider keyed functions to emulate a random oracle.


6

Pointcheval and Stern [PS00] proved that the Schnorr signature is existentially unforgeable under chosen-message attacks (EU-CMA) in the random oracle model assuming that the discrete-logarithm problem$^1$ (DLP) is hard. On a high level, the reduction (from DLP to the EU-CMA-security of Schnorr signature) works as follows. The reduction algorithm $\...


6

Probabilistic encryption is a necessity for ANY public-key encryption scheme. The reason is that in such schemes anybody can perform the encryption, thus if the encryption was deterministic, that would allow to check a guess of the plaintext. That would be a total disaster in a lot of applications: enciphering a coin toss, a name on the class roll, a price, ...


6

This was discussed by Coron in 1. You are actually asking why the random oracle can't just be some uncontrollable ideal random oracle. In fact Bellare and Rogaway when introduced their Full Domain Hash scheme (FDH) in the seminal works 2,3 used this uncontrollable random oracle to analyze the security reduction for FDH. The thing about using reductions ...


5

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


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


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