projects / u / mdw / putty / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Fix the nasty flashing-light-grey-on-resize problem, after MCV
[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
32874aea 288static word32 bitsel(word32 * input, const int *bitnums, int size)
289{
d1e726bc 290 word32 ret = 0;
291 while (size--) {
32874aea 292 int bitpos = *bitnums++;
293 ret <<= 1;
294 if (bitpos >= 0)
295 ret |= 1 & (input[bitpos / 32] >> (bitpos % 32));
d1e726bc 296 }
297 return ret;
298}
374330e2 299
32874aea 300void des_key_setup(word32 key_msw, word32 key_lsw, DESContext * sched)
301{
d1e726bc 302
303 static const int PC1_Cbits[] = {
32874aea 304 7, 15, 23, 31, 39, 47, 55, 63, 6, 14, 22, 30, 38, 46,
305 54, 62, 5, 13, 21, 29, 37, 45, 53, 61, 4, 12, 20, 28
d1e726bc 306 };
307 static const int PC1_Dbits[] = {
32874aea 308 1, 9, 17, 25, 33, 41, 49, 57, 2, 10, 18, 26, 34, 42,
309 50, 58, 3, 11, 19, 27, 35, 43, 51, 59, 36, 44, 52, 60
d1e726bc 310 };
1608bfe3 311 /*
312 * The bit numbers in the two lists below don't correspond to
313 * the ones in the above description of PC2, because in the
314 * above description C and D are concatenated so `bit 28' means
315 * bit 0 of C. In this implementation we're using the standard
316 * `bitsel' function above and C is in the second word, so bit
317 * 0 of C is addressed by writing `32' here.
318 */
d1e726bc 319 static const int PC2_0246[] = {
32874aea 320 49, 36, 59, 55, -1, -1, 37, 41, 48, 56, 34, 52, -1, -1, 15, 4,
321 25, 19, 9, 1, -1, -1, 12, 7, 17, 0, 22, 3, -1, -1, 46, 43
d1e726bc 322 };
323 static const int PC2_1357[] = {
32874aea 324 -1, -1, 57, 32, 45, 54, 39, 50, -1, -1, 44, 53, 33, 40, 47, 58,
325 -1, -1, 26, 16, 5, 11, 23, 8, -1, -1, 10, 14, 6, 20, 27, 24
d1e726bc 326 };
32874aea 327 static const int leftshifts[] =
328 { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };
d1e726bc 329
330 word32 C, D;
331 word32 buf[2];
332 int i;
333
334 buf[0] = key_lsw;
335 buf[1] = key_msw;
336
337 C = bitsel(buf, PC1_Cbits, 28);
338 D = bitsel(buf, PC1_Dbits, 28);
339
340 for (i = 0; i < 16; i++) {
32874aea 341 C = rotl28(C, leftshifts[i]);
342 D = rotl28(D, leftshifts[i]);
343 buf[0] = D;
344 buf[1] = C;
345 sched->k0246[i] = bitsel(buf, PC2_0246, 32);
346 sched->k1357[i] = bitsel(buf, PC2_1357, 32);
d1e726bc 347 }
374330e2 348
d1e726bc 349 sched->eiv0 = sched->eiv1 = 0;
32874aea 350 sched->div0 = sched->div1 = 0; /* for good measure */
d1e726bc 351}
374330e2 352
d1e726bc 353static const word32 SPboxes[8][64] = {
354 {0x01010400, 0x00000000, 0x00010000, 0x01010404,
32874aea 355 0x01010004, 0x00010404, 0x00000004, 0x00010000,
356 0x00000400, 0x01010400, 0x01010404, 0x00000400,
357 0x01000404, 0x01010004, 0x01000000, 0x00000004,
358 0x00000404, 0x01000400, 0x01000400, 0x00010400,
359 0x00010400, 0x01010000, 0x01010000, 0x01000404,
360 0x00010004, 0x01000004, 0x01000004, 0x00010004,
361 0x00000000, 0x00000404, 0x00010404, 0x01000000,
362 0x00010000, 0x01010404, 0x00000004, 0x01010000,
363 0x01010400, 0x01000000, 0x01000000, 0x00000400,
364 0x01010004, 0x00010000, 0x00010400, 0x01000004,
365 0x00000400, 0x00000004, 0x01000404, 0x00010404,
366 0x01010404, 0x00010004, 0x01010000, 0x01000404,
367 0x01000004, 0x00000404, 0x00010404, 0x01010400,
368 0x00000404, 0x01000400, 0x01000400, 0x00000000,
369 0x00010004, 0x00010400, 0x00000000, 0x01010004L},
d1e726bc 370
371 {0x80108020, 0x80008000, 0x00008000, 0x00108020,
32874aea 372 0x00100000, 0x00000020, 0x80100020, 0x80008020,
373 0x80000020, 0x80108020, 0x80108000, 0x80000000,
374 0x80008000, 0x00100000, 0x00000020, 0x80100020,
375 0x00108000, 0x00100020, 0x80008020, 0x00000000,
376 0x80000000, 0x00008000, 0x00108020, 0x80100000,
377 0x00100020, 0x80000020, 0x00000000, 0x00108000,
378 0x00008020, 0x80108000, 0x80100000, 0x00008020,
379 0x00000000, 0x00108020, 0x80100020, 0x00100000,
380 0x80008020, 0x80100000, 0x80108000, 0x00008000,
381 0x80100000, 0x80008000, 0x00000020, 0x80108020,
382 0x00108020, 0x00000020, 0x00008000, 0x80000000,
383 0x00008020, 0x80108000, 0x00100000, 0x80000020,
384 0x00100020, 0x80008020, 0x80000020, 0x00100020,
385 0x00108000, 0x00000000, 0x80008000, 0x00008020,
386 0x80000000, 0x80100020, 0x80108020, 0x00108000L},
d1e726bc 387
388 {0x00000208, 0x08020200, 0x00000000, 0x08020008,
32874aea 389 0x08000200, 0x00000000, 0x00020208, 0x08000200,
390 0x00020008, 0x08000008, 0x08000008, 0x00020000,
391 0x08020208, 0x00020008, 0x08020000, 0x00000208,
392 0x08000000, 0x00000008, 0x08020200, 0x00000200,
393 0x00020200, 0x08020000, 0x08020008, 0x00020208,
394 0x08000208, 0x00020200, 0x00020000, 0x08000208,
395 0x00000008, 0x08020208, 0x00000200, 0x08000000,
396 0x08020200, 0x08000000, 0x00020008, 0x00000208,
397 0x00020000, 0x08020200, 0x08000200, 0x00000000,
398 0x00000200, 0x00020008, 0x08020208, 0x08000200,
399 0x08000008, 0x00000200, 0x00000000, 0x08020008,
400 0x08000208, 0x00020000, 0x08000000, 0x08020208,
401 0x00000008, 0x00020208, 0x00020200, 0x08000008,
402 0x08020000, 0x08000208, 0x00000208, 0x08020000,
403 0x00020208, 0x00000008, 0x08020008, 0x00020200L},
d1e726bc 404
405 {0x00802001, 0x00002081, 0x00002081, 0x00000080,
32874aea 406 0x00802080, 0x00800081, 0x00800001, 0x00002001,
407 0x00000000, 0x00802000, 0x00802000, 0x00802081,
408 0x00000081, 0x00000000, 0x00800080, 0x00800001,
409 0x00000001, 0x00002000, 0x00800000, 0x00802001,
410 0x00000080, 0x00800000, 0x00002001, 0x00002080,
411 0x00800081, 0x00000001, 0x00002080, 0x00800080,
412 0x00002000, 0x00802080, 0x00802081, 0x00000081,
413 0x00800080, 0x00800001, 0x00802000, 0x00802081,
414 0x00000081, 0x00000000, 0x00000000, 0x00802000,
415 0x00002080, 0x00800080, 0x00800081, 0x00000001,
416 0x00802001, 0x00002081, 0x00002081, 0x00000080,
417 0x00802081, 0x00000081, 0x00000001, 0x00002000,
418 0x00800001, 0x00002001, 0x00802080, 0x00800081,
419 0x00002001, 0x00002080, 0x00800000, 0x00802001,
420 0x00000080, 0x00800000, 0x00002000, 0x00802080L},
d1e726bc 421
422 {0x00000100, 0x02080100, 0x02080000, 0x42000100,
32874aea 423 0x00080000, 0x00000100, 0x40000000, 0x02080000,
424 0x40080100, 0x00080000, 0x02000100, 0x40080100,
425 0x42000100, 0x42080000, 0x00080100, 0x40000000,
426 0x02000000, 0x40080000, 0x40080000, 0x00000000,
427 0x40000100, 0x42080100, 0x42080100, 0x02000100,
428 0x42080000, 0x40000100, 0x00000000, 0x42000000,
429 0x02080100, 0x02000000, 0x42000000, 0x00080100,
430 0x00080000, 0x42000100, 0x00000100, 0x02000000,
431 0x40000000, 0x02080000, 0x42000100, 0x40080100,
432 0x02000100, 0x40000000, 0x42080000, 0x02080100,
433 0x40080100, 0x00000100, 0x02000000, 0x42080000,
434 0x42080100, 0x00080100, 0x42000000, 0x42080100,
435 0x02080000, 0x00000000, 0x40080000, 0x42000000,
436 0x00080100, 0x02000100, 0x40000100, 0x00080000,
437 0x00000000, 0x40080000, 0x02080100, 0x40000100L},
d1e726bc 438
439 {0x20000010, 0x20400000, 0x00004000, 0x20404010,
32874aea 440 0x20400000, 0x00000010, 0x20404010, 0x00400000,
441 0x20004000, 0x00404010, 0x00400000, 0x20000010,
442 0x00400010, 0x20004000, 0x20000000, 0x00004010,
443 0x00000000, 0x00400010, 0x20004010, 0x00004000,
444 0x00404000, 0x20004010, 0x00000010, 0x20400010,
445 0x20400010, 0x00000000, 0x00404010, 0x20404000,
446 0x00004010, 0x00404000, 0x20404000, 0x20000000,
447 0x20004000, 0x00000010, 0x20400010, 0x00404000,
448 0x20404010, 0x00400000, 0x00004010, 0x20000010,
449 0x00400000, 0x20004000, 0x20000000, 0x00004010,
450 0x20000010, 0x20404010, 0x00404000, 0x20400000,
451 0x00404010, 0x20404000, 0x00000000, 0x20400010,
452 0x00000010, 0x00004000, 0x20400000, 0x00404010,
453 0x00004000, 0x00400010, 0x20004010, 0x00000000,
454 0x20404000, 0x20000000, 0x00400010, 0x20004010L},
d1e726bc 455
456 {0x00200000, 0x04200002, 0x04000802, 0x00000000,
32874aea 457 0x00000800, 0x04000802, 0x00200802, 0x04200800,
458 0x04200802, 0x00200000, 0x00000000, 0x04000002,
459 0x00000002, 0x04000000, 0x04200002, 0x00000802,
460 0x04000800, 0x00200802, 0x00200002, 0x04000800,
461 0x04000002, 0x04200000, 0x04200800, 0x00200002,
462 0x04200000, 0x00000800, 0x00000802, 0x04200802,
463 0x00200800, 0x00000002, 0x04000000, 0x00200800,
464 0x04000000, 0x00200800, 0x00200000, 0x04000802,
465 0x04000802, 0x04200002, 0x04200002, 0x00000002,
466 0x00200002, 0x04000000, 0x04000800, 0x00200000,
467 0x04200800, 0x00000802, 0x00200802, 0x04200800,
468 0x00000802, 0x04000002, 0x04200802, 0x04200000,
469 0x00200800, 0x00000000, 0x00000002, 0x04200802,
470 0x00000000, 0x00200802, 0x04200000, 0x00000800,
471 0x04000002, 0x04000800, 0x00000800, 0x00200002L},
d1e726bc 472
473 {0x10001040, 0x00001000, 0x00040000, 0x10041040,
32874aea 474 0x10000000, 0x10001040, 0x00000040, 0x10000000,
475 0x00040040, 0x10040000, 0x10041040, 0x00041000,
476 0x10041000, 0x00041040, 0x00001000, 0x00000040,
477 0x10040000, 0x10000040, 0x10001000, 0x00001040,
478 0x00041000, 0x00040040, 0x10040040, 0x10041000,
479 0x00001040, 0x00000000, 0x00000000, 0x10040040,
480 0x10000040, 0x10001000, 0x00041040, 0x00040000,
481 0x00041040, 0x00040000, 0x10041000, 0x00001000,
482 0x00000040, 0x10040040, 0x00001000, 0x00041040,
483 0x10001000, 0x00000040, 0x10000040, 0x10040000,
484 0x10040040, 0x10000000, 0x00040000, 0x10001040,
485 0x00000000, 0x10041040, 0x00040040, 0x10000040,
486 0x10040000, 0x10001000, 0x10001040, 0x00000000,
487 0x10041040, 0x00041000, 0x00041000, 0x00001040,
488 0x00001040, 0x00040040, 0x10000000, 0x10041000L}
d1e726bc 489};
374330e2 490
d1e726bc 491#define f(R, K0246, K1357) (\
492 s0246 = R ^ K0246, \
493 s1357 = R ^ K1357, \
494 s0246 = rotl(s0246, 28), \
495 SPboxes[0] [(s0246 >> 24) & 0x3F] | \
496 SPboxes[1] [(s1357 >> 24) & 0x3F] | \
497 SPboxes[2] [(s0246 >> 16) & 0x3F] | \
498 SPboxes[3] [(s1357 >> 16) & 0x3F] | \
499 SPboxes[4] [(s0246 >> 8) & 0x3F] | \
500 SPboxes[5] [(s1357 >> 8) & 0x3F] | \
501 SPboxes[6] [(s0246 ) & 0x3F] | \
502 SPboxes[7] [(s1357 ) & 0x3F])
503
504#define bitswap(L, R, n, mask) (\
505 swap = mask & ( (R >> n) ^ L ), \
506 R ^= swap << n, \
507 L ^= swap)
508
509/* Initial permutation */
510#define IP(L, R) (\
511 bitswap(R, L, 4, 0x0F0F0F0F), \
512 bitswap(R, L, 16, 0x0000FFFF), \
513 bitswap(L, R, 2, 0x33333333), \
514 bitswap(L, R, 8, 0x00FF00FF), \
515 bitswap(R, L, 1, 0x55555555))
516
517/* Final permutation */
518#define FP(L, R) (\
519 bitswap(R, L, 1, 0x55555555), \
520 bitswap(L, R, 8, 0x00FF00FF), \
521 bitswap(L, R, 2, 0x33333333), \
522 bitswap(R, L, 16, 0x0000FFFF), \
523 bitswap(R, L, 4, 0x0F0F0F0F))
524
32874aea 525void des_encipher(word32 * output, word32 L, word32 R, DESContext * sched)
526{
d1e726bc 527 word32 swap, s0246, s1357;
528
529 IP(L, R);
530
531 L = rotl(L, 1);
532 R = rotl(R, 1);
533
32874aea 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]);
d1e726bc 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
32874aea 554 swap = L;
555 L = R;
556 R = swap;
d1e726bc 557
558 FP(L, R);
559
560 output[0] = L;
561 output[1] = R;
562}
374330e2 563
32874aea 564void des_decipher(word32 * output, word32 L, word32 R, DESContext * sched)
565{
d1e726bc 566 word32 swap, s0246, s1357;
374330e2 567
d1e726bc 568 IP(L, R);
374330e2 569
d1e726bc 570 L = rotl(L, 1);
571 R = rotl(R, 1);
374330e2 572
d1e726bc 573 L ^= f(R, sched->k0246[15], sched->k1357[15]);
574 R ^= f(L, sched->k0246[14], sched->k1357[14]);
575 L ^= f(R, sched->k0246[13], sched->k1357[13]);
576 R ^= f(L, sched->k0246[12], sched->k1357[12]);
577 L ^= f(R, sched->k0246[11], sched->k1357[11]);
578 R ^= f(L, sched->k0246[10], sched->k1357[10]);
32874aea 579 L ^= f(R, sched->k0246[9], sched->k1357[9]);
580 R ^= f(L, sched->k0246[8], sched->k1357[8]);
581 L ^= f(R, sched->k0246[7], sched->k1357[7]);
582 R ^= f(L, sched->k0246[6], sched->k1357[6]);
583 L ^= f(R, sched->k0246[5], sched->k1357[5]);
584 R ^= f(L, sched->k0246[4], sched->k1357[4]);
585 L ^= f(R, sched->k0246[3], sched->k1357[3]);
586 R ^= f(L, sched->k0246[2], sched->k1357[2]);
587 L ^= f(R, sched->k0246[1], sched->k1357[1]);
588 R ^= f(L, sched->k0246[0], sched->k1357[0]);
d1e726bc 589
590 L = rotl(L, 31);
591 R = rotl(R, 31);
592
32874aea 593 swap = L;
594 L = R;
595 R = swap;
d1e726bc 596
597 FP(L, R);
598
599 output[0] = L;
600 output[1] = R;
374330e2 601}
602
d1e726bc 603#define GET_32BIT_MSB_FIRST(cp) \
604 (((unsigned long)(unsigned char)(cp)[3]) | \
605 ((unsigned long)(unsigned char)(cp)[2] << 8) | \
606 ((unsigned long)(unsigned char)(cp)[1] << 16) | \
607 ((unsigned long)(unsigned char)(cp)[0] << 24))
608
609#define PUT_32BIT_MSB_FIRST(cp, value) do { \
610 (cp)[3] = (value); \
611 (cp)[2] = (value) >> 8; \
612 (cp)[1] = (value) >> 16; \
613 (cp)[0] = (value) >> 24; } while (0)
614
615static void des_cbc_encrypt(unsigned char *dest, const unsigned char *src,
32874aea 616 unsigned int len, DESContext * sched)
617{
d1e726bc 618 word32 out[2], iv0, iv1;
619 unsigned int i;
620
621 assert((len & 7) == 0);
622
623 iv0 = sched->eiv0;
624 iv1 = sched->eiv1;
625 for (i = 0; i < len; i += 8) {
32874aea 626 iv0 ^= GET_32BIT_MSB_FIRST(src);
627 src += 4;
628 iv1 ^= GET_32BIT_MSB_FIRST(src);
629 src += 4;
630 des_encipher(out, iv0, iv1, sched);
631 iv0 = out[0];
632 iv1 = out[1];
633 PUT_32BIT_MSB_FIRST(dest, iv0);
634 dest += 4;
635 PUT_32BIT_MSB_FIRST(dest, iv1);
636 dest += 4;
374330e2 637 }
d1e726bc 638 sched->eiv0 = iv0;
639 sched->eiv1 = iv1;
374330e2 640}
641
d1e726bc 642static void des_cbc_decrypt(unsigned char *dest, const unsigned char *src,
32874aea 643 unsigned int len, DESContext * sched)
644{
d1e726bc 645 word32 out[2], iv0, iv1, xL, xR;
646 unsigned int i;
647
648 assert((len & 7) == 0);
649
650 iv0 = sched->div0;
651 iv1 = sched->div1;
652 for (i = 0; i < len; i += 8) {
32874aea 653 xL = GET_32BIT_MSB_FIRST(src);
654 src += 4;
655 xR = GET_32BIT_MSB_FIRST(src);
656 src += 4;
657 des_decipher(out, xL, xR, sched);
658 iv0 ^= out[0];
659 iv1 ^= out[1];
660 PUT_32BIT_MSB_FIRST(dest, iv0);
661 dest += 4;
662 PUT_32BIT_MSB_FIRST(dest, iv1);
663 dest += 4;
664 iv0 = xL;
665 iv1 = xR;
374330e2 666 }
d1e726bc 667 sched->div0 = iv0;
668 sched->div1 = iv1;
374330e2 669}
670
d1e726bc 671static void des_3cbc_encrypt(unsigned char *dest, const unsigned char *src,
32874aea 672 unsigned int len, DESContext * scheds)
673{
d1e726bc 674 des_cbc_encrypt(dest, src, len, &scheds[0]);
675 des_cbc_decrypt(dest, src, len, &scheds[1]);
676 des_cbc_encrypt(dest, src, len, &scheds[2]);
374330e2 677}
678
033b4cef 679static void des_cbc3_encrypt(unsigned char *dest, const unsigned char *src,
32874aea 680 unsigned int len, DESContext * scheds)
681{
033b4cef 682 word32 out[2], iv0, iv1;
683 unsigned int i;
684
685 assert((len & 7) == 0);
686
687 iv0 = scheds->eiv0;
688 iv1 = scheds->eiv1;
689 for (i = 0; i < len; i += 8) {
32874aea 690 iv0 ^= GET_32BIT_MSB_FIRST(src);
691 src += 4;
692 iv1 ^= GET_32BIT_MSB_FIRST(src);
693 src += 4;
694 des_encipher(out, iv0, iv1, &scheds[0]);
695 des_decipher(out, out[0], out[1], &scheds[1]);
696 des_encipher(out, out[0], out[1], &scheds[2]);
697 iv0 = out[0];
698 iv1 = out[1];
699 PUT_32BIT_MSB_FIRST(dest, iv0);
700 dest += 4;
701 PUT_32BIT_MSB_FIRST(dest, iv1);
702 dest += 4;
033b4cef 703 }
704 scheds->eiv0 = iv0;
705 scheds->eiv1 = iv1;
706}
707
d1e726bc 708static void des_3cbc_decrypt(unsigned char *dest, const unsigned char *src,
32874aea 709 unsigned int len, DESContext * scheds)
710{
d1e726bc 711 des_cbc_decrypt(dest, src, len, &scheds[2]);
712 des_cbc_encrypt(dest, src, len, &scheds[1]);
713 des_cbc_decrypt(dest, src, len, &scheds[0]);
374330e2 714}
715
033b4cef 716static void des_cbc3_decrypt(unsigned char *dest, const unsigned char *src,
32874aea 717 unsigned int len, DESContext * scheds)
718{
033b4cef 719 word32 out[2], iv0, iv1, xL, xR;
720 unsigned int i;
721
722 assert((len & 7) == 0);
723
724 iv0 = scheds->div0;
725 iv1 = scheds->div1;
726 for (i = 0; i < len; i += 8) {
32874aea 727 xL = GET_32BIT_MSB_FIRST(src);
728 src += 4;
729 xR = GET_32BIT_MSB_FIRST(src);
730 src += 4;
731 des_decipher(out, xL, xR, &scheds[2]);
732 des_encipher(out, out[0], out[1], &scheds[1]);
733 des_decipher(out, out[0], out[1], &scheds[0]);
734 iv0 ^= out[0];
735 iv1 ^= out[1];
736 PUT_32BIT_MSB_FIRST(dest, iv0);
737 dest += 4;
738 PUT_32BIT_MSB_FIRST(dest, iv1);
739 dest += 4;
740 iv0 = xL;
741 iv1 = xR;
033b4cef 742 }
743 scheds->div0 = iv0;
744 scheds->div1 = iv1;
745}
746
d39f364a 747static DESContext cskeys[3], sckeys[3];
374330e2 748
32874aea 749static void des3_cskey(unsigned char *key)
750{
d1e726bc 751 des_key_setup(GET_32BIT_MSB_FIRST(key),
32874aea 752 GET_32BIT_MSB_FIRST(key + 4), &cskeys[0]);
753 des_key_setup(GET_32BIT_MSB_FIRST(key + 8),
754 GET_32BIT_MSB_FIRST(key + 12), &cskeys[1]);
755 des_key_setup(GET_32BIT_MSB_FIRST(key + 16),
756 GET_32BIT_MSB_FIRST(key + 20), &cskeys[2]);
d39f364a 757 logevent("Initialised triple-DES client->server encryption");
758}
759
0d7c43a6 760static void des_cskey(unsigned char *key)
761{
762 des_key_setup(GET_32BIT_MSB_FIRST(key),
763 GET_32BIT_MSB_FIRST(key + 4), &cskeys[0]);
764 logevent("Initialised single-DES client->server encryption");
765}
766
32874aea 767static void des3_csiv(unsigned char *key)
768{
d39f364a 769 cskeys[0].eiv0 = GET_32BIT_MSB_FIRST(key);
32874aea 770 cskeys[0].eiv1 = GET_32BIT_MSB_FIRST(key + 4);
d39f364a 771}
772
32874aea 773static void des3_sciv(unsigned char *key)
774{
d39f364a 775 sckeys[0].div0 = GET_32BIT_MSB_FIRST(key);
32874aea 776 sckeys[0].div1 = GET_32BIT_MSB_FIRST(key + 4);
d39f364a 777}
778
32874aea 779static void des3_sckey(unsigned char *key)
780{
d39f364a 781 des_key_setup(GET_32BIT_MSB_FIRST(key),
32874aea 782 GET_32BIT_MSB_FIRST(key + 4), &sckeys[0]);
783 des_key_setup(GET_32BIT_MSB_FIRST(key + 8),
784 GET_32BIT_MSB_FIRST(key + 12), &sckeys[1]);
785 des_key_setup(GET_32BIT_MSB_FIRST(key + 16),
786 GET_32BIT_MSB_FIRST(key + 20), &sckeys[2]);
d39f364a 787 logevent("Initialised triple-DES server->client encryption");
788}
789
0d7c43a6 790static void des_sckey(unsigned char *key)
791{
792 des_key_setup(GET_32BIT_MSB_FIRST(key),
793 GET_32BIT_MSB_FIRST(key + 4), &sckeys[0]);
794 logevent("Initialised single-DES server->client encryption");
795}
796
32874aea 797static void des3_sesskey(unsigned char *key)
798{
d39f364a 799 des3_cskey(key);
800 des3_sckey(key);
374330e2 801}
802
32874aea 803static void des3_encrypt_blk(unsigned char *blk, int len)
804{
d39f364a 805 des_3cbc_encrypt(blk, blk, len, cskeys);
374330e2 806}
807
32874aea 808static void des3_decrypt_blk(unsigned char *blk, int len)
809{
d39f364a 810 des_3cbc_decrypt(blk, blk, len, sckeys);
374330e2 811}
812
32874aea 813static void des3_ssh2_encrypt_blk(unsigned char *blk, int len)
814{
033b4cef 815 des_cbc3_encrypt(blk, blk, len, cskeys);
816}
817
32874aea 818static void des3_ssh2_decrypt_blk(unsigned char *blk, int len)
819{
033b4cef 820 des_cbc3_decrypt(blk, blk, len, sckeys);
821}
822
0d7c43a6 823static void des_ssh2_encrypt_blk(unsigned char *blk, int len)
824{
825 des_cbc_encrypt(blk, blk, len, cskeys);
826}
827
828static void des_ssh2_decrypt_blk(unsigned char *blk, int len)
829{
830 des_cbc_decrypt(blk, blk, len, sckeys);
831}
832
32874aea 833void des3_decrypt_pubkey(unsigned char *key, unsigned char *blk, int len)
834{
7cca0d81 835 DESContext ourkeys[3];
836 des_key_setup(GET_32BIT_MSB_FIRST(key),
32874aea 837 GET_32BIT_MSB_FIRST(key + 4), &ourkeys[0]);
838 des_key_setup(GET_32BIT_MSB_FIRST(key + 8),
839 GET_32BIT_MSB_FIRST(key + 12), &ourkeys[1]);
7cca0d81 840 des_key_setup(GET_32BIT_MSB_FIRST(key),
32874aea 841 GET_32BIT_MSB_FIRST(key + 4), &ourkeys[2]);
7cca0d81 842 des_3cbc_decrypt(blk, blk, len, ourkeys);
ee5c1422 843 memset(ourkeys, 0, sizeof(ourkeys));
7cca0d81 844}
845
32874aea 846void des3_encrypt_pubkey(unsigned char *key, unsigned char *blk, int len)
847{
6e522441 848 DESContext ourkeys[3];
849 des_key_setup(GET_32BIT_MSB_FIRST(key),
32874aea 850 GET_32BIT_MSB_FIRST(key + 4), &ourkeys[0]);
851 des_key_setup(GET_32BIT_MSB_FIRST(key + 8),
852 GET_32BIT_MSB_FIRST(key + 12), &ourkeys[1]);
6e522441 853 des_key_setup(GET_32BIT_MSB_FIRST(key),
32874aea 854 GET_32BIT_MSB_FIRST(key + 4), &ourkeys[2]);
6e522441 855 des_3cbc_encrypt(blk, blk, len, ourkeys);
ee5c1422 856 memset(ourkeys, 0, sizeof(ourkeys));
6e522441 857}
858
9dda6459 859void des3_decrypt_pubkey_ossh(unsigned char *key, unsigned char *iv,
860 unsigned char *blk, int len)
861{
862 DESContext ourkeys[3];
863 des_key_setup(GET_32BIT_MSB_FIRST(key),
864 GET_32BIT_MSB_FIRST(key + 4), &ourkeys[0]);
865 des_key_setup(GET_32BIT_MSB_FIRST(key + 8),
866 GET_32BIT_MSB_FIRST(key + 12), &ourkeys[1]);
867 des_key_setup(GET_32BIT_MSB_FIRST(key + 16),
868 GET_32BIT_MSB_FIRST(key + 20), &ourkeys[2]);
869 ourkeys[0].div0 = GET_32BIT_MSB_FIRST(iv);
870 ourkeys[0].div1 = GET_32BIT_MSB_FIRST(iv+4);
871 des_cbc3_decrypt(blk, blk, len, ourkeys);
ee5c1422 872 memset(ourkeys, 0, sizeof(ourkeys));
9dda6459 873}
874
875void des3_encrypt_pubkey_ossh(unsigned char *key, unsigned char *iv,
876 unsigned char *blk, int len)
877{
878 DESContext ourkeys[3];
879 des_key_setup(GET_32BIT_MSB_FIRST(key),
880 GET_32BIT_MSB_FIRST(key + 4), &ourkeys[0]);
881 des_key_setup(GET_32BIT_MSB_FIRST(key + 8),
882 GET_32BIT_MSB_FIRST(key + 12), &ourkeys[1]);
883 des_key_setup(GET_32BIT_MSB_FIRST(key + 16),
884 GET_32BIT_MSB_FIRST(key + 20), &ourkeys[2]);
885 ourkeys[0].eiv0 = GET_32BIT_MSB_FIRST(iv);
886 ourkeys[0].eiv1 = GET_32BIT_MSB_FIRST(iv+4);
887 des_cbc3_encrypt(blk, blk, len, ourkeys);
ee5c1422 888 memset(ourkeys, 0, sizeof(ourkeys));
9dda6459 889}
890
65a22376 891static const struct ssh2_cipher ssh_3des_ssh2 = {
d39f364a 892 des3_csiv, des3_cskey,
893 des3_sciv, des3_sckey,
033b4cef 894 des3_ssh2_encrypt_blk,
895 des3_ssh2_decrypt_blk,
896 "3des-cbc",
d2a0e0be 897 8, 168
033b4cef 898};
899
0d7c43a6 900/*
901 * Single DES in ssh2. It isn't clear that "des-cbc" is an official
902 * cipher name, but ssh.com support it and apparently aren't the
903 * only people to do so, so we sigh and implement it anyway.
904 */
905static const struct ssh2_cipher ssh_des_ssh2 = {
906 des3_csiv, des_cskey, /* iv functions shared with 3des */
907 des3_sciv, des_sckey,
908 des_ssh2_encrypt_blk,
909 des_ssh2_decrypt_blk,
910 "des-cbc",
911 8, 56
912};
913
65a22376 914static const struct ssh2_cipher *const des3_list[] = {
0a3f1d48 915 &ssh_3des_ssh2
916};
917
65a22376 918const struct ssh2_ciphers ssh2_3des = {
0a3f1d48 919 sizeof(des3_list) / sizeof(*des3_list),
920 des3_list
921};
922
0d7c43a6 923static const struct ssh2_cipher *const des_list[] = {
924 &ssh_des_ssh2
925};
926
927const struct ssh2_ciphers ssh2_des = {
928 sizeof(des3_list) / sizeof(*des_list),
929 des_list
930};
931
65a22376 932const struct ssh_cipher ssh_3des = {
033b4cef 933 des3_sesskey,
374330e2 934 des3_encrypt_blk,
e5574168 935 des3_decrypt_blk,
0a3f1d48 936 8
374330e2 937};
938
32874aea 939static void des_sesskey(unsigned char *key)
940{
0d7c43a6 941 des_cskey(key);
942 des_sckey(key);
9697bfd2 943}
944
32874aea 945static void des_encrypt_blk(unsigned char *blk, int len)
946{
d39f364a 947 des_cbc_encrypt(blk, blk, len, cskeys);
9697bfd2 948}
949
32874aea 950static void des_decrypt_blk(unsigned char *blk, int len)
951{
d39f364a 952 des_cbc_decrypt(blk, blk, len, cskeys);
9697bfd2 953}
954
65a22376 955const struct ssh_cipher ssh_des = {
9697bfd2 956 des_sesskey,
957 des_encrypt_blk,
e5574168 958 des_decrypt_blk,
0a3f1d48 959 8
9697bfd2 960};
Local modifications for Simon Tatham's `PuTTY' SSH client and terminal emulator