[Next] [Up] [Previous] [Index]

# Skipjack

Skipjack, the originally secret algorithm associated with the controversial Clipper chip, was declassified on Tuesday, June 23, 1998, and appeared as a .PDF document at the NIST web site the following morning.

The basic round type of Skipjack forms another alternative, alongside those offered by SAFER and IDEA, to the Feistel round structure seen in DES, LUCIFER and Blowfish, among other block ciphers. In each round, one of four quarters of the block is subjected to four Feistel rounds on a small scale, and one other quarter is modified by being XORed with the round number and the quarter that went through the mini-Feistel cipher, either before or after that step. No bit transposes are required in Skipjack, making it efficient to implement on a general-purpose computer.

Skipjack has 32 rounds. These rounds are of two types, A and B. A type A round proceeds as follows:

The first quarter of the block (called W1) is enciphered by the "G permutation", which is actually a four-round Feistel cipher. The result, and the round number (where round numbers go from 1 through 32), are XORed with the fourth quarter of the block (W4). Then each quarter of the block is moved to the next position; W1 to W2, W2 to W3, W3 to W4, and W4 back to W1.

A type B round proceeds as follows:

The second quarter of the block (W2) is XORed with the round number and the first quarter of the block (W1). Then the first quarter of the block is enciphered by the "G permutation". Again, each quarter of the block is moved to the next position; W1 to W2, W2 to W3, W3 to W4, and W4 back to W1.

The rotation of quarters of the block is not omitted after the last round. The 32 rounds of Skipjack consists of eight type A rounds, eight type B rounds, eight type A rounds, and eight type B rounds. Note that by having a type A round first, and a type B round last, the form of the first quarter on the "inside" is XORed with one of the other quarters in the first and last rounds.

Permutation G is a four-round Feistel cipher, involving dividing its 16-bit input into two 8-bit halves. Like DES, the left half of the block is not changed in each round, but acts as input to the f-function, the output of which is XORed to the right half. Unlike DES, the two halves are swapped after the last round (as the algorithm has only four rounds, all four iterations of the f-function can be illustrated, going alternately from right to left, and then from left to right; in that form, no swaps at all are required).

The f-function of the G permutation is as simple as one might expect for an f-function only 8 bits wide: the input is first XORed with the current round's subkey, and then the result is substituted according to a lookup table, called F.

The subkeys for G, each one byte long, are simply four consecutive bytes of the 80-bit key. The first four bytes are used in the first round, the next four bytes in the second, the last two bytes followed by the first two bytes in the third, and so on.

The operation of Skipjack may be made clearer by the following diagram:

which illustrates the first 12 rounds of Skipjack. The first round, of type A, is shown with the G function illustrated in full. The next seven rounds, also of type A, are shown with the G function indicated by a box marked with a G. Then the last four of the twelve rounds shown, of type B, are showed the same way. There are dotted lines dividing the rounds in the diagram.

Instead of rotating the quarters of the block, the functions move between columns; since the last rotation is not skipped, this illustration will show, if continued to include all 32 rounds, the quarters ending up in their proper places without any final rotation being required.

The S-box of Skipjack, called F, which is the heart of the f-function of the Feistel mini-cipher that is the G permutation, is as follows:

``` a3 d7 09 83 f8 48 f6 f4 b3 21 15 78 99 b1 af f9
e7 2d 4d 8a ce 4c ca 2e 52 95 d9 1e 4e 38 44 28
0a df 02 a0 17 f1 60 68 12 b7 7a c3 e9 fa 3d 53
96 84 6b ba f2 63 9a 19 7c ae e5 f5 f7 16 6a a2
39 b6 7b 0f c1 93 81 1b ee b4 1a ea d0 91 2f b8
55 b9 da 85 3f 41 bf e0 5a 58 80 5f 66 0b d8 90
35 d5 c0 a7 33 06 65 69 45 00 94 56 6d 98 9b 76
97 fc b2 c2 b0 fe db 20 e1 eb d6 e4 dd 47 4a 1d
42 ed 9e 6e 49 3c cd 43 27 d2 07 d4 de c7 67 18
89 cb 30 1f 8d c6 8f aa c8 74 dc c9 5d 5c 31 a4
70 88 61 2c 9f 0d 2b 87 50 82 54 64 26 7d 03 40
34 4b 1c 73 d1 c4 fd 3b cc fb 7f ab e6 3e 5b a5
ad 04 23 9c 14 51 22 f0 29 79 71 7e ff 8c 0e e2
0c ef bc 72 75 6f 37 a1 ec d3 8e 62 8b 86 10 e8
08 77 11 be 92 4f 24 c5 32 36 9d cf f3 a6 bb ac
5e 6c a9 13 57 25 b5 e3 bd a8 3a 01 05 59 2a 46
```

