What is the ideal cipher model? What is the ideal cipher model?  
What assumptions does it make about a block cipher?  
How does it relate to assuming that my block cipher is a pseudo-random permutation (PRP)?
When is the ideal cipher model appropriate to use?  
How do I tell whether a particular block cipher can reasonably be modelled using the ideal cipher model?
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.