Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 $O(2^{56})$ followed by a chosen plaintext attack of complexity $O(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?

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  AnotherTest Feb 23 at 20:12
    
@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. –  fgrieu Feb 28 at 8:43
2  
@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 at 14:05
    
@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. –  fgrieu Feb 28 at 18:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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