Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:54 ADT
David Wagner (daw@CS.Berkeley.EDU)
Sat, 25 Jul 1998 19:21:29 -0700 (PDT)
> > Furthermore, if DES were a group, then single-DES (and 3-DES) would
> > be breakable with about 2^{28} offline work and one known plaintext
> > via a meet-in-the-middle attack.
> >
> > The attack works as follows. Suppose we have a known text pair (P,C).
> > First, we store (E_i(P), i) in a lookup table keyed on E_i(P) for
> > 2^{28} values of i. Next, we compute D_j(C) for 2^{28} values of j
> > and look for a match in the table of the form E_i(P) = D_j(C). When
> > we find such a match, we can deduce that the 2-DES key (i,j) is
> > equivalent to the unknown single-DES key. This will let us decrypt
> > the rest of the ciphertext.
>
> It seems to me that this is assuming rather more than just group
> properties. In particular, I'm guessing that for this to be true the
> group would have to have at most 2^29 generators.
I don't think so. (Though I could be wrong.) Here's my reasoning.
Let I be the set of i's, and J be the set of j's. Identify each
key with the corresponding element of the permutation group S_{2^{64}},
and use * to denote the group operation (namely, composition), so
that i*j represents the key (or equivalently, the group element)
which is equivalent to encryption by key j followed by encryption
by key i. Write i^{-1} for the inverse of i, i.e. the group element
l such that i*l = l*i = the identity. Write k for the unknown key
which we are trying to find. Finally, define the set I' as
I' = { k * i^{-1} : i in I }.
With the notation out of the way, I'll proceed with the analysis of
the algorithm.
Claim. If the intersection of I' and J is non-empty, then
the algorithm will succeed with high probability.
Proof. Suppose k * i^{-1} = j; then k = j*i, and so E_k(x) = E_j(E_i(x))
for all x. In particular, E_j(E_i(P)) = E_k(P) = C, so
E_i(P) = D_j(C). So long as there is no other i',j' such
that E_i'(P) = D_j'(C), the algorithm will output the 2-DES
key (i,j), which is equivalent to the key j*i = k, so the
algorithm will be correct in this case.
This leaves only the case where E_i'(P) = D_j'(C). If
j'*i' = k, then the algorithm will be correct, so we only
need to consider i',j' such that j'*i' != k. Then we can
expect that E_i'(P) = D_j'(C) occurs with probability
2^{-64}, for random i',j'. Since there are 2^{56} pairs
i',j', the probability of failure is at most about 2^{-8},
which is acceptably small. (Moreover, it can be made
arbitrarily small by testing i',j' on a few extra pairs
of known plaintext.)
Claim. The intersection of I' and J will be non-empty with
good probability.
Proof. An easy application of the birthday paradox: I' and J
are random, with |I'| = |J| = 2^{28}, so the probability
of an empty intersection is
(1 - 2^{-56})^{2^{56}} ~ e^{-1} ~ .368.
This failure probability can be easily made exponentially
small by increasing the size of |I'| and |J| by a constant
factor.
Does that seem right? I could well be doing something wrong.
(I haven't seen the full details of this sort of attack anywhere
in the literature -- I've only seen the complexity of it alluded
to in one paper -- so I am making this up as I go along, and might
well have made a mistake somewhere.)
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:54 ADT