What is the ideal cipher model?

Question

1. What is the ideal cipher model?
2. What assumptions does it make about a block cipher?
3. How does it relate to assuming that my block cipher is a pseudo-random permutation (PRP)?
4. When is the ideal cipher model appropriate to use?
5. How do I tell whether a particular block cipher can reasonably be modelled using the ideal cipher model?

Answer 1

When cryptographers create algorithms, they usually provide some argument that the algorithm is secure. They need to start the argument with some set of assumptions. For example, the in public-key cryptography, they may begin with the assumption that factoring large numbers is hard.

Many algorithms use use a block cipher as a building block. The arguments that these algorithms are secure need to make some (mathematical) assumption about the block cipher in question in order to get started. Normally, the assumption goes something like this: "If the encryption key is chosen at random, then an attacker who does not know the key cannot distinguish between the block cipher and a truly random permutation, even using a chosen-plaintext attack." (This is an informal statement of the pseudo-random permutation [PRP] assumption.)

But the PRP assumption isn't always applicable. Sometimes block ciphers are used in ways where the key is either not random or not secret (we'll see an example in a bit). In these cases, we need to make some other assumption about the block cipher's security properties.

What is the ideal cipher model? This is where the ideal cipher model comes into play. In the ideal cipher model, we just pretend the block cipher is a random permutation for every key. Furthermore, we treat these permutations as independent. We assume that if an attacker wants to know what happens when a block is encrypted under a given key, he has to go to the work of computing it himself. He can't infer anything about the output by encrypting other blocks, or the same block under a different key. (Exception: Given a fixed key, no two inputs will produce the same output. So the attacker can rule out that possibility, but that's it.)

Example: the Davies-Meyer Compression function. Some hash functions, such as MD5, SHA-1, and SHA-2, are examples of Merkle-Damgard constructions. Let's say we'd like to find an argument that Merkle-Damgard constructions are collision-resistant. They look like this (IV is a constant, and Hash is the output):

The function $f$ above is a compression function. Now, it's possible to show that if $f$ is secure, then so is the hash function. But we can go a bit deeper using the ideal cipher model. For MD5, SHA-1, and SHA-2, $f$ is built out of a block cipher $E$ using a so-called Davies-Meyer construction (each of these three hash functions uses a different block cipher):

$f(\mathrm{M}, H) = E_{M}(H) \oplus H,$

where $M$ is the message block and $H$ is other input (the chaining value). So $M$ is being used as the key, but if someone is trying to find a collision for MD5, then each message block $M$ is under his control. It is neither random nor secret. So we can't use the PRP assumption.

But we can model $E$ as an ideal cipher. Using this assumption, we can show, for example, that no one could find a collision for MD5 or SHA2 without doing an insane amount of work (or getting really, really, lucky).

But wait! We can find collisions for MD5! So what went wrong? Well, the ideal cipher model is just a heuristic. Block ciphers must be describable using simple algorithms --- we can't generate and store random tables listing every output under every key, these tables would be huge. This makes it inevitable that there's some mathematical relationship between different outputs and different keys.

When is it appropriate to use the ideal cipher model? Because the ideal cipher model is a heuristic way of modeling block ciphers, rather than an assumption that could plausibly be true in a technical sense, it should be avoided whenever possible. But sometimes, notably in hash functions that don't have a random secret key, it's our only option.

How do I tell when a block cipher can reasonably be modeled using the ideal cipher model? It's better to ask if the block cipher is being used in a way that requires the ideal cipher model (as opposed to a PRP assumption). Next, look at how the block cipher is being used. In MD5 and SHA1, SHA2, for example, the block cipher is buried inside of the compression function, and the attacker doesn't have complete control over the inputs to this function. Since the attacker is a couple steps removed from the actual block cipher, using the ideal cipher model becomes a bit more reasonable because it may be harder for the attacker to exploit the block cipher's weaknesses. Ultimately, the best test is the test of time.

That being said, certain common ways of constructing block ciphers have been proven to result in constructions that are indifferentiable from an ideal cipher... but these proofs make heuristic assumptions about the internals of the block cipher. So although these proofs are interesting from an academic perspective, it's not clear how much they contribute to trusting a real-world block cipher in the ideal cipher model.

Answer 2

An Ideal Cipher with $k$-bit keys and a $b$-bit blocksize is a family of $2^k$ permutations on the set $\{0,1\}^b$ indexed by the set $\{0,1\}^k$, selected uniformly at random from the set of all such families of permutations. See e.g. http://eprint.iacr.org/2005/210.pdf.

