In 1998 Michael Luby and Charles Rackoff published a paper in the SIAM Journal of Computing, entitled "How to construct pseudorandom permutations and pseudorandom functions", which subsequently made them quite famous (in geeky crypto circles, anyway). Essentially, they generalize the idea behind DES (and all other Feistel ciphers) by noting that the entirety of DES's security is with it's round function, which is simply a one way function of some key bits and half of the plaintext block. This is of course obvious to anyone familiar with the algorithm, but then they ask an important question - what would happen if the one way function in use was very, very strong? How many rounds would you need then? Would it be secure at all?
And from there, they show how turn a one way function into a block cipher, with what is now called the Luby-Rackoff transformation (or the Luby-Rackoff construction). Generally the function chosen is a cryptographic hash function like SHA-1, though it is also possible to use one based on DES or any other strong algorithm (this is extremely uncommon, however). It works as follows:
- Choose a one way function, f, which takes two inputs, of size n and k bits, and outputs n bits. For example, f(a,b) = SHA-1(a || b), with n = 160 and k being 128 (the choice of k is arbitrary in this example, since SHA-1 can accept an input of virtually any length).
- Choose a key of length 2k bits, splitting it in to two parts, KL and KR.
- Split the input into 2 pieces, L and R, each n bits long (thus, the total block size is 2n bits).
- Compute R = R ⊕ f(L,KL)
- Compute L = L ⊕ f(R,KR)
- Compute R = R ⊕ f(L,KL)
- Compute L = L ⊕ f(R,KR)
- Output (L || R) as the ciphertext.
Essentially this is a Feistel cipher with an extremely simple key schedule, and an arbitrary choice of round function, which is applied 4 times (the original paper suggested only three, but there are some attacks which can be applied when only three rounds are used). This is fine, and, if f is a reasonably good pseudo-random function, then the construction is secure. But nobody uses this in practice, because it's way too slow.
Wait, why is this important, then? It's important because it can be (and is) proven to be secure if f is sufficiently secure on it's own. Which means that if we can find a good enough one way function, we can create a provably secure block cipher. And from there, we can create provably secure hash functions and stream ciphers with ease (using, for example, Davies-Meyer and OFB, resp). But, nobody knows if one way functions actually exist. But it lets us, from a theoretical perspective, at least, base everything on the existence (or lack thereof) of one way function. If one way functions exist, then secure block ciphers exist. If secure block ciphers exist... and we're off to the races.
| 
