sshdes.c

   1 #include <assert.h>
   2 #include "ssh.h"
   3
   4
   5 /* des.c - implementation of DES
   6  */
   7
   8 /*
   9  * Description of DES
  10  * ------------------
  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
 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
 279 typedef struct {
 280     word32 k0246[16], k1357[16];
 281     word32 eiv0, eiv1;
 282     word32 div0, div1;
 283 } DESContext;
 284
 285 #define rotl(x, c) ( (x << c) | (x >> (32-c)) )
 286 #define rotl28(x, c) ( ( (x << c) | (x >> (28-c)) ) & 0x0FFFFFFF)
 287
 288 static 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 }
 298
 299 void 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     };
 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      */
 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     }
 345
 346     sched->eiv0 = sched->eiv1 = 0;
 347     sched->div0 = sched->div1 = 0;       /* for good measure */
 348 }
 349
 350 static 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 };
 487
 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
 522 void 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 }
 557
 558 void des_decipher(word32 *output, word32 L, word32 R, DESContext *sched) {
 559     word32 swap, s0246, s1357;
 560
 561     IP(L, R);
 562
 563     L = rotl(L, 1);
 564     R = rotl(R, 1);
 565
 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;
 592 }
 593
 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
 606 static 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;
 623     }
 624     sched->eiv0 = iv0;
 625     sched->eiv1 = iv1;
 626 }
 627
 628 static 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;
 647     }
 648     sched->div0 = iv0;
 649     sched->div1 = iv1;
 650 }
 651
 652 static 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]);
 657 }
 658
 659 static 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
 683 static 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]);
 688 }
 689
 690 static 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
 716 static DESContext cskeys[3], sckeys[3];
 717
 718 static void des3_cskey(unsigned char *key) {
 719     des_key_setup(GET_32BIT_MSB_FIRST(key),
 720                   GET_32BIT_MSB_FIRST(key+4), &cskeys[0]);
 721     des_key_setup(GET_32BIT_MSB_FIRST(key+8),
 722                   GET_32BIT_MSB_FIRST(key+12), &cskeys[1]);
 723     des_key_setup(GET_32BIT_MSB_FIRST(key+16),
 724                   GET_32BIT_MSB_FIRST(key+20), &cskeys[2]);
 725     logevent("Initialised triple-DES client->server encryption");
 726 }
 727
 728 static 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
 733 static 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
 738 static 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
 748 static void des3_sesskey(unsigned char *key) {
 749     des3_cskey(key);
 750     des3_sckey(key);
 751 }
 752
 753 static void des3_encrypt_blk(unsigned char *blk, int len) {
 754     des_3cbc_encrypt(blk, blk, len, cskeys);
 755 }
 756
 757 static void des3_decrypt_blk(unsigned char *blk, int len) {
 758     des_3cbc_decrypt(blk, blk, len, sckeys);
 759 }
 760
 761 static void des3_ssh2_encrypt_blk(unsigned char *blk, int len) {
 762     des_cbc3_encrypt(blk, blk, len, cskeys);
 763 }
 764
 765 static void des3_ssh2_decrypt_blk(unsigned char *blk, int len) {
 766     des_cbc3_decrypt(blk, blk, len, sckeys);
 767 }
 768
 769 void 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
 781 void 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
 793 static const struct ssh2_cipher ssh_3des_ssh2 = {
 794     des3_csiv, des3_cskey,
 795     des3_sciv, des3_sckey,
 796     des3_ssh2_encrypt_blk,
 797     des3_ssh2_decrypt_blk,
 798     "3des-cbc",
 799     8, 168
 800 };
 801
 802 static const struct ssh2_cipher *const des3_list[] = {
 803     &ssh_3des_ssh2
 804 };
 805
 806 const struct ssh2_ciphers ssh2_3des = {
 807     sizeof(des3_list) / sizeof(*des3_list),
 808     des3_list
 809 };
 810
 811 const struct ssh_cipher ssh_3des = {
 812     des3_sesskey,
 813     des3_encrypt_blk,
 814     des3_decrypt_blk,
 815     8
 816 };
 817
 818 static void des_sesskey(unsigned char *key) {
 819     des_key_setup(GET_32BIT_MSB_FIRST(key),
 820                   GET_32BIT_MSB_FIRST(key+4), &cskeys[0]);
 821     logevent("Initialised single-DES encryption");
 822 }
 823
 824 static void des_encrypt_blk(unsigned char *blk, int len) {
 825     des_cbc_encrypt(blk, blk, len, cskeys);
 826 }
 827
 828 static void des_decrypt_blk(unsigned char *blk, int len) {
 829     des_cbc_decrypt(blk, blk, len, cskeys);
 830 }
 831
 832 const struct ssh_cipher ssh_des = {
 833     des_sesskey,
 834     des_encrypt_blk,
 835     des_decrypt_blk,
 836     8
 837 };