4
$\begingroup$

Say we have an ideal 16-bit PRP. Since it appears that a permutation with a small domain can be used to turn it into a PRF, which can then be used in a Feistel network. On the surface, it makes it look like this means a trivial random permutation implemented using nothing more than a lookup table could then be used to create an ideal cipher with an arbitrary block and key size, which is obviously not the case. There must be something I am missing.

The way I see it:

  • A small, random permutation can be implemented in practice using a lookup table.

  • A random permutation can be used to implement a PRP, e.g. $C = \pi(P \oplus K) \oplus K$.

  • A PRP with a small domain can be used to construct a secure PRF.

  • A secure PRF in a Feistel network can be used to create a secure block cipher.

A random permutation with a small domain can be implemented easily using a lookup table. Were I any more naïve, I would have proclaimed that I had just discovered an information theoretic secure cipher that fits the ideal cipher model, but obviously that is not the case. Why is this?

This is not a cryptosystem review question in disguise. I am simply curious to know the reason why an ideal but small PRP cannot be used to construct a cipher that fits the ideal cipher model.

$\endgroup$
10
  • 6
    $\begingroup$ A fixed lookup table implements a particular permutation, but not a family of permutations. A block cipher implements the later. A fixed lookup table lacks a key. The question needs to carefully separate when PRF/PRP stands for a family (there is a key input), and when it stands for a particular function or permutation. $\endgroup$
    – fgrieu
    Jul 1, 2018 at 7:25
  • 1
    $\begingroup$ @fgrieu In this case it is an unkeyed permutation. A fixed lookup table could implement an Even-Mansour cipher (of very small block size and key size). $\endgroup$
    – forest
    Jul 2, 2018 at 7:27
  • $\begingroup$ ‘Unkeyed PRP’ is a contradiction in terms. You're mixing two categories: a distribution (perhaps uniform) on the space of permutations or functions, and a keyed family of functions. $\pi$ is presumably here a (uniform) random permutation—a random variable modeling uniform random distribution on permutations. An ideal cipher is a map from keys to independent uniform random permutations. Neither of these is a specific computable object; they're probability distributions. A PRP or a PRF, in contrast, is a specific computable object, which you might use with a uniform random key. $\endgroup$ Jul 4, 2018 at 13:48
  • $\begingroup$ @SqueamishOssifrage Perhaps I used the terminology incorrectly. Here, $\pi$ is a fixed random permutation, equivalent to a block cipher with a fixed key (i.e. $\pi(m) = E_K(m)$ with a public $K$). $\endgroup$
    – forest
    Jul 5, 2018 at 2:42
  • 1
    $\begingroup$ @forest OK, you're right, there is a sensible notion of ‘fixed random permutation’ which is a random permutation used in a protocol where everyone in any instance of the protocol shares the same permutation (hence it is fixed), but we are considering a distribution on protocols induced by a distribution on permutations rather than one particular protocol using one particular permutation (hence it is random). Yes, that's fine. Note that ‘keyed PRP’ is redundant (but not wrong): a PRP is by definition keyed. $\endgroup$ Jul 5, 2018 at 22:51

1 Answer 1

1
$\begingroup$

There are $2^{16}!$ distinct permutations of the 16-bit strings $\{0,1\}^{16}$. For any fixed Feistel structure built out of one of these as you suggest, there are still only $2^{16}!$ possible outcomes.

There are $2^{128}!$ distinct permutations of the 128-bit strings $\{0,1\}^{128}$. In an ideal cipher, for any fixed key $k$, $E_k$ is an independent uniform random permutation: each possible permutation has probability $1/2^{128}!$ of being $E_k$.

But in your construction, there are at least $2^{128}! - 2^{16}!$ permutations that $E_k$ cannot be. (There may be more because conceivably some pairs of permutations may collide under the Feistel structure, pending further analysis to rule that out.) So no matter what Feistel structure you choose, or non-Feistel composition of the permutation, you cannot get an ideal 128-bit block cipher out of a random 16-bit permutation.

What about a pseudorandom permutation family? Maybe you can, on average, make a good PRP out of this, if you specified enough details to matter.

Table lookups are, indeed, a common design element in cryptographic primitives, including the venerable DES. You can view AES as a composition of table lookups and xor, but as the rest of the paper demonstrates this implementation strategy will lead you into trouble, which is why alternative designs like Serpent and newer designs like Salsa20 don't even tempt implementors into using secret-dependent table lookups.

Further, to make a thing that can be computed with, rather than a probability distribution that can be studied, you need to choose particular tables—and as Don Coppersmith and his team at IBM learned in 1974, the choice of tables can be tricky.

$\endgroup$
2
  • $\begingroup$ Maybe you can, on average, make a good PRP out of this, if you specified enough details to matter. Can you elaborate a bit on this? $\endgroup$
    – forest
    Jul 5, 2018 at 23:30
  • $\begingroup$ @forest Not really—what I was getting at is that is that someone could, in principle, write down a lower bound on the expected PRP-distinguisher advantage in the random (permutation) oracle model, and it might be a pretty good expected advantage averaged over all permutations, but that's waaaaay more analysis that I'm keen to do right now. $\endgroup$ Jul 5, 2018 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.