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