projects / u / mdw / putty / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Wez Furlong's patch to add xterm mouse reporting and proper mouse
[u/mdw/putty] / sshdes.c
CommitLineData
374330e2 1#include <assert.h>
2#include "ssh.h"
3
033b4cef 4
d1e726bc 5/* des.c - implementation of DES
6 */
7
374330e2 8/*
d1e726bc 9 * Description of DES
1608bfe3 10 * ------------------
d1e726bc 11 *
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.
16 *
17 * The DES encryption routine requires a 64-bit input, and a key schedule K
18 * containing 16 48-bit elements.
19 *
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
27 * of the last round.)
28 * The 64-bit output block is permuted by the inverse of IP and returned.
29 *
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.)
32 *
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.
35 *
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
38 * a 48-bit block X.
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.
44 *
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.
48 *
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
54 * function PC2.
55 *
56 * That's the actual algorithm. Now for the tedious details: all those
57 * painful permutations and lookup tables.
58 *
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).
61 *
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
66 *
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).
69 *
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
72 *
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
77 * least significant.
78 *
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
83 *
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
88 *
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
93 *
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
98 *
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
103 *
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
108 *
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
113 *
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
118 *
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).
121 *
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
124 *
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).
128 *
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
131 *
132 * And the word D contains these bits.
133 *
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
136 *
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).
142 *
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
145 */
146
1608bfe3 147/*
148 * Implementation details
149 * ----------------------
150 *
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
153 * differences...
154 *
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
162 * below.
163 *
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
170 * table lookups.
171 *
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.
177 *
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
184 * code such as
185 *
186 * y |= SPboxes[0][ (rotl(R, 5) ^ top6bitsofK) & 0x3F ];
187 * t |= SPboxes[1][ (rotl(R,11) ^ next6bitsofK) & 0x3F ];
188 *
189 * and so on; and the key schedule preparation would have to
190 * provide each 6-bit chunk separately.
191 *
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:
195 *
196 * 3322222222221111111111
197 * bit 10987654321098765432109876543210
198 *
199 * box0 XXXXX X
200 * box1 XXXXXX
201 * box2 XXXXXX
202 * box3 XXXXXX
203 * box4 XXXXXX
204 * box5 XXXXXX
205 * box6 XXXXXX
206 * box7 X XXXXX
207 *
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.
214 *
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.
226 *
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.
232 *
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).
239 *
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!
246 *
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
250 *
251 * difference = ((R >> 4) ^ L) & 0x0F0F0F0F
252 * R ^= (difference << 4)
253 * L ^= difference
254 *
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
258 * do:
259 *
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
270 *
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.)
274 *
275 * The final permutation is just the inverse of IP, so it can be
276 * performed by a similar set of operations.
277 */
278
d1e726bc 279typedef struct {
280 word32 k0246[16], k1357[16];
281 word32 eiv0, eiv1;
282 word32 div0, div1;
283} DESContext;
374330e2 284
d1e726bc 285#define rotl(x, c) ( (x << c) | (x >> (32-c)) )
286#define rotl28(x, c) ( ( (x << c) | (x >> (28-c)) ) & 0x0FFFFFFF)
374330e2 287
d1e726bc 288static word32 bitsel(word32 *input, const int *bitnums, int size) {
289 word32 ret = 0;
290 while (size--) {
291 int bitpos = *bitnums++;
292 ret <<= 1;
293 if (bitpos >= 0)
294 ret |= 1 & (input[bitpos / 32] >> (bitpos % 32));
295 }
296 return ret;
297}
374330e2 298
d1e726bc 299void des_key_setup(word32 key_msw, word32 key_lsw, DESContext *sched) {
300
301 static const int PC1_Cbits[] = {
302 7, 15, 23, 31, 39, 47, 55, 63, 6, 14, 22, 30, 38, 46,
303 54, 62, 5, 13, 21, 29, 37, 45, 53, 61, 4, 12, 20, 28
304 };
305 static const int PC1_Dbits[] = {
306 1, 9, 17, 25, 33, 41, 49, 57, 2, 10, 18, 26, 34, 42,
307 50, 58, 3, 11, 19, 27, 35, 43, 51, 59, 36, 44, 52, 60
308 };
1608bfe3 309 /*
310 * The bit numbers in the two lists below don't correspond to
311 * the ones in the above description of PC2, because in the
312 * above description C and D are concatenated so `bit 28' means
313 * bit 0 of C. In this implementation we're using the standard
314 * `bitsel' function above and C is in the second word, so bit
315 * 0 of C is addressed by writing `32' here.
316 */
d1e726bc 317 static const int PC2_0246[] = {
318 49, 36, 59, 55, -1, -1, 37, 41, 48, 56, 34, 52, -1, -1, 15, 4,
319 25, 19, 9, 1, -1, -1, 12, 7, 17, 0, 22, 3, -1, -1, 46, 43
320 };
321 static const int PC2_1357[] = {
322 -1, -1, 57, 32, 45, 54, 39, 50, -1, -1, 44, 53, 33, 40, 47, 58,
323 -1, -1, 26, 16, 5, 11, 23, 8, -1, -1, 10, 14, 6, 20, 27, 24
324 };
325 static const int leftshifts[] = {1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1};
326
327 word32 C, D;
328 word32 buf[2];
329 int i;
330
331 buf[0] = key_lsw;
332 buf[1] = key_msw;
333
334 C = bitsel(buf, PC1_Cbits, 28);
335 D = bitsel(buf, PC1_Dbits, 28);
336
337 for (i = 0; i < 16; i++) {
338 C = rotl28(C, leftshifts[i]);
339 D = rotl28(D, leftshifts[i]);
340 buf[0] = D;
341 buf[1] = C;
342 sched->k0246[i] = bitsel(buf, PC2_0246, 32);
343 sched->k1357[i] = bitsel(buf, PC2_1357, 32);
344 }
374330e2 345
d1e726bc 346 sched->eiv0 = sched->eiv1 = 0;
347 sched->div0 = sched->div1 = 0; /* for good measure */
348}
374330e2 349
d1e726bc 350static const word32 SPboxes[8][64] = {
351 {0x01010400, 0x00000000, 0x00010000, 0x01010404,
352 0x01010004, 0x00010404, 0x00000004, 0x00010000,
353 0x00000400, 0x01010400, 0x01010404, 0x00000400,
354 0x01000404, 0x01010004, 0x01000000, 0x00000004,
355 0x00000404, 0x01000400, 0x01000400, 0x00010400,
356 0x00010400, 0x01010000, 0x01010000, 0x01000404,
357 0x00010004, 0x01000004, 0x01000004, 0x00010004,
358 0x00000000, 0x00000404, 0x00010404, 0x01000000,
359 0x00010000, 0x01010404, 0x00000004, 0x01010000,
360 0x01010400, 0x01000000, 0x01000000, 0x00000400,
361 0x01010004, 0x00010000, 0x00010400, 0x01000004,
362 0x00000400, 0x00000004, 0x01000404, 0x00010404,
363 0x01010404, 0x00010004, 0x01010000, 0x01000404,
364 0x01000004, 0x00000404, 0x00010404, 0x01010400,
365 0x00000404, 0x01000400, 0x01000400, 0x00000000,
366 0x00010004, 0x00010400, 0x00000000, 0x01010004L},
367
368 {0x80108020, 0x80008000, 0x00008000, 0x00108020,
369 0x00100000, 0x00000020, 0x80100020, 0x80008020,
370 0x80000020, 0x80108020, 0x80108000, 0x80000000,
371 0x80008000, 0x00100000, 0x00000020, 0x80100020,
372 0x00108000, 0x00100020, 0x80008020, 0x00000000,
373 0x80000000, 0x00008000, 0x00108020, 0x80100000,
374 0x00100020, 0x80000020, 0x00000000, 0x00108000,
375 0x00008020, 0x80108000, 0x80100000, 0x00008020,
376 0x00000000, 0x00108020, 0x80100020, 0x00100000,
377 0x80008020, 0x80100000, 0x80108000, 0x00008000,
378 0x80100000, 0x80008000, 0x00000020, 0x80108020,
379 0x00108020, 0x00000020, 0x00008000, 0x80000000,
380 0x00008020, 0x80108000, 0x00100000, 0x80000020,
381 0x00100020, 0x80008020, 0x80000020, 0x00100020,
382 0x00108000, 0x00000000, 0x80008000, 0x00008020,
383 0x80000000, 0x80100020, 0x80108020, 0x00108000L},
384
385 {0x00000208, 0x08020200, 0x00000000, 0x08020008,
386 0x08000200, 0x00000000, 0x00020208, 0x08000200,
387 0x00020008, 0x08000008, 0x08000008, 0x00020000,
388 0x08020208, 0x00020008, 0x08020000, 0x00000208,
389 0x08000000, 0x00000008, 0x08020200, 0x00000200,
390 0x00020200, 0x08020000, 0x08020008, 0x00020208,
391 0x08000208, 0x00020200, 0x00020000, 0x08000208,
392 0x00000008, 0x08020208, 0x00000200, 0x08000000,
393 0x08020200, 0x08000000, 0x00020008, 0x00000208,
394 0x00020000, 0x08020200, 0x08000200, 0x00000000,
395 0x00000200, 0x00020008, 0x08020208, 0x08000200,
396 0x08000008, 0x00000200, 0x00000000, 0x08020008,
397 0x08000208, 0x00020000, 0x08000000, 0x08020208,
398 0x00000008, 0x00020208, 0x00020200, 0x08000008,
399 0x08020000, 0x08000208, 0x00000208, 0x08020000,
400 0x00020208, 0x00000008, 0x08020008, 0x00020200L},
401
402 {0x00802001, 0x00002081, 0x00002081, 0x00000080,
403 0x00802080, 0x00800081, 0x00800001, 0x00002001,
404 0x00000000, 0x00802000, 0x00802000, 0x00802081,
405 0x00000081, 0x00000000, 0x00800080, 0x00800001,
406 0x00000001, 0x00002000, 0x00800000, 0x00802001,
407 0x00000080, 0x00800000, 0x00002001, 0x00002080,
408 0x00800081, 0x00000001, 0x00002080, 0x00800080,
409 0x00002000, 0x00802080, 0x00802081, 0x00000081,
410 0x00800080, 0x00800001, 0x00802000, 0x00802081,
411 0x00000081, 0x00000000, 0x00000000, 0x00802000,
412 0x00002080, 0x00800080, 0x00800081, 0x00000001,
413 0x00802001, 0x00002081, 0x00002081, 0x00000080,
414 0x00802081, 0x00000081, 0x00000001, 0x00002000,
415 0x00800001, 0x00002001, 0x00802080, 0x00800081,
416 0x00002001, 0x00002080, 0x00800000, 0x00802001,
417 0x00000080, 0x00800000, 0x00002000, 0x00802080L},
418
419 {0x00000100, 0x02080100, 0x02080000, 0x42000100,
420 0x00080000, 0x00000100, 0x40000000, 0x02080000,
421 0x40080100, 0x00080000, 0x02000100, 0x40080100,
422 0x42000100, 0x42080000, 0x00080100, 0x40000000,
423 0x02000000, 0x40080000, 0x40080000, 0x00000000,
424 0x40000100, 0x42080100, 0x42080100, 0x02000100,
425 0x42080000, 0x40000100, 0x00000000, 0x42000000,
426 0x02080100, 0x02000000, 0x42000000, 0x00080100,
427 0x00080000, 0x42000100, 0x00000100, 0x02000000,
428 0x40000000, 0x02080000, 0x42000100, 0x40080100,
429 0x02000100, 0x40000000, 0x42080000, 0x02080100,
430 0x40080100, 0x00000100, 0x02000000, 0x42080000,
431 0x42080100, 0x00080100, 0x42000000, 0x42080100,
432 0x02080000, 0x00000000, 0x40080000, 0x42000000,
433 0x00080100, 0x02000100, 0x40000100, 0x00080000,
434 0x00000000, 0x40080000, 0x02080100, 0x40000100L},
435
436 {0x20000010, 0x20400000, 0x00004000, 0x20404010,
437 0x20400000, 0x00000010, 0x20404010, 0x00400000,
438 0x20004000, 0x00404010, 0x00400000, 0x20000010,
439 0x00400010, 0x20004000, 0x20000000, 0x00004010,
440 0x00000000, 0x00400010, 0x20004010, 0x00004000,
441 0x00404000, 0x20004010, 0x00000010, 0x20400010,
442 0x20400010, 0x00000000, 0x00404010, 0x20404000,
443 0x00004010, 0x00404000, 0x20404000, 0x20000000,
444 0x20004000, 0x00000010, 0x20400010, 0x00404000,
445 0x20404010, 0x00400000, 0x00004010, 0x20000010,
446 0x00400000, 0x20004000, 0x20000000, 0x00004010,
447 0x20000010, 0x20404010, 0x00404000, 0x20400000,
448 0x00404010, 0x20404000, 0x00000000, 0x20400010,
449 0x00000010, 0x00004000, 0x20400000, 0x00404010,
450 0x00004000, 0x00400010, 0x20004010, 0x00000000,
451 0x20404000, 0x20000000, 0x00400010, 0x20004010L},
452
453 {0x00200000, 0x04200002, 0x04000802, 0x00000000,
454 0x00000800, 0x04000802, 0x00200802, 0x04200800,
455 0x04200802, 0x00200000, 0x00000000, 0x04000002,
456 0x00000002, 0x04000000, 0x04200002, 0x00000802,
457 0x04000800, 0x00200802, 0x00200002, 0x04000800,
458 0x04000002, 0x04200000, 0x04200800, 0x00200002,
459 0x04200000, 0x00000800, 0x00000802, 0x04200802,
460 0x00200800, 0x00000002, 0x04000000, 0x00200800,
461 0x04000000, 0x00200800, 0x00200000, 0x04000802,
462 0x04000802, 0x04200002, 0x04200002, 0x00000002,
463 0x00200002, 0x04000000, 0x04000800, 0x00200000,
464 0x04200800, 0x00000802, 0x00200802, 0x04200800,
465 0x00000802, 0x04000002, 0x04200802, 0x04200000,
466 0x00200800, 0x00000000, 0x00000002, 0x04200802,
467 0x00000000, 0x00200802, 0x04200000, 0x00000800,
468 0x04000002, 0x04000800, 0x00000800, 0x00200002L},
469
470 {0x10001040, 0x00001000, 0x00040000, 0x10041040,
471 0x10000000, 0x10001040, 0x00000040, 0x10000000,
472 0x00040040, 0x10040000, 0x10041040, 0x00041000,
473 0x10041000, 0x00041040, 0x00001000, 0x00000040,
474 0x10040000, 0x10000040, 0x10001000, 0x00001040,
475 0x00041000, 0x00040040, 0x10040040, 0x10041000,
476 0x00001040, 0x00000000, 0x00000000, 0x10040040,
477 0x10000040, 0x10001000, 0x00041040, 0x00040000,
478 0x00041040, 0x00040000, 0x10041000, 0x00001000,
479 0x00000040, 0x10040040, 0x00001000, 0x00041040,
480 0x10001000, 0x00000040, 0x10000040, 0x10040000,
481 0x10040040, 0x10000000, 0x00040000, 0x10001040,
482 0x00000000, 0x10041040, 0x00040040, 0x10000040,
483 0x10040000, 0x10001000, 0x10001040, 0x00000000,
484 0x10041040, 0x00041000, 0x00041000, 0x00001040,
485 0x00001040, 0x00040040, 0x10000000, 0x10041000L}
486};
374330e2 487
d1e726bc 488#define f(R, K0246, K1357) (\
489 s0246 = R ^ K0246, \
490 s1357 = R ^ K1357, \
491 s0246 = rotl(s0246, 28), \
492 SPboxes[0] [(s0246 >> 24) & 0x3F] | \
493 SPboxes[1] [(s1357 >> 24) & 0x3F] | \
494 SPboxes[2] [(s0246 >> 16) & 0x3F] | \
495 SPboxes[3] [(s1357 >> 16) & 0x3F] | \
496 SPboxes[4] [(s0246 >> 8) & 0x3F] | \
497 SPboxes[5] [(s1357 >> 8) & 0x3F] | \
498 SPboxes[6] [(s0246 ) & 0x3F] | \
499 SPboxes[7] [(s1357 ) & 0x3F])
500
501#define bitswap(L, R, n, mask) (\
502 swap = mask & ( (R >> n) ^ L ), \
503 R ^= swap << n, \
504 L ^= swap)
505
506/* Initial permutation */
507#define IP(L, R) (\
508 bitswap(R, L, 4, 0x0F0F0F0F), \
509 bitswap(R, L, 16, 0x0000FFFF), \
510 bitswap(L, R, 2, 0x33333333), \
511 bitswap(L, R, 8, 0x00FF00FF), \
512 bitswap(R, L, 1, 0x55555555))
513
514/* Final permutation */
515#define FP(L, R) (\
516 bitswap(R, L, 1, 0x55555555), \
517 bitswap(L, R, 8, 0x00FF00FF), \
518 bitswap(L, R, 2, 0x33333333), \
519 bitswap(R, L, 16, 0x0000FFFF), \
520 bitswap(R, L, 4, 0x0F0F0F0F))
521
522void des_encipher(word32 *output, word32 L, word32 R, DESContext *sched) {
523 word32 swap, s0246, s1357;
524
525 IP(L, R);
526
527 L = rotl(L, 1);
528 R = rotl(R, 1);
529
530 L ^= f(R, sched->k0246[ 0], sched->k1357[ 0]);
531 R ^= f(L, sched->k0246[ 1], sched->k1357[ 1]);
532 L ^= f(R, sched->k0246[ 2], sched->k1357[ 2]);
533 R ^= f(L, sched->k0246[ 3], sched->k1357[ 3]);
534 L ^= f(R, sched->k0246[ 4], sched->k1357[ 4]);
535 R ^= f(L, sched->k0246[ 5], sched->k1357[ 5]);
536 L ^= f(R, sched->k0246[ 6], sched->k1357[ 6]);
537 R ^= f(L, sched->k0246[ 7], sched->k1357[ 7]);
538 L ^= f(R, sched->k0246[ 8], sched->k1357[ 8]);
539 R ^= f(L, sched->k0246[ 9], sched->k1357[ 9]);
540 L ^= f(R, sched->k0246[10], sched->k1357[10]);
541 R ^= f(L, sched->k0246[11], sched->k1357[11]);
542 L ^= f(R, sched->k0246[12], sched->k1357[12]);
543 R ^= f(L, sched->k0246[13], sched->k1357[13]);
544 L ^= f(R, sched->k0246[14], sched->k1357[14]);
545 R ^= f(L, sched->k0246[15], sched->k1357[15]);
546
547 L = rotl(L, 31);
548 R = rotl(R, 31);
549
550 swap = L; L = R; R = swap;
551
552 FP(L, R);
553
554 output[0] = L;
555 output[1] = R;
556}
374330e2 557
d1e726bc 558void des_decipher(word32 *output, word32 L, word32 R, DESContext *sched) {
559 word32 swap, s0246, s1357;
374330e2 560
d1e726bc 561 IP(L, R);
374330e2 562
d1e726bc 563 L = rotl(L, 1);
564 R = rotl(R, 1);
374330e2 565
d1e726bc 566 L ^= f(R, sched->k0246[15], sched->k1357[15]);
567 R ^= f(L, sched->k0246[14], sched->k1357[14]);
568 L ^= f(R, sched->k0246[13], sched->k1357[13]);
569 R ^= f(L, sched->k0246[12], sched->k1357[12]);
570 L ^= f(R, sched->k0246[11], sched->k1357[11]);
571 R ^= f(L, sched->k0246[10], sched->k1357[10]);
572 L ^= f(R, sched->k0246[ 9], sched->k1357[ 9]);
573 R ^= f(L, sched->k0246[ 8], sched->k1357[ 8]);
574 L ^= f(R, sched->k0246[ 7], sched->k1357[ 7]);
575 R ^= f(L, sched->k0246[ 6], sched->k1357[ 6]);
576 L ^= f(R, sched->k0246[ 5], sched->k1357[ 5]);
577 R ^= f(L, sched->k0246[ 4], sched->k1357[ 4]);
578 L ^= f(R, sched->k0246[ 3], sched->k1357[ 3]);
579 R ^= f(L, sched->k0246[ 2], sched->k1357[ 2]);
580 L ^= f(R, sched->k0246[ 1], sched->k1357[ 1]);
581 R ^= f(L, sched->k0246[ 0], sched->k1357[ 0]);
582
583 L = rotl(L, 31);
584 R = rotl(R, 31);
585
586 swap = L; L = R; R = swap;
587
588 FP(L, R);
589
590 output[0] = L;
591 output[1] = R;
374330e2 592}
593
d1e726bc 594#define GET_32BIT_MSB_FIRST(cp) \
595 (((unsigned long)(unsigned char)(cp)[3]) | \
596 ((unsigned long)(unsigned char)(cp)[2] << 8) | \
597 ((unsigned long)(unsigned char)(cp)[1] << 16) | \
598 ((unsigned long)(unsigned char)(cp)[0] << 24))
599
600#define PUT_32BIT_MSB_FIRST(cp, value) do { \
601 (cp)[3] = (value); \
602 (cp)[2] = (value) >> 8; \
603 (cp)[1] = (value) >> 16; \
604 (cp)[0] = (value) >> 24; } while (0)
605
606static void des_cbc_encrypt(unsigned char *dest, const unsigned char *src,
607 unsigned int len, DESContext *sched) {
608 word32 out[2], iv0, iv1;
609 unsigned int i;
610
611 assert((len & 7) == 0);
612
613 iv0 = sched->eiv0;
614 iv1 = sched->eiv1;
615 for (i = 0; i < len; i += 8) {
616 iv0 ^= GET_32BIT_MSB_FIRST(src); src += 4;
617 iv1 ^= GET_32BIT_MSB_FIRST(src); src += 4;
618 des_encipher(out, iv0, iv1, sched);
619 iv0 = out[0];
620 iv1 = out[1];
621 PUT_32BIT_MSB_FIRST(dest, iv0); dest += 4;
622 PUT_32BIT_MSB_FIRST(dest, iv1); dest += 4;
374330e2 623 }
d1e726bc 624 sched->eiv0 = iv0;
625 sched->eiv1 = iv1;
374330e2 626}
627
d1e726bc 628static void des_cbc_decrypt(unsigned char *dest, const unsigned char *src,
629 unsigned int len, DESContext *sched) {
630 word32 out[2], iv0, iv1, xL, xR;
631 unsigned int i;
632
633 assert((len & 7) == 0);
634
635 iv0 = sched->div0;
636 iv1 = sched->div1;
637 for (i = 0; i < len; i += 8) {
638 xL = GET_32BIT_MSB_FIRST(src); src += 4;
639 xR = GET_32BIT_MSB_FIRST(src); src += 4;
640 des_decipher(out, xL, xR, sched);
641 iv0 ^= out[0];
642 iv1 ^= out[1];
643 PUT_32BIT_MSB_FIRST(dest, iv0); dest += 4;
644 PUT_32BIT_MSB_FIRST(dest, iv1); dest += 4;
645 iv0 = xL;
646 iv1 = xR;
374330e2 647 }
d1e726bc 648 sched->div0 = iv0;
649 sched->div1 = iv1;
374330e2 650}
651
d1e726bc 652static void des_3cbc_encrypt(unsigned char *dest, const unsigned char *src,
653 unsigned int len, DESContext *scheds) {
654 des_cbc_encrypt(dest, src, len, &scheds[0]);
655 des_cbc_decrypt(dest, src, len, &scheds[1]);
656 des_cbc_encrypt(dest, src, len, &scheds[2]);
374330e2 657}
658
033b4cef 659static void des_cbc3_encrypt(unsigned char *dest, const unsigned char *src,
660 unsigned int len, DESContext *scheds) {
661 word32 out[2], iv0, iv1;
662 unsigned int i;
663
664 assert((len & 7) == 0);
665
666 iv0 = scheds->eiv0;
667 iv1 = scheds->eiv1;
668 for (i = 0; i < len; i += 8) {
669 iv0 ^= GET_32BIT_MSB_FIRST(src); src += 4;
670 iv1 ^= GET_32BIT_MSB_FIRST(src); src += 4;
671 des_encipher(out, iv0, iv1, &scheds[0]);
672 des_decipher(out, out[0], out[1], &scheds[1]);
673 des_encipher(out, out[0], out[1], &scheds[2]);
674 iv0 = out[0];
675 iv1 = out[1];
676 PUT_32BIT_MSB_FIRST(dest, iv0); dest += 4;
677 PUT_32BIT_MSB_FIRST(dest, iv1); dest += 4;
678 }
679 scheds->eiv0 = iv0;
680 scheds->eiv1 = iv1;
681}
682
d1e726bc 683static void des_3cbc_decrypt(unsigned char *dest, const unsigned char *src,
684 unsigned int len, DESContext *scheds) {
685 des_cbc_decrypt(dest, src, len, &scheds[2]);
686 des_cbc_encrypt(dest, src, len, &scheds[1]);
687 des_cbc_decrypt(dest, src, len, &scheds[0]);
374330e2 688}
689
033b4cef 690static void des_cbc3_decrypt(unsigned char *dest, const unsigned char *src,
691 unsigned int len, DESContext *scheds) {
692 word32 out[2], iv0, iv1, xL, xR;
693 unsigned int i;
694
695 assert((len & 7) == 0);
696
697 iv0 = scheds->div0;
698 iv1 = scheds->div1;
699 for (i = 0; i < len; i += 8) {
700 xL = GET_32BIT_MSB_FIRST(src); src += 4;
701 xR = GET_32BIT_MSB_FIRST(src); src += 4;
702 des_decipher(out, xL, xR, &scheds[2]);
703 des_encipher(out, out[0], out[1], &scheds[1]);
704 des_decipher(out, out[0], out[1], &scheds[0]);
705 iv0 ^= out[0];
706 iv1 ^= out[1];
707 PUT_32BIT_MSB_FIRST(dest, iv0); dest += 4;
708 PUT_32BIT_MSB_FIRST(dest, iv1); dest += 4;
709 iv0 = xL;
710 iv1 = xR;
711 }
712 scheds->div0 = iv0;
713 scheds->div1 = iv1;
714}
715
d39f364a 716static DESContext cskeys[3], sckeys[3];
374330e2 717
d39f364a 718static void des3_cskey(unsigned char *key) {
d1e726bc 719 des_key_setup(GET_32BIT_MSB_FIRST(key),
d39f364a 720 GET_32BIT_MSB_FIRST(key+4), &cskeys[0]);
d1e726bc 721 des_key_setup(GET_32BIT_MSB_FIRST(key+8),
d39f364a 722 GET_32BIT_MSB_FIRST(key+12), &cskeys[1]);
d1e726bc 723 des_key_setup(GET_32BIT_MSB_FIRST(key+16),
d39f364a 724 GET_32BIT_MSB_FIRST(key+20), &cskeys[2]);
725 logevent("Initialised triple-DES client->server encryption");
726}
727
728static void des3_csiv(unsigned char *key) {
729 cskeys[0].eiv0 = GET_32BIT_MSB_FIRST(key);
730 cskeys[0].eiv1 = GET_32BIT_MSB_FIRST(key+4);
731}
732
733static void des3_sciv(unsigned char *key) {
734 sckeys[0].div0 = GET_32BIT_MSB_FIRST(key);
735 sckeys[0].div1 = GET_32BIT_MSB_FIRST(key+4);
736}
737
738static void des3_sckey(unsigned char *key) {
739 des_key_setup(GET_32BIT_MSB_FIRST(key),
740 GET_32BIT_MSB_FIRST(key+4), &sckeys[0]);
741 des_key_setup(GET_32BIT_MSB_FIRST(key+8),
742 GET_32BIT_MSB_FIRST(key+12), &sckeys[1]);
743 des_key_setup(GET_32BIT_MSB_FIRST(key+16),
744 GET_32BIT_MSB_FIRST(key+20), &sckeys[2]);
745 logevent("Initialised triple-DES server->client encryption");
746}
747
748static void des3_sesskey(unsigned char *key) {
749 des3_cskey(key);
750 des3_sckey(key);
374330e2 751}
752
753static void des3_encrypt_blk(unsigned char *blk, int len) {
d39f364a 754 des_3cbc_encrypt(blk, blk, len, cskeys);
374330e2 755}
756
757static void des3_decrypt_blk(unsigned char *blk, int len) {
d39f364a 758 des_3cbc_decrypt(blk, blk, len, sckeys);
374330e2 759}
760
033b4cef 761static void des3_ssh2_encrypt_blk(unsigned char *blk, int len) {
762 des_cbc3_encrypt(blk, blk, len, cskeys);
763}
764
765static void des3_ssh2_decrypt_blk(unsigned char *blk, int len) {
766 des_cbc3_decrypt(blk, blk, len, sckeys);
767}
768
7cca0d81 769void des3_decrypt_pubkey(unsigned char *key,
770 unsigned char *blk, int len) {
771 DESContext ourkeys[3];
772 des_key_setup(GET_32BIT_MSB_FIRST(key),
773 GET_32BIT_MSB_FIRST(key+4), &ourkeys[0]);
774 des_key_setup(GET_32BIT_MSB_FIRST(key+8),
775 GET_32BIT_MSB_FIRST(key+12), &ourkeys[1]);
776 des_key_setup(GET_32BIT_MSB_FIRST(key),
777 GET_32BIT_MSB_FIRST(key+4), &ourkeys[2]);
778 des_3cbc_decrypt(blk, blk, len, ourkeys);
779}
780
6e522441 781void des3_encrypt_pubkey(unsigned char *key,
782 unsigned char *blk, int len) {
783 DESContext ourkeys[3];
784 des_key_setup(GET_32BIT_MSB_FIRST(key),
785 GET_32BIT_MSB_FIRST(key+4), &ourkeys[0]);
786 des_key_setup(GET_32BIT_MSB_FIRST(key+8),
787 GET_32BIT_MSB_FIRST(key+12), &ourkeys[1]);
788 des_key_setup(GET_32BIT_MSB_FIRST(key),
789 GET_32BIT_MSB_FIRST(key+4), &ourkeys[2]);
790 des_3cbc_encrypt(blk, blk, len, ourkeys);
791}
792
65a22376 793static const struct ssh2_cipher ssh_3des_ssh2 = {
d39f364a 794 des3_csiv, des3_cskey,
795 des3_sciv, des3_sckey,
033b4cef 796 des3_ssh2_encrypt_blk,
797 des3_ssh2_decrypt_blk,
798 "3des-cbc",
d2a0e0be 799 8, 168
033b4cef 800};
801
65a22376 802static const struct ssh2_cipher *const des3_list[] = {
0a3f1d48 803 &ssh_3des_ssh2
804};
805
65a22376 806const struct ssh2_ciphers ssh2_3des = {
0a3f1d48 807 sizeof(des3_list) / sizeof(*des3_list),
808 des3_list
809};
810
65a22376 811const struct ssh_cipher ssh_3des = {
033b4cef 812 des3_sesskey,
374330e2 813 des3_encrypt_blk,
e5574168 814 des3_decrypt_blk,
0a3f1d48 815 8
374330e2 816};
817
9697bfd2 818static void des_sesskey(unsigned char *key) {
d1e726bc 819 des_key_setup(GET_32BIT_MSB_FIRST(key),
d39f364a 820 GET_32BIT_MSB_FIRST(key+4), &cskeys[0]);
c5e9c988 821 logevent("Initialised single-DES encryption");
9697bfd2 822}
823
824static void des_encrypt_blk(unsigned char *blk, int len) {
d39f364a 825 des_cbc_encrypt(blk, blk, len, cskeys);
9697bfd2 826}
827
828static void des_decrypt_blk(unsigned char *blk, int len) {
d39f364a 829 des_cbc_decrypt(blk, blk, len, cskeys);
9697bfd2 830}
831
65a22376 832const struct ssh_cipher ssh_des = {
9697bfd2 833 des_sesskey,
834 des_encrypt_blk,
e5574168 835 des_decrypt_blk,
0a3f1d48 836 8
9697bfd2 837};
Local modifications for Simon Tatham's `PuTTY' SSH client and terminal emulator