release/src/router/busybox/libbb/pw_encrypt_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  * Redistribution and use in source and binary forms, with or without
  16  * modification, are permitted provided that the following conditions
  17  * are met:
  18  * 1. Redistributions of source code must retain the above copyright
  19  *    notice, this list of conditions and the following disclaimer.
  20  * 2. Redistributions in binary form must reproduce the above copyright
  21  *    notice, this list of conditions and the following disclaimer in the
  22  *    documentation and/or other materials provided with the distribution.
  23  * 3. Neither the name of the author nor the names of other contributors
  24  *    may be used to endorse or promote products derived from this software
  25  *    without specific prior written permission.
  26  *
  27  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  28  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  29  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  30  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  31  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  32  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  33  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  34  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  35  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  36  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  37  * SUCH DAMAGE.
  38  *
  39  * This is an original implementation of the DES and the crypt(3) interfaces
  40  * by David Burren <davidb@werj.com.au>.
  41  *
  42  * An excellent reference on the underlying algorithm (and related
  43  * algorithms) is:
  44  *
  45  *      B. Schneier, Applied Cryptography: protocols, algorithms,
  46  *      and source code in C, John Wiley & Sons, 1994.
  47  *
  48  * Note that in that book's description of DES the lookups for the initial,
  49  * pbox, and final permutations are inverted (this has been brought to the
  50  * attention of the author).  A list of errata for this book has been
  51  * posted to the sci.crypt newsgroup by the author and is available for FTP.
  52  *
  53  * ARCHITECTURE ASSUMPTIONS:
  54  *      It is assumed that the 8-byte arrays passed by reference can be
  55  *      addressed as arrays of uint32_t's (ie. the CPU is not picky about
  56  *      alignment).
  57  */
  58
  59
  60 /* Parts busybox doesn't need or had optimized */
  61 #define USE_PRECOMPUTED_u_sbox 1
  62 #define USE_REPETITIVE_SPEEDUP 0
  63 #define USE_ip_mask 0
  64 #define USE_de_keys 0
  65
  66
  67 /* A pile of data */
  68 static const uint8_t IP[64] = {
  69         58, 50, 42, 34, 26, 18, 10,  2, 60, 52, 44, 36, 28, 20, 12,  4,
  70         62, 54, 46, 38, 30, 22, 14,  6, 64, 56, 48, 40, 32, 24, 16,  8,
  71         57, 49, 41, 33, 25, 17,  9,  1, 59, 51, 43, 35, 27, 19, 11,  3,
  72         61, 53, 45, 37, 29, 21, 13,  5, 63, 55, 47, 39, 31, 23, 15,  7
  73 };
  74
  75 static const uint8_t key_perm[56] = {
  76         57, 49, 41, 33, 25, 17,  9,  1, 58, 50, 42, 34, 26, 18,
  77         10,  2, 59, 51, 43, 35, 27, 19, 11,  3, 60, 52, 44, 36,
  78         63, 55, 47, 39, 31, 23, 15,  7, 62, 54, 46, 38, 30, 22,
  79         14,  6, 61, 53, 45, 37, 29, 21, 13,  5, 28, 20, 12,  4
  80 };
  81
  82 static const uint8_t key_shifts[16] = {
  83         1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
  84 };
  85
  86 static const uint8_t comp_perm[48] = {
  87         14, 17, 11, 24,  1,  5,  3, 28, 15,  6, 21, 10,
  88         23, 19, 12,  4, 26,  8, 16,  7, 27, 20, 13,  2,
  89         41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
  90         44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
  91 };
  92
  93 /*
  94  * No E box is used, as it's replaced by some ANDs, shifts, and ORs.
  95  */
  96 #if !USE_PRECOMPUTED_u_sbox
  97 static const uint8_t sbox[8][64] = {
  98         {       14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
  99                  0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
 100                  4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
 101                 15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13
 102         },
 103         {       15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
 104                  3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
 105                  0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
 106                 13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9
 107         },
 108         {       10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
 109                 13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
 110                 13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
 111                  1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12
 112         },
 113         {        7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
 114                 13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
 115                 10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
 116                  3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14
 117         },
 118         {        2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
 119                 14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
 120                  4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
 121                 11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3
 122         },
 123         {       12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
 124                 10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
 125                  9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
 126                  4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13
 127         },
 128         {        4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
 129                 13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
 130                  1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
 131                  6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12
 132         },
 133         {       13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
 134                  1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
 135                  7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
 136                  2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
 137         }
 138 };
 139 #else /* precomputed, with half-bytes packed into one byte */
 140 static const uint8_t u_sbox[8][32] = {
 141         {       0x0e, 0xf4, 0x7d, 0x41, 0xe2, 0x2f, 0xdb, 0x18,
 142                 0xa3, 0x6a, 0xc6, 0xbc, 0x95, 0x59, 0x30, 0x87,
 143                 0xf4, 0xc1, 0x8e, 0x28, 0x4d, 0x96, 0x12, 0x7b,
 144                 0x5f, 0xbc, 0x39, 0xe7, 0xa3, 0x0a, 0x65, 0xd0,
 145         },
 146         {       0x3f, 0xd1, 0x48, 0x7e, 0xf6, 0x2b, 0x83, 0xe4,
 147                 0xc9, 0x07, 0x12, 0xad, 0x6c, 0x90, 0xb5, 0x5a,
 148                 0xd0, 0x8e, 0xa7, 0x1b, 0x3a, 0xf4, 0x4d, 0x21,
 149                 0xb5, 0x68, 0x7c, 0xc6, 0x09, 0x53, 0xe2, 0x9f,
 150         },
 151         {       0xda, 0x70, 0x09, 0x9e, 0x36, 0x43, 0x6f, 0xa5,
 152                 0x21, 0x8d, 0x5c, 0xe7, 0xcb, 0xb4, 0xf2, 0x18,
 153                 0x1d, 0xa6, 0xd4, 0x09, 0x68, 0x9f, 0x83, 0x70,
 154                 0x4b, 0xf1, 0xe2, 0x3c, 0xb5, 0x5a, 0x2e, 0xc7,
 155         },
 156         {       0xd7, 0x8d, 0xbe, 0x53, 0x60, 0xf6, 0x09, 0x3a,
 157                 0x41, 0x72, 0x28, 0xc5, 0x1b, 0xac, 0xe4, 0x9f,
 158                 0x3a, 0xf6, 0x09, 0x60, 0xac, 0x1b, 0xd7, 0x8d,
 159                 0x9f, 0x41, 0x53, 0xbe, 0xc5, 0x72, 0x28, 0xe4,
 160         },
 161         {       0xe2, 0xbc, 0x24, 0xc1, 0x47, 0x7a, 0xdb, 0x16,
 162                 0x58, 0x05, 0xf3, 0xaf, 0x3d, 0x90, 0x8e, 0x69,
 163                 0xb4, 0x82, 0xc1, 0x7b, 0x1a, 0xed, 0x27, 0xd8,
 164                 0x6f, 0xf9, 0x0c, 0x95, 0xa6, 0x43, 0x50, 0x3e,
 165         },
 166         {       0xac, 0xf1, 0x4a, 0x2f, 0x79, 0xc2, 0x96, 0x58,
 167                 0x60, 0x1d, 0xd3, 0xe4, 0x0e, 0xb7, 0x35, 0x8b,
 168                 0x49, 0x3e, 0x2f, 0xc5, 0x92, 0x58, 0xfc, 0xa3,
 169                 0xb7, 0xe0, 0x14, 0x7a, 0x61, 0x0d, 0x8b, 0xd6,
 170         },
 171         {       0xd4, 0x0b, 0xb2, 0x7e, 0x4f, 0x90, 0x18, 0xad,
 172                 0xe3, 0x3c, 0x59, 0xc7, 0x25, 0xfa, 0x86, 0x61,
 173                 0x61, 0xb4, 0xdb, 0x8d, 0x1c, 0x43, 0xa7, 0x7e,
 174                 0x9a, 0x5f, 0x06, 0xf8, 0xe0, 0x25, 0x39, 0xc2,
 175         },
 176         {       0x1d, 0xf2, 0xd8, 0x84, 0xa6, 0x3f, 0x7b, 0x41,
 177                 0xca, 0x59, 0x63, 0xbe, 0x05, 0xe0, 0x9c, 0x27,
 178                 0x27, 0x1b, 0xe4, 0x71, 0x49, 0xac, 0x8e, 0xd2,
 179                 0xf0, 0xc6, 0x9a, 0x0d, 0x3f, 0x53, 0x65, 0xb8,
 180         },
 181 };
 182 #endif
 183
 184 static const uint8_t pbox[32] = {
 185         16,  7, 20, 21, 29, 12, 28, 17,  1, 15, 23, 26,  5, 18, 31, 10,
 186          2,  8, 24, 14, 32, 27,  3,  9, 19, 13, 30,  6, 22, 11,  4, 25
 187 };
 188
 189 static const uint32_t bits32[32] =
 190 {
 191         0x80000000, 0x40000000, 0x20000000, 0x10000000,
 192         0x08000000, 0x04000000, 0x02000000, 0x01000000,
 193         0x00800000, 0x00400000, 0x00200000, 0x00100000,
 194         0x00080000, 0x00040000, 0x00020000, 0x00010000,
 195         0x00008000, 0x00004000, 0x00002000, 0x00001000,
 196         0x00000800, 0x00000400, 0x00000200, 0x00000100,
 197         0x00000080, 0x00000040, 0x00000020, 0x00000010,
 198         0x00000008, 0x00000004, 0x00000002, 0x00000001
 199 };
 200
 201 static const uint8_t bits8[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
 202
 203
 204 static int
 205 ascii_to_bin(char ch)
 206 {
 207         if (ch > 'z')
 208                 return 0;
 209         if (ch >= 'a')
 210                 return (ch - 'a' + 38);
 211         if (ch > 'Z')
 212                 return 0;
 213         if (ch >= 'A')
 214                 return (ch - 'A' + 12);
 215         if (ch > '9')
 216                 return 0;
 217         if (ch >= '.')
 218                 return (ch - '.');
 219         return 0;
 220 }
 221
 222
 223 /* Static stuff that stays resident and doesn't change after
 224  * being initialized, and therefore doesn't need to be made
 225  * reentrant. */
 226 struct const_des_ctx {
 227 #if USE_ip_mask
 228         uint8_t init_perm[64]; /* referenced 2 times */
 229 #endif
 230         uint8_t final_perm[64]; /* 2 times */
 231         uint8_t m_sbox[4][4096]; /* 5 times */
 232 };
 233 #define C (*cctx)
 234 #define init_perm  (C.init_perm )
 235 #define final_perm (C.final_perm)
 236 #define m_sbox     (C.m_sbox    )
 237
 238 static struct const_des_ctx*
 239 const_des_init(void)
 240 {
 241         unsigned i, j, b;
 242         struct const_des_ctx *cctx;
 243
 244 #if !USE_PRECOMPUTED_u_sbox
 245         uint8_t u_sbox[8][64];
 246
 247         cctx = xmalloc(sizeof(*cctx));
 248
 249         /* Invert the S-boxes, reordering the input bits. */
 250         for (i = 0; i < 8; i++) {
 251                 for (j = 0; j < 64; j++) {
 252                         b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
 253                         u_sbox[i][j] = sbox[i][b];
 254                 }
 255         }
 256         for (i = 0; i < 8; i++) {
 257                 fprintf(stderr, "\t{\t");
 258                 for (j = 0; j < 64; j+=2)
 259                         fprintf(stderr, " 0x%02x,", u_sbox[i][j] + u_sbox[i][j+1]*16);
 260                 fprintf(stderr, "\n\t},\n");
 261         }
 262         /*
 263          * Convert the inverted S-boxes into 4 arrays of 8 bits.
 264          * Each will handle 12 bits of the S-box input.
 265          */
 266         for (b = 0; b < 4; b++)
 267                 for (i = 0; i < 64; i++)
 268                         for (j = 0; j < 64; j++)
 269                                 m_sbox[b][(i << 6) | j] =
 270                                         (uint8_t)((u_sbox[(b << 1)][i] << 4) |
 271                                                 u_sbox[(b << 1) + 1][j]);
 272 #else
 273         cctx = xmalloc(sizeof(*cctx));
 274
 275         /*
 276          * Convert the inverted S-boxes into 4 arrays of 8 bits.
 277          * Each will handle 12 bits of the S-box input.
 278          */
 279         for (b = 0; b < 4; b++)
 280          for (i = 0; i < 64; i++)
 281           for (j = 0; j < 64; j++) {
 282                 uint8_t lo, hi;
 283                 hi = u_sbox[(b << 1)][i / 2];
 284                 if (!(i & 1))
 285                         hi <<= 4;
 286                 lo = u_sbox[(b << 1) + 1][j / 2];
 287                 if (j & 1)
 288                         lo >>= 4;
 289                 m_sbox[b][(i << 6) | j] = (hi & 0xf0) | (lo & 0x0f);
 290         }
 291 #endif
 292
 293         /*
 294          * Set up the initial & final permutations into a useful form.
 295          */
 296         for (i = 0; i < 64; i++) {
 297                 final_perm[i] = IP[i] - 1;
 298 #if USE_ip_mask
 299                 init_perm[final_perm[i]] = (uint8_t)i;
 300 #endif
 301         }
 302
 303         return cctx;
 304 }
 305
 306
 307 struct des_ctx {
 308         const struct const_des_ctx *const_ctx;
 309         uint32_t saltbits; /* referenced 5 times */
 310 #if USE_REPETITIVE_SPEEDUP
 311         uint32_t old_salt; /* 3 times */
 312         uint32_t old_rawkey0, old_rawkey1; /* 3 times each */
 313 #endif
 314         uint8_t un_pbox[32]; /* 2 times */
 315         uint8_t inv_comp_perm[56]; /* 3 times */
 316         uint8_t inv_key_perm[64]; /* 3 times */
 317         uint32_t en_keysl[16], en_keysr[16]; /* 2 times each */
 318 #if USE_de_keys
 319         uint32_t de_keysl[16], de_keysr[16]; /* 2 times each */
 320 #endif
 321 #if USE_ip_mask
 322         uint32_t ip_maskl[8][256], ip_maskr[8][256]; /* 9 times each */
 323 #endif
 324         uint32_t fp_maskl[8][256], fp_maskr[8][256]; /* 9 times each */
 325         uint32_t key_perm_maskl[8][128], key_perm_maskr[8][128]; /* 9 times */
 326         uint32_t comp_maskl[8][128], comp_maskr[8][128]; /* 9 times each */
 327         uint32_t psbox[4][256]; /* 5 times */
 328 };
 329 #define D (*ctx)
 330 #define const_ctx       (D.const_ctx      )
 331 #define saltbits        (D.saltbits       )
 332 #define old_salt        (D.old_salt       )
 333 #define old_rawkey0     (D.old_rawkey0    )
 334 #define old_rawkey1     (D.old_rawkey1    )
 335 #define un_pbox         (D.un_pbox        )
 336 #define inv_comp_perm   (D.inv_comp_perm  )
 337 #define inv_key_perm    (D.inv_key_perm   )
 338 #define en_keysl        (D.en_keysl       )
 339 #define en_keysr        (D.en_keysr       )
 340 #define de_keysl        (D.de_keysl       )
 341 #define de_keysr        (D.de_keysr       )
 342 #define ip_maskl        (D.ip_maskl       )
 343 #define ip_maskr        (D.ip_maskr       )
 344 #define fp_maskl        (D.fp_maskl       )
 345 #define fp_maskr        (D.fp_maskr       )
 346 #define key_perm_maskl  (D.key_perm_maskl )
 347 #define key_perm_maskr  (D.key_perm_maskr )
 348 #define comp_maskl      (D.comp_maskl     )
 349 #define comp_maskr      (D.comp_maskr     )
 350 #define psbox           (D.psbox          )
 351
 352 static struct des_ctx*
 353 des_init(struct des_ctx *ctx, const struct const_des_ctx *cctx)
 354 {
 355         int i, j, b, k, inbit, obit;
 356         uint32_t p;
 357         const uint32_t *bits28, *bits24;
 358
 359         if (!ctx)
 360                 ctx = xmalloc(sizeof(*ctx));
 361         const_ctx = cctx;
 362
 363 #if USE_REPETITIVE_SPEEDUP
 364         old_rawkey0 = old_rawkey1 = 0;
 365         old_salt = 0;
 366 #endif
 367         saltbits = 0;
 368         bits28 = bits32 + 4;
 369         bits24 = bits28 + 4;
 370
 371         /* Initialise the inverted key permutation. */
 372         for (i = 0; i < 64; i++) {
 373                 inv_key_perm[i] = 255;
 374         }
 375
 376         /*
 377          * Invert the key permutation and initialise the inverted key
 378          * compression permutation.
 379          */
 380         for (i = 0; i < 56; i++) {
 381                 inv_key_perm[key_perm[i] - 1] = (uint8_t)i;
 382                 inv_comp_perm[i] = 255;
 383         }
 384
 385         /* Invert the key compression permutation. */
 386         for (i = 0; i < 48; i++) {
 387                 inv_comp_perm[comp_perm[i] - 1] = (uint8_t)i;
 388         }
 389
 390         /*
 391          * Set up the OR-mask arrays for the initial and final permutations,
 392          * and for the key initial and compression permutations.
 393          */
 394         for (k = 0; k < 8; k++) {
 395                 uint32_t il, ir;
 396                 uint32_t fl, fr;
 397                 for (i = 0; i < 256; i++) {
 398 #if USE_ip_mask
 399                         il = 0;
 400                         ir = 0;
 401 #endif
 402                         fl = 0;
 403                         fr = 0;
 404                         for (j = 0; j < 8; j++) {
 405                                 inbit = 8 * k + j;
 406                                 if (i & bits8[j]) {
 407 #if USE_ip_mask
 408                                         obit = init_perm[inbit];
 409                                         if (obit < 32)
 410                                                 il |= bits32[obit];
 411                                         else
 412                                                 ir |= bits32[obit - 32];
 413 #endif
 414                                         obit = final_perm[inbit];
 415                                         if (obit < 32)
 416                                                 fl |= bits32[obit];
 417                                         else
 418                                                 fr |= bits32[obit - 32];
 419                                 }
 420                         }
 421 #if USE_ip_mask
 422                         ip_maskl[k][i] = il;
 423                         ip_maskr[k][i] = ir;
 424 #endif
 425                         fp_maskl[k][i] = fl;
 426                         fp_maskr[k][i] = fr;
 427                 }
 428                 for (i = 0; i < 128; i++) {
 429                         il = 0;
 430                         ir = 0;
 431                         for (j = 0; j < 7; j++) {
 432                                 inbit = 8 * k + j;
 433                                 if (i & bits8[j + 1]) {
 434                                         obit = inv_key_perm[inbit];
 435                                         if (obit == 255)
 436                                                 continue;
 437                                         if (obit < 28)
 438                                                 il |= bits28[obit];
 439                                         else
 440                                                 ir |= bits28[obit - 28];
 441                                 }
 442                         }
 443                         key_perm_maskl[k][i] = il;
 444                         key_perm_maskr[k][i] = ir;
 445                         il = 0;
 446                         ir = 0;
 447                         for (j = 0; j < 7; j++) {
 448                                 inbit = 7 * k + j;
 449                                 if (i & bits8[j + 1]) {
 450                                         obit = inv_comp_perm[inbit];
 451                                         if (obit == 255)
 452                                                 continue;
 453                                         if (obit < 24)
 454                                                 il |= bits24[obit];
 455                                         else
 456                                                 ir |= bits24[obit - 24];
 457                                 }
 458                         }
 459                         comp_maskl[k][i] = il;
 460                         comp_maskr[k][i] = ir;
 461                 }
 462         }
 463
 464         /*
 465          * Invert the P-box permutation, and convert into OR-masks for
 466          * handling the output of the S-box arrays setup above.
 467          */
 468         for (i = 0; i < 32; i++)
 469                 un_pbox[pbox[i] - 1] = (uint8_t)i;
 470
 471         for (b = 0; b < 4; b++) {
 472                 for (i = 0; i < 256; i++) {
 473                         p = 0;
 474                         for (j = 0; j < 8; j++) {
 475                                 if (i & bits8[j])
 476                                         p |= bits32[un_pbox[8 * b + j]];
 477                         }
 478                         psbox[b][i] = p;
 479                 }
 480         }
 481
 482         return ctx;
 483 }
 484
 485
 486 static void
 487 setup_salt(struct des_ctx *ctx, uint32_t salt)
 488 {
 489         uint32_t obit, saltbit;
 490         int i;
 491
 492 #if USE_REPETITIVE_SPEEDUP
 493         if (salt == old_salt)
 494                 return;
 495         old_salt = salt;
 496 #endif
 497
 498         saltbits = 0;
 499         saltbit = 1;
 500         obit = 0x800000;
 501         for (i = 0; i < 24; i++) {
 502                 if (salt & saltbit)
 503                         saltbits |= obit;
 504                 saltbit <<= 1;
 505                 obit >>= 1;
 506         }
 507 }
 508
 509 static void
 510 des_setkey(struct des_ctx *ctx, const char *key)
 511 {
 512         uint32_t k0, k1, rawkey0, rawkey1;
 513         int shifts, round;
 514
 515         rawkey0 = ntohl(*(const uint32_t *) key);
 516         rawkey1 = ntohl(*(const uint32_t *) (key + 4));
 517
 518 #if USE_REPETITIVE_SPEEDUP
 519         if ((rawkey0 | rawkey1)
 520          && rawkey0 == old_rawkey0
 521          && rawkey1 == old_rawkey1
 522         ) {
 523                 /*
 524                  * Already setup for this key.
 525                  * This optimisation fails on a zero key (which is weak and
 526                  * has bad parity anyway) in order to simplify the starting
 527                  * conditions.
 528                  */
 529                 return;
 530         }
 531         old_rawkey0 = rawkey0;
 532         old_rawkey1 = rawkey1;
 533 #endif
 534
 535         /*
 536          * Do key permutation and split into two 28-bit subkeys.
 537          */
 538         k0 = key_perm_maskl[0][rawkey0 >> 25]
 539            | key_perm_maskl[1][(rawkey0 >> 17) & 0x7f]
 540            | key_perm_maskl[2][(rawkey0 >> 9) & 0x7f]
 541            | key_perm_maskl[3][(rawkey0 >> 1) & 0x7f]
 542            | key_perm_maskl[4][rawkey1 >> 25]
 543            | key_perm_maskl[5][(rawkey1 >> 17) & 0x7f]
 544            | key_perm_maskl[6][(rawkey1 >> 9) & 0x7f]
 545            | key_perm_maskl[7][(rawkey1 >> 1) & 0x7f];
 546         k1 = key_perm_maskr[0][rawkey0 >> 25]
 547            | key_perm_maskr[1][(rawkey0 >> 17) & 0x7f]
 548            | key_perm_maskr[2][(rawkey0 >> 9) & 0x7f]
 549            | key_perm_maskr[3][(rawkey0 >> 1) & 0x7f]
 550            | key_perm_maskr[4][rawkey1 >> 25]
 551            | key_perm_maskr[5][(rawkey1 >> 17) & 0x7f]
 552            | key_perm_maskr[6][(rawkey1 >> 9) & 0x7f]
 553            | key_perm_maskr[7][(rawkey1 >> 1) & 0x7f];
 554         /*
 555          * Rotate subkeys and do compression permutation.
 556          */
 557         shifts = 0;
 558         for (round = 0; round < 16; round++) {
 559                 uint32_t t0, t1;
 560
 561                 shifts += key_shifts[round];
 562
 563                 t0 = (k0 << shifts) | (k0 >> (28 - shifts));
 564                 t1 = (k1 << shifts) | (k1 >> (28 - shifts));
 565
 566 #if USE_de_keys
 567                 de_keysl[15 - round] =
 568 #endif
 569                 en_keysl[round] = comp_maskl[0][(t0 >> 21) & 0x7f]
 570                                 | comp_maskl[1][(t0 >> 14) & 0x7f]
 571                                 | comp_maskl[2][(t0 >> 7) & 0x7f]
 572                                 | comp_maskl[3][t0 & 0x7f]
 573                                 | comp_maskl[4][(t1 >> 21) & 0x7f]
 574                                 | comp_maskl[5][(t1 >> 14) & 0x7f]
 575                                 | comp_maskl[6][(t1 >> 7) & 0x7f]
 576                                 | comp_maskl[7][t1 & 0x7f];
 577
 578 #if USE_de_keys
 579                 de_keysr[15 - round] =
 580 #endif
 581                 en_keysr[round] = comp_maskr[0][(t0 >> 21) & 0x7f]
 582                                 | comp_maskr[1][(t0 >> 14) & 0x7f]
 583                                 | comp_maskr[2][(t0 >> 7) & 0x7f]
 584                                 | comp_maskr[3][t0 & 0x7f]
 585                                 | comp_maskr[4][(t1 >> 21) & 0x7f]
 586                                 | comp_maskr[5][(t1 >> 14) & 0x7f]
 587                                 | comp_maskr[6][(t1 >> 7) & 0x7f]
 588                                 | comp_maskr[7][t1 & 0x7f];
 589         }
 590 }
 591
 592
 593 static void
 594 do_des(struct des_ctx *ctx, /*uint32_t l_in, uint32_t r_in,*/ uint32_t *l_out, uint32_t *r_out, int count)
 595 {
 596         const struct const_des_ctx *cctx = const_ctx;
 597         /*
 598          * l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
 599          */
 600         uint32_t l, r, *kl, *kr;
 601         uint32_t f = f; /* silence gcc */
 602         uint32_t r48l, r48r;
 603         int round;
 604
 605         /* Do initial permutation (IP). */
 606 #if USE_ip_mask
 607         uint32_t l_in = 0;
 608         uint32_t r_in = 0;
 609         l = ip_maskl[0][l_in >> 24]
 610           | ip_maskl[1][(l_in >> 16) & 0xff]
 611           | ip_maskl[2][(l_in >> 8) & 0xff]
 612           | ip_maskl[3][l_in & 0xff]
 613           | ip_maskl[4][r_in >> 24]
 614           | ip_maskl[5][(r_in >> 16) & 0xff]
 615           | ip_maskl[6][(r_in >> 8) & 0xff]
 616           | ip_maskl[7][r_in & 0xff];
 617         r = ip_maskr[0][l_in >> 24]
 618           | ip_maskr[1][(l_in >> 16) & 0xff]
 619           | ip_maskr[2][(l_in >> 8) & 0xff]
 620           | ip_maskr[3][l_in & 0xff]
 621           | ip_maskr[4][r_in >> 24]
 622           | ip_maskr[5][(r_in >> 16) & 0xff]
 623           | ip_maskr[6][(r_in >> 8) & 0xff]
 624           | ip_maskr[7][r_in & 0xff];
 625 #elif 0 /* -65 bytes (using the fact that l_in == r_in == 0) */
 626         l = r = 0;
 627         for (round = 0; round < 8; round++) {
 628                 l |= ip_maskl[round][0];
 629                 r |= ip_maskr[round][0];
 630         }
 631         bb_error_msg("l:%x r:%x", l, r); /* reports 0, 0 always! */
 632 #else /* using the fact that ip_maskX[] is constant (written to by des_init) */
 633         l = r = 0;
 634 #endif
 635
 636         do {
 637                 /* Do each round. */
 638                 kl = en_keysl;
 639                 kr = en_keysr;
 640                 round = 16;
 641                 do {
 642                         /* Expand R to 48 bits (simulate the E-box). */
 643                         r48l    = ((r & 0x00000001) << 23)
 644                                 | ((r & 0xf8000000) >> 9)
 645                                 | ((r & 0x1f800000) >> 11)
 646                                 | ((r & 0x01f80000) >> 13)
 647                                 | ((r & 0x001f8000) >> 15);
 648
 649                         r48r    = ((r & 0x0001f800) << 7)
 650                                 | ((r & 0x00001f80) << 5)
 651                                 | ((r & 0x000001f8) << 3)
 652                                 | ((r & 0x0000001f) << 1)
 653                                 | ((r & 0x80000000) >> 31);
 654                         /*
 655                          * Do salting for crypt() and friends, and
 656                          * XOR with the permuted key.
 657                          */
 658                         f = (r48l ^ r48r) & saltbits;
 659                         r48l ^= f ^ *kl++;
 660                         r48r ^= f ^ *kr++;
 661                         /*
 662                          * Do sbox lookups (which shrink it back to 32 bits)
 663                          * and do the pbox permutation at the same time.
 664                          */
 665                         f = psbox[0][m_sbox[0][r48l >> 12]]
 666                           | psbox[1][m_sbox[1][r48l & 0xfff]]
 667                           | psbox[2][m_sbox[2][r48r >> 12]]
 668                           | psbox[3][m_sbox[3][r48r & 0xfff]];
 669                         /* Now that we've permuted things, complete f(). */
 670                         f ^= l;
 671                         l = r;
 672                         r = f;
 673                 } while (--round);
 674                 r = l;
 675                 l = f;
 676         } while (--count);
 677
 678         /* Do final permutation (inverse of IP). */
 679         *l_out  = fp_maskl[0][l >> 24]
 680                 | fp_maskl[1][(l >> 16) & 0xff]
 681                 | fp_maskl[2][(l >> 8) & 0xff]
 682                 | fp_maskl[3][l & 0xff]
 683                 | fp_maskl[4][r >> 24]
 684                 | fp_maskl[5][(r >> 16) & 0xff]
 685                 | fp_maskl[6][(r >> 8) & 0xff]
 686                 | fp_maskl[7][r & 0xff];
 687         *r_out  = fp_maskr[0][l >> 24]
 688                 | fp_maskr[1][(l >> 16) & 0xff]
 689                 | fp_maskr[2][(l >> 8) & 0xff]
 690                 | fp_maskr[3][l & 0xff]
 691                 | fp_maskr[4][r >> 24]
 692                 | fp_maskr[5][(r >> 16) & 0xff]
 693                 | fp_maskr[6][(r >> 8) & 0xff]
 694                 | fp_maskr[7][r & 0xff];
 695 }
 696
 697 #define DES_OUT_BUFSIZE 21
 698
 699 static void
 700 to64_msb_first(char *s, unsigned v)
 701 {
 702 #if 0
 703         *s++ = ascii64[(v >> 18) & 0x3f]; /* bits 23..18 */
 704         *s++ = ascii64[(v >> 12) & 0x3f]; /* bits 17..12 */
 705         *s++ = ascii64[(v >> 6) & 0x3f]; /* bits 11..6 */
 706         *s   = ascii64[v & 0x3f]; /* bits 5..0 */
 707 #endif
 708         *s++ = i64c(v >> 18); /* bits 23..18 */
 709         *s++ = i64c(v >> 12); /* bits 17..12 */
 710         *s++ = i64c(v >> 6); /* bits 11..6 */
 711         *s   = i64c(v); /* bits 5..0 */
 712 }
 713
 714 static char *
 715 NOINLINE
 716 des_crypt(struct des_ctx *ctx, char output[DES_OUT_BUFSIZE],
 717                 const unsigned char *key, const unsigned char *setting)
 718 {
 719         uint32_t salt, r0, r1, keybuf[2];
 720         uint8_t *q;
 721
 722         /*
 723          * Copy the key, shifting each character up by one bit
 724          * and padding with zeros.
 725          */
 726         q = (uint8_t *)keybuf;
 727         while (q - (uint8_t *)keybuf != 8) {
 728                 *q = *key << 1;
 729                 if (*q)
 730                         key++;
 731                 q++;
 732         }
 733         des_setkey(ctx, (char *)keybuf);
 734
 735         /*
 736          * setting - 2 bytes of salt
 737          * key - up to 8 characters
 738          */
 739         salt = (ascii_to_bin(setting[1]) << 6)
 740              |  ascii_to_bin(setting[0]);
 741
 742         output[0] = setting[0];
 743         /*
 744          * If the encrypted password that the salt was extracted from
 745          * is only 1 character long, the salt will be corrupted.  We
 746          * need to ensure that the output string doesn't have an extra
 747          * NUL in it!
 748          */
 749         output[1] = setting[1] ? setting[1] : output[0];
 750
 751         setup_salt(ctx, salt);
 752         /* Do it. */
 753         do_des(ctx, /*0, 0,*/ &r0, &r1, 25 /* count */);
 754
 755         /* Now encode the result. */
 756 #if 0
 757 {
 758         uint32_t l = (r0 >> 8);
 759         q = (uint8_t *)output + 2;
 760         *q++ = ascii64[(l >> 18) & 0x3f]; /* bits 31..26 of r0 */
 761         *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 25..20 of r0 */
 762         *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 19..14 of r0 */
 763         *q++ = ascii64[l & 0x3f]; /* bits 13..8 of r0 */
 764         l = ((r0 << 16) | (r1 >> 16));
 765         *q++ = ascii64[(l >> 18) & 0x3f]; /* bits 7..2 of r0 */
 766         *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 1..2 of r0 and 31..28 of r1 */
 767         *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 27..22 of r1 */
 768         *q++ = ascii64[l & 0x3f]; /* bits 21..16 of r1 */
 769         l = r1 << 2;
 770         *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 15..10 of r1 */
 771         *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 9..4 of r1 */
 772         *q++ = ascii64[l & 0x3f]; /* bits 3..0 of r1 + 00 */
 773         *q = 0;
 774 }
 775 #else
 776         /* Each call takes low-order 24 bits and stores 4 chars */
 777         /* bits 31..8 of r0 */
 778         to64_msb_first(output + 2, (r0 >> 8));
 779         /* bits 7..0 of r0 and 31..16 of r1 */
 780         to64_msb_first(output + 6, (r0 << 16) | (r1 >> 16));
 781         /* bits 15..0 of r1 and two zero bits (plus extra zero byte) */
 782         to64_msb_first(output + 10, (r1 << 8));
 783         /* extra zero byte is encoded as '.', fixing it */
 784         output[13] = '\0';
 785 #endif
 786
 787         return output;
 788 }
 789
 790 #undef USE_PRECOMPUTED_u_sbox
 791 #undef USE_REPETITIVE_SPEEDUP
 792 #undef USE_ip_mask
 793 #undef USE_de_keys
 794
 795 #undef C
 796 #undef init_perm
 797 #undef final_perm
 798 #undef m_sbox
 799 #undef D
 800 #undef const_ctx
 801 #undef saltbits
 802 #undef old_salt
 803 #undef old_rawkey0
 804 #undef old_rawkey1
 805 #undef un_pbox
 806 #undef inv_comp_perm
 807 #undef inv_key_perm
 808 #undef en_keysl
 809 #undef en_keysr
 810 #undef de_keysl
 811 #undef de_keysr
 812 #undef ip_maskl
 813 #undef ip_maskr
 814 #undef fp_maskl
 815 #undef fp_maskr
 816 #undef key_perm_maskl
 817 #undef key_perm_maskr
 818 #undef comp_maskl
 819 #undef comp_maskr
 820 #undef psbox