5 /* des.c - implementation of DES
12 * Unlike the description in FIPS 46, I'm going to use _sensible_ indices:
13 * bits in an n-bit word are numbered from 0 at the LSB to n-1 at the MSB.
14 * And S-boxes are indexed by six consecutive bits, not by the outer two
15 * followed by the middle four.
17 * The DES encryption routine requires a 64-bit input, and a key schedule K
18 * containing 16 48-bit elements.
20 * First the input is permuted by the initial permutation IP.
21 * Then the input is split into 32-bit words L and R. (L is the MSW.)
22 * Next, 16 rounds. In each round:
23 * (L, R) <- (R, L xor f(R, K[i]))
24 * Then the pre-output words L and R are swapped.
25 * Then L and R are glued back together into a 64-bit word. (L is the MSW,
26 * again, but since we just swapped them, the MSW is the R that came out
28 * The 64-bit output block is permuted by the inverse of IP and returned.
30 * Decryption is identical except that the elements of K are used in the
31 * opposite order. (This wouldn't work if that word swap didn't happen.)
33 * The function f, used in each round, accepts a 32-bit word R and a
34 * 48-bit key block K. It produces a 32-bit output.
36 * First R is expanded to 48 bits using the bit-selection function E.
37 * The resulting 48-bit block is XORed with the key block K to produce
39 * This block X is split into eight groups of 6 bits. Each group of 6
40 * bits is then looked up in one of the eight S-boxes to convert
41 * it to 4 bits. These eight groups of 4 bits are glued back
42 * together to produce a 32-bit preoutput block.
43 * The preoutput block is permuted using the permutation P and returned.
45 * Key setup maps a 64-bit key word into a 16x48-bit key schedule. Although
46 * the approved input format for the key is a 64-bit word, eight of the
47 * bits are discarded, so the actual quantity of key used is 56 bits.
49 * First the input key is converted to two 28-bit words C and D using
50 * the bit-selection function PC1.
51 * Then 16 rounds of key setup occur. In each round, C and D are each
52 * rotated left by either 1 or 2 bits (depending on which round), and
53 * then converted into a key schedule element using the bit-selection
56 * That's the actual algorithm. Now for the tedious details: all those
57 * painful permutations and lookup tables.
59 * IP is a 64-to-64 bit permutation. Its output contains the following
60 * bits of its input (listed in order MSB to LSB of output).
62 * 6 14 22 30 38 46 54 62 4 12 20 28 36 44 52 60
63 * 2 10 18 26 34 42 50 58 0 8 16 24 32 40 48 56
64 * 7 15 23 31 39 47 55 63 5 13 21 29 37 45 53 61
65 * 3 11 19 27 35 43 51 59 1 9 17 25 33 41 49 57
67 * E is a 32-to-48 bit selection function. Its output contains the following
68 * bits of its input (listed in order MSB to LSB of output).
70 * 0 31 30 29 28 27 28 27 26 25 24 23 24 23 22 21 20 19 20 19 18 17 16 15
71 * 16 15 14 13 12 11 12 11 10 9 8 7 8 7 6 5 4 3 4 3 2 1 0 31
73 * The S-boxes are arbitrary table-lookups each mapping a 6-bit input to a
74 * 4-bit output. In other words, each S-box is an array[64] of 4-bit numbers.
75 * The S-boxes are listed below. The first S-box listed is applied to the
76 * most significant six bits of the block X; the last one is applied to the
79 * 14 0 4 15 13 7 1 4 2 14 15 2 11 13 8 1
80 * 3 10 10 6 6 12 12 11 5 9 9 5 0 3 7 8
81 * 4 15 1 12 14 8 8 2 13 4 6 9 2 1 11 7
82 * 15 5 12 11 9 3 7 14 3 10 10 0 5 6 0 13
84 * 15 3 1 13 8 4 14 7 6 15 11 2 3 8 4 14
85 * 9 12 7 0 2 1 13 10 12 6 0 9 5 11 10 5
86 * 0 13 14 8 7 10 11 1 10 3 4 15 13 4 1 2
87 * 5 11 8 6 12 7 6 12 9 0 3 5 2 14 15 9
89 * 10 13 0 7 9 0 14 9 6 3 3 4 15 6 5 10
90 * 1 2 13 8 12 5 7 14 11 12 4 11 2 15 8 1
91 * 13 1 6 10 4 13 9 0 8 6 15 9 3 8 0 7
92 * 11 4 1 15 2 14 12 3 5 11 10 5 14 2 7 12
94 * 7 13 13 8 14 11 3 5 0 6 6 15 9 0 10 3
95 * 1 4 2 7 8 2 5 12 11 1 12 10 4 14 15 9
96 * 10 3 6 15 9 0 0 6 12 10 11 1 7 13 13 8
97 * 15 9 1 4 3 5 14 11 5 12 2 7 8 2 4 14
99 * 2 14 12 11 4 2 1 12 7 4 10 7 11 13 6 1
100 * 8 5 5 0 3 15 15 10 13 3 0 9 14 8 9 6
101 * 4 11 2 8 1 12 11 7 10 1 13 14 7 2 8 13
102 * 15 6 9 15 12 0 5 9 6 10 3 4 0 5 14 3
104 * 12 10 1 15 10 4 15 2 9 7 2 12 6 9 8 5
105 * 0 6 13 1 3 13 4 14 14 0 7 11 5 3 11 8
106 * 9 4 14 3 15 2 5 12 2 9 8 5 12 15 3 10
107 * 7 11 0 14 4 1 10 7 1 6 13 0 11 8 6 13
109 * 4 13 11 0 2 11 14 7 15 4 0 9 8 1 13 10
110 * 3 14 12 3 9 5 7 12 5 2 10 15 6 8 1 6
111 * 1 6 4 11 11 13 13 8 12 1 3 4 7 10 14 7
112 * 10 9 15 5 6 0 8 15 0 14 5 2 9 3 2 12
114 * 13 1 2 15 8 13 4 8 6 10 15 3 11 7 1 4
115 * 10 12 9 5 3 6 14 11 5 0 0 14 12 9 7 2
116 * 7 2 11 1 4 14 1 7 9 4 12 10 14 8 2 13
117 * 0 15 6 12 10 9 13 0 15 3 3 5 5 6 8 11
119 * P is a 32-to-32 bit permutation. Its output contains the following
120 * bits of its input (listed in order MSB to LSB of output).
122 * 16 25 12 11 3 20 4 15 31 17 9 6 27 14 1 22
123 * 30 24 8 18 0 5 29 23 13 19 2 26 10 21 28 7
125 * PC1 is a 64-to-56 bit selection function. Its output is in two words,
126 * C and D. The word C contains the following bits of its input (listed
127 * in order MSB to LSB of output).
129 * 7 15 23 31 39 47 55 63 6 14 22 30 38 46
130 * 54 62 5 13 21 29 37 45 53 61 4 12 20 28
132 * And the word D contains these bits.
134 * 1 9 17 25 33 41 49 57 2 10 18 26 34 42
135 * 50 58 3 11 19 27 35 43 51 59 36 44 52 60
137 * PC2 is a 56-to-48 bit selection function. Its input is in two words,
138 * C and D. These are treated as one 56-bit word (with C more significant,
139 * so that bits 55 to 28 of the word are bits 27 to 0 of C, and bits 27 to
140 * 0 of the word are bits 27 to 0 of D). The output contains the following
141 * bits of this 56-bit input word (listed in order MSB to LSB of output).
143 * 42 39 45 32 55 51 53 28 41 50 35 46 33 37 44 52 30 48 40 49 29 36 43 54
144 * 15 4 25 19 9 1 26 16 5 11 23 8 12 7 17 0 22 3 10 14 6 20 27 24
148 * Implementation details
149 * ----------------------
151 * If you look at the code in this module, you'll find it looks
152 * nothing _like_ the above algorithm. Here I explain the
155 * Key setup has not been heavily optimised here. We are not
156 * concerned with key agility: we aren't codebreakers. We don't
157 * mind a little delay (and it really is a little one; it may be a
158 * factor of five or so slower than it could be but it's still not
159 * an appreciable length of time) while setting up. The only tweaks
160 * in the key setup are ones which change the format of the key
161 * schedule to speed up the actual encryption. I'll describe those
164 * The first and most obvious optimisation is the S-boxes. Since
165 * each S-box always targets the same four bits in the final 32-bit
166 * word, so the output from (for example) S-box 0 must always be
167 * shifted left 28 bits, we can store the already-shifted outputs
168 * in the lookup tables. This reduces lookup-and-shift to lookup,
169 * so the S-box step is now just a question of ORing together eight
172 * The permutation P is just a bit order change; it's invariant
173 * with respect to OR, in that P(x)|P(y) = P(x|y). Therefore, we
174 * can apply P to every entry of the S-box tables and then we don't
175 * have to do it in the code of f(). This yields a set of tables
176 * which might be called SP-boxes.
178 * The bit-selection function E is our next target. Note that E is
179 * immediately followed by the operation of splitting into 6-bit
180 * chunks. Examining the 6-bit chunks coming out of E we notice
181 * they're all contiguous within the word (speaking cyclically -
182 * the end two wrap round); so we can extract those bit strings
183 * individually rather than explicitly running E. This would yield
186 * y |= SPboxes[0][ (rotl(R, 5) ^ top6bitsofK) & 0x3F ];
187 * t |= SPboxes[1][ (rotl(R,11) ^ next6bitsofK) & 0x3F ];
189 * and so on; and the key schedule preparation would have to
190 * provide each 6-bit chunk separately.
192 * Really we'd like to XOR in the key schedule element before
193 * looking up bit strings in R. This we can't do, naively, because
194 * the 6-bit strings we want overlap. But look at the strings:
196 * 3322222222221111111111
197 * bit 10987654321098765432109876543210
208 * The bit strings we need to XOR in for boxes 0, 2, 4 and 6 don't
209 * overlap with each other. Neither do the ones for boxes 1, 3, 5
210 * and 7. So we could provide the key schedule in the form of two
211 * words that we can separately XOR into R, and then every S-box
212 * index is available as a (cyclically) contiguous 6-bit substring
213 * of one or the other of the results.
215 * The comments in Eric Young's libdes implementation point out
216 * that two of these bit strings require a rotation (rather than a
217 * simple shift) to extract. It's unavoidable that at least _one_
218 * must do; but we can actually run the whole inner algorithm (all
219 * 16 rounds) rotated one bit to the left, so that what the `real'
220 * DES description sees as L=0x80000001 we see as L=0x00000003.
221 * This requires rotating all our SP-box entries one bit to the
222 * left, and rotating each word of the key schedule elements one to
223 * the left, and rotating L and R one bit left just after IP and
224 * one bit right again just before FP. And in each round we convert
225 * a rotate into a shift, so we've saved a few per cent.
227 * That's about it for the inner loop; the SP-box tables as listed
228 * below are what I've described here (the original S value,
229 * shifted to its final place in the input to P, run through P, and
230 * then rotated one bit left). All that remains is to optimise the
231 * initial permutation IP.
233 * IP is not an arbitrary permutation. It has the nice property
234 * that if you take any bit number, write it in binary (6 bits),
235 * permute those 6 bits and invert some of them, you get the final
236 * position of that bit. Specifically, the bit whose initial
237 * position is given (in binary) as fedcba ends up in position
238 * AcbFED (where a capital letter denotes the inverse of a bit).
240 * We have the 64-bit data in two 32-bit words L and R, where bits
241 * in L are those with f=1 and bits in R are those with f=0. We
242 * note that we can do a simple transformation: suppose we exchange
243 * the bits with f=1,c=0 and the bits with f=0,c=1. This will cause
244 * the bit fedcba to be in position cedfba - we've `swapped' bits c
245 * and f in the position of each bit!
247 * Better still, this transformation is easy. In the example above,
248 * bits in L with c=0 are bits 0x0F0F0F0F, and those in R with c=1
249 * are 0xF0F0F0F0. So we can do
251 * difference = ((R >> 4) ^ L) & 0x0F0F0F0F
252 * R ^= (difference << 4)
255 * to perform the swap. Let's denote this by bitswap(4,0x0F0F0F0F).
256 * Also, we can invert the bit at the top just by exchanging L and
257 * R. So in a few swaps and a few of these bit operations we can
260 * Initially the position of bit fedcba is fedcba
261 * Swap L with R to make it Fedcba
262 * Perform bitswap( 4,0x0F0F0F0F) to make it cedFba
263 * Perform bitswap(16,0x0000FFFF) to make it ecdFba
264 * Swap L with R to make it EcdFba
265 * Perform bitswap( 2,0x33333333) to make it bcdFEa
266 * Perform bitswap( 8,0x00FF00FF) to make it dcbFEa
267 * Swap L with R to make it DcbFEa
268 * Perform bitswap( 1,0x55555555) to make it acbFED
269 * Swap L with R to make it AcbFED
271 * (In the actual code the four swaps are implicit: R and L are
272 * simply used the other way round in the first, second and last
273 * bitswap operations.)
275 * The final permutation is just the inverse of IP, so it can be
276 * performed by a similar set of operations.
280 word32 k0246
[16], k1357
[16];
284 #define rotl(x, c) ( (x << c) | (x >> (32-c)) )
285 #define rotl28(x, c) ( ( (x << c) | (x >> (28-c)) ) & 0x0FFFFFFF)
287 static word32
bitsel(word32
* input
, const int *bitnums
, int size
)
291 int bitpos
= *bitnums
++;
294 ret
|= 1 & (input
[bitpos
/ 32] >> (bitpos
% 32));
299 static void des_key_setup(word32 key_msw
, word32 key_lsw
, DESContext
* sched
)
302 static const int PC1_Cbits
[] = {
303 7, 15, 23, 31, 39, 47, 55, 63, 6, 14, 22, 30, 38, 46,
304 54, 62, 5, 13, 21, 29, 37, 45, 53, 61, 4, 12, 20, 28
306 static const int PC1_Dbits
[] = {
307 1, 9, 17, 25, 33, 41, 49, 57, 2, 10, 18, 26, 34, 42,
308 50, 58, 3, 11, 19, 27, 35, 43, 51, 59, 36, 44, 52, 60
311 * The bit numbers in the two lists below don't correspond to
312 * the ones in the above description of PC2, because in the
313 * above description C and D are concatenated so `bit 28' means
314 * bit 0 of C. In this implementation we're using the standard
315 * `bitsel' function above and C is in the second word, so bit
316 * 0 of C is addressed by writing `32' here.
318 static const int PC2_0246
[] = {
319 49, 36, 59, 55, -1, -1, 37, 41, 48, 56, 34, 52, -1, -1, 15, 4,
320 25, 19, 9, 1, -1, -1, 12, 7, 17, 0, 22, 3, -1, -1, 46, 43
322 static const int PC2_1357
[] = {
323 -1, -1, 57, 32, 45, 54, 39, 50, -1, -1, 44, 53, 33, 40, 47, 58,
324 -1, -1, 26, 16, 5, 11, 23, 8, -1, -1, 10, 14, 6, 20, 27, 24
326 static const int leftshifts
[] =
327 { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };
336 C
= bitsel(buf
, PC1_Cbits
, 28);
337 D
= bitsel(buf
, PC1_Dbits
, 28);
339 for (i
= 0; i
< 16; i
++) {
340 C
= rotl28(C
, leftshifts
[i
]);
341 D
= rotl28(D
, leftshifts
[i
]);
344 sched
->k0246
[i
] = bitsel(buf
, PC2_0246
, 32);
345 sched
->k1357
[i
] = bitsel(buf
, PC2_1357
, 32);
348 sched
->iv0
= sched
->iv1
= 0;
351 static const word32 SPboxes
[8][64] = {
352 {0x01010400, 0x00000000, 0x00010000, 0x01010404,
353 0x01010004, 0x00010404, 0x00000004, 0x00010000,
354 0x00000400, 0x01010400, 0x01010404, 0x00000400,
355 0x01000404, 0x01010004, 0x01000000, 0x00000004,
356 0x00000404, 0x01000400, 0x01000400, 0x00010400,
357 0x00010400, 0x01010000, 0x01010000, 0x01000404,
358 0x00010004, 0x01000004, 0x01000004, 0x00010004,
359 0x00000000, 0x00000404, 0x00010404, 0x01000000,
360 0x00010000, 0x01010404, 0x00000004, 0x01010000,
361 0x01010400, 0x01000000, 0x01000000, 0x00000400,
362 0x01010004, 0x00010000, 0x00010400, 0x01000004,
363 0x00000400, 0x00000004, 0x01000404, 0x00010404,
364 0x01010404, 0x00010004, 0x01010000, 0x01000404,
365 0x01000004, 0x00000404, 0x00010404, 0x01010400,
366 0x00000404, 0x01000400, 0x01000400, 0x00000000,
367 0x00010004, 0x00010400, 0x00000000, 0x01010004L
},
369 {0x80108020, 0x80008000, 0x00008000, 0x00108020,
370 0x00100000, 0x00000020, 0x80100020, 0x80008020,
371 0x80000020, 0x80108020, 0x80108000, 0x80000000,
372 0x80008000, 0x00100000, 0x00000020, 0x80100020,
373 0x00108000, 0x00100020, 0x80008020, 0x00000000,
374 0x80000000, 0x00008000, 0x00108020, 0x80100000,
375 0x00100020, 0x80000020, 0x00000000, 0x00108000,
376 0x00008020, 0x80108000, 0x80100000, 0x00008020,
377 0x00000000, 0x00108020, 0x80100020, 0x00100000,
378 0x80008020, 0x80100000, 0x80108000, 0x00008000,
379 0x80100000, 0x80008000, 0x00000020, 0x80108020,
380 0x00108020, 0x00000020, 0x00008000, 0x80000000,
381 0x00008020, 0x80108000, 0x00100000, 0x80000020,
382 0x00100020, 0x80008020, 0x80000020, 0x00100020,
383 0x00108000, 0x00000000, 0x80008000, 0x00008020,
384 0x80000000, 0x80100020, 0x80108020, 0x00108000L
},
386 {0x00000208, 0x08020200, 0x00000000, 0x08020008,
387 0x08000200, 0x00000000, 0x00020208, 0x08000200,
388 0x00020008, 0x08000008, 0x08000008, 0x00020000,
389 0x08020208, 0x00020008, 0x08020000, 0x00000208,
390 0x08000000, 0x00000008, 0x08020200, 0x00000200,
391 0x00020200, 0x08020000, 0x08020008, 0x00020208,
392 0x08000208, 0x00020200, 0x00020000, 0x08000208,
393 0x00000008, 0x08020208, 0x00000200, 0x08000000,
394 0x08020200, 0x08000000, 0x00020008, 0x00000208,
395 0x00020000, 0x08020200, 0x08000200, 0x00000000,
396 0x00000200, 0x00020008, 0x08020208, 0x08000200,
397 0x08000008, 0x00000200, 0x00000000, 0x08020008,
398 0x08000208, 0x00020000, 0x08000000, 0x08020208,
399 0x00000008, 0x00020208, 0x00020200, 0x08000008,
400 0x08020000, 0x08000208, 0x00000208, 0x08020000,
401 0x00020208, 0x00000008, 0x08020008, 0x00020200L
},
403 {0x00802001, 0x00002081, 0x00002081, 0x00000080,
404 0x00802080, 0x00800081, 0x00800001, 0x00002001,
405 0x00000000, 0x00802000, 0x00802000, 0x00802081,
406 0x00000081, 0x00000000, 0x00800080, 0x00800001,
407 0x00000001, 0x00002000, 0x00800000, 0x00802001,
408 0x00000080, 0x00800000, 0x00002001, 0x00002080,
409 0x00800081, 0x00000001, 0x00002080, 0x00800080,
410 0x00002000, 0x00802080, 0x00802081, 0x00000081,
411 0x00800080, 0x00800001, 0x00802000, 0x00802081,
412 0x00000081, 0x00000000, 0x00000000, 0x00802000,
413 0x00002080, 0x00800080, 0x00800081, 0x00000001,
414 0x00802001, 0x00002081, 0x00002081, 0x00000080,
415 0x00802081, 0x00000081, 0x00000001, 0x00002000,
416 0x00800001, 0x00002001, 0x00802080, 0x00800081,
417 0x00002001, 0x00002080, 0x00800000, 0x00802001,
418 0x00000080, 0x00800000, 0x00002000, 0x00802080L
},
420 {0x00000100, 0x02080100, 0x02080000, 0x42000100,
421 0x00080000, 0x00000100, 0x40000000, 0x02080000,
422 0x40080100, 0x00080000, 0x02000100, 0x40080100,
423 0x42000100, 0x42080000, 0x00080100, 0x40000000,
424 0x02000000, 0x40080000, 0x40080000, 0x00000000,
425 0x40000100, 0x42080100, 0x42080100, 0x02000100,
426 0x42080000, 0x40000100, 0x00000000, 0x42000000,
427 0x02080100, 0x02000000, 0x42000000, 0x00080100,
428 0x00080000, 0x42000100, 0x00000100, 0x02000000,
429 0x40000000, 0x02080000, 0x42000100, 0x40080100,
430 0x02000100, 0x40000000, 0x42080000, 0x02080100,
431 0x40080100, 0x00000100, 0x02000000, 0x42080000,
432 0x42080100, 0x00080100, 0x42000000, 0x42080100,
433 0x02080000, 0x00000000, 0x40080000, 0x42000000,
434 0x00080100, 0x02000100, 0x40000100, 0x00080000,
435 0x00000000, 0x40080000, 0x02080100, 0x40000100L
},
437 {0x20000010, 0x20400000, 0x00004000, 0x20404010,
438 0x20400000, 0x00000010, 0x20404010, 0x00400000,
439 0x20004000, 0x00404010, 0x00400000, 0x20000010,
440 0x00400010, 0x20004000, 0x20000000, 0x00004010,
441 0x00000000, 0x00400010, 0x20004010, 0x00004000,
442 0x00404000, 0x20004010, 0x00000010, 0x20400010,
443 0x20400010, 0x00000000, 0x00404010, 0x20404000,
444 0x00004010, 0x00404000, 0x20404000, 0x20000000,
445 0x20004000, 0x00000010, 0x20400010, 0x00404000,
446 0x20404010, 0x00400000, 0x00004010, 0x20000010,
447 0x00400000, 0x20004000, 0x20000000, 0x00004010,
448 0x20000010, 0x20404010, 0x00404000, 0x20400000,
449 0x00404010, 0x20404000, 0x00000000, 0x20400010,
450 0x00000010, 0x00004000, 0x20400000, 0x00404010,
451 0x00004000, 0x00400010, 0x20004010, 0x00000000,
452 0x20404000, 0x20000000, 0x00400010, 0x20004010L
},
454 {0x00200000, 0x04200002, 0x04000802, 0x00000000,
455 0x00000800, 0x04000802, 0x00200802, 0x04200800,
456 0x04200802, 0x00200000, 0x00000000, 0x04000002,
457 0x00000002, 0x04000000, 0x04200002, 0x00000802,
458 0x04000800, 0x00200802, 0x00200002, 0x04000800,
459 0x04000002, 0x04200000, 0x04200800, 0x00200002,
460 0x04200000, 0x00000800, 0x00000802, 0x04200802,
461 0x00200800, 0x00000002, 0x04000000, 0x00200800,
462 0x04000000, 0x00200800, 0x00200000, 0x04000802,
463 0x04000802, 0x04200002, 0x04200002, 0x00000002,
464 0x00200002, 0x04000000, 0x04000800, 0x00200000,
465 0x04200800, 0x00000802, 0x00200802, 0x04200800,
466 0x00000802, 0x04000002, 0x04200802, 0x04200000,
467 0x00200800, 0x00000000, 0x00000002, 0x04200802,
468 0x00000000, 0x00200802, 0x04200000, 0x00000800,
469 0x04000002, 0x04000800, 0x00000800, 0x00200002L
},
471 {0x10001040, 0x00001000, 0x00040000, 0x10041040,
472 0x10000000, 0x10001040, 0x00000040, 0x10000000,
473 0x00040040, 0x10040000, 0x10041040, 0x00041000,
474 0x10041000, 0x00041040, 0x00001000, 0x00000040,
475 0x10040000, 0x10000040, 0x10001000, 0x00001040,
476 0x00041000, 0x00040040, 0x10040040, 0x10041000,
477 0x00001040, 0x00000000, 0x00000000, 0x10040040,
478 0x10000040, 0x10001000, 0x00041040, 0x00040000,
479 0x00041040, 0x00040000, 0x10041000, 0x00001000,
480 0x00000040, 0x10040040, 0x00001000, 0x00041040,
481 0x10001000, 0x00000040, 0x10000040, 0x10040000,
482 0x10040040, 0x10000000, 0x00040000, 0x10001040,
483 0x00000000, 0x10041040, 0x00040040, 0x10000040,
484 0x10040000, 0x10001000, 0x10001040, 0x00000000,
485 0x10041040, 0x00041000, 0x00041000, 0x00001040,
486 0x00001040, 0x00040040, 0x10000000, 0x10041000L
}
489 #define f(R, K0246, K1357) (\
492 s0246 = rotl(s0246, 28), \
493 SPboxes[0] [(s0246 >> 24) & 0x3F] | \
494 SPboxes[1] [(s1357 >> 24) & 0x3F] | \
495 SPboxes[2] [(s0246 >> 16) & 0x3F] | \
496 SPboxes[3] [(s1357 >> 16) & 0x3F] | \
497 SPboxes[4] [(s0246 >> 8) & 0x3F] | \
498 SPboxes[5] [(s1357 >> 8) & 0x3F] | \
499 SPboxes[6] [(s0246 ) & 0x3F] | \
500 SPboxes[7] [(s1357 ) & 0x3F])
502 #define bitswap(L, R, n, mask) (\
503 swap = mask & ( (R >> n) ^ L ), \
507 /* Initial permutation */
509 bitswap(R, L, 4, 0x0F0F0F0F), \
510 bitswap(R, L, 16, 0x0000FFFF), \
511 bitswap(L, R, 2, 0x33333333), \
512 bitswap(L, R, 8, 0x00FF00FF), \
513 bitswap(R, L, 1, 0x55555555))
515 /* Final permutation */
517 bitswap(R, L, 1, 0x55555555), \
518 bitswap(L, R, 8, 0x00FF00FF), \
519 bitswap(L, R, 2, 0x33333333), \
520 bitswap(R, L, 16, 0x0000FFFF), \
521 bitswap(R, L, 4, 0x0F0F0F0F))
523 static void des_encipher(word32
* output
, word32 L
, word32 R
,
526 word32 swap
, s0246
, s1357
;
533 L
^= f(R
, sched
->k0246
[0], sched
->k1357
[0]);
534 R
^= f(L
, sched
->k0246
[1], sched
->k1357
[1]);
535 L
^= f(R
, sched
->k0246
[2], sched
->k1357
[2]);
536 R
^= f(L
, sched
->k0246
[3], sched
->k1357
[3]);
537 L
^= f(R
, sched
->k0246
[4], sched
->k1357
[4]);
538 R
^= f(L
, sched
->k0246
[5], sched
->k1357
[5]);
539 L
^= f(R
, sched
->k0246
[6], sched
->k1357
[6]);
540 R
^= f(L
, sched
->k0246
[7], sched
->k1357
[7]);
541 L
^= f(R
, sched
->k0246
[8], sched
->k1357
[8]);
542 R
^= f(L
, sched
->k0246
[9], sched
->k1357
[9]);
543 L
^= f(R
, sched
->k0246
[10], sched
->k1357
[10]);
544 R
^= f(L
, sched
->k0246
[11], sched
->k1357
[11]);
545 L
^= f(R
, sched
->k0246
[12], sched
->k1357
[12]);
546 R
^= f(L
, sched
->k0246
[13], sched
->k1357
[13]);
547 L
^= f(R
, sched
->k0246
[14], sched
->k1357
[14]);
548 R
^= f(L
, sched
->k0246
[15], sched
->k1357
[15]);
563 static void des_decipher(word32
* output
, word32 L
, word32 R
,
566 word32 swap
, s0246
, s1357
;
573 L
^= f(R
, sched
->k0246
[15], sched
->k1357
[15]);
574 R
^= f(L
, sched
->k0246
[14], sched
->k1357
[14]);
575 L
^= f(R
, sched
->k0246
[13], sched
->k1357
[13]);
576 R
^= f(L
, sched
->k0246
[12], sched
->k1357
[12]);
577 L
^= f(R
, sched
->k0246
[11], sched
->k1357
[11]);
578 R
^= f(L
, sched
->k0246
[10], sched
->k1357
[10]);
579 L
^= f(R
, sched
->k0246
[9], sched
->k1357
[9]);
580 R
^= f(L
, sched
->k0246
[8], sched
->k1357
[8]);
581 L
^= f(R
, sched
->k0246
[7], sched
->k1357
[7]);
582 R
^= f(L
, sched
->k0246
[6], sched
->k1357
[6]);
583 L
^= f(R
, sched
->k0246
[5], sched
->k1357
[5]);
584 R
^= f(L
, sched
->k0246
[4], sched
->k1357
[4]);
585 L
^= f(R
, sched
->k0246
[3], sched
->k1357
[3]);
586 R
^= f(L
, sched
->k0246
[2], sched
->k1357
[2]);
587 L
^= f(R
, sched
->k0246
[1], sched
->k1357
[1]);
588 R
^= f(L
, sched
->k0246
[0], sched
->k1357
[0]);
603 #define GET_32BIT_MSB_FIRST(cp) \
604 (((unsigned long)(unsigned char)(cp)[3]) | \
605 ((unsigned long)(unsigned char)(cp)[2] << 8) | \
606 ((unsigned long)(unsigned char)(cp)[1] << 16) | \
607 ((unsigned long)(unsigned char)(cp)[0] << 24))
609 #define PUT_32BIT_MSB_FIRST(cp, value) do { \
611 (cp)[2] = (value) >> 8; \
612 (cp)[1] = (value) >> 16; \
613 (cp)[0] = (value) >> 24; } while (0)
615 static void des_cbc_encrypt(unsigned char *dest
, const unsigned char *src
,
616 unsigned int len
, DESContext
* sched
)
618 word32 out
[2], iv0
, iv1
;
621 assert((len
& 7) == 0);
625 for (i
= 0; i
< len
; i
+= 8) {
626 iv0
^= GET_32BIT_MSB_FIRST(src
);
628 iv1
^= GET_32BIT_MSB_FIRST(src
);
630 des_encipher(out
, iv0
, iv1
, sched
);
633 PUT_32BIT_MSB_FIRST(dest
, iv0
);
635 PUT_32BIT_MSB_FIRST(dest
, iv1
);
642 static void des_cbc_decrypt(unsigned char *dest
, const unsigned char *src
,
643 unsigned int len
, DESContext
* sched
)
645 word32 out
[2], iv0
, iv1
, xL
, xR
;
648 assert((len
& 7) == 0);
652 for (i
= 0; i
< len
; i
+= 8) {
653 xL
= GET_32BIT_MSB_FIRST(src
);
655 xR
= GET_32BIT_MSB_FIRST(src
);
657 des_decipher(out
, xL
, xR
, sched
);
660 PUT_32BIT_MSB_FIRST(dest
, iv0
);
662 PUT_32BIT_MSB_FIRST(dest
, iv1
);
671 static void des_3cbc_encrypt(unsigned char *dest
, const unsigned char *src
,
672 unsigned int len
, DESContext
* scheds
)
674 des_cbc_encrypt(dest
, src
, len
, &scheds
[0]);
675 des_cbc_decrypt(dest
, src
, len
, &scheds
[1]);
676 des_cbc_encrypt(dest
, src
, len
, &scheds
[2]);
679 static void des_cbc3_encrypt(unsigned char *dest
, const unsigned char *src
,
680 unsigned int len
, DESContext
* scheds
)
682 word32 out
[2], iv0
, iv1
;
685 assert((len
& 7) == 0);
689 for (i
= 0; i
< len
; i
+= 8) {
690 iv0
^= GET_32BIT_MSB_FIRST(src
);
692 iv1
^= GET_32BIT_MSB_FIRST(src
);
694 des_encipher(out
, iv0
, iv1
, &scheds
[0]);
695 des_decipher(out
, out
[0], out
[1], &scheds
[1]);
696 des_encipher(out
, out
[0], out
[1], &scheds
[2]);
699 PUT_32BIT_MSB_FIRST(dest
, iv0
);
701 PUT_32BIT_MSB_FIRST(dest
, iv1
);
708 static void des_3cbc_decrypt(unsigned char *dest
, const unsigned char *src
,
709 unsigned int len
, DESContext
* scheds
)
711 des_cbc_decrypt(dest
, src
, len
, &scheds
[2]);
712 des_cbc_encrypt(dest
, src
, len
, &scheds
[1]);
713 des_cbc_decrypt(dest
, src
, len
, &scheds
[0]);
716 static void des_cbc3_decrypt(unsigned char *dest
, const unsigned char *src
,
717 unsigned int len
, DESContext
* scheds
)
719 word32 out
[2], iv0
, iv1
, xL
, xR
;
722 assert((len
& 7) == 0);
726 for (i
= 0; i
< len
; i
+= 8) {
727 xL
= GET_32BIT_MSB_FIRST(src
);
729 xR
= GET_32BIT_MSB_FIRST(src
);
731 des_decipher(out
, xL
, xR
, &scheds
[2]);
732 des_encipher(out
, out
[0], out
[1], &scheds
[1]);
733 des_decipher(out
, out
[0], out
[1], &scheds
[0]);
736 PUT_32BIT_MSB_FIRST(dest
, iv0
);
738 PUT_32BIT_MSB_FIRST(dest
, iv1
);
747 static void des_sdctr3(unsigned char *dest
, const unsigned char *src
,
748 unsigned int len
, DESContext
* scheds
)
750 word32 b
[2], iv0
, iv1
, tmp
;
753 assert((len
& 7) == 0);
757 for (i
= 0; i
< len
; i
+= 8) {
758 des_encipher(b
, iv0
, iv1
, &scheds
[2]);
759 des_decipher(b
, b
[0], b
[1], &scheds
[1]);
760 des_encipher(b
, b
[0], b
[1], &scheds
[0]);
761 tmp
= GET_32BIT_MSB_FIRST(src
);
762 PUT_32BIT_MSB_FIRST(dest
, tmp
^ b
[0]);
765 tmp
= GET_32BIT_MSB_FIRST(src
);
766 PUT_32BIT_MSB_FIRST(dest
, tmp
^ b
[0]);
769 if ((iv0
= (iv0
+ 1) & 0xffffffff) == 0)
770 iv1
= (iv1
+ 1) & 0xffffffff;
776 static void *des3_make_context(void)
778 return snewn(3, DESContext
);
781 static void *des3_ssh1_make_context(void)
783 /* Need 3 keys for each direction, in SSH-1 */
784 return snewn(6, DESContext
);
787 static void *des_make_context(void)
789 return snew(DESContext
);
792 static void *des_ssh1_make_context(void)
794 /* Need one key for each direction, in SSH-1 */
795 return snewn(2, DESContext
);
798 static void des3_free_context(void *handle
) /* used for both 3DES and DES */
803 static void des3_key(void *handle
, unsigned char *key
)
805 DESContext
*keys
= (DESContext
*) handle
;
806 des_key_setup(GET_32BIT_MSB_FIRST(key
),
807 GET_32BIT_MSB_FIRST(key
+ 4), &keys
[0]);
808 des_key_setup(GET_32BIT_MSB_FIRST(key
+ 8),
809 GET_32BIT_MSB_FIRST(key
+ 12), &keys
[1]);
810 des_key_setup(GET_32BIT_MSB_FIRST(key
+ 16),
811 GET_32BIT_MSB_FIRST(key
+ 20), &keys
[2]);
814 static void des3_iv(void *handle
, unsigned char *key
)
816 DESContext
*keys
= (DESContext
*) handle
;
817 keys
[0].iv0
= GET_32BIT_MSB_FIRST(key
);
818 keys
[0].iv1
= GET_32BIT_MSB_FIRST(key
+ 4);
821 static void des_key(void *handle
, unsigned char *key
)
823 DESContext
*keys
= (DESContext
*) handle
;
824 des_key_setup(GET_32BIT_MSB_FIRST(key
),
825 GET_32BIT_MSB_FIRST(key
+ 4), &keys
[0]);
828 static void des3_sesskey(void *handle
, unsigned char *key
)
830 DESContext
*keys
= (DESContext
*) handle
;
832 des3_key(keys
+3, key
);
835 static void des3_encrypt_blk(void *handle
, unsigned char *blk
, int len
)
837 DESContext
*keys
= (DESContext
*) handle
;
838 des_3cbc_encrypt(blk
, blk
, len
, keys
);
841 static void des3_decrypt_blk(void *handle
, unsigned char *blk
, int len
)
843 DESContext
*keys
= (DESContext
*) handle
;
844 des_3cbc_decrypt(blk
, blk
, len
, keys
+3);
847 static void des3_ssh2_encrypt_blk(void *handle
, unsigned char *blk
, int len
)
849 DESContext
*keys
= (DESContext
*) handle
;
850 des_cbc3_encrypt(blk
, blk
, len
, keys
);
853 static void des3_ssh2_decrypt_blk(void *handle
, unsigned char *blk
, int len
)
855 DESContext
*keys
= (DESContext
*) handle
;
856 des_cbc3_decrypt(blk
, blk
, len
, keys
);
859 static void des3_ssh2_sdctr(void *handle
, unsigned char *blk
, int len
)
861 DESContext
*keys
= (DESContext
*) handle
;
862 des_sdctr3(blk
, blk
, len
, keys
);
865 static void des_ssh2_encrypt_blk(void *handle
, unsigned char *blk
, int len
)
867 DESContext
*keys
= (DESContext
*) handle
;
868 des_cbc_encrypt(blk
, blk
, len
, keys
);
871 static void des_ssh2_decrypt_blk(void *handle
, unsigned char *blk
, int len
)
873 DESContext
*keys
= (DESContext
*) handle
;
874 des_cbc_decrypt(blk
, blk
, len
, keys
);
877 void des3_decrypt_pubkey(unsigned char *key
, unsigned char *blk
, int len
)
879 DESContext ourkeys
[3];
880 des_key_setup(GET_32BIT_MSB_FIRST(key
),
881 GET_32BIT_MSB_FIRST(key
+ 4), &ourkeys
[0]);
882 des_key_setup(GET_32BIT_MSB_FIRST(key
+ 8),
883 GET_32BIT_MSB_FIRST(key
+ 12), &ourkeys
[1]);
884 des_key_setup(GET_32BIT_MSB_FIRST(key
),
885 GET_32BIT_MSB_FIRST(key
+ 4), &ourkeys
[2]);
886 des_3cbc_decrypt(blk
, blk
, len
, ourkeys
);
887 memset(ourkeys
, 0, sizeof(ourkeys
));
890 void des3_encrypt_pubkey(unsigned char *key
, unsigned char *blk
, int len
)
892 DESContext ourkeys
[3];
893 des_key_setup(GET_32BIT_MSB_FIRST(key
),
894 GET_32BIT_MSB_FIRST(key
+ 4), &ourkeys
[0]);
895 des_key_setup(GET_32BIT_MSB_FIRST(key
+ 8),
896 GET_32BIT_MSB_FIRST(key
+ 12), &ourkeys
[1]);
897 des_key_setup(GET_32BIT_MSB_FIRST(key
),
898 GET_32BIT_MSB_FIRST(key
+ 4), &ourkeys
[2]);
899 des_3cbc_encrypt(blk
, blk
, len
, ourkeys
);
900 memset(ourkeys
, 0, sizeof(ourkeys
));
903 void des3_decrypt_pubkey_ossh(unsigned char *key
, unsigned char *iv
,
904 unsigned char *blk
, int len
)
906 DESContext ourkeys
[3];
907 des_key_setup(GET_32BIT_MSB_FIRST(key
),
908 GET_32BIT_MSB_FIRST(key
+ 4), &ourkeys
[0]);
909 des_key_setup(GET_32BIT_MSB_FIRST(key
+ 8),
910 GET_32BIT_MSB_FIRST(key
+ 12), &ourkeys
[1]);
911 des_key_setup(GET_32BIT_MSB_FIRST(key
+ 16),
912 GET_32BIT_MSB_FIRST(key
+ 20), &ourkeys
[2]);
913 ourkeys
[0].iv0
= GET_32BIT_MSB_FIRST(iv
);
914 ourkeys
[0].iv1
= GET_32BIT_MSB_FIRST(iv
+4);
915 des_cbc3_decrypt(blk
, blk
, len
, ourkeys
);
916 memset(ourkeys
, 0, sizeof(ourkeys
));
919 void des3_encrypt_pubkey_ossh(unsigned char *key
, unsigned char *iv
,
920 unsigned char *blk
, int len
)
922 DESContext ourkeys
[3];
923 des_key_setup(GET_32BIT_MSB_FIRST(key
),
924 GET_32BIT_MSB_FIRST(key
+ 4), &ourkeys
[0]);
925 des_key_setup(GET_32BIT_MSB_FIRST(key
+ 8),
926 GET_32BIT_MSB_FIRST(key
+ 12), &ourkeys
[1]);
927 des_key_setup(GET_32BIT_MSB_FIRST(key
+ 16),
928 GET_32BIT_MSB_FIRST(key
+ 20), &ourkeys
[2]);
929 ourkeys
[0].iv0
= GET_32BIT_MSB_FIRST(iv
);
930 ourkeys
[0].iv1
= GET_32BIT_MSB_FIRST(iv
+4);
931 des_cbc3_encrypt(blk
, blk
, len
, ourkeys
);
932 memset(ourkeys
, 0, sizeof(ourkeys
));
935 static void des_keysetup_xdmauth(unsigned char *keydata
, DESContext
*dc
)
937 unsigned char key
[8];
944 for (i
= 0; i
< 8; i
++) {
946 bits
= (bits
<< 8) | keydata
[j
];
950 key
[i
] = (bits
>> (nbits
- 7)) << 1;
951 bits
&= ~(0x7F << (nbits
- 7));
955 des_key_setup(GET_32BIT_MSB_FIRST(key
), GET_32BIT_MSB_FIRST(key
+ 4), dc
);
958 void des_encrypt_xdmauth(unsigned char *keydata
, unsigned char *blk
, int len
)
961 des_keysetup_xdmauth(keydata
, &dc
);
962 des_cbc_encrypt(blk
, blk
, 24, &dc
);
965 void des_decrypt_xdmauth(unsigned char *keydata
, unsigned char *blk
, int len
)
968 des_keysetup_xdmauth(keydata
, &dc
);
969 des_cbc_decrypt(blk
, blk
, 24, &dc
);
972 static const struct ssh2_cipher ssh_3des_ssh2
= {
973 des3_make_context
, des3_free_context
, des3_iv
, des3_key
,
974 des3_ssh2_encrypt_blk
, des3_ssh2_decrypt_blk
,
976 8, 168, "triple-DES CBC"
979 static const struct ssh2_cipher ssh_3des_ssh2_ctr
= {
980 des3_make_context
, des3_free_context
, des3_iv
, des3_key
,
981 des3_ssh2_sdctr
, des3_ssh2_sdctr
,
983 8, 168, "triple-DES SDCTR"
987 * Single DES in SSH-2. "des-cbc" is marked as HISTORIC in
988 * draft-ietf-secsh-assignednumbers-04.txt, referring to
989 * FIPS-46-3. ("Single DES (i.e., DES) will be permitted
990 * for legacy systems only.") , but ssh.com support it and
991 * apparently aren't the only people to do so, so we sigh
992 * and implement it anyway.
994 static const struct ssh2_cipher ssh_des_ssh2
= {
995 des_make_context
, des3_free_context
, des3_iv
, des_key
,
996 des_ssh2_encrypt_blk
, des_ssh2_decrypt_blk
,
998 8, 56, "single-DES CBC"
1001 static const struct ssh2_cipher ssh_des_sshcom_ssh2
= {
1002 des_make_context
, des3_free_context
, des3_iv
, des_key
,
1003 des_ssh2_encrypt_blk
, des_ssh2_decrypt_blk
,
1005 8, 56, "single-DES CBC"
1009 * "3des-ctr" is disabled because it hasn't had any interoperability
1010 * testing, which is in turn because I couldn't find another implementation
1011 * to test against. Once it's been tested, it can be enabled in standard
1014 static const struct ssh2_cipher
*const des3_list
[] = {
1015 /* &ssh_3des_ssh2_ctr, */
1019 const struct ssh2_ciphers ssh2_3des
= {
1020 sizeof(des3_list
) / sizeof(*des3_list
),
1024 static const struct ssh2_cipher
*const des_list
[] = {
1026 &ssh_des_sshcom_ssh2
1029 const struct ssh2_ciphers ssh2_des
= {
1030 sizeof(des_list
) / sizeof(*des_list
),
1034 const struct ssh_cipher ssh_3des
= {
1035 des3_ssh1_make_context
, des3_free_context
, des3_sesskey
,
1036 des3_encrypt_blk
, des3_decrypt_blk
,
1037 8, "triple-DES inner-CBC"
1040 static void des_sesskey(void *handle
, unsigned char *key
)
1042 DESContext
*keys
= (DESContext
*) handle
;
1044 des_key(keys
+1, key
);
1047 static void des_encrypt_blk(void *handle
, unsigned char *blk
, int len
)
1049 DESContext
*keys
= (DESContext
*) handle
;
1050 des_cbc_encrypt(blk
, blk
, len
, keys
);
1053 static void des_decrypt_blk(void *handle
, unsigned char *blk
, int len
)
1055 DESContext
*keys
= (DESContext
*) handle
;
1056 des_cbc_decrypt(blk
, blk
, len
, keys
+1);
1059 const struct ssh_cipher ssh_des
= {
1060 des_ssh1_make_context
, des3_free_context
, des_sesskey
,
1061 des_encrypt_blk
, des_decrypt_blk
,