The IC model is primarily useful for proofs where you need to assume that the adversary can get no significant advantage merely by knowing --or even choosing-- the $k$-bit string $K$. Or to put it another way, it is useful where you need a component that acts randomly and unpredictably even when the adversary knows/controls all the inputs. To illustrate, consider DES (a decidely non-ideal cipher), which has the complementation property whereby $E_{K}(P) = E_{K^C}(P^C)$ with probability 1 ($X^C$ is the complement of $X$). Contrast this with an Ideal Cipher, where $E_{K}(P)$ and $E_{K^C}(P^C)$ are both independently and uniformly random values that will equal each other only with probability $\frac{1}{2^b}$.

The IC model is not especially helpful when trying to prove the confidentiality of an actual blockcipher or cryptosystem (it's too strong of an assumption that no real cipher can ever hope to meet). But it is (allegedly) useful for modeling other properties of blockciphers, like collision-resistance or pre-image resistance.

Answer 3

Partial answer for points 1 to 3...

The ideal cipher model describes a keyed permutation that approximates a random oracle, but with a fixed input size.
An ideal cipher with a block size $B$-bits and key size $N$-bits should exhibit the following properties:

1. Given any single key $K$, the distribution of ciphertexts for all $2^B$ plaintexts is statistically random

2. Given any single key $K$, there will be $2^N$ unique ciphertexts for all $2^B$ plaintexts

3. Given any single plaintext $P$, the probability of a possible ciphertext occurring should be $1/{2^N}$ for all $2^N$ keys, making the cipher behave like a random function with a fixed $P$

4. The workload for finding the matching plaintext or any statistical information about the plaintext from a given ciphertext for someone without knowledge of the key should be at least as hard as an exhaustive keys earch

5. The workload for finding the matching key from a given plaintext/ciphertext combination for someone without knowledge of the key should be at least as hard as an exhaustive keysearch

Given any single plaintext $P$, there are $2^N$ ciphertexts for all keys, and if $N=B$, all ciphertexts should NOT be distinct. The choice of ciphertext should model a random function. This may not make sense, but if they were distinct, the cipher would not approximate a random oracle. This can be shown using examples where $B$ is very small:

With a 2-bit block and 2-bit key, the following 2 tables are constructed of all possible inputs $P$ and outputs $C$ for all keys:

    P0 P1 P2 P3
K0  2  0  3  1 
K1  3  0  1  2
K2  1  2  3  0
K3  2  3  0  1

    P0 P1 P2 P3
K0  2  3  1  0
K1  3  1  0  2
K2  0  2  3  1
K3  1  0  2  3

    P0 P1 P2 P3
K0  2  0  3  1
K1  3  0  1  2
K2  1  2  3  0
K3  0  3  2  1

Table 1 exhibits the property where a plaintext will not encrypt to itself under any key.
Table 2 exhibits the property where a plaintext will have a unique ciphertext for each key.
Table 3 does not exhibit the property of table 1, nor does it exhibit the property of table 2.
In all tables, there are no equivalent keys, and there are no keys where $C=P$ for all values of $P$

In the 1st table, the probability of a 1 being the ciphertext for any key with $P1$ is 0.0.
In the 2nd table, the probability of a 1 being the ciphertext for $P0$ and $K3$ is 0.5 if the values for $K2$ and $K3$ are not yet determined, instead of the expected 0.25.
Therefore, property 3 cannot be met, as the cipher with a fixed $P$ no longer behaves like a random function. In practice the table 1 example may not be a bad thing to have, for obvious reasons.

The first 3 properties make an ideal cipher a pseudo-random permutation.
All block ciphers must exhibit property 2 in order for the ciphertext to be invertible back to plaintext

I do not believe I am well qualified to answer points 4 or 5, but the ideal cipher model is used to build cryptographic constructions around block ciphers that are believed to be secure, and then infer the security of the construction from the model using the key and block sizes of the cipher.
The only way to tell if a cipher behaves ideally is with brute force, and for large block and key sizes that is not currently possible.
This is in addition to the cipher itself being proven to be resistant to all known attacks with workloads at least as hard as exhaustive key search.
Even for small ciphers, say 12-bits with a 24-bit key, there would be 96 GiB of data required to hold all the outputs, and then the distributions would need to be tested for ideal randomness. 24-bit blocks and 48-bit keys would need 12 ZiB of data to analyze, which as far as I know is more than any one high density storage cluster on the planet is currently capable of holding.
The storage requirement in bits is $B*2^{N+B}$, and for key and block sizes of modern ciphers such as AES, would be at minimum $2^{263}$, and at maximum far exceeding the number of atoms in the universe.