| Eli Biham, Alex Biryukov, Orr Dunkelman, Eran Richardson | Adi Shamir | ||
| Computer Science Dept. | Applied Math Dept. | ||
| Technion | The Weizmann Institute | ||
| Israel | Israel |
This note summarizes our first week of analysis. The main result is an attack on a variant, which we call SkipJack-3XOR (SkipJack minus 3 XORs). The only difference between SkipJack and SkipJack-3XOR is the removal of 3 out of the 320 XOR operations. The attack uses the ciphertexts derived from about 500 plaintexts which are identical except for the second 16 bit word. Its total running time is equivalent to about one million SkipJack encryptions, which can be carried out in seconds on a personal computer.
This is still a preliminary result, but it reiterates our earlier comment that SkipJack does not have a conservative design with a large margin of safety.
The attack is differential, and uses the following characteristic of SkipJack-3XOR: A plaintext difference (0,a,0,0) leads to the difference (b,c,0,0) after round 16 with probability 1, which in turn leads to a difference (d,0,0,0) after round 28 with probability 2^-16, for some unspecified non-zero values a,b,c, and d. This difference leads to some difference (e,f,g,0) in the ciphertexts, for some e,f, and g.
The attack requires two pairs of plaintexts with such a differential behavior. To get them, encrypt 2^9=512 distinct plaintexts which are identical except at their second word. They give rise to about 2^18/2=2^17 pairs, and each pair has the required property with probability 2^-16. The two right pairs can be easily recognized since the two ciphertexts in each pair must be equal in their last 16 bits.
The basic steps of the attack are:
(1) We know the input differences and the actual outputs of the 32nd G permutation. Each right pair yields a subset of about 2^16 possible key bytes cv_4,...,cv_7, and the intersection of the two subsets is likely to define these 32 key bits uniquely. This part can be implemented in about 2^16 evaluations of G.
(2) The 29th G permutation shares two key bytes cv_4, cv_5 with the 32nd G permutation, which are already known. 2^16 possible combinations of the two key bytes cv_2, cv_3 and the inputs to the 30th G permutation in both pairs can be found. A careful implementation of this step requires the time equivalent of 2^17 evaluations of G.
(3) For each of the 2^16 combinations we still miss the key bytes cv_8, cv_9 entering the last two F tables in round 30, and the key bytes cv_0 and cv_1 entering the first two F tables in round 31. Together they are equivalent to a single G, which we call G'. In each right pair, the two encryptions have the same value in G'. We view both right pairs as a super pair of two G' evaluations, whose actual inputs and outputs are known. The analysis of G' takes about the equivalent of 2^9 G evaluations, and thus the total complexity is equivalent to about 2^25 G evaluations.
Since each SkipJack encryption contains 2^5=32 G evaluations, the total time complexity of this cryptanalytic attack is equivalent to about one million SkipJack encryptions, and can be carried out in seconds on a personal computer.