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