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