Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Shannon's paper states:
A system is pure if all keys are equally likely and if for any three transformations, $T_i$, $T_j$, $T_k$ in the set, the product $T_iT_j^{-1}T_k$ is also a transformation in the set.
But this is exactly the construction of Triple-DES! So, using this terminology, it is not a pure system, since that would mean a 56-bit DES brute-force attack could be successfully mounted against a 168-bit Triple-DES key. Is that right?
Yes.
For DES, it looks like the composition $T_i\circ T_j^{-1}\circ T_k$ is normally not a $T_l$ with another key $l$.
I do not have a proof of this fact.
So DES is not a pure system, and otherwise triple-DES would not more secure than DES itself.
In a comment, fgrieu linked a proof for a weaker fact, that DES is not a group (by Campbell and Wiener).
They actually did some experiments searching keys $i, j, k, l$ so that $(T_l \circ T_k \circ T_j \circ T_i)(\mathtt 0) = c$, with 50 different random values $c$ messages randomly selected from the full $2^{64}$ block set. They found such a set of keys for all 50 values $c$.
Since the set $K$ of DES keys has only size $2^{56}$, also the set $T_*(\mathtt 0) = \{T_m(\mathtt 0) \mid m\in K\}$ has at most size $2^{56}$. The probability that all 50 messages would be in this set $T_*(\mathtt 0)$ was estimated as $\leq (2^{-7})^{50} = 2^{-350}$. So very probably $(T_l \circ T_k \circ T_j \circ T_i)$ is usually not a $T_m$, i.e. the set of DES encryptions is not closed under composition.
The paper also provides some lower bounds on the size of the subgroup spanned from all the DES encryptions by calculating the cycle sizes of $T_{\mathtt{1...1}} \circ T_{\mathtt{0...0}}$ applied to various messages, which all must be factors of the order of the cyclic group spanned by $T_{\mathtt{1...1}} \circ T_{\mathtt{0...0}}$, which itself is a subgroup of the group spanned by all DES encryptions (and decryptions). The lowest common multiple they got was more than $10^{2499}$, much larger than the number of all DES keys (or even all triple DES keys).
What does this mean for our question?
DES (or any set of permutations $\{T_i \mid i \in K\}$) being a group (subgroup of the set of permutations) would include that for each key $i$ and $j$ the composition $T_i \circ T_j$ is a DES encryption $T_l$, and also each decryption $T_j^{-1}$ is an encryption $T_m$. From that we could conclude that $T_i \circ T_j^{-1} \circ T_k$ is also a member of the group, i.e. that the set would be a pure set.
The reverse doesn't follow that easily, and neither is the proof directly applicable to our situation (both look at different corollaries from the group property).
I suppose one could do similar experiments as they did, search keys $i,j,k$ so that $(T_i \circ T_j^{-1} \circ T_k)(\mathtt 0) = c$ for random messages $c$ and argument similarly that this should give not as many matches as it does when that would be in $T_m$.
The other point of view is the practical one: If DES were pure, triple DES would be essentially the same as DES, and would be already broken by appliying a DES brute forcer on a triple-DES encrypted message. I can't believe nobody tried that yet.
