Another Attack on Modified Skipjack



In my last note I presented a 64 bit, known plaintext attack against
4 rounds of rule A of Skipjack.  Here I present a *much* faster attack,
one which I think could be implemented on a desk top machine.  This
also leads to a theoretical known ciphertext attack.

Using the same notation as in my last note, recall that the
key equation was

   w_4^4 = G^1(w_1^1)= G^1(G^0(W_1^0)+W_4^0),

where "+" denotes bitwise addition.  The two permutations G_0 and G_1
only depend on the first 8 bytes, CV_0...CV_7, of the key.  I want
to rewrite this as follows:  let H^i be the inverse of G^i:
H^i(G^i(w)) = G^i(H^i(w)) = w for any word w.  Then we can rewrite
this equation as

           H^1(w_4^4) = G^0(W_1^0)+W_4^0.

Notice that the LHS depends only on known things and the unknown CV_4,
CV_5, CV_6 and CV_7, while the RHS depends on the unknown CV_0, CV_1,
CV_2 and CV_3.  We are going to do what is called a man-in-the-middle
attack:

Step 1:  compute all possible values of H^1(w_4^4) by exhausting
over all possible values of the CV_4--CV_7.  This takes
32 bits of work.

Step 2:  compute all possible values of G^0(W_1^0)+W_4^0.  This also
takes 32 bits of work.

Step 3:  sort the two lists and compare until you find the ones that
agree.  This gives you the only possibilities for CV_0...CV_7.  
Sorting the list take about 32*2^32 operations, or about 37 bits
of work.  It also requires about 2^32 memory.  [Someone correct
me if these estimates are off.]  

Step 4: exhaust over the remaining two bytes of unknown key.  As
before, this is 16 bits of work and so inconsequential.

Therefore, we have gotten the key in 37 bits of work.


Because this has reduced the work factor so much, we can convert
this to a known ciphertext attack.  The steps are almost the same as
before, but the work goes up because more is unknown.

Step 1:  Since w_4^4 is known, this step still requires 32 bits
of work.

Step 2:  In this step, w_1^0 and W_4^0 are unknown.  Therefore we
have to exhaust over all the 2^32 values these words could take on
as well as over the values of CV_0--CV_3.  Hence this step 
requires 64 bits of work.

Step 3:  One of the lists to be sorted is much longer, and so
this step now requires about 64*2^64 work or about 70 bits.

Step 4:  We now have to exhaust over the two remaining bytes
of the key and the four unknown bytes of the plaintext, so this
step will require 48 bits of work.  It can probably be optimised,
but Steps 2 and 3 take so much work that it is probably not
worth it.


Questions:

1) Can you extend this revised attack to one against 5 rounds of A?

2) What about 6 rounds of A?