projects / u / mdw / putty / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Added a large comment describing the transformations between the DES
[u/mdw/putty] / sshdes.c
1 #include <assert.h>
2 #include "ssh.h"
3
4 /* des.c - implementation of DES
5 */
6
7 /*
8 * Description of DES
9 * ------------------
10 *
11 * Unlike the description in FIPS 46, I'm going to use _sensible_ indices:
12 * bits in an n-bit word are numbered from 0 at the LSB to n-1 at the MSB.
13 * And S-boxes are indexed by six consecutive bits, not by the outer two
14 * followed by the middle four.
15 *
16 * The DES encryption routine requires a 64-bit input, and a key schedule K
17 * containing 16 48-bit elements.
18 *
19 * First the input is permuted by the initial permutation IP.
20 * Then the input is split into 32-bit words L and R. (L is the MSW.)
21 * Next, 16 rounds. In each round:
22 * (L, R) <- (R, L xor f(R, K[i]))
23 * Then the pre-output words L and R are swapped.
24 * Then L and R are glued back together into a 64-bit word. (L is the MSW,
25 * again, but since we just swapped them, the MSW is the R that came out
26 * of the last round.)
27 * The 64-bit output block is permuted by the inverse of IP and returned.
28 *
29 * Decryption is identical except that the elements of K are used in the
30 * opposite order. (This wouldn't work if that word swap didn't happen.)
31 *
32 * The function f, used in each round, accepts a 32-bit word R and a
33 * 48-bit key block K. It produces a 32-bit output.
34 *
35 * First R is expanded to 48 bits using the bit-selection function E.
36 * The resulting 48-bit block is XORed with the key block K to produce
37 * a 48-bit block X.
38 * This block X is split into eight groups of 6 bits. Each group of 6
39 * bits is then looked up in one of the eight S-boxes to convert
40 * it to 4 bits. These eight groups of 4 bits are glued back
41 * together to produce a 32-bit preoutput block.
42 * The preoutput block is permuted using the permutation P and returned.
43 *
44 * Key setup maps a 64-bit key word into a 16x48-bit key schedule. Although
45 * the approved input format for the key is a 64-bit word, eight of the
46 * bits are discarded, so the actual quantity of key used is 56 bits.
47 *
48 * First the input key is converted to two 28-bit words C and D using
49 * the bit-selection function PC1.
50 * Then 16 rounds of key setup occur. In each round, C and D are each
51 * rotated left by either 1 or 2 bits (depending on which round), and
52 * then converted into a key schedule element using the bit-selection
53 * function PC2.
54 *
55 * That's the actual algorithm. Now for the tedious details: all those
56 * painful permutations and lookup tables.
57 *
58 * IP is a 64-to-64 bit permutation. Its output contains the following
59 * bits of its input (listed in order MSB to LSB of output).
60 *
61 * 6 14 22 30 38 46 54 62 4 12 20 28 36 44 52 60
62 * 2 10 18 26 34 42 50 58 0 8 16 24 32 40 48 56
63 * 7 15 23 31 39 47 55 63 5 13 21 29 37 45 53 61
64 * 3 11 19 27 35 43 51 59 1 9 17 25 33 41 49 57
65 *
66 * E is a 32-to-48 bit selection function. Its output contains the following
67 * bits of its input (listed in order MSB to LSB of output).
68 *
69 * 0 31 30 29 28 27 28 27 26 25 24 23 24 23 22 21 20 19 20 19 18 17 16 15
70 * 16 15 14 13 12 11 12 11 10 9 8 7 8 7 6 5 4 3 4 3 2 1 0 31
71 *
72 * The S-boxes are arbitrary table-lookups each mapping a 6-bit input to a
73 * 4-bit output. In other words, each S-box is an array[64] of 4-bit numbers.
74 * The S-boxes are listed below. The first S-box listed is applied to the
75 * most significant six bits of the block X; the last one is applied to the
76 * least significant.
77 *
78 * 14 0 4 15 13 7 1 4 2 14 15 2 11 13 8 1
79 * 3 10 10 6 6 12 12 11 5 9 9 5 0 3 7 8
80 * 4 15 1 12 14 8 8 2 13 4 6 9 2 1 11 7
81 * 15 5 12 11 9 3 7 14 3 10 10 0 5 6 0 13
82 *
83 * 15 3 1 13 8 4 14 7 6 15 11 2 3 8 4 14
84 * 9 12 7 0 2 1 13 10 12 6 0 9 5 11 10 5
85 * 0 13 14 8 7 10 11 1 10 3 4 15 13 4 1 2
86 * 5 11 8 6 12 7 6 12 9 0 3 5 2 14 15 9
87 *
88 * 10 13 0 7 9 0 14 9 6 3 3 4 15 6 5 10
89 * 1 2 13 8 12 5 7 14 11 12 4 11 2 15 8 1
90 * 13 1 6 10 4 13 9 0 8 6 15 9 3 8 0 7
91 * 11 4 1 15 2 14 12 3 5 11 10 5 14 2 7 12
92 *
93 * 7 13 13 8 14 11 3 5 0 6 6 15 9 0 10 3
94 * 1 4 2 7 8 2 5 12 11 1 12 10 4 14 15 9
95 * 10 3 6 15 9 0 0 6 12 10 11 1 7 13 13 8
96 * 15 9 1 4 3 5 14 11 5 12 2 7 8 2 4 14
97 *
98 * 2 14 12 11 4 2 1 12 7 4 10 7 11 13 6 1
99 * 8 5 5 0 3 15 15 10 13 3 0 9 14 8 9 6
100 * 4 11 2 8 1 12 11 7 10 1 13 14 7 2 8 13
101 * 15 6 9 15 12 0 5 9 6 10 3 4 0 5 14 3
102 *
103 * 12 10 1 15 10 4 15 2 9 7 2 12 6 9 8 5
104 * 0 6 13 1 3 13 4 14 14 0 7 11 5 3 11 8
105 * 9 4 14 3 15 2 5 12 2 9 8 5 12 15 3 10
106 * 7 11 0 14 4 1 10 7 1 6 13 0 11 8 6 13
107 *
108 * 4 13 11 0 2 11 14 7 15 4 0 9 8 1 13 10
109 * 3 14 12 3 9 5 7 12 5 2 10 15 6 8 1 6
110 * 1 6 4 11 11 13 13 8 12 1 3 4 7 10 14 7
111 * 10 9 15 5 6 0 8 15 0 14 5 2 9 3 2 12
112 *
113 * 13 1 2 15 8 13 4 8 6 10 15 3 11 7 1 4
114 * 10 12 9 5 3 6 14 11 5 0 0 14 12 9 7 2
115 * 7 2 11 1 4 14 1 7 9 4 12 10 14 8 2 13
116 * 0 15 6 12 10 9 13 0 15 3 3 5 5 6 8 11
117 *
118 * P is a 32-to-32 bit permutation. Its output contains the following
119 * bits of its input (listed in order MSB to LSB of output).
120 *
121 * 16 25 12 11 3 20 4 15 31 17 9 6 27 14 1 22
122 * 30 24 8 18 0 5 29 23 13 19 2 26 10 21 28 7
123 *
124 * PC1 is a 64-to-56 bit selection function. Its output is in two words,
125 * C and D. The word C contains the following bits of its input (listed
126 * in order MSB to LSB of output).
127 *
128 * 7 15 23 31 39 47 55 63 6 14 22 30 38 46
129 * 54 62 5 13 21 29 37 45 53 61 4 12 20 28
130 *
131 * And the word D contains these bits.
132 *
133 * 1 9 17 25 33 41 49 57 2 10 18 26 34 42
134 * 50 58 3 11 19 27 35 43 51 59 36 44 52 60
135 *
136 * PC2 is a 56-to-48 bit selection function. Its input is in two words,
137 * C and D. These are treated as one 56-bit word (with C more significant,
138 * so that bits 55 to 28 of the word are bits 27 to 0 of C, and bits 27 to
139 * 0 of the word are bits 27 to 0 of D). The output contains the following
140 * bits of this 56-bit input word (listed in order MSB to LSB of output).
141 *
142 * 42 39 45 32 55 51 53 28 41 50 35 46 33 37 44 52 30 48 40 49 29 36 43 54
143 * 15 4 25 19 9 1 26 16 5 11 23 8 12 7 17 0 22 3 10 14 6 20 27 24
144 */
145
146 /*
147 * Implementation details
148 * ----------------------
149 *
150 * If you look at the code in this module, you'll find it looks
151 * nothing _like_ the above algorithm. Here I explain the
152 * differences...
153 *
154 * Key setup has not been heavily optimised here. We are not
155 * concerned with key agility: we aren't codebreakers. We don't
156 * mind a little delay (and it really is a little one; it may be a
157 * factor of five or so slower than it could be but it's still not
158 * an appreciable length of time) while setting up. The only tweaks
159 * in the key setup are ones which change the format of the key
160 * schedule to speed up the actual encryption. I'll describe those
161 * below.
162 *
163 * The first and most obvious optimisation is the S-boxes. Since
164 * each S-box always targets the same four bits in the final 32-bit
165 * word, so the output from (for example) S-box 0 must always be
166 * shifted left 28 bits, we can store the already-shifted outputs
167 * in the lookup tables. This reduces lookup-and-shift to lookup,
168 * so the S-box step is now just a question of ORing together eight
169 * table lookups.
170 *
171 * The permutation P is just a bit order change; it's invariant
172 * with respect to OR, in that P(x)|P(y) = P(x|y). Therefore, we
173 * can apply P to every entry of the S-box tables and then we don't
174 * have to do it in the code of f(). This yields a set of tables
175 * which might be called SP-boxes.
176 *
177 * The bit-selection function E is our next target. Note that E is
178 * immediately followed by the operation of splitting into 6-bit
179 * chunks. Examining the 6-bit chunks coming out of E we notice
180 * they're all contiguous within the word (speaking cyclically -
181 * the end two wrap round); so we can extract those bit strings
182 * individually rather than explicitly running E. This would yield
183 * code such as
184 *
185 * y |= SPboxes[0][ (rotl(R, 5) ^ top6bitsofK) & 0x3F ];
186 * t |= SPboxes[1][ (rotl(R,11) ^ next6bitsofK) & 0x3F ];
187 *
188 * and so on; and the key schedule preparation would have to
189 * provide each 6-bit chunk separately.
190 *
191 * Really we'd like to XOR in the key schedule element before
192 * looking up bit strings in R. This we can't do, naively, because
193 * the 6-bit strings we want overlap. But look at the strings:
194 *
195 * 3322222222221111111111
196 * bit 10987654321098765432109876543210
197 *
198 * box0 XXXXX X
199 * box1 XXXXXX
200 * box2 XXXXXX
201 * box3 XXXXXX
202 * box4 XXXXXX
203 * box5 XXXXXX
204 * box6 XXXXXX
205 * box7 X XXXXX
206 *
207 * The bit strings we need to XOR in for boxes 0, 2, 4 and 6 don't
208 * overlap with each other. Neither do the ones for boxes 1, 3, 5
209 * and 7. So we could provide the key schedule in the form of two
210 * words that we can separately XOR into R, and then every S-box
211 * index is available as a (cyclically) contiguous 6-bit substring
212 * of one or the other of the results.
213 *
214 * The comments in Eric Young's libdes implementation point out
215 * that two of these bit strings require a rotation (rather than a
216 * simple shift) to extract. It's unavoidable that at least _one_
217 * must do; but we can actually run the whole inner algorithm (all
218 * 16 rounds) rotated one bit to the left, so that what the `real'
219 * DES description sees as L=0x80000001 we see as L=0x00000003.
220 * This requires rotating all our SP-box entries one bit to the
221 * left, and rotating each word of the key schedule elements one to
222 * the left, and rotating L and R one bit left just after IP and
223 * one bit right again just before FP. And in each round we convert
224 * a rotate into a shift, so we've saved a few per cent.
225 *
226 * That's about it for the inner loop; the SP-box tables as listed
227 * below are what I've described here (the original S value,
228 * shifted to its final place in the input to P, run through P, and
229 * then rotated one bit left). All that remains is to optimise the
230 * initial permutation IP.
231 *
232 * IP is not an arbitrary permutation. It has the nice property
233 * that if you take any bit number, write it in binary (6 bits),
234 * permute those 6 bits and invert some of them, you get the final
235 * position of that bit. Specifically, the bit whose initial
236 * position is given (in binary) as fedcba ends up in position
237 * AcbFED (where a capital letter denotes the inverse of a bit).
238 *
239 * We have the 64-bit data in two 32-bit words L and R, where bits
240 * in L are those with f=1 and bits in R are those with f=0. We
241 * note that we can do a simple transformation: suppose we exchange
242 * the bits with f=1,c=0 and the bits with f=0,c=1. This will cause
243 * the bit fedcba to be in position cedfba - we've `swapped' bits c
244 * and f in the position of each bit!
245 *
246 * Better still, this transformation is easy. In the example above,
247 * bits in L with c=0 are bits 0x0F0F0F0F, and those in R with c=1
248 * are 0xF0F0F0F0. So we can do
249 *
250 * difference = ((R >> 4) ^ L) & 0x0F0F0F0F
251 * R ^= (difference << 4)
252 * L ^= difference
253 *
254 * to perform the swap. Let's denote this by bitswap(4,0x0F0F0F0F).
255 * Also, we can invert the bit at the top just by exchanging L and
256 * R. So in a few swaps and a few of these bit operations we can
257 * do:
258 *
259 * Initially the position of bit fedcba is fedcba
260 * Swap L with R to make it Fedcba
261 * Perform bitswap( 4,0x0F0F0F0F) to make it cedFba
262 * Perform bitswap(16,0x0000FFFF) to make it ecdFba
263 * Swap L with R to make it EcdFba
264 * Perform bitswap( 2,0x33333333) to make it bcdFEa
265 * Perform bitswap( 8,0x00FF00FF) to make it dcbFEa
266 * Swap L with R to make it DcbFEa
267 * Perform bitswap( 1,0x55555555) to make it acbFED
268 * Swap L with R to make it AcbFED
269 *
270 * (In the actual code the four swaps are implicit: R and L are
271 * simply used the other way round in the first, second and last
272 * bitswap operations.)
273 *
274 * The final permutation is just the inverse of IP, so it can be
275 * performed by a similar set of operations.
276 */
277
278 typedef struct {
279 word32 k0246[16], k1357[16];
280 word32 eiv0, eiv1;
281 word32 div0, div1;
282 } DESContext;
283
284 #define rotl(x, c) ( (x << c) | (x >> (32-c)) )
285 #define rotl28(x, c) ( ( (x << c) | (x >> (28-c)) ) & 0x0FFFFFFF)
286
287 static word32 bitsel(word32 *input, const int *bitnums, int size) {
288 word32 ret = 0;
289 while (size--) {
290 int bitpos = *bitnums++;
291 ret <<= 1;
292 if (bitpos >= 0)
293 ret |= 1 & (input[bitpos / 32] >> (bitpos % 32));
294 }
295 return ret;
296 }
297
298 void des_key_setup(word32 key_msw, word32 key_lsw, DESContext *sched) {
299
300 static const int PC1_Cbits[] = {
301 7, 15, 23, 31, 39, 47, 55, 63, 6, 14, 22, 30, 38, 46,
302 54, 62, 5, 13, 21, 29, 37, 45, 53, 61, 4, 12, 20, 28
303 };
304 static const int PC1_Dbits[] = {
305 1, 9, 17, 25, 33, 41, 49, 57, 2, 10, 18, 26, 34, 42,
306 50, 58, 3, 11, 19, 27, 35, 43, 51, 59, 36, 44, 52, 60
307 };
308 /*
309 * The bit numbers in the two lists below don't correspond to
310 * the ones in the above description of PC2, because in the
311 * above description C and D are concatenated so `bit 28' means
312 * bit 0 of C. In this implementation we're using the standard
313 * `bitsel' function above and C is in the second word, so bit
314 * 0 of C is addressed by writing `32' here.
315 */
316 static const int PC2_0246[] = {
317 49, 36, 59, 55, -1, -1, 37, 41, 48, 56, 34, 52, -1, -1, 15, 4,
318 25, 19, 9, 1, -1, -1, 12, 7, 17, 0, 22, 3, -1, -1, 46, 43
319 };
320 static const int PC2_1357[] = {
321 -1, -1, 57, 32, 45, 54, 39, 50, -1, -1, 44, 53, 33, 40, 47, 58,
322 -1, -1, 26, 16, 5, 11, 23, 8, -1, -1, 10, 14, 6, 20, 27, 24
323 };
324 static const int leftshifts[] = {1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1};
325
326 word32 C, D;
327 word32 buf[2];
328 int i;
329
330 buf[0] = key_lsw;
331 buf[1] = key_msw;
332
333 C = bitsel(buf, PC1_Cbits, 28);
334 D = bitsel(buf, PC1_Dbits, 28);
335
336 for (i = 0; i < 16; i++) {
337 C = rotl28(C, leftshifts[i]);
338 D = rotl28(D, leftshifts[i]);
339 buf[0] = D;
340 buf[1] = C;
341 sched->k0246[i] = bitsel(buf, PC2_0246, 32);
342 sched->k1357[i] = bitsel(buf, PC2_1357, 32);
343 }
344
345 sched->eiv0 = sched->eiv1 = 0;
346 sched->div0 = sched->div1 = 0; /* for good measure */
347 }
348
349 static const word32 SPboxes[8][64] = {
350 {0x01010400, 0x00000000, 0x00010000, 0x01010404,
351 0x01010004, 0x00010404, 0x00000004, 0x00010000,
352 0x00000400, 0x01010400, 0x01010404, 0x00000400,
353 0x01000404, 0x01010004, 0x01000000, 0x00000004,
354 0x00000404, 0x01000400, 0x01000400, 0x00010400,
355 0x00010400, 0x01010000, 0x01010000, 0x01000404,
356 0x00010004, 0x01000004, 0x01000004, 0x00010004,
357 0x00000000, 0x00000404, 0x00010404, 0x01000000,
358 0x00010000, 0x01010404, 0x00000004, 0x01010000,
359 0x01010400, 0x01000000, 0x01000000, 0x00000400,
360 0x01010004, 0x00010000, 0x00010400, 0x01000004,
361 0x00000400, 0x00000004, 0x01000404, 0x00010404,
362 0x01010404, 0x00010004, 0x01010000, 0x01000404,
363 0x01000004, 0x00000404, 0x00010404, 0x01010400,
364 0x00000404, 0x01000400, 0x01000400, 0x00000000,
365 0x00010004, 0x00010400, 0x00000000, 0x01010004L},
366
367 {0x80108020, 0x80008000, 0x00008000, 0x00108020,
368 0x00100000, 0x00000020, 0x80100020, 0x80008020,
369 0x80000020, 0x80108020, 0x80108000, 0x80000000,
370 0x80008000, 0x00100000, 0x00000020, 0x80100020,
371 0x00108000, 0x00100020, 0x80008020, 0x00000000,
372 0x80000000, 0x00008000, 0x00108020, 0x80100000,
373 0x00100020, 0x80000020, 0x00000000, 0x00108000,
374 0x00008020, 0x80108000, 0x80100000, 0x00008020,
375 0x00000000, 0x00108020, 0x80100020, 0x00100000,
376 0x80008020, 0x80100000, 0x80108000, 0x00008000,
377 0x80100000, 0x80008000, 0x00000020, 0x80108020,
378 0x00108020, 0x00000020, 0x00008000, 0x80000000,
379 0x00008020, 0x80108000, 0x00100000, 0x80000020,
380 0x00100020, 0x80008020, 0x80000020, 0x00100020,
381 0x00108000, 0x00000000, 0x80008000, 0x00008020,
382 0x80000000, 0x80100020, 0x80108020, 0x00108000L},
383
384 {0x00000208, 0x08020200, 0x00000000, 0x08020008,
385 0x08000200, 0x00000000, 0x00020208, 0x08000200,
386 0x00020008, 0x08000008, 0x08000008, 0x00020000,
387 0x08020208, 0x00020008, 0x08020000, 0x00000208,
388 0x08000000, 0x00000008, 0x08020200, 0x00000200,
389 0x00020200, 0x08020000, 0x08020008, 0x00020208,
390 0x08000208, 0x00020200, 0x00020000, 0x08000208,
391 0x00000008, 0x08020208, 0x00000200, 0x08000000,
392 0x08020200, 0x08000000, 0x00020008, 0x00000208,
393 0x00020000, 0x08020200, 0x08000200, 0x00000000,
394 0x00000200, 0x00020008, 0x08020208, 0x08000200,
395 0x08000008, 0x00000200, 0x00000000, 0x08020008,
396 0x08000208, 0x00020000, 0x08000000, 0x08020208,
397 0x00000008, 0x00020208, 0x00020200, 0x08000008,
398 0x08020000, 0x08000208, 0x00000208, 0x08020000,
399 0x00020208, 0x00000008, 0x08020008, 0x00020200L},
400
401 {0x00802001, 0x00002081, 0x00002081, 0x00000080,
402 0x00802080, 0x00800081, 0x00800001, 0x00002001,
403 0x00000000, 0x00802000, 0x00802000, 0x00802081,
404 0x00000081, 0x00000000, 0x00800080, 0x00800001,
405 0x00000001, 0x00002000, 0x00800000, 0x00802001,
406 0x00000080, 0x00800000, 0x00002001, 0x00002080,
407 0x00800081, 0x00000001, 0x00002080, 0x00800080,
408 0x00002000, 0x00802080, 0x00802081, 0x00000081,
409 0x00800080, 0x00800001, 0x00802000, 0x00802081,
410 0x00000081, 0x00000000, 0x00000000, 0x00802000,
411 0x00002080, 0x00800080, 0x00800081, 0x00000001,
412 0x00802001, 0x00002081, 0x00002081, 0x00000080,
413 0x00802081, 0x00000081, 0x00000001, 0x00002000,
414 0x00800001, 0x00002001, 0x00802080, 0x00800081,
415 0x00002001, 0x00002080, 0x00800000, 0x00802001,
416 0x00000080, 0x00800000, 0x00002000, 0x00802080L},
417
418 {0x00000100, 0x02080100, 0x02080000, 0x42000100,
419 0x00080000, 0x00000100, 0x40000000, 0x02080000,
420 0x40080100, 0x00080000, 0x02000100, 0x40080100,
421 0x42000100, 0x42080000, 0x00080100, 0x40000000,
422 0x02000000, 0x40080000, 0x40080000, 0x00000000,
423 0x40000100, 0x42080100, 0x42080100, 0x02000100,
424 0x42080000, 0x40000100, 0x00000000, 0x42000000,
425 0x02080100, 0x02000000, 0x42000000, 0x00080100,
426 0x00080000, 0x42000100, 0x00000100, 0x02000000,
427 0x40000000, 0x02080000, 0x42000100, 0x40080100,
428 0x02000100, 0x40000000, 0x42080000, 0x02080100,
429 0x40080100, 0x00000100, 0x02000000, 0x42080000,
430 0x42080100, 0x00080100, 0x42000000, 0x42080100,
431 0x02080000, 0x00000000, 0x40080000, 0x42000000,
432 0x00080100, 0x02000100, 0x40000100, 0x00080000,
433 0x00000000, 0x40080000, 0x02080100, 0x40000100L},
434
435 {0x20000010, 0x20400000, 0x00004000, 0x20404010,
436 0x20400000, 0x00000010, 0x20404010, 0x00400000,
437 0x20004000, 0x00404010, 0x00400000, 0x20000010,
438 0x00400010, 0x20004000, 0x20000000, 0x00004010,
439 0x00000000, 0x00400010, 0x20004010, 0x00004000,
440 0x00404000, 0x20004010, 0x00000010, 0x20400010,
441 0x20400010, 0x00000000, 0x00404010, 0x20404000,
442 0x00004010, 0x00404000, 0x20404000, 0x20000000,
443 0x20004000, 0x00000010, 0x20400010, 0x00404000,
444 0x20404010, 0x00400000, 0x00004010, 0x20000010,
445 0x00400000, 0x20004000, 0x20000000, 0x00004010,
446 0x20000010, 0x20404010, 0x00404000, 0x20400000,
447 0x00404010, 0x20404000, 0x00000000, 0x20400010,
448 0x00000010, 0x00004000, 0x20400000, 0x00404010,
449 0x00004000, 0x00400010, 0x20004010, 0x00000000,
450 0x20404000, 0x20000000, 0x00400010, 0x20004010L},
451
452 {0x00200000, 0x04200002, 0x04000802, 0x00000000,
453 0x00000800, 0x04000802, 0x00200802, 0x04200800,
454 0x04200802, 0x00200000, 0x00000000, 0x04000002,
455 0x00000002, 0x04000000, 0x04200002, 0x00000802,
456 0x04000800, 0x00200802, 0x00200002, 0x04000800,
457 0x04000002, 0x04200000, 0x04200800, 0x00200002,
458 0x04200000, 0x00000800, 0x00000802, 0x04200802,
459 0x00200800, 0x00000002, 0x04000000, 0x00200800,
460 0x04000000, 0x00200800, 0x00200000, 0x04000802,
461 0x04000802, 0x04200002, 0x04200002, 0x00000002,
462 0x00200002, 0x04000000, 0x04000800, 0x00200000,
463 0x04200800, 0x00000802, 0x00200802, 0x04200800,
464 0x00000802, 0x04000002, 0x04200802, 0x04200000,
465 0x00200800, 0x00000000, 0x00000002, 0x04200802,
466 0x00000000, 0x00200802, 0x04200000, 0x00000800,
467 0x04000002, 0x04000800, 0x00000800, 0x00200002L},
468
469 {0x10001040, 0x00001000, 0x00040000, 0x10041040,
470 0x10000000, 0x10001040, 0x00000040, 0x10000000,
471 0x00040040, 0x10040000, 0x10041040, 0x00041000,
472 0x10041000, 0x00041040, 0x00001000, 0x00000040,
473 0x10040000, 0x10000040, 0x10001000, 0x00001040,
474 0x00041000, 0x00040040, 0x10040040, 0x10041000,
475 0x00001040, 0x00000000, 0x00000000, 0x10040040,
476 0x10000040, 0x10001000, 0x00041040, 0x00040000,
477 0x00041040, 0x00040000, 0x10041000, 0x00001000,
478 0x00000040, 0x10040040, 0x00001000, 0x00041040,
479 0x10001000, 0x00000040, 0x10000040, 0x10040000,
480 0x10040040, 0x10000000, 0x00040000, 0x10001040,
481 0x00000000, 0x10041040, 0x00040040, 0x10000040,
482 0x10040000, 0x10001000, 0x10001040, 0x00000000,
483 0x10041040, 0x00041000, 0x00041000, 0x00001040,
484 0x00001040, 0x00040040, 0x10000000, 0x10041000L}
485 };
486
487 #define f(R, K0246, K1357) (\
488 s0246 = R ^ K0246, \
489 s1357 = R ^ K1357, \
490 s0246 = rotl(s0246, 28), \
491 SPboxes[0] [(s0246 >> 24) & 0x3F] | \
492 SPboxes[1] [(s1357 >> 24) & 0x3F] | \
493 SPboxes[2] [(s0246 >> 16) & 0x3F] | \
494 SPboxes[3] [(s1357 >> 16) & 0x3F] | \
495 SPboxes[4] [(s0246 >> 8) & 0x3F] | \
496 SPboxes[5] [(s1357 >> 8) & 0x3F] | \
497 SPboxes[6] [(s0246 ) & 0x3F] | \
498 SPboxes[7] [(s1357 ) & 0x3F])
499
500 #define bitswap(L, R, n, mask) (\
501 swap = mask & ( (R >> n) ^ L ), \
502 R ^= swap << n, \
503 L ^= swap)
504
505 /* Initial permutation */
506 #define IP(L, R) (\
507 bitswap(R, L, 4, 0x0F0F0F0F), \
508 bitswap(R, L, 16, 0x0000FFFF), \
509 bitswap(L, R, 2, 0x33333333), \
510 bitswap(L, R, 8, 0x00FF00FF), \
511 bitswap(R, L, 1, 0x55555555))
512
513 /* Final permutation */
514 #define FP(L, R) (\
515 bitswap(R, L, 1, 0x55555555), \
516 bitswap(L, R, 8, 0x00FF00FF), \
517 bitswap(L, R, 2, 0x33333333), \
518 bitswap(R, L, 16, 0x0000FFFF), \
519 bitswap(R, L, 4, 0x0F0F0F0F))
520
521 void des_encipher(word32 *output, word32 L, word32 R, DESContext *sched) {
522 word32 swap, s0246, s1357;
523
524 IP(L, R);
525
526 L = rotl(L, 1);
527 R = rotl(R, 1);
528
529 L ^= f(R, sched->k0246[ 0], sched->k1357[ 0]);
530 R ^= f(L, sched->k0246[ 1], sched->k1357[ 1]);
531 L ^= f(R, sched->k0246[ 2], sched->k1357[ 2]);
532 R ^= f(L, sched->k0246[ 3], sched->k1357[ 3]);
533 L ^= f(R, sched->k0246[ 4], sched->k1357[ 4]);
534 R ^= f(L, sched->k0246[ 5], sched->k1357[ 5]);
535 L ^= f(R, sched->k0246[ 6], sched->k1357[ 6]);
536 R ^= f(L, sched->k0246[ 7], sched->k1357[ 7]);
537 L ^= f(R, sched->k0246[ 8], sched->k1357[ 8]);
538 R ^= f(L, sched->k0246[ 9], sched->k1357[ 9]);
539 L ^= f(R, sched->k0246[10], sched->k1357[10]);
540 R ^= f(L, sched->k0246[11], sched->k1357[11]);
541 L ^= f(R, sched->k0246[12], sched->k1357[12]);
542 R ^= f(L, sched->k0246[13], sched->k1357[13]);
543 L ^= f(R, sched->k0246[14], sched->k1357[14]);
544 R ^= f(L, sched->k0246[15], sched->k1357[15]);
545
546 L = rotl(L, 31);
547 R = rotl(R, 31);
548
549 swap = L; L = R; R = swap;
550
551 FP(L, R);
552
553 output[0] = L;
554 output[1] = R;
555 }
556
557 void des_decipher(word32 *output, word32 L, word32 R, DESContext *sched) {
558 word32 swap, s0246, s1357;
559
560 IP(L, R);
561
562 L = rotl(L, 1);
563 R = rotl(R, 1);
564
565 L ^= f(R, sched->k0246[15], sched->k1357[15]);
566 R ^= f(L, sched->k0246[14], sched->k1357[14]);
567 L ^= f(R, sched->k0246[13], sched->k1357[13]);
568 R ^= f(L, sched->k0246[12], sched->k1357[12]);
569 L ^= f(R, sched->k0246[11], sched->k1357[11]);
570 R ^= f(L, sched->k0246[10], sched->k1357[10]);
571 L ^= f(R, sched->k0246[ 9], sched->k1357[ 9]);
572 R ^= f(L, sched->k0246[ 8], sched->k1357[ 8]);
573 L ^= f(R, sched->k0246[ 7], sched->k1357[ 7]);
574 R ^= f(L, sched->k0246[ 6], sched->k1357[ 6]);
575 L ^= f(R, sched->k0246[ 5], sched->k1357[ 5]);
576 R ^= f(L, sched->k0246[ 4], sched->k1357[ 4]);
577 L ^= f(R, sched->k0246[ 3], sched->k1357[ 3]);
578 R ^= f(L, sched->k0246[ 2], sched->k1357[ 2]);
579 L ^= f(R, sched->k0246[ 1], sched->k1357[ 1]);
580 R ^= f(L, sched->k0246[ 0], sched->k1357[ 0]);
581
582 L = rotl(L, 31);
583 R = rotl(R, 31);
584
585 swap = L; L = R; R = swap;
586
587 FP(L, R);
588
589 output[0] = L;
590 output[1] = R;
591 }
592
593 #define GET_32BIT_MSB_FIRST(cp) \
594 (((unsigned long)(unsigned char)(cp)[3]) | \
595 ((unsigned long)(unsigned char)(cp)[2] << 8) | \
596 ((unsigned long)(unsigned char)(cp)[1] << 16) | \
597 ((unsigned long)(unsigned char)(cp)[0] << 24))
598
599 #define PUT_32BIT_MSB_FIRST(cp, value) do { \
600 (cp)[3] = (value); \
601 (cp)[2] = (value) >> 8; \
602 (cp)[1] = (value) >> 16; \
603 (cp)[0] = (value) >> 24; } while (0)
604
605 static void des_cbc_encrypt(unsigned char *dest, const unsigned char *src,
606 unsigned int len, DESContext *sched) {
607 word32 out[2], iv0, iv1;
608 unsigned int i;
609
610 assert((len & 7) == 0);
611
612 iv0 = sched->eiv0;
613 iv1 = sched->eiv1;
614 for (i = 0; i < len; i += 8) {
615 iv0 ^= GET_32BIT_MSB_FIRST(src); src += 4;
616 iv1 ^= GET_32BIT_MSB_FIRST(src); src += 4;
617 des_encipher(out, iv0, iv1, sched);
618 iv0 = out[0];
619 iv1 = out[1];
620 PUT_32BIT_MSB_FIRST(dest, iv0); dest += 4;
621 PUT_32BIT_MSB_FIRST(dest, iv1); dest += 4;
622 }
623 sched->eiv0 = iv0;
624 sched->eiv1 = iv1;
625 }
626
627 static void des_cbc_decrypt(unsigned char *dest, const unsigned char *src,
628 unsigned int len, DESContext *sched) {
629 word32 out[2], iv0, iv1, xL, xR;
630 unsigned int i;
631
632 assert((len & 7) == 0);
633
634 iv0 = sched->div0;
635 iv1 = sched->div1;
636 for (i = 0; i < len; i += 8) {
637 xL = GET_32BIT_MSB_FIRST(src); src += 4;
638 xR = GET_32BIT_MSB_FIRST(src); src += 4;
639 des_decipher(out, xL, xR, sched);
640 iv0 ^= out[0];
641 iv1 ^= out[1];
642 PUT_32BIT_MSB_FIRST(dest, iv0); dest += 4;
643 PUT_32BIT_MSB_FIRST(dest, iv1); dest += 4;
644 iv0 = xL;
645 iv1 = xR;
646 }
647 sched->div0 = iv0;
648 sched->div1 = iv1;
649 }
650
651 static void des_3cbc_encrypt(unsigned char *dest, const unsigned char *src,
652 unsigned int len, DESContext *scheds) {
653 des_cbc_encrypt(dest, src, len, &scheds[0]);
654 des_cbc_decrypt(dest, src, len, &scheds[1]);
655 des_cbc_encrypt(dest, src, len, &scheds[2]);
656 }
657
658 static void des_3cbc_decrypt(unsigned char *dest, const unsigned char *src,
659 unsigned int len, DESContext *scheds) {
660 des_cbc_decrypt(dest, src, len, &scheds[2]);
661 des_cbc_encrypt(dest, src, len, &scheds[1]);
662 des_cbc_decrypt(dest, src, len, &scheds[0]);
663 }
664
665 DESContext keys[3];
666
667 static void des3_sesskey(unsigned char *key) {
668 des_key_setup(GET_32BIT_MSB_FIRST(key),
669 GET_32BIT_MSB_FIRST(key+4), &keys[0]);
670 des_key_setup(GET_32BIT_MSB_FIRST(key+8),
671 GET_32BIT_MSB_FIRST(key+12), &keys[1]);
672 des_key_setup(GET_32BIT_MSB_FIRST(key+16),
673 GET_32BIT_MSB_FIRST(key+20), &keys[2]);
674 logevent("Initialised triple-DES encryption");
675 }
676
677 static void des3_encrypt_blk(unsigned char *blk, int len) {
678 des_3cbc_encrypt(blk, blk, len, keys);
679 }
680
681 static void des3_decrypt_blk(unsigned char *blk, int len) {
682 des_3cbc_decrypt(blk, blk, len, keys);
683 }
684
685 struct ssh_cipher ssh_3des = {
686 des3_sesskey,
687 des3_encrypt_blk,
688 des3_decrypt_blk
689 };
690
691 static void des_sesskey(unsigned char *key) {
692 des_key_setup(GET_32BIT_MSB_FIRST(key),
693 GET_32BIT_MSB_FIRST(key+4), &keys[0]);
694 logevent("Initialised single-DES encryption");
695 }
696
697 static void des_encrypt_blk(unsigned char *blk, int len) {
698 des_cbc_encrypt(blk, blk, len, keys);
699 }
700
701 static void des_decrypt_blk(unsigned char *blk, int len) {
702 des_cbc_decrypt(blk, blk, len, keys);
703 }
704
705 struct ssh_cipher ssh_des = {
706 des_sesskey,
707 des_encrypt_blk,
708 des_decrypt_blk
709 };
Local modifications for Simon Tatham's `PuTTY' SSH client and terminal emulator