or, in decimal form,

``` 163 215   9 131 248  72 246 244 179  33  21 120 153 177 175 249
231  45  77 138 206  76 202  46  82 149 217  30  78  56  68  40
10 223   2 160  23 241  96 104  18 183 122 195 233 250  61  83
150 132 107 186 242  99 154  25 124 174 229 245 247  22 106 162
57 182 123  15 193 147 129  27 238 180  26 234 208 145  47 184
85 185 218 133  63  65 191 224  90  88 128  95 102  11 216 144
53 213 192 167  51   6 101 105  69   0 148  86 109 152 155 118
151 252 178 194 176 254 219  32 225 235 214 228 221  71  74  29
66 237 158 110  73  60 205  67  39 210   7 212 222 199 103  24
137 203  48  31 141 198 143 170 200 116 220 201  93  92  49 164
112 136  97  44 159  13  43 135  80 130  84 100  38 125   3  64
52  75  28 115 209 196 253  59 204 251 127 171 230  62  91 165
173   4  35 156  20  81  34 240  41 121 113 126 255 140  14 226
12 239 188 114 117 111  55 161 236 211 142  98 139 134  16 232
8 119  17 190 146  79  36 197  50  54 157 207 243 166 187 172
94 108 169  19  87  37 181 227 189 168  58   1   5  89  42  70
```

This was double-checked by looking at the inverse of this S-box generated by the same program that converted what I typed from hexadecimal to decimal, as the S-box is a straight permutation of the numbers from 0 to 255. In the original document in the electronic form in which it was publicly distributed, and which was based on scanned images, lowercase c and e are sometimes difficult to distinguish.

For decipherment, each round is replaced by a corresponding deciphering round, and these rounds are, of course, executed in the reverse of the enciphering order.

The deciphering equivalent of a type A round is as follows:

The first quarter, W1, is XORed with W2 and the round number (rounds now counting down from 32 to 1). Then the second quarter, W2, is subjected to the inverse of the G permutation. Then, each quarter is moved to the position of the preceding one; W1 to W4, W2 to W1, W3 to W2, and W4 to W3.

The deciphering equivalent of a type B round is the following:

The second quarter, W2, is subjected to the inverse of the G permutation. The third quarter, W3, is then XORed with the round number and the changed value of W2. Again, each quarter is moved to the position of the preceding one; W1 to W4, W2 to W1, W3 to W2, and W4 to W3.

The deciphering equivalent of the G permutation involves using the four subkeys in reverse order - and reversing the roles of the right and left halves of the 16-bit quarter block.

SKIPJACK was declassified in order to facilitate finding private companies to manufacture devices using that algorithm for use by the U.S. Government. Some people have called attention to the fact that only a short time previously, government spokespersons were saying that the disclosure of that algorithm would harm national security.

However, I have noted that the inconsistency involved may be more apparent than real. Between the statements cited, and the declassification of SKIPJACK, a paper was published by an academic researcher noting that Feistel ciphers of a particular type, specifically those in which the f-function was itself a series of Feistel rounds, could be proven to be immune to differential cryptanalysis.

SKIPJACK, although not precisely of that type, is closely related: one of the four subblocks undergoes Feistel rounds, but in addition to the result being used, as an f-function output, on another subblock, the subblock is also retained in its modified state.

