Cryptanalysis of SkipJack-4XOR

Eli Biham, Alex Biryukov, Orr Dunkelman, Eran Richardson Adi Shamir
Computer Science Dept.
Applied Math Dept.
TechnionThe Weizmann Institute

June 30, 1998

This note can be found in
Feel free to distribute


SkipJack is the secret key encryption algorithm used by the US government in the Clipper chip and Fortezza PC card. It was implemented in tamper-resistant hardware and its structure had been classified since its introduction in 1993. On June 24th, 1998, SkipJack was unclassified, and its description is available at the web site of NIST.

In a note from June 25th, we described our initial observations on SkipJack, after several hours of analysis. In this note we summarize our new observations after several days of analysis.

The main new result in this note is an attack on a variant of SkipJack which contains all 32 rounds but omits four XORs. We call this variant SkipJack-4XOR (SkipJack minus four XORs). For the sake of simplicity, we describe in this note an unoptimized attack which requires 2^48 time, using about 2^25 chosen plaintexts or about 2^49 known plaintexts. Improved attacks on SkipJack-4XOR and on other variants which are even closer to SkipJack will be described in a forthcoming note.

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.

In the remainder of this note we first describe additional observations and extensions of our previous note, and then describe a new technical tool, which we call the Yoyo game. Finally, we describe a simple version of our attack on SkipJack-4XOR, which suffices to get the above results.

Improvements of the Attacks From the Previous Note

The attacks in the previous note used the probability of certain characteristics of the G permutations. As these attacks did not use the internal paths of these characteristics, we can increase the probabilities by looking at the corresponding differentials. We used a cycle of three characteristics (a,0)->(0,b)->(a,b)->(a,0). The characteristic (a,0)->(0,b) has the same probability as a differential and as a characteristic. (0,b)->(a,b) and (a,b)->(a,0) have over a thousand small-probability counterparts with the same external differences. The total probability of all these characteristics is almost twice that of the original characteristics (e.g., 137088/2^32 instead of 73728/2^32 in one case). As these two characteristics were used twice in the attack, the total complexity of the attack reduces by a factor of almost 4.

We had also investigated other differentials of G. The characteristics we described with probability of around 2^-10.42 (and other lower probability characteristics with zero differences in the first and fourth rounds of the G permutation) do not have any counterparts, and thus the corresponding differentials have the same probabilities as the characteristics. The best other differential we are aware of is 002A->0095 with probability 2^-14.715, and the best possible differential with the same input and output differences is 7F7F->7F7F with probability 2^-15.84.

David Wagner (private communication) described various interesting improvements and provided an extended attack on the 16-round variant of SkipJack. We are grateful for his insightful contribution.

Additional Observations

It is interesting to note that due to the switchover from Rule A to Rule B iterations, the data between rounds 5 and 12 is very badly mixed. As mentioned in our previous note, in the border between the two rules (after rounds 8 and 24), the leftmost word is exchanged with word 2, and the new word 1 XORed with the new word 2. We observed that the output of the G permutation in round 5 becomes the input to the G permutation in round 12, unaffected by other words (but XORed with the fixed value 8 XOR 9 = 1). Thus, this word is not affected by any other word during 8 consecutive rounds. A similar property occurs in word 3 from round 7 to round 11, and in word 4 from round 6 to round 10. On the other hand, from round 4 to round 13 word 2 (renamed later to word 1) is affected several times by the other words, and the G permutation is applied on it several times, but it does not affect the other words. Actually this word affects other words only twice, and on both occasions it affects the same word (word 1, renamed later to word 2), which in turn is affected only by these two XOR mixings. This phenomena is the combination of the XOR structure of the last Rule A round and the first Rule B round, that actually exchanges the two leftmost words, together with the change of the direction of the XOR mixing arrows from right-to-left to left-to-right.

A better presentation of the first 16 rounds of SkipJack than the one presented in our previous note is:

Description of SkipJack-4XOR

