This question has been studied in the literature and has been answered positively. Namely, it is possible to construct a variable input length (VIL) pseudo-random permutation from a fixed input length permutation.
Motivation:
- Such a (generic) construction is valuable since we wouldn't need to custom-build block ciphers for different sizes if needed.
- The advantage of such construction compared to typical modes of operations is that there's no length expansion. Consequently, such a mode provides weaker confidentiality guarantees compared to the traditional IND-CPA notion. However, this may be enough for certain applications where plaintexts are never encrypted twice, but bandwidth saving is highly important.
It is unclear if this is practical since we tend to standardize a small set of good primitives and modes of operations that are thoroughly analyzed. I would be curious whether there are applications built on VIL PRP. In any case, one of the first construction was presented by Bellare and Rogaway in their paper: On the Construction of
Variable-Input-Length Ciphers. The construction feels somewhat magical; one encrypts with CBC but somehow removes part of the ciphertext, et voila... Concretely:
- Apply the CBC-MAC to the message and consider the output as an IV.
- From the previous IV, only encrypt part of the message with the CBC mode (remove a block from the plaintext).
- The block cipher output is now the concatenation of the outputs in steps 1 and 2.
Remark: Although we are somehow encrypting with CBC in step 2, this construction is different because the ciphertext length is the same as that of the plaintext.
The key property that allows this construction is what Bellare and Rogaway call parsimoniousness (hard to pronounce...). A keyed scheme $F$ (PRF, for example) is parsimonious if, for all keys, $k$ and input $m$, the last $n$ bits of $m$ can be deterministically derived from $F(k,m)$ and the first bits of $m$ besides the last $n$ bits. Observing that the CBC-MAC and the CBC mode of encryption are parsimonious is essentially what allows the construction above.
Some improvements to Bellare and Rogaway's work are in this paper: Efficient Constructions of Variable-Input-Length
Block Ciphers by Patel, Ramzan, and Sundaram.
Very recently, Banfi introduced the Secure Codebook Mode (SCB) (an interesting wrapper around ECB). The paper takes a different approach to answer the question. In contrast to previous work (Bellare-Rogaway), SCB provides strong confidentiality guarantees, namely semantic security. At what cost? Well, one has to pay for the correctness and keeping state. That is, SCB "sacrifices" perfect correctness, but this can be tuned.
