I don't know the real answer here. I'm trying to figure it out.
What is the fastest way to turn a pseudorandom permutation into a block cipher? If f(*) is a pseudorandom permutation mapping an n-bit string into an n-bit string, and k0 and k1 are secret n-bit keys, then k0 XOR f(k1 XOR *) is a block cipher with an effective key length of n-1. This is proven in
S. Even and Y. Mansour, "A construction of a cipher from a single pseudorandom permutation." Advances in Cryptology -- ASIACRYPT '91. Lecture Notes in Computer Science, vol 739, 210-224, Springer-Verlag (1992)
I got that reference from a paper by Joe Killian and Phillip Rogaway on DESX. Rogaway's paper shows that the same trick can be used to extend the effective key length of DES. Instead of DES(k,x) where k is effectively 55 bits, they define DESX as "k0 XOR DES(k, k1 XOR x)" where k0 and k1 (and the results of DES) are 64 bits. They prove this gives DESX an effective key length of 118, or more generally, k0 XOR f(k, k1 XOR *) has an effective key length of m+n-1 where k has effective length m, and each of k0, k1, *, f(*) has length n.
The proof runs like this: Start with f and g undefined, and choose k. Let an attacker ask for f(x), f^-1(x), k0 XOR f(k1 XOR x), k1 XOR f^-1(k0 XOR x). Answer these queries with random values unless previous answers predetermine what the answer should be. As long as no query about k0 XOR f(k1 XOR *) or k1 XOR f^-1(k0 XOR *) predetermines an answer to f(*) or f^-1(*) (or vice versa), there is no evidence at all that f(*) and k0 XOR f(k1 XOR *) are related. Then they examine how likely it is for one query to have its answer predetermined by a previous one.
I'm still reading these papers. One caveat is that the proofs treat the pseudorandom permutation as a black box, assuming that if you've only seen f(0) then all you know about f(1) is that it isn't f(0). Linear and differential cryptanalysis treat ciphers as white boxes. They make use of the fact that f(0) and f(1) will resemble each other somewhat because 0 and 1 resemble each other somewhat.
Before I found the references above I was toying with the construct k XOR f(k XOR x). Here's what I found about that. f is the permutation, g is the block cipher constructed somehow from f, Eve is an evesdropper doing cryptanalysis, and k is a key. ^ means XOR.
Anything we do after the last time we use the key is pointless; Eve knows how to undo it and will do so. Similarly, anything we do before the first time we use the key is pointless. The simplest remaining scheme is to use the key first thing and last thing, then leave the middle the same. That is, g(k,x) = k^f(k^x).
John Kelsey has noted that if two keys k1, k2 differ in the last 3 bytes only, it is possible with k^f(k^x) to figure out what the difference is. For every possible setting d of the last 3 bytes, try g(k1,x) = k1^f(k1^x) ?= d^k2^f(k2^d^x) = d^g(k2,d^x) and if it succeeds, then d is the difference between k1 and k2.
Here are some other proposed g's:
I had one other result with k^f(k^x): it doesn't form a group unless f(f(f(x)))==x for all x. "Forming a group" means, given i there exists a j so that g(i,g(i,x))=g(j,x) for all x.
i^f(i^x) forms a group with respect to i if and only if for all i there exists j such that for all x,
i^f(i^ i^(f(i^x))) == j^f(j^x)
<=> i^f(f(i^x)) == j^f(j^x)
<=> i^i^f(f(i^x)) == i^j^f(j^x)
<=> f(f(i^x)) == i^j^f(j^i^i^x)
setting k=i^j and y=i^x,
<=> f(f(y)) == k^f(k^y).Thus, if it forms a group,
f(f(f(f(y)))) == k^f(k^ k^f(k^y))
== k^f(f(k^y))
== k^ k^f(k^ k^y)
== f(y)
<=> f(f(f(y))) == y (since f is a permutation)
Therefore i XOR f( i XOR x ) will form a group with respect to i only if f(f(f(x))) == x for all x, which can be tested easily.
Hash functions and block ciphers