# Find out which keying option is being used in Triple DES?

As far as I know, there are three standard options for the three keys $K_1$, $K_2$ and $K_3$ used by 3DES:

1. Three distinct keys.
2. The first and last key are equal: $K_1$ = $K_3$.
3. Three equal keys: $K_1 = K_2 = K_3$

I wonder whether there is a way to find out which one of these options is (most likely) being used, given a set of known (plaintext, ciphertext) pairs. The attack does not need to reveal the keys; the goal is simply to find out which keying option is being used.

Currently, the only method I could think of consists of trying to recover the key. That is, apply known attacks on the third and second keying options. For example, a brute-force attack of complexity $2^{56}$ followed by a chosen plaintext attack of complexity $2^{57}$.

So the question is really: is there a way of doing this more efficiently, without having to figure out the keys. If that's not possible, (how) can the above mentioned method be optimized?

-

Actually, there's no known way (assuming practical amounts of computing power) to distinguish keying methods 1 and 2. You mention a "brute-force attack of complexity $O(2^{56})$ followed by a chosen plaintext attack of complexity $O(2^{57})$", there's no obvious way to frame an attack against either of the first two options in this matter; you can't do a brute force attack on one of the keys, because there's no obvious way to confirm a guess on a potential key (other than immediately doing a brute force attack on another of the keys, in which case you're really talking about an effort of $O(2^{112})$.
On the other hand, it is feasible (if moderately difficult) to distinguish the third option from the other two. This third option is essentially DES; a brute force search of all possible $2^{56}$ DES keys will distinguish it given a single plaintext/ciphertext pair. In addition, with sufficient known plaintext/ciphertext, linear cryptanalysis can make the distinguishing effort moderately easier.
The best work I known on linear cryptanalysis is this paper; using approximately $2^{43}$ plaintext/ciphertext pairs (that is, a few trillion), they are able to distinguish DES from a random permutation with about $O(2^{39})$ DES computations, which is moderately cheaper than simple brute force.
@fgrieu: I don't immediately see how knowledge of (even) the entire cycle structure would give you a hint about which keying option was used. For example, if $A$, $B$, $C$ are random even permutations, then both $AB^{-1}C$ and $AB^{-1}A$ are also random even permutations; hence you would need to make some assumptions about what permutations DES may generate beyond 'it's always an even permutation' –  poncho Feb 28 '14 at 14:05