Can you create a strong blockcipher with small blocksize, given a strong blockcipher of conventional blocksize?

Question

Suppose I want a strong 20-bit blockcipher. In other words, I want a function that takes a key (suppose the key is 128 bits), and implements a permutation from 20 bits to 20 bits. The set of permutations should be close to a randomly-chosen subset of size $2^{128}$ of all $2^{20}!$ permutations on 20 bits.

I don't want you to build a new blockcipher from scratch. Instead, assume you have a "strong" blockcipher like AES (128-bit blocksize, 128-bit keysize) and use this to build your 20-bit cipher.

Of course, your construction should be practical (i.e., you should be able to run it in both directions with reasonable amounts of time and memory).

Answer 1

What you're looking for can be done using existing schemes for format preserving encryption (FPE). In general, FPE schemes convert an existing strong algorithm like AES into a block cipher that operates on a set of any size. For instance, FPE can encrypt 15 digit integers to other 15 digit integers (eg for credit card numbers, one of the common reasons for using FPE). Most of these schemes can be easily adapted for the set [0...2^20), usually with no special changes. For further details see this paper or this wikipedia article.

I assume you're aware that any 20 bit block cipher suffers serious intrinsic weaknesses (eg collisions using it in CBC mode) and have a specific reason for needing a 20 bit permutation.

Answer 2

For these parameters, and if speed is not an issue, it is reasonable to build a new cipher using a balanced Feistel construct, with the strong cipher used in the round function.

With enough rounds, it is computationally indistinguishable from a perfect cipher, except for one detail: the permutation obtained is even. This is an issue if and only if the adversary can obtain $2^{20}-2$ distinct plaintext/ciphertext pairs, as this allows to determine the two remaining pairs. This can be fixed too, by swapping two specific ciphertexts for half of the keys, like in the following pseudocode example.

parameters:
    B = 10                        // half the number of bits per block, see note
    N = 8                         // number of rounds, see note

key setup with a 128-bit key:
    derive the AES subkeys from the 128-bit key
    encipher the 128-bit constant zero with AES, and..
    set X to 0 or 1, according to some bit of the result

enciphering plaintext block P, assumed to be 2*B bits
    L := P>>B                      // extract left  B bits
    R := P & ((1<<B)-1)            // extract right B bits
    for I from 1 to N              // round loop
      encipher ((I<<B) | R) with AES, keep the B right bits H
      L := L ^ H
      exchange R and L
    C =  (R<<B) | L                // append the halves, with R on the left
    if C < 2                       // swap ciphertext 0 and 1 for half the keys
      C := C^X                     // here X is 0 or 1 as obtained in key setup
   output ciphertext block C

deciphering ciphertext block C, assumed to be 2*B bits
    if C < 2                       // swap ciphertext 0 and 1 for half the keys
      C := C^X                     // here X is 0 or 1 as obtained in key setup
    L := C>>B                      // extract left  B bits
    R := C & ((1<<B)-1)            // extract right B bits
    for I from N downto 1          // round loop
      encipher ((I<<B)|R) with AES, keep the B right bits H
      L := L ^ H
      exchange R and L
    P =  (R<<B) | L                // append the halves, with R on the left
    output plaintext block P

Note: A classic result by Luby and Rackoff ensures that as $B$ grows, $N=4$ rounds is asymptotically enough to make the cipher demonstrably safe (or just $N=3$ when the adversary has no access to decryption, which is usually a safe assumption) against an adversary restricted to $2^{(2\cdot B)/4}$ plaintext/ciphertext pairs. But here $B$ is small, and perhaps we are interested with uniform distribution of the permutations obtained. Say, the cipher is used in a lottery, to assign rewards as a function of the ticket number, and the number-to-reward mapping is revealed progressively by increasing reward; one could analyze what is assigned to the lower-reward tickets, and when two or three remain gain some little information about their likely assignment. In that case, we need $N>3$ for very small $B$, in particular $B=2$. It is easy to show that $N=4$, $B=2$ is inadequate: there are no more than $2^{N\cdot B\cdot 2^B+1}=2^{33}$ choices for { N round functions of B->B bits, one extra bit X}, this is not a multiple of the number of permutations of $2\cdot B$ bits which is $(2B)!=24$, thus some permutations are bound to be more probable than others, and detectably so with moderate effort. Also and most importantly, the non-linearity of the round functions must be allowed to spread (and would not spread at all for $B=1$, which must be excluded). Still, $N=8$ is on the safe side for $B=10$, but I lack a proof.

Note: the Feistel construction (and the Luby-Rackoff proof) assume independent round functions. This is approximated with a single AES key, by injecting the round number in the input of AES. The decision to swap ciphertext 0 and 1 is similarly derived. Care is taken that disjoint AES block ranges are used for these $N+1$ uses, and only a tiny portion of the AES block space is used.

Answer 3

There is a generic construction, by Granboulan and myself, which shows that it can be done "perfectly": if you have a seekable pseudo-random stream (which you can get with a conventional block cipher in CTR mode), then you can have a pseudo-random permutation over a domain of arbitrary size $N$, such that evaluating that permutation over a given input uses negligible memory, and $O((\log N)^3)$ lookups in the seekable stream.

Unfortunately, this entails evaluating an hypergeometric distribution, which is cumbersome. The prototype we used followed that distribution exactly, hence the "perfect", but implied fiddling with floating point numbers with a high precision, and this was expensive. A basic PC would encrypt at most a dozen values per second with that (not thoroughly optimized) code.

Approximate solutions, such as unbalanced Feistel networks (see @Jack's answer), will give you something which is "good enough" for most purposes, and efficient.