syslinux/menu/libmenu/des.c

   1 /*
   2  * FreeSec: libcrypt for NetBSD
   3  *
   4  * Copyright (c) 1994 David Burren
   5  * All rights reserved.
   6  *
   7  * Adapted for FreeBSD-2.0 by Geoffrey M. Rehmet
   8  *      this file should now *only* export crypt(), in order to make
   9  *      binaries of libcrypt exportable from the USA
  10  *
  11  * Adapted for FreeBSD-4.0 by Mark R V Murray
  12  *      this file should now *only* export crypt_des(), in order to make
  13  *      a module that can be optionally included in libcrypt.
  14  *
  15  * Adapted for pxelinux menu environment by Th.Gebhardt
  16  *      removed dependencies of standard C libs
  17  *      added LOWSPACE option (using common space for different arrays)
  18  *
  19  * Redistribution and use in source and binary forms, with or without
  20  * modification, are permitted provided that the following conditions
  21  * are met:
  22  * 1. Redistributions of source code must retain the above copyright
  23  *    notice, this list of conditions and the following disclaimer.
  24  * 2. Redistributions in binary form must reproduce the above copyright
  25  *    notice, this list of conditions and the following disclaimer in the
  26  *    documentation and/or other materials provided with the distribution.
  27  * 3. Neither the name of the author nor the names of other contributors
  28  *    may be used to endorse or promote products derived from this software
  29  *    without specific prior written permission.
  30  *
  31  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  32  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  33  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  34  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  35  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  36  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  37  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  38  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  39  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  40  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  41  * SUCH DAMAGE.
  42  *
  43  * This is an original implementation of the DES and the crypt(3) interfaces
  44  * by David Burren <davidb@werj.com.au>.
  45  *
  46  * An excellent reference on the underlying algorithm (and related
  47  * algorithms) is:
  48  *
  49  *      B. Schneier, Applied Cryptography: protocols, algorithms,
  50  *      and source code in C, John Wiley & Sons, 1994.
  51  *
  52  * Note that in that book's description of DES the lookups for the initial,
  53  * pbox, and final permutations are inverted (this has been brought to the
  54  * attention of the author).  A list of errata for this book has been
  55  * posted to the sci.crypt newsgroup by the author and is available for FTP.
  56  *
  57  * ARCHITECTURE ASSUMPTIONS:
  58  *      It is assumed that the 8-byte arrays passed by reference can be
  59  *      addressed as arrays of u_int32_t's (ie. the CPU is not picky about
  60  *      alignment).
  61  */
  62
  63
  64 #define LOWSPACE
  65
  66 #ifndef NULL
  67 #define NULL ((void *) 0)
  68 #endif
  69
  70 typedef unsigned long my_u_int32_t;
  71 typedef unsigned char my_u_char_t;
  72
  73 /* Re-entrantify me -- all this junk needs to be in
  74  * struct crypt_data to make this really reentrant... */
  75 static my_u_char_t      inv_key_perm[64];
  76 static my_u_char_t      inv_comp_perm[56];
  77 static my_u_char_t      u_sbox[8][64];
  78 static my_u_char_t      un_pbox[32];
  79 static my_u_int32_t en_keysl[16], en_keysr[16];
  80 static my_u_int32_t de_keysl[16], de_keysr[16];
  81
  82 #ifndef LOWSPACE
  83 static my_u_int32_t ip_maskl[8][256], ip_maskr[8][256];
  84 static my_u_int32_t fp_maskl[8][256], fp_maskr[8][256];
  85 static my_u_int32_t key_perm_maskl[8][128], key_perm_maskr[8][128];
  86 static my_u_int32_t comp_maskl[8][128], comp_maskr[8][128];
  87 #endif
  88
  89 static my_u_int32_t saltbits;
  90 static my_u_int32_t old_salt;
  91 static my_u_int32_t old_rawkey0, old_rawkey1;
  92
  93 #ifdef LOWSPACE
  94 static my_u_int32_t common[8][256];
  95 #endif
  96
  97 /* Static stuff that stays resident and doesn't change after
  98  * being initialized, and therefore doesn't need to be made
  99  * reentrant. */
 100 static my_u_char_t      init_perm[64], final_perm[64];
 101 static my_u_char_t      m_sbox[4][4096];
 102
 103 #ifndef LOWSPACE
 104 static my_u_int32_t psbox[4][256];
 105 #endif
 106
 107 /* A pile of data */
 108 static const my_u_char_t        ascii64[] = "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
 109
 110 static const my_u_char_t        IP[64] = {
 111         58, 50, 42, 34, 26, 18, 10,  2, 60, 52, 44, 36, 28, 20, 12,  4,
 112         62, 54, 46, 38, 30, 22, 14,  6, 64, 56, 48, 40, 32, 24, 16,  8,
 113         57, 49, 41, 33, 25, 17,  9,  1, 59, 51, 43, 35, 27, 19, 11,  3,
 114         61, 53, 45, 37, 29, 21, 13,  5, 63, 55, 47, 39, 31, 23, 15,  7
 115 };
 116
 117 static const my_u_char_t        key_perm[56] = {
 118         57, 49, 41, 33, 25, 17,  9,  1, 58, 50, 42, 34, 26, 18,
 119         10,  2, 59, 51, 43, 35, 27, 19, 11,  3, 60, 52, 44, 36,
 120         63, 55, 47, 39, 31, 23, 15,  7, 62, 54, 46, 38, 30, 22,
 121         14,  6, 61, 53, 45, 37, 29, 21, 13,  5, 28, 20, 12,  4
 122 };
 123
 124 static const my_u_char_t        key_shifts[16] = {
 125         1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
 126 };
 127
 128 static const my_u_char_t        comp_perm[48] = {
 129         14, 17, 11, 24,  1,  5,  3, 28, 15,  6, 21, 10,
 130         23, 19, 12,  4, 26,  8, 16,  7, 27, 20, 13,  2,
 131         41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
 132         44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
 133 };
 134
 135 /*
 136  *      No E box is used, as it's replaced by some ANDs, shifts, and ORs.
 137  */
 138
 139 static const my_u_char_t        sbox[8][64] = {
 140         {
 141                 14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
 142                  0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
 143                  4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
 144                 15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13
 145         },
 146         {
 147                 15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
 148                  3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
 149                  0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
 150                 13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9
 151         },
 152         {
 153                 10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
 154                 13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
 155                 13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
 156                  1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12
 157         },
 158         {
 159                  7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
 160                 13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
 161                 10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
 162                  3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14
 163         },
 164         {
 165                  2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
 166                 14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
 167                  4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
 168                 11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3
 169         },
 170         {
 171                 12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
 172                 10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
 173                  9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
 174                  4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13
 175         },
 176         {
 177                  4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
 178                 13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
 179                  1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
 180                  6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12
 181         },
 182         {
 183                 13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
 184                  1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
 185                  7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
 186                  2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
 187         }
 188 };
 189
 190 static const my_u_char_t        pbox[32] = {
 191         16,  7, 20, 21, 29, 12, 28, 17,  1, 15, 23, 26,  5, 18, 31, 10,
 192          2,  8, 24, 14, 32, 27,  3,  9, 19, 13, 30,  6, 22, 11,  4, 25
 193 };
 194
 195 static const my_u_int32_t bits32[32] =
 196 {
 197         0x80000000, 0x40000000, 0x20000000, 0x10000000,
 198         0x08000000, 0x04000000, 0x02000000, 0x01000000,
 199         0x00800000, 0x00400000, 0x00200000, 0x00100000,
 200         0x00080000, 0x00040000, 0x00020000, 0x00010000,
 201         0x00008000, 0x00004000, 0x00002000, 0x00001000,
 202         0x00000800, 0x00000400, 0x00000200, 0x00000100,
 203         0x00000080, 0x00000040, 0x00000020, 0x00000010,
 204         0x00000008, 0x00000004, 0x00000002, 0x00000001
 205 };
 206
 207 static const my_u_int32_t bits28[28] =
 208 {
 209         0x08000000, 0x04000000, 0x02000000, 0x01000000,
 210         0x00800000, 0x00400000, 0x00200000, 0x00100000,
 211         0x00080000, 0x00040000, 0x00020000, 0x00010000,
 212         0x00008000, 0x00004000, 0x00002000, 0x00001000,
 213         0x00000800, 0x00000400, 0x00000200, 0x00000100,
 214         0x00000080, 0x00000040, 0x00000020, 0x00000010,
 215         0x00000008, 0x00000004, 0x00000002, 0x00000001
 216 };
 217
 218 static const my_u_int32_t bits24[24] =
 219 {
 220         0x00800000, 0x00400000, 0x00200000, 0x00100000,
 221         0x00080000, 0x00040000, 0x00020000, 0x00010000,
 222         0x00008000, 0x00004000, 0x00002000, 0x00001000,
 223         0x00000800, 0x00000400, 0x00000200, 0x00000100,
 224         0x00000080, 0x00000040, 0x00000020, 0x00000010,
 225         0x00000008, 0x00000004, 0x00000002, 0x00000001
 226 };
 227
 228 static const my_u_char_t        bits8[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
 229 // static const my_u_int32_t *bits28, *bits24;
 230
 231
 232 static int
 233 ascii_to_bin(char ch)
 234 {
 235         if (ch > 'z')
 236                 return(0);
 237         if (ch >= 'a')
 238                 return(ch - 'a' + 38);
 239         if (ch > 'Z')
 240                 return(0);
 241         if (ch >= 'A')
 242                 return(ch - 'A' + 12);
 243         if (ch > '9')
 244                 return(0);
 245         if (ch >= '.')
 246                 return(ch - '.');
 247         return(0);
 248 }
 249
 250 static void
 251 des_init(void)
 252 {
 253
 254 #ifdef LOWSPACE
 255         int     i, j, b;
 256 #else
 257         int     i, j, b, k, inbit, obit;
 258         my_u_int32_t    *p, *il, *ir, *fl, *fr;
 259 #endif
 260         static int des_initialised = 0;
 261
 262         if (des_initialised==1)
 263             return;
 264
 265         old_rawkey0 = old_rawkey1 = 0L;
 266         saltbits = 0L;
 267         old_salt = 0L;
 268         //      bits24 = (bits28 = bits32 + 4) + 4;
 269
 270         /*
 271          * Invert the S-boxes, reordering the input bits.
 272          */
 273         for (i = 0; i < 8; i++)
 274                 for (j = 0; j < 64; j++) {
 275                         b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
 276                         u_sbox[i][j] = sbox[i][b];
 277                 }
 278
 279         /*
 280          * Convert the inverted S-boxes into 4 arrays of 8 bits.
 281          * Each will handle 12 bits of the S-box input.
 282          */
 283         for (b = 0; b < 4; b++)
 284                 for (i = 0; i < 64; i++)
 285                         for (j = 0; j < 64; j++)
 286                                 m_sbox[b][(i << 6) | j] =
 287                                         (my_u_char_t)((u_sbox[(b << 1)][i] << 4) |
 288                                         u_sbox[(b << 1) + 1][j]);
 289
 290         /*
 291          * Set up the initial & final permutations into a useful form, and
 292          * initialise the inverted key permutation.
 293          */
 294         for (i = 0; i < 64; i++) {
 295                 init_perm[final_perm[i] = IP[i] - 1] = (my_u_char_t)i;
 296                 inv_key_perm[i] = 255;
 297         }
 298
 299         /*
 300          * Invert the key permutation and initialise the inverted key
 301          * compression permutation.
 302          */
 303         for (i = 0; i < 56; i++) {
 304                 inv_key_perm[key_perm[i] - 1] = (my_u_char_t)i;
 305                 inv_comp_perm[i] = 255;
 306         }
 307
 308         /*
 309          * Invert the key compression permutation.
 310          */
 311         for (i = 0; i < 48; i++) {
 312                 inv_comp_perm[comp_perm[i] - 1] = (my_u_char_t)i;
 313         }
 314
 315         /*
 316          * Set up the OR-mask arrays for the initial and final permutations,
 317          * and for the key initial and compression permutations.
 318          */
 319
 320 #ifndef LOWSPACE
 321         for (k = 0; k < 8; k++) {
 322                 for (i = 0; i < 256; i++) {
 323                         *(il = &ip_maskl[k][i]) = 0L;
 324                         *(ir = &ip_maskr[k][i]) = 0L;
 325                         *(fl = &fp_maskl[k][i]) = 0L;
 326                         *(fr = &fp_maskr[k][i]) = 0L;
 327                         for (j = 0; j < 8; j++) {
 328                                 inbit = 8 * k + j;
 329                                 if (i & bits8[j]) {
 330                                         if ((obit = init_perm[inbit]) < 32)
 331                                                 *il |= bits32[obit];
 332                                         else
 333                                                 *ir |= bits32[obit-32];
 334                                         if ((obit = final_perm[inbit]) < 32)
 335                                                 *fl |= bits32[obit];
 336                                         else
 337                                                 *fr |= bits32[obit - 32];
 338                                 }
 339                         }
 340                 }
 341                 for (i = 0; i < 128; i++) {
 342                         *(il = &key_perm_maskl[k][i]) = 0L;
 343                         *(ir = &key_perm_maskr[k][i]) = 0L;
 344                         for (j = 0; j < 7; j++) {
 345                                 inbit = 8 * k + j;
 346                                 if (i & bits8[j + 1]) {
 347                                         if ((obit = inv_key_perm[inbit]) == 255)
 348                                                 continue;
 349                                         if (obit < 28)
 350                                                 *il |= bits28[obit];
 351                                         else
 352                                                 *ir |= bits28[obit - 28];
 353                                 }
 354                         }
 355                         *(il = &comp_maskl[k][i]) = 0L;
 356                         *(ir = &comp_maskr[k][i]) = 0L;
 357                         for (j = 0; j < 7; j++) {
 358                                 inbit = 7 * k + j;
 359                                 if (i & bits8[j + 1]) {
 360                                         if ((obit=inv_comp_perm[inbit]) == 255)
 361                                                 continue;
 362                                         if (obit < 24)
 363                                                 *il |= bits24[obit];
 364                                         else
 365                                                 *ir |= bits24[obit - 24];
 366                                 }
 367                         }
 368                 }
 369         }
 370 #endif
 371
 372         /*
 373          * Invert the P-box permutation, and convert into OR-masks for
 374          * handling the output of the S-box arrays setup above.
 375          */
 376         for (i = 0; i < 32; i++)
 377                 un_pbox[pbox[i] - 1] = (my_u_char_t)i;
 378
 379 #ifndef LOWSPACE
 380         for (b = 0; b < 4; b++)
 381                 for (i = 0; i < 256; i++) {
 382                         *(p = &psbox[b][i]) = 0L;
 383                         for (j = 0; j < 8; j++) {
 384                                 if (i & bits8[j])
 385                                         *p |= bits32[un_pbox[8 * b + j]];
 386                         }
 387                 }
 388 #endif
 389         des_initialised = 1;
 390 }
 391
 392
 393 #ifdef LOWSPACE
 394
 395 static void
 396 setup_ip_maskl(void)
 397 {
 398   int           i, j, k, inbit, obit;
 399   my_u_int32_t  *il;
 400
 401   for (k = 0; k < 8; k++) {
 402     for (i = 0; i < 256; i++) {
 403       *(il = &common[k][i]) = 0L;
 404       for (j = 0; j < 8; j++) {
 405         inbit = 8 * k + j;
 406         if (i & bits8[j]) {
 407           if ((obit = init_perm[inbit]) < 32)
 408             *il |= bits32[obit];
 409         }
 410       }
 411     }
 412   }
 413 }
 414
 415 static void
 416 setup_ip_maskr(void)
 417 {
 418   int           i, j, k, inbit, obit;
 419   my_u_int32_t  *ir;
 420
 421   for (k = 0; k < 8; k++) {
 422     for (i = 0; i < 256; i++) {
 423       *(ir = &common[k][i]) = 0L;
 424       for (j = 0; j < 8; j++) {
 425         inbit = 8 * k + j;
 426         if (i & bits8[j]) {
 427           if ((obit = init_perm[inbit]) >= 32)
 428             *ir |= bits32[obit-32];
 429         }
 430       }
 431     }
 432   }
 433 }
 434
 435 static void
 436 setup_fp_maskl(void)
 437 {
 438   int           i, j, k, inbit, obit;
 439   my_u_int32_t  *fl;
 440
 441   for (k = 0; k < 8; k++) {
 442     for (i = 0; i < 256; i++) {
 443       *(fl = &common[k][i]) = 0L;
 444       for (j = 0; j < 8; j++) {
 445         inbit = 8 * k + j;
 446         if (i & bits8[j]) {
 447           if ((obit = final_perm[inbit]) < 32)
 448             *fl |= bits32[obit];
 449         }
 450       }
 451     }
 452   }
 453 }
 454
 455 static void
 456 setup_fp_maskr(void)
 457 {
 458   int           i, j, k, inbit, obit;
 459   my_u_int32_t  *fr;
 460
 461   for (k = 0; k < 8; k++) {
 462     for (i = 0; i < 256; i++) {
 463       *(fr = &common[k][i]) = 0L;
 464       for (j = 0; j < 8; j++) {
 465         inbit = 8 * k + j;
 466         if (i & bits8[j]) {
 467           if ((obit = final_perm[inbit]) >= 32)
 468             *fr |= bits32[obit - 32];
 469         }
 470       }
 471     }
 472   }
 473 }
 474
 475 static void
 476 setup_key_perm_maskl(void)
 477 {
 478   int           i, j, k, inbit, obit;
 479   my_u_int32_t  *il;
 480
 481   for (k = 0; k < 8; k++) {
 482     for (i = 0; i < 128; i++) {
 483       *(il = &common[k][i]) = 0L;
 484       for (j = 0; j < 7; j++) {
 485         inbit = 8 * k + j;
 486         if (i & bits8[j + 1]) {
 487           if ((obit = inv_key_perm[inbit]) == 255)
 488             continue;
 489           if (obit < 28)
 490             *il |= bits28[obit];
 491         }
 492       }
 493     }
 494   }
 495 }
 496
 497 static void
 498 setup_key_perm_maskr(void)
 499 {
 500   int           i, j, k, inbit, obit;
 501   my_u_int32_t  *ir;
 502
 503   for (k = 0; k < 8; k++) {
 504     for (i = 0; i < 128; i++) {
 505       *(ir = &common[k][i]) = 0L;
 506       for (j = 0; j < 7; j++) {
 507         inbit = 8 * k + j;
 508         if (i & bits8[j + 1]) {
 509           if ((obit = inv_key_perm[inbit]) == 255)
 510             continue;
 511           if (obit >= 28)
 512             *ir |= bits28[obit - 28];
 513         }
 514       }
 515     }
 516   }
 517 }
 518
 519 static void
 520 setup_comp_maskl(void)
 521 {
 522   int           i, j, k, inbit, obit;
 523   my_u_int32_t  *il;
 524
 525   for (k = 0; k < 8; k++) {
 526     for (i = 0; i < 128; i++) {
 527       *(il = &common[k][i]) = 0L;
 528       for (j = 0; j < 7; j++) {
 529         inbit = 7 * k + j;
 530         if (i & bits8[j + 1]) {
 531           if ((obit=inv_comp_perm[inbit]) == 255)
 532             continue;
 533           if (obit < 24)
 534             *il |= bits24[obit];
 535         }
 536       }
 537     }
 538   }
 539 }
 540
 541 static void
 542 setup_comp_maskr(void)
 543 {
 544   int           i, j, k, inbit, obit;
 545   my_u_int32_t  *ir;
 546
 547   for (k = 0; k < 8; k++) {
 548     for (i = 0; i < 128; i++) {
 549       *(ir = &common[k][i]) = 0L;
 550       for (j = 0; j < 7; j++) {
 551         inbit = 7 * k + j;
 552         if (i & bits8[j + 1]) {
 553           if ((obit=inv_comp_perm[inbit]) == 255)
 554             continue;
 555           if (obit >= 24)
 556             *ir |= bits24[obit - 24];
 557         }
 558       }
 559     }
 560   }
 561 }
 562
 563 static void
 564 setup_psbox(void)
 565 {
 566   int           i, j, b;
 567   my_u_int32_t  *p;
 568
 569   for (b = 0; b < 4; b++)
 570     for (i = 0; i < 256; i++) {
 571       *(p = &common[b][i]) = 0L;
 572       for (j = 0; j < 8; j++) {
 573         if (i & bits8[j])
 574           *p |= bits32[un_pbox[8 * b + j]];
 575       }
 576     }
 577 }
 578
 579 #endif
 580
 581 static void
 582 setup_salt(my_u_int32_t salt)
 583 {
 584         my_u_int32_t    obit, saltbit;
 585         int     i;
 586
 587         if (salt == old_salt)
 588                 return;
 589         old_salt = salt;
 590
 591         saltbits = 0L;
 592         saltbit = 1;
 593         obit = 0x800000;
 594         for (i = 0; i < 24; i++) {
 595                 if (salt & saltbit)
 596                         saltbits |= obit;
 597                 saltbit <<= 1;
 598                 obit >>= 1;
 599         }
 600 }
 601
 602
 603 static my_u_int32_t char_to_int(const char *key)
 604 {
 605   my_u_int32_t byte0,byte1,byte2,byte3;
 606   byte0 = (my_u_int32_t) (my_u_char_t) key[0];
 607   byte1 = (my_u_int32_t) (my_u_char_t) key[1];
 608   byte2 = (my_u_int32_t) (my_u_char_t) key[2];
 609   byte3 = (my_u_int32_t) (my_u_char_t) key[3];
 610
 611   return byte0 << 24 |  byte1 << 16 | byte2 << 8 | byte3 ;
 612 }
 613
 614
 615 static int
 616 des_setkey(const char *key)
 617 {
 618         my_u_int32_t    k0, k1, rawkey0, rawkey1;
 619         int             shifts, round;
 620
 621         des_init();
 622
 623         /*  rawkey0 = ntohl(*(const my_u_int32_t *) key);
 624          *  rawkey1 = ntohl(*(const my_u_int32_t *) (key + 4));
 625          */
 626
 627         rawkey0 = char_to_int(key);
 628         rawkey1 = char_to_int(key+4);
 629
 630         if ((rawkey0 | rawkey1)
 631             && rawkey0 == old_rawkey0
 632             && rawkey1 == old_rawkey1) {
 633                 /*
 634                  * Already setup for this key.
 635                  * This optimisation fails on a zero key (which is weak and
 636                  * has bad parity anyway) in order to simplify the starting
 637                  * conditions.
 638                  */
 639                 return(0);
 640         }
 641         old_rawkey0 = rawkey0;
 642         old_rawkey1 = rawkey1;
 643
 644         /*
 645          *      Do key permutation and split into two 28-bit subkeys.
 646          */
 647
 648 #ifdef LOWSPACE
 649         setup_key_perm_maskl();
 650         k0 = common[0][rawkey0 >> 25]
 651            | common[1][(rawkey0 >> 17) & 0x7f]
 652            | common[2][(rawkey0 >> 9) & 0x7f]
 653            | common[3][(rawkey0 >> 1) & 0x7f]
 654            | common[4][rawkey1 >> 25]
 655            | common[5][(rawkey1 >> 17) & 0x7f]
 656            | common[6][(rawkey1 >> 9) & 0x7f]
 657            | common[7][(rawkey1 >> 1) & 0x7f];
 658         setup_key_perm_maskr();
 659         k1 = common[0][rawkey0 >> 25]
 660            | common[1][(rawkey0 >> 17) & 0x7f]
 661            | common[2][(rawkey0 >> 9) & 0x7f]
 662            | common[3][(rawkey0 >> 1) & 0x7f]
 663            | common[4][rawkey1 >> 25]
 664            | common[5][(rawkey1 >> 17) & 0x7f]
 665            | common[6][(rawkey1 >> 9) & 0x7f]
 666            | common[7][(rawkey1 >> 1) & 0x7f];
 667 #else
 668         k0 = key_perm_maskl[0][rawkey0 >> 25]
 669            | key_perm_maskl[1][(rawkey0 >> 17) & 0x7f]
 670            | key_perm_maskl[2][(rawkey0 >> 9) & 0x7f]
 671            | key_perm_maskl[3][(rawkey0 >> 1) & 0x7f]
 672            | key_perm_maskl[4][rawkey1 >> 25]
 673            | key_perm_maskl[5][(rawkey1 >> 17) & 0x7f]
 674            | key_perm_maskl[6][(rawkey1 >> 9) & 0x7f]
 675            | key_perm_maskl[7][(rawkey1 >> 1) & 0x7f];
 676         k1 = key_perm_maskr[0][rawkey0 >> 25]
 677            | key_perm_maskr[1][(rawkey0 >> 17) & 0x7f]
 678            | key_perm_maskr[2][(rawkey0 >> 9) & 0x7f]
 679            | key_perm_maskr[3][(rawkey0 >> 1) & 0x7f]
 680            | key_perm_maskr[4][rawkey1 >> 25]
 681            | key_perm_maskr[5][(rawkey1 >> 17) & 0x7f]
 682            | key_perm_maskr[6][(rawkey1 >> 9) & 0x7f]
 683            | key_perm_maskr[7][(rawkey1 >> 1) & 0x7f];
 684 #endif
 685
 686         /*
 687          *      Rotate subkeys and do compression permutation.
 688          */
 689         shifts = 0;
 690         for (round = 0; round < 16; round++) {
 691                 my_u_int32_t    t0, t1;
 692
 693                 shifts += key_shifts[round];
 694
 695                 t0 = (k0 << shifts) | (k0 >> (28 - shifts));
 696                 t1 = (k1 << shifts) | (k1 >> (28 - shifts));
 697
 698 #ifdef LOWSPACE
 699                 setup_comp_maskl();
 700                 de_keysl[15 - round] =
 701                 en_keysl[round] = common[0][(t0 >> 21) & 0x7f]
 702                                 | common[1][(t0 >> 14) & 0x7f]
 703                                 | common[2][(t0 >> 7) & 0x7f]
 704                                 | common[3][t0 & 0x7f]
 705                                 | common[4][(t1 >> 21) & 0x7f]
 706                                 | common[5][(t1 >> 14) & 0x7f]
 707                                 | common[6][(t1 >> 7) & 0x7f]
 708                                 | common[7][t1 & 0x7f];
 709
 710                 setup_comp_maskr();
 711                 de_keysr[15 - round] =
 712                 en_keysr[round] = common[0][(t0 >> 21) & 0x7f]
 713                                 | common[1][(t0 >> 14) & 0x7f]
 714                                 | common[2][(t0 >> 7) & 0x7f]
 715                                 | common[3][t0 & 0x7f]
 716                                 | common[4][(t1 >> 21) & 0x7f]
 717                                 | common[5][(t1 >> 14) & 0x7f]
 718                                 | common[6][(t1 >> 7) & 0x7f]
 719                                 | common[7][t1 & 0x7f];
 720 #else
 721                 de_keysl[15 - round] =
 722                 en_keysl[round] = comp_maskl[0][(t0 >> 21) & 0x7f]
 723                                 | comp_maskl[1][(t0 >> 14) & 0x7f]
 724                                 | comp_maskl[2][(t0 >> 7) & 0x7f]
 725                                 | comp_maskl[3][t0 & 0x7f]
 726                                 | comp_maskl[4][(t1 >> 21) & 0x7f]
 727                                 | comp_maskl[5][(t1 >> 14) & 0x7f]
 728                                 | comp_maskl[6][(t1 >> 7) & 0x7f]
 729                                 | comp_maskl[7][t1 & 0x7f];
 730
 731                 de_keysr[15 - round] =
 732                 en_keysr[round] = comp_maskr[0][(t0 >> 21) & 0x7f]
 733                                 | comp_maskr[1][(t0 >> 14) & 0x7f]
 734                                 | comp_maskr[2][(t0 >> 7) & 0x7f]
 735                                 | comp_maskr[3][t0 & 0x7f]
 736                                 | comp_maskr[4][(t1 >> 21) & 0x7f]
 737                                 | comp_maskr[5][(t1 >> 14) & 0x7f]
 738                                 | comp_maskr[6][(t1 >> 7) & 0x7f]
 739                                 | comp_maskr[7][t1 & 0x7f];
 740 #endif
 741         }
 742         return(0);
 743 }
 744
 745
 746 static int
 747 do_des( my_u_int32_t l_in, my_u_int32_t r_in, my_u_int32_t *l_out, my_u_int32_t *r_out, int count)
 748 {
 749         /*
 750          *      l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
 751          */
 752         my_u_int32_t    l, r, *kl, *kr, *kl1, *kr1;
 753         my_u_int32_t    f, r48l, r48r;
 754         int             round;
 755
 756         if (count == 0) {
 757                 return(1);
 758         } else if (count > 0) {
 759                 /*
 760                  * Encrypting
 761                  */
 762                 kl1 = en_keysl;
 763                 kr1 = en_keysr;
 764         } else {
 765                 /*
 766                  * Decrypting
 767                  */
 768                 count = -count;
 769                 kl1 = de_keysl;
 770                 kr1 = de_keysr;
 771         }
 772
 773         /*
 774          *      Do initial permutation (IP).
 775          */
 776
 777 #ifdef LOWSPACE
 778         setup_ip_maskl();
 779         l = common[0][l_in >> 24]
 780           | common[1][(l_in >> 16) & 0xff]
 781           | common[2][(l_in >> 8) & 0xff]
 782           | common[3][l_in & 0xff]
 783           | common[4][r_in >> 24]
 784           | common[5][(r_in >> 16) & 0xff]
 785           | common[6][(r_in >> 8) & 0xff]
 786           | common[7][r_in & 0xff];
 787         setup_ip_maskr();
 788         r = common[0][l_in >> 24]
 789           | common[1][(l_in >> 16) & 0xff]
 790           | common[2][(l_in >> 8) & 0xff]
 791           | common[3][l_in & 0xff]
 792           | common[4][r_in >> 24]
 793           | common[5][(r_in >> 16) & 0xff]
 794           | common[6][(r_in >> 8) & 0xff]
 795           | common[7][r_in & 0xff];
 796 #else
 797         l = ip_maskl[0][l_in >> 24]
 798           | ip_maskl[1][(l_in >> 16) & 0xff]
 799           | ip_maskl[2][(l_in >> 8) & 0xff]
 800           | ip_maskl[3][l_in & 0xff]
 801           | ip_maskl[4][r_in >> 24]
 802           | ip_maskl[5][(r_in >> 16) & 0xff]
 803           | ip_maskl[6][(r_in >> 8) & 0xff]
 804           | ip_maskl[7][r_in & 0xff];
 805         r = ip_maskr[0][l_in >> 24]
 806           | ip_maskr[1][(l_in >> 16) & 0xff]
 807           | ip_maskr[2][(l_in >> 8) & 0xff]
 808           | ip_maskr[3][l_in & 0xff]
 809           | ip_maskr[4][r_in >> 24]
 810           | ip_maskr[5][(r_in >> 16) & 0xff]
 811           | ip_maskr[6][(r_in >> 8) & 0xff]
 812           | ip_maskr[7][r_in & 0xff];
 813 #endif
 814
 815         while (count--) {
 816                 /*
 817                  * Do each round.
 818                  */
 819                 kl = kl1;
 820                 kr = kr1;
 821                 round = 16;
 822                 while (round--) {
 823                         /*
 824                          * Expand R to 48 bits (simulate the E-box).
 825                          */
 826                         r48l    = ((r & 0x00000001) << 23)
 827                                 | ((r & 0xf8000000) >> 9)
 828                                 | ((r & 0x1f800000) >> 11)
 829                                 | ((r & 0x01f80000) >> 13)
 830                                 | ((r & 0x001f8000) >> 15);
 831
 832                         r48r    = ((r & 0x0001f800) << 7)
 833                                 | ((r & 0x00001f80) << 5)
 834                                 | ((r & 0x000001f8) << 3)
 835                                 | ((r & 0x0000001f) << 1)
 836                                 | ((r & 0x80000000) >> 31);
 837                         /*
 838                          * Do salting for crypt() and friends, and
 839                          * XOR with the permuted key.
 840                          */
 841                         f = (r48l ^ r48r) & saltbits;
 842                         r48l ^= f ^ *kl++;
 843                         r48r ^= f ^ *kr++;
 844                         /*
 845                          * Do sbox lookups (which shrink it back to 32 bits)
 846                          * and do the pbox permutation at the same time.
 847                          */
 848
 849 #ifdef LOWSPACE
 850                         setup_psbox();
 851                         f = common[0][m_sbox[0][r48l >> 12]]
 852                           | common[1][m_sbox[1][r48l & 0xfff]]
 853                           | common[2][m_sbox[2][r48r >> 12]]
 854                           | common[3][m_sbox[3][r48r & 0xfff]];
 855 #else
 856                         f = psbox[0][m_sbox[0][r48l >> 12]]
 857                           | psbox[1][m_sbox[1][r48l & 0xfff]]
 858                           | psbox[2][m_sbox[2][r48r >> 12]]
 859                           | psbox[3][m_sbox[3][r48r & 0xfff]];
 860 #endif
 861                         /*
 862                          * Now that we've permuted things, complete f().
 863                          */
 864                         f ^= l;
 865                         l = r;
 866                         r = f;
 867                 }
 868                 r = l;
 869                 l = f;
 870         }
 871         /*
 872          * Do final permutation (inverse of IP).
 873          */
 874
 875 #ifdef LOWSPACE
 876         setup_fp_maskl();
 877         *l_out  = common[0][l >> 24]
 878                 | common[1][(l >> 16) & 0xff]
 879                 | common[2][(l >> 8) & 0xff]
 880                 | common[3][l & 0xff]
 881                 | common[4][r >> 24]
 882                 | common[5][(r >> 16) & 0xff]
 883                 | common[6][(r >> 8) & 0xff]
 884                 | common[7][r & 0xff];
 885         setup_fp_maskr();
 886         *r_out  = common[0][l >> 24]
 887                 | common[1][(l >> 16) & 0xff]
 888                 | common[2][(l >> 8) & 0xff]
 889                 | common[3][l & 0xff]
 890                 | common[4][r >> 24]
 891                 | common[5][(r >> 16) & 0xff]
 892                 | common[6][(r >> 8) & 0xff]
 893                 | common[7][r & 0xff];
 894 #else
 895         *l_out  = fp_maskl[0][l >> 24]
 896                 | fp_maskl[1][(l >> 16) & 0xff]
 897                 | fp_maskl[2][(l >> 8) & 0xff]
 898                 | fp_maskl[3][l & 0xff]
 899                 | fp_maskl[4][r >> 24]
 900                 | fp_maskl[5][(r >> 16) & 0xff]
 901                 | fp_maskl[6][(r >> 8) & 0xff]
 902                 | fp_maskl[7][r & 0xff];
 903         *r_out  = fp_maskr[0][l >> 24]
 904                 | fp_maskr[1][(l >> 16) & 0xff]
 905                 | fp_maskr[2][(l >> 8) & 0xff]
 906                 | fp_maskr[3][l & 0xff]
 907                 | fp_maskr[4][r >> 24]
 908                 | fp_maskr[5][(r >> 16) & 0xff]
 909                 | fp_maskr[6][(r >> 8) & 0xff]
 910                 | fp_maskr[7][r & 0xff];
 911 #endif
 912         return(0);
 913 }
 914
 915
 916 #if 0
 917 static int
 918 des_cipher(const char *in, char *out, my_u_int32_t salt, int count)
 919 {
 920         my_u_int32_t    l_out, r_out, rawl, rawr;
 921         int             retval;
 922         union {
 923                 my_u_int32_t    *ui32;
 924                 const char      *c;
 925         } trans;
 926
 927         des_init();
 928
 929         setup_salt(salt);
 930
 931         trans.c = in;
 932         rawl = ntohl(*trans.ui32++);
 933         rawr = ntohl(*trans.ui32);
 934
 935         retval = do_des(rawl, rawr, &l_out, &r_out, count);
 936
 937         trans.c = out;
 938         *trans.ui32++ = htonl(l_out);
 939         *trans.ui32 = htonl(r_out);
 940         return(retval);
 941 }
 942 #endif
 943
 944
 945 void
 946 setkey(const char *key)
 947 {
 948         int     i, j;
 949         my_u_int32_t    packed_keys[2];
 950         my_u_char_t     *p;
 951
 952         p = (my_u_char_t *) packed_keys;
 953
 954         for (i = 0; i < 8; i++) {
 955                 p[i] = 0;
 956                 for (j = 0; j < 8; j++)
 957                         if (*key++ & 1)
 958                                 p[i] |= bits8[j];
 959         }
 960         des_setkey(p);
 961 }
 962
 963
 964 void
 965 encrypt(char *block, int flag)
 966 {
 967         my_u_int32_t    io[2];
 968         my_u_char_t     *p;
 969         int     i, j;
 970
 971         des_init();
 972
 973         setup_salt(0L);
 974         p = block;
 975         for (i = 0; i < 2; i++) {
 976                 io[i] = 0L;
 977                 for (j = 0; j < 32; j++)
 978                         if (*p++ & 1)
 979                                 io[i] |= bits32[j];
 980         }
 981         do_des(io[0], io[1], io, io + 1, flag ? -1 : 1);
 982         for (i = 0; i < 2; i++)
 983                 for (j = 0; j < 32; j++)
 984                         block[(i << 5) | j] = (io[i] & bits32[j]) ? 1 : 0;
 985 }
 986
 987 char *crypt(const char *key, const char *setting)
 988 {
 989         my_u_int32_t    count, salt, l, r0, r1, keybuf[2];
 990         my_u_char_t             *p, *q;
 991         static char     output[21];
 992
 993         des_init();
 994
 995         /*
 996          * Copy the key, shifting each character up by one bit
 997          * and padding with zeros.
 998          */
 999         q = (my_u_char_t *)keybuf;
1000         while (q - (my_u_char_t *)keybuf - 8) {
1001                 *q++ = *key << 1;
1002                 if (*(q - 1))
1003                         key++;
1004         }
1005         if (des_setkey((char *)keybuf))
1006                 return(NULL);
1007
1008 #if 0
1009         if (*setting == _PASSWORD_EFMT1) {
1010                 int             i;
1011                 /*
1012                  * "new"-style:
1013                  *      setting - underscore, 4 bytes of count, 4 bytes of salt
1014                  *      key - unlimited characters
1015                  */
1016                 for (i = 1, count = 0L; i < 5; i++)
1017                         count |= ascii_to_bin(setting[i]) << ((i - 1) * 6);
1018
1019                 for (i = 5, salt = 0L; i < 9; i++)
1020                         salt |= ascii_to_bin(setting[i]) << ((i - 5) * 6);
1021
1022                 while (*key) {
1023                         /*
1024                          * Encrypt the key with itself.
1025                          */
1026                         if (des_cipher((char *)keybuf, (char *)keybuf, 0L, 1))
1027                                 return(NULL);
1028                         /*
1029                          * And XOR with the next 8 characters of the key.
1030                          */
1031                         q = (my_u_char_t *)keybuf;
1032                         while (q - (my_u_char_t *)keybuf - 8 && *key)
1033                                 *q++ ^= *key++ << 1;
1034
1035                         if (des_setkey((char *)keybuf))
1036                                 return(NULL);
1037                 }
1038                 strncpy(output, setting, 9);
1039
1040                 /*
1041                  * Double check that we weren't given a short setting.
1042                  * If we were, the above code will probably have created
1043                  * wierd values for count and salt, but we don't really care.
1044                  * Just make sure the output string doesn't have an extra
1045                  * NUL in it.
1046                  */
1047                 output[9] = '\0';
1048                 p = (my_u_char_t *)output + strlen(output);
1049         } else
1050 #endif
1051         {
1052                 /*
1053                  * "old"-style:
1054                  *      setting - 2 bytes of salt
1055                  *      key - up to 8 characters
1056                  */
1057                 count = 25;
1058
1059                 salt = (ascii_to_bin(setting[1]) << 6)
1060                      |  ascii_to_bin(setting[0]);
1061
1062                 output[0] = setting[0];
1063                 /*
1064                  * If the encrypted password that the salt was extracted from
1065                  * is only 1 character long, the salt will be corrupted.  We
1066                  * need to ensure that the output string doesn't have an extra
1067                  * NUL in it!
1068                  */
1069                 output[1] = setting[1] ? setting[1] : output[0];
1070
1071                 p = (my_u_char_t *)output + 2;
1072         }
1073         setup_salt(salt);
1074         /*
1075          * Do it.
1076          */
1077         if (do_des(0L, 0L, &r0, &r1, (int)count))
1078                 return(NULL);
1079         /*
1080          * Now encode the result...
1081          */
1082         l = (r0 >> 8);
1083         *p++ = ascii64[(l >> 18) & 0x3f];
1084         *p++ = ascii64[(l >> 12) & 0x3f];
1085         *p++ = ascii64[(l >> 6) & 0x3f];
1086         *p++ = ascii64[l & 0x3f];
1087
1088         l = (r0 << 16) | ((r1 >> 16) & 0xffff);
1089         *p++ = ascii64[(l >> 18) & 0x3f];
1090         *p++ = ascii64[(l >> 12) & 0x3f];
1091         *p++ = ascii64[(l >> 6) & 0x3f];
1092         *p++ = ascii64[l & 0x3f];
1093
1094         l = r1 << 2;
1095         *p++ = ascii64[(l >> 12) & 0x3f];
1096         *p++ = ascii64[(l >> 6) & 0x3f];
1097         *p++ = ascii64[l & 0x3f];
1098         *p = 0;
1099
1100         return(output);
1101 }
1102