Notes on an attack on Modified Skipjack



This note demonstrates what is perhaps obvious:  four rounds of
Skipjack (Rule A) is not secure.  I will show this by giving a known
plaintext attack which requires 2^64 work, which is less than a brute
for attack of 2^80 work.  Here, "work" means number of encryptions
through four rounds of A, and not  bit operations.

A word on notation:  for brevity I will say, for example, that something
takes 64 bits of work, rather than writing 2^64.

Given a plaintext P and the corresponding ciphertext C, we want to
find the key K = CV1, CV2,...,CV9.  The key to doing this is to note
that after only four rounds, "bit mixing" is not complete.  In
particular,  note that w_4^4 of C is given by the formula

   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.  In other
words, if we encrypt P with *any* key which agrees with with K in
these bytes, then the resulting ciphertext will agree with C in
the last word, W_4^4.  Therefore, if we arbitrarily fix the last two
bytes (say all zeros) and encrypt P with the 2^64 possible remaining
keys, we will find the value (or possible values) of the first 
8 bytes with 64 bits of work.  

For each possible value, we can now encrypt P with the 2^16 possible
keys and compare the results to the remaining words of C.  This
will yield the last two bytes of K.

The work in this stage is negligible compared to the previous work, so
we see that we can recover K with only 64 bits of work.


Questions:

1)  Can this attack be extended to 5 rounds of rule A?

2)  If this  were actually implemented on, say, a Sparc Station or
Pentium machine, how long would 2^64 encryptions with four rounds of
rule A take?

3)  Can this attack be optimised---that is, can we recover the key
in less than 64 bits of work?

4)  Is there a known ciphertext attack---that is, can we recover the
key only given one or more ciphertexts?

5)  Does this attack work against 4 rounds of rule B?

6)  Scheier says that there are attacks against 4 rounds of rule A
followed by four rounds of rule B, and against 8 rounds of rule B.
Can you find them?  

7)  Why won't the 8 round attack on B work against A?