sshdes.c

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