In this note we consider variants of SkipJack which are identical to the original version except for the removal of a few XOR operations. We use the name SkipJack-(i1,...,ik) to denote the variant in which the XOR operations at rounds i1,...,ik are removed, and the name SkipJack-4XOR as a shorthand for SkipJack-(1,16,17,32), which is the main variant we attack. The following figure describes the first 16 rounds of this variant (rounds 17 to 32 are identical, except for the round indices):

The Yoyo Game

Consider the first 16 rounds of SkipJack-4XOR. We are interested in pairs of encryptions P=(w_1, w_2, w_3, w_4) and P^*=(w^*_1, w^*_2, w^*_3, w^*_4) which have the same data at the leftmost word in the input of round 5. As this word is not affected by any other word until it becomes word 2 in round 12, we can conclude that both encryptions have the same data in word 2 after round 12.

We next observe that given a pair with such an equality in the data, we can exchange the first word of the plaintexts (w^*_1, w_2, w_3, w_4) and (w_1, w^*_2, w^*_3, w^*_4), and this new pair of plaintexts still has the same property of equality in the input of round 5. Moreover, if the first words of the plaintexts are equal (i.e., w_1=w^*_1 and thus exchanging them does nothing) we can exchange the second words (w_2 with w^*_2) and get the same property. If they are also equal, we can exchange w_3 with w^*_3 and get the same property. If they are also equal, we exchange w_4 with w_4^*. However, if the property holds, this last case is impossible, as a difference of only one word ensures that the property is not satisfied.

Given the ciphertexts we can carry out a similar operation of exchanging words 2. If words 2 are equal, exchange words 1, then words 4, and then words 3. Also in this case a difference of only one word ensures that the property is not satisfied.

The Yoyo game starts by choosing an arbitrary pair of distinct plaintexts P_0, P^*_0. Both plaintexts are encrypted to C_0, C^*_0. We exchange a pair of words of the two ciphertexts as described above, receiving C_1 and C^*_1, and decrypt them to get P_1, P^*_1. Now we exchange the words of the plaintexts as described above, receiving P_2 and P^*_2, and encrypt to get C_2, C^*_2. The Yoyo game repeats this forever.

In this game, whenever we start with a pair of plaintexts with equality at the leftmost word in the input of round 5, all the later received pairs of encryptions must have the same property, and if we start with a pair of plaintexts which have different values at the leftmost word in the input of round 5, all the later received encryptions cannot have equality in any of the subsequent pairs of encryptions.

There are some heuristic techniques to identify that a cycle of such pairs of encryptions does not have the equality property. For example, when we receive a pair of plaintexts (or ciphertexts) of which three words are equal but the fourth differ, we know for sure that the equality property does not hold, and thus all the pairs in the cycle do not have such an equality. As there are four cases for such 48-bit zero differences, the probability of obtaining such pairs is 2^-46 in each step of the game. Once such a pair is encountered, we can stop the Yoyo game, since we know that its continuation will simply repeat the same sequence of steps in reverse order.

On the other hand, if the equality property holds we are ensured that at least two words differ, and thus each step generates a new set of encryptions. As the whole process is reversible, the expected cycle size is proportional to the number of such pairs, i.e., O(2^112).

This game can be used for several purposes. The first is to identify pairs with the equality property. After trying 2^16 pairs, and computing the game for each, we can identify the few with a cycle of size larger than 2^50 for instance. (Note that it is easy to generate 2^16 pairs from 2^16+1 plaintexts in such a way that exactly one of them satisfies the property). Then we can use it to recover the keys. However, as we are aware of better attacks on the same cipher, this is not proposed here.

Another application might be to increase the probability of finding right pairs for other attacks. Assume that we already got a right pair, and wish to compute additional right pairs. If right pairs have the same equality property, then such a game can give us many candidates with this property for almost free.

Cryptanalysis of SkipJack-4XOR

In this section we describe a simple attack on the 32-round SkipJack-4XOR, which recovers the full 80-bit key in time 2^48 using 2^25 chosen plaintexts.

