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 };