Also, note that SKIPJACK consists of eight type A rounds, followed by eight type B rounds twice, instead of sixteen type A rounds and then sixteen type B rounds. Since the type A rounds are appropriate for the beginning of the cipher, and the type B rounds are appropriate for its end, it might seem at first that this weakened the cipher. However, the boomerang attack, which was discovered after the declassification of SKIPJACK, allows differential cryptanalysis to be done independently on the first and last half of a block cipher; thus, if SKIPJACK were composed of two halves, each with one type of round, it could have been attacked as if it consisted of only a single type of round.

It may also be noted that a recent book, Top Secret Intranet, reveals that SKIPJACK was considered adequate to safeguard information classified SECRET but not information classified TOP SECRET. This appears to refer to early 1999, and may still be the case as of this writing (May 1999). Also, note that SKIPJACK has an 80-bit key, the key-length limit for exportable ciphers is 40 bits, and some suppliers of encryption equipment to the U.S. government have advertised their equipment provides a 120-bit key or a 160-bit key. This may be because 40 is a multiple of both 8 and 10, and 2^10 equals 1024, which is just over 1000. Thus every 40 bits in a key can have just over a trillion possible values, making it easy to express the number of possible keys in decimal terms.

One notes that the key consists of 10 bytes, which is a number of the form 4n+2. While it might not increase the security of SKIPJACK to do so, if there are no subtle traps in the structure of SKIPJACK, which appears to have a simple and uniform structure, it might be possible to use a key composed of the next such number of bytes with it: 14 bytes. That is an interesting possibility, because such a key would be a 112-bit key, exactly twice as long as the key used in DES.

One other thing I remembered from reading Top Secret Intranet was how the CIA had licensed various reference works, to make conveniently available within their own secured intranet, so that subjects that were being referenced could not be seen on the outside, potentially leaking information.

When I heard the news that, due to using out-of-date maps as a reference, the embassy of the People's Republic of China in Belgrade was bombed on May 7, 1999, the first thought that crossed my mind was that this could have been caused by the one atlas made more convenient to consult than any paper maps, the one used on this system, might have been the outdated one that was at fault.

The name Skipjack was noted as being the name of a kind of boat.

A skipjack is a sailing vessel; currently, it is the official state boat of the state of Maryland. The name came from several types of fish that leaped out of the water, such as skipjack tuna and skipjack shad, because this type of ship was fast and agile.

In 1976, the Canadian singer Gordon Lightfoot recorded the well-known song "The Wreck of the Edmund Fitzgerald", which was about the sinking of a ship that carried such cargoes as iron ore across Lake Superior.

Although this is the most famous recent song I know of concerning a maritime disaster, there have been many others. For example, several popular songs were inspired by the sinking of the Titanic, such as "Be British", "The Titanic (It Was Sad when that Great Ship Went Down)", and several others, including songs by Leadbelly (Huddle William Ledbetter) and Blind Willie Johnson.

It was in 1977 that Meneely Van Sante recorded "The Claude W. Somers". This boat, a skipjack, which was at the time dredging for oysters in Chesapeake Bay, sank in 1977 due to being struck by a squall, and the six people aboard died, consisting of its owner and captain Thompson Wallace, and his crew, all but one of whom were members of his family.

They were engaged in dredging for oysters in Chesapeake Bay. On that tragic day, rough weather was forecast for the afternoon, but they ventured out to work only in the morning, before it was expected to strike. After the ship was hit, they recieved assistance, but elected to remain aboard the vessel rather than abandoning it when it was no longer safe to continue towing it.

Thompson Wallace was one of the few black men who owned a skipjack; there were many skilled black sailors who were involved in the Chesapeake Bay oyster fishery, but there was opposition to black people owning boats instead of working for white owners, and black people also faced difficulties in selling their catch. He was not its first owner, the ship having been constructed in 1911.

No doubt this was one of the factors that made it difficult to just walk away from the ship, and instead encouraged them to make extra effort, and take additional risks, to try and save it.

The ship was recovered, and it was repaired, and now takes passengers in the service of a museum, due to its historical significance as one of the few surviving examples of this kind of ship, important in the past economic life of Chesapeake Bay.

[Next] [Up] [Previous] [Index]