The starting point of the attack is the observation that the differential characteristic we used in our previous note can use partially unspecified differences. In this way we can use the following characteristic of SkipJack-4XOR: An initial unspecified difference (a,b,0,0) leads to the difference (0,c,0,0) with probability 2^-16 for some non-zero a,b,c. This difference leads to some difference (d,0,0,0) in the data (as represented in the above figure) between rounds 8 and 9, and to some (e,0,0,0) after round 12. The difference after round 16 becomes (f,g,0,0) for some non-zero f and g. This 16-round characteristic has probability 2^-16. It is easy to see that this characteristic is iterative, and thus a full 32-round characteristic of SkipJack-4XOR has probability 2^-32.

Given 2^32 pairs of plaintexts differing only in the leftmost two words, and their ciphertexts, it is easy to discard almost all the wrong pairs, as the ciphertext pairs should have the same values of the rightmost two words. Thus it is expected that only one right pair remains, along with one wrong pair. Due to their simple characterization, these 2^32 pairs can be packed into a single structure of 2^17 chosen plaintexts, or alternatively be found in approximately 2^33 known plaintexts.

The actual attack requires four distinct plaintexts (rather than a pair) with the same value of the rightmost two words, and which happen to have the same value v_1 of the leftmost word in the input of round 5, and the same value v_2 of the leftmost word in the input of round 21 (for some arbitrary v_1 and v_2). Such four plaintexts are expected to be found in a structure of 2^25 random plaintexts whose rightmost two words are fixed, as the number of quartets is about 2^96, and there are six 16-bit equality conditions at rounds 5 and 21. Given the ciphertexts, it is easy to identify the right pairs, and thus also the four plaintexts and their corresponding ciphertexts. Now, we know that the data in the second word after round 28 is the same in all four encryptions. Notice that the G permutation in round 32 and the G permutation in round 29 share two common key bytes.

For the four ciphertexts, try decrypting the second word by all the possible 32-bit subkeys of round 32 (i.e., defined by the key bytes cv_4, ..., cv_7), receiving some values X1,X2,X3,X4 for each possible subkey. Keep the differences X1 XOR X2, X1 XOR X3, X1 XOR X4 in a table together with their corresponding subkeys cv_4, ..., cv_7. We also know the outputs of the G permutation in round 29 up to some unknown 16-bit fixed value (which is the common value of the rightmost word at that round), and we know that the inputs Y1,Y2,Y3,Y4 satisfy (Y1 XOR Y2, Y1 XOR Y3, Y1 XOR Y4) equal the 48 bits in the real (X1 XOR X2, X1 XOR X3, X1 XOR X4). We can try all the 2^48 possible combinations of the 16-bit fixed value and the 32-bit subkey of round 29, consisting of cv_6,...,cv_9, and compute the 48-bit differences. For each such value we verify that such a difference exists in the table and that the common two key bytes are equal. It is expected that about 2^16 possible candidate combinations of the fixed value, of the 32-bit subkey of round 29, and of the subkey of round 32 remain. Thus, we get 2^16 candidates for cv_4,...,cv_9, leaving only cv_0,...,cv_3 unknown. Since there are only 2^32 possible values for these four bytes, we can find them by an exhaustive search of 2^48 time without change of the overall time complexity.

This attack can also be converted into a known plaintext attack using 2^49 known plaintexts and essentially the same time complexity.


1. For the sake of simplicity we did not describe the most efficient implementation of our attack on SkipJack-4XOR. Optimized versions can reduce both the running time and the number of required plaintexts.

2. Similar attacks are possible on ciphers which are even more similar to SkipJack, such as SkipJack-(1,16,17) and SkipJack-(16,17,32), but with higher complexities.

Details on these improved results will be given in a forthcoming announcement.


It is a pleasure to acknowledge Rivka Zur, the Technion CS secretary, for preparing the figures. We also thank Charanjit Jutla for correcting a typo in the first version.
Back to Observations on the SkipJack Encryption Algorithm