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 */ 68static 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 75static 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 82static 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 86static 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 97static 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 */ 140static 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 184static 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 189static 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 201static const uint8_t bits8[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 }; 202 203 204static int 205ascii_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. */ 226struct 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 238static struct const_des_ctx* 239const_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 307struct 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 352static struct des_ctx* 353des_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 486static void 487setup_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 509static void 510des_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 593static void 594do_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 699static void 700to64_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 714static char * 715NOINLINE 716des_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 821