Why is DES not an ideal cipher?

Question

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?

Answer 1

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

Answer 2

An ‘ideal [block] cipher’ is a probability distribution on block ciphers, i.e. families $\{E_k\}$ of permutations keyed by a key $k$. Specifically, if $E$ is an ideal block cipher, then for any fixed key $k$ independently, $E_k$ is a uniform random permutation—that is, for any fixed permutation $\pi$ of $n$-bit blocks, $$\Pr[E_k = \pi] = 1/2^n!$$ Indeed, since they are independent, for any sequence $k_1, k_2, \ldots, k_r$ of keys and sequence $\pi_1, \pi_2, \ldots, \pi_r$ of permutations, $$\Pr[E_{k_1} = \pi_1, E_{k_2} = \pi_2, \ldots, E_{k_r} = \pi_r] = (1/2^n!)^r.$$ If the random variable $E$ is an ideal block cipher, then the random variable $E_k$ is a random permutation, and for any $n$-bit block $x \in \{0,1\}^n$, the random variable $E_k(x)$ is a random $n$-bit block with distribution $\Pr[E_k(x) = y] = 1/2^n$ for any $n$-bit block $y \in \{0,1\}^n$. (However, note that for any fixed $k$ and $x \ne x'$, since $E_k$ is a permutation, $E_k(x)$ and $E_k(x')$ are not independent random variables, as they would be for a uniform random function rather than uniform random permutation.)

DES is one specific block cipher—one specific family of $2^{56}$ (mostly, if not all, distinct) permutations, not a probability distribution on families of $2^{56}$ permutations. It wasn't even chosen by rolling a $2^{64}!$-sided die $2^{56}$ times: it is highly structured, and as such can be efficiently implemented and computed. The structure is designed so that for the most part it doesn't have many interesting relations, though there are some that stand out, like $E_{\overline k}(\overline x) = \overline{E_k(x)}$ where $\overline x$ is the bitwise complement, which is exhibited by an ideal block cipher with only negligible probability.

The security goal that we more commonly ask of block ciphers is pseudorandom permutation or PRP security. This is quantified by the best probability a cost-limited random algorithm $A$ can attain at distinguishing an oracle for a uniform random permutation from an oracle for DES under a uniform random key: $$\operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{DES}}(A) = |\Pr[A(\operatorname{DES}_k) = 1] - \Pr[A(\pi) = 1]|,$$ where $\pi$ is a uniform random permutation of 64-bit blocks and $k$ is a uniform random 56-bit key. Of course, in the case of DES, the computational cost of making this advantage essentially 1, the best possible advantage an adversary can hope to achieve and the worst possible security a putative PRP can provide, was demonstrated to be feasible twenty years ago and is now spent by the Bitcoin network in a fraction of a second.

But the ideal block cipher model is convenient for theoretical purposes because $\Pr[E_k(x) = y] = 1/2^n$ for any $k$, $x$, and $y$, which is a much stronger statement than we can say for a PRP.