Why is DES not an ideal cipher? From Cryptography I on Coursera, Week 2, "Exhaustive Key Search Attacks":


  Now let's assume that DES is what's called an ideal cipher [...] Of course,
   DES is not a collection of 2^56 random functions


Prof. Boneh doesn't offer any explanation of that, he mentions that in passing like something obvious. But why exactly DES is not an ideal cipher? Is it simply because there are no ideal ciphers at all?

And a follow-up question, if DES is not a collection of 2^56 random permutations, then how many permutations does it actually offer? And how do I calculate that number?
DES uses a 56-bit key (formally, a 64-bit key, out of which 8 bits are simply ignored), so it represents a family of exactly $2^{56}$ permutations(*).

If you were to select a permutation at random among all the permutations of a space of 64-bit blocks, then there are $2^{64}!$ such permutations, a truly huge number, and you would need, on average, $\log 2^{64}!$ bits to simply represent such a permutation, i.e. about 144 billions of gigabytes. Now, DES for a given key can be represented in a much more compact way (the code that executes DES fits in a couple of kilobytes, and an extra 56 bits for the key). In that sense, DES selects permutations out of the very very few (relatively speaking) that can be represented in a few kilobytes of code.

If you prefer, if you have a computer with a budget of 2048 bytes for code and data, then there are at most $2^{16384}$ possible programs for that computer, that can thus represent only $2^{16384}$ different functions (most of them won't actually run or do anything useful, and even for those whose execution terminates, most won't be permutations of a given space of 64-bit blocks). $2^{16384}$ is already a mind-bogglingly large number, but it is insignificantly small compared to the number of permutations over 64-bit blocks, which is about $2^{1153978594521722658473.7}$ (I computed that with Stirling's formula).

An "ideal cipher" is supposed to be a family of permutations, such as each key represents a random choice among the whole set of possible permutations. That set is immense. Concrete block ciphers, in order to be actually implementable, must necessarily be restricted to a very small subset of such permutations, i.e. the one for which there can exist some code that implements them within a given budget. In that sense, no concrete block cipher can be "ideal".

(*) To my knowledge, it is not proven that all of them are distinct; however, it seems improbable that any two match exactly.