# 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