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] ALIGN1 = {
  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] ALIGN1 = {
  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] ALIGN1 = {
  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] ALIGN1 = {
  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] ALIGN1 = {
 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] ALIGN4 = {
 190         0x80000000, 0x40000000, 0x20000000, 0x10000000,
 191         0x08000000, 0x04000000, 0x02000000, 0x01000000,
 192         0x00800000, 0x00400000, 0x00200000, 0x00100000,
 193         0x00080000, 0x00040000, 0x00020000, 0x00010000,
 194         0x00008000, 0x00004000, 0x00002000, 0x00001000,
 195         0x00000800, 0x00000400, 0x00000200, 0x00000100,
 196         0x00000080, 0x00000040, 0x00000020, 0x00000010,
 197         0x00000008, 0x00000004, 0x00000002, 0x00000001
 198 };
 199
 200 static const uint8_t bits8[8] ALIGN1 = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
 201
 202
 203 static int
 204 ascii_to_bin(char ch)
 205 {
 206         if (ch > 'z')
 207                 return 0;
 208         if (ch >= 'a')
 209                 return (ch - 'a' + 38);
 210         if (ch > 'Z')
 211                 return 0;
 212         if (ch >= 'A')
 213                 return (ch - 'A' + 12);
 214         if (ch > '9')
 215                 return 0;
 216         if (ch >= '.')
 217                 return (ch - '.');
 218         return 0;
 219 }
 220
 221
 222 /* Static stuff that stays resident and doesn't change after
 223  * being initialized, and therefore doesn't need to be made
 224  * reentrant. */
 225 struct const_des_ctx {
 226 #if USE_ip_mask
 227         uint8_t init_perm[64]; /* referenced 2 times */
 228 #endif
 229         uint8_t final_perm[64]; /* 2 times */
 230         uint8_t m_sbox[4][4096]; /* 5 times */
 231 };
 232 #define C (*cctx)
 233 #define init_perm  (C.init_perm )
 234 #define final_perm (C.final_perm)
 235 #define m_sbox     (C.m_sbox    )
 236
 237 static struct const_des_ctx*
 238 const_des_init(void)
 239 {
 240         unsigned i, j, b;
 241         struct const_des_ctx *cctx;
 242
 243 #if !USE_PRECOMPUTED_u_sbox
 244         uint8_t u_sbox[8][64];
 245
 246         cctx = xmalloc(sizeof(*cctx));
 247
 248         /* Invert the S-boxes, reordering the input bits. */
 249         for (i = 0; i < 8; i++) {
 250                 for (j = 0; j < 64; j++) {
 251                         b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
 252                         u_sbox[i][j] = sbox[i][b];
 253                 }
 254         }
 255         for (i = 0; i < 8; i++) {
 256                 fprintf(stderr, "\t{\t");
 257                 for (j = 0; j < 64; j+=2)
 258                         fprintf(stderr, " 0x%02x,", u_sbox[i][j] + u_sbox[i][j+1]*16);
 259                 fprintf(stderr, "\n\t},\n");
 260         }
 261         /*
 262          * Convert the inverted S-boxes into 4 arrays of 8 bits.
 263          * Each will handle 12 bits of the S-box input.
 264          */
 265         for (b = 0; b < 4; b++)
 266                 for (i = 0; i < 64; i++)
 267                         for (j = 0; j < 64; j++)
 268                                 m_sbox[b][(i << 6) | j] =
 269                                         (uint8_t)((u_sbox[(b << 1)][i] << 4) |
 270                                                 u_sbox[(b << 1) + 1][j]);
 271 #else
 272         cctx = xmalloc(sizeof(*cctx));
 273
 274         /*
 275          * Convert the inverted S-boxes into 4 arrays of 8 bits.
 276          * Each will handle 12 bits of the S-box input.
 277          */
 278         for (b = 0; b < 4; b++)
 279          for (i = 0; i < 64; i++)
 280           for (j = 0; j < 64; j++) {
 281                 uint8_t lo, hi;
 282                 hi = u_sbox[(b << 1)][i / 2];
 283                 if (!(i & 1))
 284                         hi <<= 4;
 285                 lo = u_sbox[(b << 1) + 1][j / 2];
 286                 if (j & 1)
 287                         lo >>= 4;
 288                 m_sbox[b][(i << 6) | j] = (hi & 0xf0) | (lo & 0x0f);
 289         }
 290 #endif
 291
 292         /*
 293          * Set up the initial & final permutations into a useful form.
 294          */
 295         for (i = 0; i < 64; i++) {
 296                 final_perm[i] = IP[i] - 1;
 297 #if USE_ip_mask
 298                 init_perm[final_perm[i]] = (uint8_t)i;
 299 #endif
 300         }
 301
 302         return cctx;
 303 }
 304
 305
 306 struct des_ctx {
 307         const struct const_des_ctx *const_ctx;
 308         uint32_t saltbits; /* referenced 5 times */
 309 #if USE_REPETITIVE_SPEEDUP
 310         uint32_t old_salt; /* 3 times */
 311         uint32_t old_rawkey0, old_rawkey1; /* 3 times each */
 312 #endif
 313         uint8_t un_pbox[32]; /* 2 times */
 314         uint8_t inv_comp_perm[56]; /* 3 times */
 315         uint8_t inv_key_perm[64]; /* 3 times */
 316         uint32_t en_keysl[16], en_keysr[16]; /* 2 times each */
 317 #if USE_de_keys
 318         uint32_t de_keysl[16], de_keysr[16]; /* 2 times each */
 319 #endif
 320 #if USE_ip_mask
 321         uint32_t ip_maskl[8][256], ip_maskr[8][256]; /* 9 times each */
 322 #endif
 323         uint32_t fp_maskl[8][256], fp_maskr[8][256]; /* 9 times each */
 324         uint32_t key_perm_maskl[8][128], key_perm_maskr[8][128]; /* 9 times */
 325         uint32_t comp_maskl[8][128], comp_maskr[8][128]; /* 9 times each */
 326         uint32_t psbox[4][256]; /* 5 times */
 327 };
 328 #define D (*ctx)
 329 #define const_ctx       (D.const_ctx      )
 330 #define saltbits        (D.saltbits       )
 331 #define old_salt        (D.old_salt       )
 332 #define old_rawkey0     (D.old_rawkey0    )
 333 #define old_rawkey1     (D.old_rawkey1    )
 334 #define un_pbox         (D.un_pbox        )
 335 #define inv_comp_perm   (D.inv_comp_perm  )
 336 #define inv_key_perm    (D.inv_key_perm   )
 337 #define en_keysl        (D.en_keysl       )
 338 #define en_keysr        (D.en_keysr       )
 339 #define de_keysl        (D.de_keysl       )
 340 #define de_keysr        (D.de_keysr       )
 341 #define ip_maskl        (D.ip_maskl       )
 342 #define ip_maskr        (D.ip_maskr       )
 343 #define fp_maskl        (D.fp_maskl       )
 344 #define fp_maskr        (D.fp_maskr       )
 345 #define key_perm_maskl  (D.key_perm_maskl )
 346 #define key_perm_maskr  (D.key_perm_maskr )
 347 #define comp_maskl      (D.comp_maskl     )
 348 #define comp_maskr      (D.comp_maskr     )
 349 #define psbox           (D.psbox          )
 350
 351 static struct des_ctx*
 352 des_init(struct des_ctx *ctx, const struct const_des_ctx *cctx)
 353 {
 354         int i, j, b, k, inbit, obit;
 355         uint32_t p;
 356         const uint32_t *bits28, *bits24;
 357
 358         if (!ctx)
 359                 ctx = xmalloc(sizeof(*ctx));
 360         const_ctx = cctx;
 361
 362 #if USE_REPETITIVE_SPEEDUP
 363         old_rawkey0 = old_rawkey1 = 0;
 364         old_salt = 0;
 365 #endif
 366         //saltbits = 0; /* not needed: we call setup_salt() before do_des() */
 367         bits28 = bits32 + 4;
 368         bits24 = bits28 + 4;
 369
 370         /* Initialise the inverted key permutation. */
 371         for (i = 0; i < 64; i++) {
 372                 inv_key_perm[i] = 255;
 373         }
 374
 375         /*
 376          * Invert the key permutation and initialise the inverted key
 377          * compression permutation.
 378          */
 379         for (i = 0; i < 56; i++) {
 380                 inv_key_perm[key_perm[i] - 1] = (uint8_t)i;
 381                 inv_comp_perm[i] = 255;
 382         }
 383
 384         /* Invert the key compression permutation. */
 385         for (i = 0; i < 48; i++) {
 386                 inv_comp_perm[comp_perm[i] - 1] = (uint8_t)i;
 387         }
 388
 389         /*
 390          * Set up the OR-mask arrays for the initial and final permutations,
 391          * and for the key initial and compression permutations.
 392          */
 393         for (k = 0; k < 8; k++) {
 394                 uint32_t il, ir;
 395                 uint32_t fl, fr;
 396                 for (i = 0; i < 256; i++) {
 397 #if USE_ip_mask
 398                         il = 0;
 399                         ir = 0;
 400 #endif
 401                         fl = 0;
 402                         fr = 0;
 403                         for (j = 0; j < 8; j++) {
 404                                 inbit = 8 * k + j;
 405                                 if (i & bits8[j]) {
 406 #if USE_ip_mask
 407                                         obit = init_perm[inbit];
 408                                         if (obit < 32)
 409                                                 il |= bits32[obit];
 410                                         else
 411                                                 ir |= bits32[obit - 32];
 412 #endif
 413                                         obit = final_perm[inbit];
 414                                         if (obit < 32)
 415                                                 fl |= bits32[obit];
 416                                         else
 417                                                 fr |= bits32[obit - 32];
 418                                 }
 419                         }
 420 #if USE_ip_mask
 421                         ip_maskl[k][i] = il;
 422                         ip_maskr[k][i] = ir;
 423 #endif
 424                         fp_maskl[k][i] = fl;
 425                         fp_maskr[k][i] = fr;
 426                 }
 427                 for (i = 0; i < 128; i++) {
 428                         il = 0;
 429                         ir = 0;
 430                         for (j = 0; j < 7; j++) {
 431                                 inbit = 8 * k + j;
 432                                 if (i & bits8[j + 1]) {
 433                                         obit = inv_key_perm[inbit];
 434                                         if (obit == 255)
 435                                                 continue;
 436                                         if (obit < 28)
 437                                                 il |= bits28[obit];
 438                                         else
 439                                                 ir |= bits28[obit - 28];
 440                                 }
 441                         }
 442                         key_perm_maskl[k][i] = il;
 443                         key_perm_maskr[k][i] = ir;
 444                         il = 0;
 445                         ir = 0;
 446                         for (j = 0; j < 7; j++) {
 447                                 inbit = 7 * k + j;
 448                                 if (i & bits8[j + 1]) {
 449                                         obit = inv_comp_perm[inbit];
 450                                         if (obit == 255)
 451                                                 continue;
 452                                         if (obit < 24)
 453                                                 il |= bits24[obit];
 454                                         else
 455                                                 ir |= bits24[obit - 24];
 456                                 }
 457                         }
 458                         comp_maskl[k][i] = il;
 459                         comp_maskr[k][i] = ir;
 460                 }
 461         }
 462
 463         /*
 464          * Invert the P-box permutation, and convert into OR-masks for
 465          * handling the output of the S-box arrays setup above.
 466          */
 467         for (i = 0; i < 32; i++)
 468                 un_pbox[pbox[i] - 1] = (uint8_t)i;
 469
 470         for (b = 0; b < 4; b++) {
 471                 for (i = 0; i < 256; i++) {
 472                         p = 0;
 473                         for (j = 0; j < 8; j++) {
 474                                 if (i & bits8[j])
 475                                         p |= bits32[un_pbox[8 * b + j]];
 476                         }
 477                         psbox[b][i] = p;
 478                 }
 479         }
 480
 481         return ctx;
 482 }
 483
 484 /* Accepts 24-bit salt at max */
 485 static void
 486 setup_salt(struct des_ctx *ctx, uint32_t salt)
 487 {
 488         uint32_t invbits;
 489
 490 #if USE_REPETITIVE_SPEEDUP
 491         if (salt == old_salt)
 492                 return;
 493         old_salt = salt;
 494 #endif
 495
 496         invbits = 0;
 497
 498         salt |= (1 << 24);
 499         do {
 500                 invbits = (invbits << 1) + (salt & 1);
 501                 salt >>= 1;
 502         } while (salt != 1);
 503
 504         saltbits = invbits;
 505 }
 506
 507 static void
 508 des_setkey(struct des_ctx *ctx, const char *key)
 509 {
 510         uint32_t k0, k1, rawkey0, rawkey1;
 511         int shifts, round;
 512
 513         rawkey0 = ntohl(*(const uint32_t *) key);
 514         rawkey1 = ntohl(*(const uint32_t *) (key + 4));
 515
 516 #if USE_REPETITIVE_SPEEDUP
 517         if ((rawkey0 | rawkey1)
 518          && rawkey0 == old_rawkey0
 519          && rawkey1 == old_rawkey1
 520         ) {
 521                 /*
 522                  * Already setup for this key.
 523                  * This optimisation fails on a zero key (which is weak and
 524                  * has bad parity anyway) in order to simplify the starting
 525                  * conditions.
 526                  */
 527                 return;
 528         }
 529         old_rawkey0 = rawkey0;
 530         old_rawkey1 = rawkey1;
 531 #endif
 532
 533         /*
 534          * Do key permutation and split into two 28-bit subkeys.
 535          */
 536         k0 = key_perm_maskl[0][rawkey0 >> 25]
 537            | key_perm_maskl[1][(rawkey0 >> 17) & 0x7f]
 538            | key_perm_maskl[2][(rawkey0 >> 9) & 0x7f]
 539            | key_perm_maskl[3][(rawkey0 >> 1) & 0x7f]
 540            | key_perm_maskl[4][rawkey1 >> 25]
 541            | key_perm_maskl[5][(rawkey1 >> 17) & 0x7f]
 542            | key_perm_maskl[6][(rawkey1 >> 9) & 0x7f]
 543            | key_perm_maskl[7][(rawkey1 >> 1) & 0x7f];
 544         k1 = key_perm_maskr[0][rawkey0 >> 25]
 545            | key_perm_maskr[1][(rawkey0 >> 17) & 0x7f]
 546            | key_perm_maskr[2][(rawkey0 >> 9) & 0x7f]
 547            | key_perm_maskr[3][(rawkey0 >> 1) & 0x7f]
 548            | key_perm_maskr[4][rawkey1 >> 25]
 549            | key_perm_maskr[5][(rawkey1 >> 17) & 0x7f]
 550            | key_perm_maskr[6][(rawkey1 >> 9) & 0x7f]
 551            | key_perm_maskr[7][(rawkey1 >> 1) & 0x7f];
 552         /*
 553          * Rotate subkeys and do compression permutation.
 554          */
 555         shifts = 0;
 556         for (round = 0; round < 16; round++) {
 557                 uint32_t t0, t1;
 558
 559                 shifts += key_shifts[round];
 560
 561                 t0 = (k0 << shifts) | (k0 >> (28 - shifts));
 562                 t1 = (k1 << shifts) | (k1 >> (28 - shifts));
 563
 564 #if USE_de_keys
 565                 de_keysl[15 - round] =
 566 #endif
 567                 en_keysl[round] = comp_maskl[0][(t0 >> 21) & 0x7f]
 568                                 | comp_maskl[1][(t0 >> 14) & 0x7f]
 569                                 | comp_maskl[2][(t0 >> 7) & 0x7f]
 570                                 | comp_maskl[3][t0 & 0x7f]
 571                                 | comp_maskl[4][(t1 >> 21) & 0x7f]
 572                                 | comp_maskl[5][(t1 >> 14) & 0x7f]
 573                                 | comp_maskl[6][(t1 >> 7) & 0x7f]
 574                                 | comp_maskl[7][t1 & 0x7f];
 575
 576 #if USE_de_keys
 577                 de_keysr[15 - round] =
 578 #endif
 579                 en_keysr[round] = comp_maskr[0][(t0 >> 21) & 0x7f]
 580                                 | comp_maskr[1][(t0 >> 14) & 0x7f]
 581                                 | comp_maskr[2][(t0 >> 7) & 0x7f]
 582                                 | comp_maskr[3][t0 & 0x7f]
 583                                 | comp_maskr[4][(t1 >> 21) & 0x7f]
 584                                 | comp_maskr[5][(t1 >> 14) & 0x7f]
 585                                 | comp_maskr[6][(t1 >> 7) & 0x7f]
 586                                 | comp_maskr[7][t1 & 0x7f];
 587         }
 588 }
 589
 590
 591 static void
 592 do_des(struct des_ctx *ctx, /*uint32_t l_in, uint32_t r_in,*/ uint32_t *l_out, uint32_t *r_out, int count)
 593 {
 594         const struct const_des_ctx *cctx = const_ctx;
 595         /*
 596          * l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
 597          */
 598         uint32_t l, r, *kl, *kr;
 599         uint32_t f = f; /* silence gcc */
 600         uint32_t r48l, r48r;
 601         int round;
 602
 603         /* Do initial permutation (IP). */
 604 #if USE_ip_mask
 605         uint32_t l_in = 0;
 606         uint32_t r_in = 0;
 607         l = ip_maskl[0][l_in >> 24]
 608           | ip_maskl[1][(l_in >> 16) & 0xff]
 609           | ip_maskl[2][(l_in >> 8) & 0xff]
 610           | ip_maskl[3][l_in & 0xff]
 611           | ip_maskl[4][r_in >> 24]
 612           | ip_maskl[5][(r_in >> 16) & 0xff]
 613           | ip_maskl[6][(r_in >> 8) & 0xff]
 614           | ip_maskl[7][r_in & 0xff];
 615         r = ip_maskr[0][l_in >> 24]
 616           | ip_maskr[1][(l_in >> 16) & 0xff]
 617           | ip_maskr[2][(l_in >> 8) & 0xff]
 618           | ip_maskr[3][l_in & 0xff]
 619           | ip_maskr[4][r_in >> 24]
 620           | ip_maskr[5][(r_in >> 16) & 0xff]
 621           | ip_maskr[6][(r_in >> 8) & 0xff]
 622           | ip_maskr[7][r_in & 0xff];
 623 #elif 0 /* -65 bytes (using the fact that l_in == r_in == 0) */
 624         l = r = 0;
 625         for (round = 0; round < 8; round++) {
 626                 l |= ip_maskl[round][0];
 627                 r |= ip_maskr[round][0];
 628         }
 629         bb_error_msg("l:%x r:%x", l, r); /* reports 0, 0 always! */
 630 #else /* using the fact that ip_maskX[] is constant (written to by des_init) */
 631         l = r = 0;
 632 #endif
 633
 634         do {
 635                 /* Do each round. */
 636                 kl = en_keysl;
 637                 kr = en_keysr;
 638                 round = 16;
 639                 do {
 640                         /* Expand R to 48 bits (simulate the E-box). */
 641                         r48l    = ((r & 0x00000001) << 23)
 642                                 | ((r & 0xf8000000) >> 9)
 643                                 | ((r & 0x1f800000) >> 11)
 644                                 | ((r & 0x01f80000) >> 13)
 645                                 | ((r & 0x001f8000) >> 15);
 646
 647                         r48r    = ((r & 0x0001f800) << 7)
 648                                 | ((r & 0x00001f80) << 5)
 649                                 | ((r & 0x000001f8) << 3)
 650                                 | ((r & 0x0000001f) << 1)
 651                                 | ((r & 0x80000000) >> 31);
 652                         /*
 653                          * Do salting for crypt() and friends, and
 654                          * XOR with the permuted key.
 655                          */
 656                         f = (r48l ^ r48r) & saltbits;
 657                         r48l ^= f ^ *kl++;
 658                         r48r ^= f ^ *kr++;
 659                         /*
 660                          * Do sbox lookups (which shrink it back to 32 bits)
 661                          * and do the pbox permutation at the same time.
 662                          */
 663                         f = psbox[0][m_sbox[0][r48l >> 12]]
 664                           | psbox[1][m_sbox[1][r48l & 0xfff]]
 665                           | psbox[2][m_sbox[2][r48r >> 12]]
 666                           | psbox[3][m_sbox[3][r48r & 0xfff]];
 667                         /* Now that we've permuted things, complete f(). */
 668                         f ^= l;
 669                         l = r;
 670                         r = f;
 671                 } while (--round);
 672                 r = l;
 673                 l = f;
 674         } while (--count);
 675
 676         /* Do final permutation (inverse of IP). */
 677         *l_out  = fp_maskl[0][l >> 24]
 678                 | fp_maskl[1][(l >> 16) & 0xff]
 679                 | fp_maskl[2][(l >> 8) & 0xff]
 680                 | fp_maskl[3][l & 0xff]
 681                 | fp_maskl[4][r >> 24]
 682                 | fp_maskl[5][(r >> 16) & 0xff]
 683                 | fp_maskl[6][(r >> 8) & 0xff]
 684                 | fp_maskl[7][r & 0xff];
 685         *r_out  = fp_maskr[0][l >> 24]
 686                 | fp_maskr[1][(l >> 16) & 0xff]
 687                 | fp_maskr[2][(l >> 8) & 0xff]
 688                 | fp_maskr[3][l & 0xff]
 689                 | fp_maskr[4][r >> 24]
 690                 | fp_maskr[5][(r >> 16) & 0xff]
 691                 | fp_maskr[6][(r >> 8) & 0xff]
 692                 | fp_maskr[7][r & 0xff];
 693 }
 694
 695 #define DES_OUT_BUFSIZE 21
 696
 697 static void
 698 to64_msb_first(char *s, unsigned v)
 699 {
 700 #if 0
 701         *s++ = ascii64[(v >> 18) & 0x3f]; /* bits 23..18 */
 702         *s++ = ascii64[(v >> 12) & 0x3f]; /* bits 17..12 */
 703         *s++ = ascii64[(v >> 6) & 0x3f]; /* bits 11..6 */
 704         *s   = ascii64[v & 0x3f]; /* bits 5..0 */
 705 #endif
 706         *s++ = i64c(v >> 18); /* bits 23..18 */
 707         *s++ = i64c(v >> 12); /* bits 17..12 */
 708         *s++ = i64c(v >> 6); /* bits 11..6 */
 709         *s   = i64c(v); /* bits 5..0 */
 710 }
 711
 712 static char *
 713 NOINLINE
 714 des_crypt(struct des_ctx *ctx, char output[DES_OUT_BUFSIZE],
 715                 const unsigned char *key, const unsigned char *salt_str)
 716 {
 717         uint32_t salt, r0, r1, keybuf[2];
 718         uint8_t *q;
 719
 720         /* Bad salt? Mimic crypt() API - return NULL */
 721         if (!salt_str[0] || !salt_str[1])
 722                 return NULL;
 723
 724         /*
 725          * Copy the key, shifting each character up by one bit
 726          * and padding with zeros.
 727          */
 728         q = (uint8_t *)keybuf;
 729         while (q - (uint8_t *)keybuf != 8) {
 730                 *q = *key << 1;
 731                 if (*q)
 732                         key++;
 733                 q++;
 734         }
 735         des_setkey(ctx, (char *)keybuf);
 736
 737         /*
 738          * salt_str - 2 chars of salt (converted to 12 bits)
 739          * key - up to 8 characters
 740          */
 741         output[0] = salt_str[0];
 742         output[1] = salt_str[1];
 743         salt = (ascii_to_bin(salt_str[1]) << 6)
 744              |  ascii_to_bin(salt_str[0]);
 745         setup_salt(ctx, salt); /* set ctx->saltbits for do_des() */
 746
 747         /* Do it. */
 748         do_des(ctx, /*0, 0,*/ &r0, &r1, 25 /* count */);
 749
 750         /* Now encode the result. */
 751 #if 0
 752 {
 753         uint32_t l = (r0 >> 8);
 754         q = (uint8_t *)output + 2;
 755         *q++ = ascii64[(l >> 18) & 0x3f]; /* bits 31..26 of r0 */
 756         *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 25..20 of r0 */
 757         *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 19..14 of r0 */
 758         *q++ = ascii64[l & 0x3f]; /* bits 13..8 of r0 */
 759         l = ((r0 << 16) | (r1 >> 16));
 760         *q++ = ascii64[(l >> 18) & 0x3f]; /* bits 7..2 of r0 */
 761         *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 1..2 of r0 and 31..28 of r1 */
 762         *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 27..22 of r1 */
 763         *q++ = ascii64[l & 0x3f]; /* bits 21..16 of r1 */
 764         l = r1 << 2;
 765         *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 15..10 of r1 */
 766         *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 9..4 of r1 */
 767         *q++ = ascii64[l & 0x3f]; /* bits 3..0 of r1 + 00 */
 768         *q = 0;
 769 }
 770 #else
 771         /* Each call takes low-order 24 bits and stores 4 chars */
 772         /* bits 31..8 of r0 */
 773         to64_msb_first(output + 2, (r0 >> 8));
 774         /* bits 7..0 of r0 and 31..16 of r1 */
 775         to64_msb_first(output + 6, (r0 << 16) | (r1 >> 16));
 776         /* bits 15..0 of r1 and two zero bits (plus extra zero byte) */
 777         to64_msb_first(output + 10, (r1 << 8));
 778         /* extra zero byte is encoded as '.', fixing it */
 779         output[13] = '\0';
 780 #endif
 781
 782         return output;
 783 }
 784
 785 #undef USE_PRECOMPUTED_u_sbox
 786 #undef USE_REPETITIVE_SPEEDUP
 787 #undef USE_ip_mask
 788 #undef USE_de_keys
 789
 790 #undef C
 791 #undef init_perm
 792 #undef final_perm
 793 #undef m_sbox
 794 #undef D
 795 #undef const_ctx
 796 #undef saltbits
 797 #undef old_salt
 798 #undef old_rawkey0
 799 #undef old_rawkey1
 800 #undef un_pbox
 801 #undef inv_comp_perm
 802 #undef inv_key_perm
 803 #undef en_keysl
 804 #undef en_keysr
 805 #undef de_keysl
 806 #undef de_keysr
 807 #undef ip_maskl
 808 #undef ip_maskr
 809 #undef fp_maskl
 810 #undef fp_maskr
 811 #undef key_perm_maskl
 812 #undef key_perm_maskr
 813 #undef comp_maskl
 814 #undef comp_maskr
 815 #undef psbox