chiark - git - mdw - termux-packages/blob - packages/libcrypt/crypt3.c

   1 /**************************************************************************
   2 *            Unix-like crypt(3) Algorithm for Password Encryption
   3 *
   4 *   File    : crypt3.c
   5 *   Purpose : Provides crypt(3) functionality to ANSI C compilers
   6 *             without a need for the crypt library.
   7 *   Author  : Michael Dipperstein
   8 *   Date    : November 3, 1998
   9 *
  10 ***************************************************************************
  11 *   The source in this file is heavily borrowed from the crypt3.c file
  12 *   found on several ftp sites on the Internet.  The original source
  13 *   claimed to be BSD, but was not distributed with any BSD license or
  14 *   copyright claims.  I am releasing the source that I have provided into
  15 *   public domain without any restrictions, warranties, or copyright
  16 *   claims of my own.
  17 *
  18 *   The code below has been cleaned and compiles correctly under, gcc,
  19 *   lcc, and Borland's bcc C compilers.  A bug involving the left and
  20 *   right halves of the encrypted data block in the widely published
  21 *   crypt3.c source has been fixed by this version.  All implicit register
  22 *   declarations have been removed, because they generated suboptimal code.
  23 *   All constant data has been explicitly declared as const and all
  24 *   declarations have been given a minimal scope, because I'm paranoid.
  25 *
  26 *   Caution: crypt() returns a pointer to static data.  I left it this way
  27 *            to maintain backward compatibility.  The downside is that
  28 *            successive calls will cause previous results to be lost.
  29 *            This can easily be changed with only minor modifications to
  30 *            the function crypt().
  31 **************************************************************************/
  32
  33 /* Initial permutation */
  34 static const char IP[] =
  35 {
  36     58, 50, 42, 34, 26, 18, 10, 2,
  37     60, 52, 44, 36, 28, 20, 12, 4,
  38     62, 54, 46, 38, 30, 22, 14, 6,
  39     64, 56, 48, 40, 32, 24, 16, 8,
  40     57, 49, 41, 33, 25, 17,  9, 1,
  41     59, 51, 43, 35, 27, 19, 11, 3,
  42     61, 53, 45, 37, 29, 21, 13, 5,
  43     63, 55, 47, 39, 31, 23, 15, 7,
  44 };
  45
  46 /* Final permutation, FP = IP^(-1) */
  47 static const char FP[] = {
  48     40, 8, 48, 16, 56, 24, 64, 32,
  49     39, 7, 47, 15, 55, 23, 63, 31,
  50     38, 6, 46, 14, 54, 22, 62, 30,
  51     37, 5, 45, 13, 53, 21, 61, 29,
  52     36, 4, 44, 12, 52, 20, 60, 28,
  53     35, 3, 43, 11, 51, 19, 59, 27,
  54     34, 2, 42, 10, 50, 18, 58, 26,
  55     33, 1, 41,  9, 49, 17, 57, 25,
  56 };
  57
  58 /**************************************************************************
  59 * Permuted-choice 1 from the key bits to yield C and D.
  60 * Note that bits 8,16... are left out:
  61 * They are intended for a parity check.
  62 **************************************************************************/
  63 static const char PC1_C[] =
  64 {
  65     57, 49, 41, 33, 25, 17,  9,
  66      1, 58, 50, 42, 34, 26, 18,
  67     10,  2, 59, 51, 43, 35, 27,
  68     19, 11,  3, 60, 52, 44, 36,
  69 };
  70
  71 static const char PC1_D[] =
  72 {
  73     63, 55, 47, 39, 31, 23, 15,
  74      7, 62, 54, 46, 38, 30, 22,
  75     14,  6, 61, 53, 45, 37, 29,
  76     21, 13,  5, 28, 20, 12,  4,
  77 };
  78
  79 /* Sequence of shifts used for the key schedule. */
  80 static const char shifts[] =
  81     {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
  82
  83 /**************************************************************************
  84 * Permuted-choice 2, to pick out the bits from the CD array that generate
  85 * the key schedule.
  86 **************************************************************************/
  87 static const char PC2_C[] =
  88 {
  89     14, 17, 11, 24,  1,  5,
  90      3, 28, 15,  6, 21, 10,
  91     23, 19, 12,  4, 26,  8,
  92     16,  7, 27, 20, 13,  2,
  93 };
  94
  95 static const char PC2_D[] =
  96 {
  97     41, 52, 31, 37, 47, 55,
  98     30, 40, 51, 45, 33, 48,
  99     44, 49, 39, 56, 34, 53,
 100     46, 42, 50, 36, 29, 32,
 101 };
 102
 103 /* The C and D arrays used to calculate the key schedule. */
 104 static char C[28];
 105 static char D[28];
 106
 107 /* The key schedule.  Generated from the key. */
 108 static char KS[16][48];
 109
 110 /* The E bit-selection table. */
 111 static char E[48];
 112 static const char e2[] =
 113 {
 114     32,  1,  2,  3,  4,  5,
 115      4,  5,  6,  7,  8,  9,
 116      8,  9, 10, 11, 12, 13,
 117     12, 13, 14, 15, 16, 17,
 118     16, 17, 18, 19, 20, 21,
 119     20, 21, 22, 23, 24, 25,
 120     24, 25, 26, 27, 28, 29,
 121     28, 29, 30, 31, 32,  1,
 122 };
 123
 124 /**************************************************************************
 125 * Function:    setkey
 126 *
 127 * Description: Set up the key schedule from the encryption key.
 128 *
 129 * Inputs:      char *key
 130 *              pointer to 64 character array.  Each character represents a
 131 *              bit in the key.
 132 *
 133 * Returns:     none
 134 **************************************************************************/
 135 void setkey(char *key)
 136 {
 137     int i, j, k, temp;
 138
 139     /**********************************************************************
 140     * First, generate C and D by permuting the key.  The low order bit of
 141     * each 8-bit char is not used, so C and D are only 28 bits apiece.
 142     **********************************************************************/
 143     for(i = 0; i < 28; i++)
 144     {
 145         C[i] = key[PC1_C[i] - 1];
 146         D[i] = key[PC1_D[i] - 1];
 147     }
 148
 149     /**********************************************************************
 150     * To generate Ki, rotate C and D according to schedule and pick up a
 151     * permutation using PC2.
 152     **********************************************************************/
 153     for(i = 0; i < 16; i++)
 154     {
 155         /* rotate */
 156         for(k = 0; k < shifts[i]; k++)
 157         {
 158             temp = C[0];
 159
 160             for(j = 0; j < 28 - 1; j++)
 161                 C[j] = C[j+1];
 162
 163             C[27] = temp;
 164             temp = D[0];
 165             for(j = 0; j < 28 - 1; j++)
 166                 D[j] = D[j+1];
 167
 168             D[27] = temp;
 169         }
 170
 171         /* get Ki. Note C and D are concatenated */
 172         for(j = 0; j < 24; j++)
 173         {
 174             KS[i][j] = C[PC2_C[j] - 1];
 175             KS[i][j + 24] = D[PC2_D[j] - 28 -1];
 176         }
 177     }
 178
 179     /* load E with the initial E bit selections */
 180     for(i=0; i < 48; i++)
 181         E[i] = e2[i];
 182 }
 183
 184 /**************************************************************************
 185 * The 8 selection functions. For some reason, they give a 0-origin
 186 * index, unlike everything else.
 187 **************************************************************************/
 188
 189 static const char S[8][64] =
 190 {
 191     {
 192         14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
 193          0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
 194          4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
 195         15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13
 196     },
 197
 198     {
 199         15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
 200          3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
 201          0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
 202         13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9
 203     },
 204
 205     {
 206         10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
 207         13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
 208         13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
 209          1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12
 210     },
 211
 212     {
 213          7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
 214         13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
 215         10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
 216          3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14
 217     },
 218
 219     {
 220          2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
 221         14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
 222          4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
 223         11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3
 224     },
 225
 226     {
 227         12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
 228         10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
 229          9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
 230          4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13
 231     },
 232
 233     {
 234          4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
 235         13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
 236          1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
 237          6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12
 238     },
 239
 240     {
 241         13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
 242          1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
 243          7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
 244          2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
 245     }
 246 };
 247
 248 /**************************************************************************
 249 * P is a permutation on the selected combination of the current L and key.
 250 **************************************************************************/
 251 static const char P[] =
 252 {
 253     16,  7, 20, 21,
 254     29, 12, 28, 17,
 255      1, 15, 23, 26,
 256      5, 18, 31, 10,
 257      2,  8, 24, 14,
 258     32, 27,  3,  9,
 259     19, 13, 30,  6,
 260     22, 11,  4, 25,
 261 };
 262
 263 /* The combination of the key and the input, before selection. */
 264 static char preS[48];
 265
 266 /**************************************************************************
 267 * Function:    encrypt
 268 *
 269 * Description: Uses DES to encrypt a 64 bit block of data.  Requires
 270 *              setkey to be invoked with the encryption key before it may
 271 *              be used.  The results of the encryption are stored in block.
 272 *
 273 * Inputs:      char *block
 274 *              pointer to 64 character array.  Each character represents a
 275 *              bit in the data block.
 276 *
 277 * Returns:     none
 278 **************************************************************************/
 279 void encrypt(char *block)
 280 {
 281     int i, ii, temp, j, k;
 282
 283     char left[32], right[32]; /* block in two halves */
 284     char old[32];
 285     char f[32];
 286
 287     /* First, permute the bits in the input */
 288     for(j = 0; j < 32; j++)
 289         left[j] = block[IP[j] - 1];
 290
 291     for(;j < 64; j++)
 292         right[j - 32] = block[IP[j] - 1];
 293
 294     /* Perform an encryption operation 16 times. */
 295     for(ii= 0; ii < 16; ii++)
 296     {
 297         i = ii;
 298         /* Save the right array, which will be the new left. */
 299         for(j = 0; j < 32; j++)
 300             old[j] = right[j];
 301
 302         /******************************************************************
 303         * Expand right to 48 bits using the E selector and
 304         * exclusive-or with the current key bits.
 305         ******************************************************************/
 306         for(j =0 ; j < 48; j++)
 307             preS[j] = right[E[j] - 1] ^ KS[i][j];
 308
 309         /******************************************************************
 310         * The pre-select bits are now considered in 8 groups of 6 bits ea.
 311         * The 8 selection functions map these 6-bit quantities into 4-bit
 312         * quantities and the results are permuted to make an f(R, K).
 313         * The indexing into the selection functions is peculiar;
 314         * it could be simplified by rewriting the tables.
 315         ******************************************************************/
 316         for(j = 0; j < 8; j++)
 317         {
 318             temp = 6 * j;
 319             k = S[j][(preS[temp + 0] << 5) +
 320                 (preS[temp + 1] << 3) +
 321                 (preS[temp + 2] << 2) +
 322                 (preS[temp + 3] << 1) +
 323                 (preS[temp + 4] << 0) +
 324                 (preS[temp + 5] << 4)];
 325
 326             temp = 4 * j;
 327
 328             f[temp + 0] = (k >> 3) & 01;
 329             f[temp + 1] = (k >> 2) & 01;
 330             f[temp + 2] = (k >> 1) & 01;
 331             f[temp + 3] = (k >> 0) & 01;
 332         }
 333
 334         /******************************************************************
 335         * The new right is left ^ f(R, K).
 336         * The f here has to be permuted first, though.
 337         ******************************************************************/
 338         for(j = 0; j < 32; j++)
 339             right[j] = left[j] ^ f[P[j] - 1];
 340
 341         /* Finally, the new left (the original right) is copied back. */
 342         for(j = 0; j < 32; j++)
 343             left[j] = old[j];
 344     }
 345
 346     /* The output left and right are reversed. */
 347     for(j = 0; j < 32; j++)
 348     {
 349         temp = left[j];
 350         left[j] = right[j];
 351         right[j] = temp;
 352     }
 353
 354     /* The final output gets the inverse permutation of the very original. */
 355     for(j = 0; j < 64; j++)
 356     {
 357         i = FP[j];
 358         if (i < 33)
 359                 block[j] = left[FP[j] - 1];
 360         else
 361                 block[j] = right[FP[j] - 33];
 362     }
 363 }
 364
 365 /**************************************************************************
 366 * Function:    crypt
 367 *
 368 * Description: Clone of Unix crypt(3) function.
 369 *
 370 * Inputs:      char *pw
 371 *              pointer to 8 character encryption key (user password)
 372 *              char *salt
 373 *              pointer to 2 character salt used to modify the DES results.
 374 *
 375 * Returns:     Pointer to static array containing the salt concatenated
 376 *              on to the encrypted results.  Same as stored in passwd file.
 377 **************************************************************************/
 378 char *crypt(char *pw, char *salt)
 379 {
 380     int i, j, temp;
 381     char c,
 382          block[66];             /* 1st store key, then results */
 383     static char iobuf[16];      /* encrypted results */
 384
 385     for(i = 0; i < 66; i++)
 386         block[i] = 0;
 387
 388     /* break pw into 64 bits */
 389     for(i = 0, c = *pw; c && (i < 64); i++)
 390     {
 391         for(j = 0; j < 7; j++, i++)
 392             block[i] = (c >> (6 - j)) & 01;
 393         pw++;
 394         c = *pw;
 395     }
 396
 397     /* set key based on pw */
 398     setkey(block);
 399
 400     for(i = 0; i < 66; i++)
 401         block[i] = 0;
 402
 403     for(i = 0; i < 2; i++)
 404     {
 405         /* store salt at beginning of results */
 406         c = *salt++;
 407         iobuf[i] = c;
 408
 409         if(c > 'Z')
 410             c -= 6;
 411
 412         if(c > '9')
 413             c -= 7;
 414
 415         c -= '.';
 416
 417         /* use salt to effect the E-bit selection */
 418         for(j = 0; j < 6; j++)
 419         {
 420             if((c >> j) & 01)
 421             {
 422                 temp = E[6 * i + j];
 423                 E[6 * i +j] = E[6 * i + j + 24];
 424                 E[6 * i + j + 24] = temp;
 425             }
 426         }
 427     }
 428
 429     /* call DES encryption 25 times using pw as key and initial data = 0 */
 430     for(i = 0; i < 25; i++)
 431         encrypt(block);
 432
 433     /* format encrypted block for standard crypt(3) output */
 434     for(i=0; i < 11; i++)
 435     {
 436         c = 0;
 437         for(j = 0; j < 6; j++)
 438         {
 439             c <<= 1;
 440             c |= block[6 * i + j];
 441         }
 442
 443         c += '.';
 444         if(c > '9')
 445             c += 7;
 446
 447         if(c > 'Z')
 448             c += 6;
 449
 450         iobuf[i + 2] = c;
 451     }
 452
 453     iobuf[i + 2] = '\0';
 454
 455     /* prevent premature NULL terminator */
 456     if(iobuf[1] == '\0')
 457         iobuf[1] = iobuf[0];
 458
 459     return(iobuf);
 460 }