2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Sorry, I meant "third and second keyring options" rather than "first and second". I've corrected it now. So the method I described is essentially what you mention in the second paragraph, followed by an attack on the second keying option. $\endgroup$
    – Aleph
    Feb 23, 2014 at 20:12
  • $\begingroup$ @AnotherTest & poncho: What about quasi-exhaustively tabulating the length of cycles, and trying to derive a distinguisher from that? Conceivably, having 2 identical permutations in the 2-keys setup could show in the cycle structure. The attack scenario could be semi-realistic in some rare setups. At least the effort for building experimental data is feasible; by keeping information for distinguished points only (like, 30 high bits fixed), moderate memory (2GB) is enough. It is entirely conjectural that a distinguisher could be built from cycle structure, even between 1-key and the rest. $\endgroup$
    – fgrieu ♦
    Feb 28, 2014 at 8:43
  • 2
    $\begingroup$ @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' $\endgroup$
    – poncho
    Feb 28, 2014 at 14:05
  • $\begingroup$ @poncho: Yes, under a random even permutation model for DES, my idea just can't work. That's bad for plausibility that the cycle structure could allow a distinguisher. An indispensable experimental preliminary would be to investigate if the cycle structure of single-DES (with external canceling of final swap) is distinguishable from that for a random (even) permutation for at least a wide class of keys; starting with "weak" (resp."semi-weak") keys, for which each round (or pair or round) is the same permutation, giving a little meat to the possibility that it shows in the cycle structure. $\endgroup$
    – fgrieu ♦
    Feb 28, 2014 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.