1 /* $NetBSD: crypt.c,v 1.41 2024/07/23 22:37:11 riastradh Exp $ */ 2 3 /* 4 * Copyright (c) 1989, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Tom Truscott. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 #include <sys/cdefs.h> 36 #if !defined(lint) 37 #if 0 38 static char sccsid[] = "@(#)crypt.c 8.1.1.1 (Berkeley) 8/18/93"; 39 #else 40 __RCSID("$NetBSD: crypt.c,v 1.41 2024/07/23 22:37:11 riastradh Exp $"); 41 #endif 42 #endif /* not lint */ 43 44 #include <limits.h> 45 #include <pwd.h> 46 #include <stdlib.h> 47 #include <string.h> /* for strcmp */ 48 #include <unistd.h> 49 #if defined(DEBUG) || defined(MAIN) || defined(UNIT_TEST) 50 #include <stdio.h> 51 #endif 52 53 #include "crypt.h" 54 55 /* 56 * UNIX password, and DES, encryption. 57 * By Tom Truscott, trt@rti.rti.org, 58 * from algorithms by Robert W. Baldwin and James Gillogly. 59 * 60 * References: 61 * "Mathematical Cryptology for Computer Scientists and Mathematicians," 62 * by Wayne Patterson, 1987, ISBN 0-8476-7438-X. 63 * 64 * "Password Security: A Case History," R. Morris and Ken Thompson, 65 * Communications of the ACM, vol. 22, pp. 594-597, Nov. 1979. 66 * 67 * "DES will be Totally Insecure within Ten Years," M.E. Hellman, 68 * IEEE Spectrum, vol. 16, pp. 32-39, July 1979. 69 */ 70 71 /* ===== Configuration ==================== */ 72 73 /* 74 * define "MUST_ALIGN" if your compiler cannot load/store 75 * long integers at arbitrary (e.g. odd) memory locations. 76 * (Either that or never pass unaligned addresses to des_cipher!) 77 */ 78 #if !defined(__vax__) && !defined(__i386__) 79 #define MUST_ALIGN 80 #endif 81 82 #ifdef CHAR_BITS 83 #if CHAR_BITS != 8 84 #error C_block structure assumes 8 bit characters 85 #endif 86 #endif 87 88 /* 89 * define "B64" to be the declaration for a 64 bit integer. 90 * XXX this feature is currently unused, see "endian" comment below. 91 */ 92 #if defined(cray) 93 #define B64 long 94 #endif 95 #if defined(convex) 96 #define B64 long long 97 #endif 98 99 /* 100 * define "LARGEDATA" to get faster permutations, by using about 72 kilobytes 101 * of lookup tables. This speeds up des_setkey() and des_cipher(), but has 102 * little effect on crypt(). 103 */ 104 #if defined(notdef) 105 #define LARGEDATA 106 #endif 107 108 /* compile with "-DSTATIC=void" when profiling */ 109 #ifndef STATIC 110 #define STATIC static void 111 #endif 112 113 /* ==================================== */ 114 115 /* 116 * Cipher-block representation (Bob Baldwin): 117 * 118 * DES operates on groups of 64 bits, numbered 1..64 (sigh). One 119 * representation is to store one bit per byte in an array of bytes. Bit N of 120 * the NBS spec is stored as the LSB of the Nth byte (index N-1) in the array. 121 * Another representation stores the 64 bits in 8 bytes, with bits 1..8 in the 122 * first byte, 9..16 in the second, and so on. The DES spec apparently has 123 * bit 1 in the MSB of the first byte, but that is particularly noxious so we 124 * bit-reverse each byte so that bit 1 is the LSB of the first byte, bit 8 is 125 * the MSB of the first byte. Specifically, the 64-bit input data and key are 126 * converted to LSB format, and the output 64-bit block is converted back into 127 * MSB format. 128 * 129 * DES operates internally on groups of 32 bits which are expanded to 48 bits 130 * by permutation E and shrunk back to 32 bits by the S boxes. To speed up 131 * the computation, the expansion is applied only once, the expanded 132 * representation is maintained during the encryption, and a compression 133 * permutation is applied only at the end. To speed up the S-box lookups, 134 * the 48 bits are maintained as eight 6 bit groups, one per byte, which 135 * directly feed the eight S-boxes. Within each byte, the 6 bits are the 136 * most significant ones. The low two bits of each byte are zero. (Thus, 137 * bit 1 of the 48 bit E expansion is stored as the "4"-valued bit of the 138 * first byte in the eight byte representation, bit 2 of the 48 bit value is 139 * the "8"-valued bit, and so on.) In fact, a combined "SPE"-box lookup is 140 * used, in which the output is the 64 bit result of an S-box lookup which 141 * has been permuted by P and expanded by E, and is ready for use in the next 142 * iteration. Two 32-bit wide tables, SPE[0] and SPE[1], are used for this 143 * lookup. Since each byte in the 48 bit path is a multiple of four, indexed 144 * lookup of SPE[0] and SPE[1] is simple and fast. The key schedule and 145 * "salt" are also converted to this 8*(6+2) format. The SPE table size is 146 * 8*64*8 = 4K bytes. 147 * 148 * To speed up bit-parallel operations (such as XOR), the 8 byte 149 * representation is "union"ed with 32 bit values "i0" and "i1", and, on 150 * machines which support it, a 64 bit value "b64". This data structure, 151 * "C_block", has two problems. First, alignment restrictions must be 152 * honored. Second, the byte-order (e.g. little-endian or big-endian) of 153 * the architecture becomes visible. 154 * 155 * The byte-order problem is unfortunate, since on the one hand it is good 156 * to have a machine-independent C_block representation (bits 1..8 in the 157 * first byte, etc.), and on the other hand it is good for the LSB of the 158 * first byte to be the LSB of i0. We cannot have both these things, so we 159 * currently use the "little-endian" representation and avoid any multi-byte 160 * operations that depend on byte order. This largely precludes use of the 161 * 64-bit datatype since the relative order of i0 and i1 are unknown. It 162 * also inhibits grouping the SPE table to look up 12 bits at a time. (The 163 * 12 bits can be stored in a 16-bit field with 3 low-order zeroes and 1 164 * high-order zero, providing fast indexing into a 64-bit wide SPE.) On the 165 * other hand, 64-bit datatypes are currently rare, and a 12-bit SPE lookup 166 * requires a 128 kilobyte table, so perhaps this is not a big loss. 167 * 168 * Permutation representation (Jim Gillogly): 169 * 170 * A transformation is defined by its effect on each of the 8 bytes of the 171 * 64-bit input. For each byte we give a 64-bit output that has the bits in 172 * the input distributed appropriately. The transformation is then the OR 173 * of the 8 sets of 64-bits. This uses 8*256*8 = 16K bytes of storage for 174 * each transformation. Unless LARGEDATA is defined, however, a more compact 175 * table is used which looks up 16 4-bit "chunks" rather than 8 8-bit chunks. 176 * The smaller table uses 16*16*8 = 2K bytes for each transformation. This 177 * is slower but tolerable, particularly for password encryption in which 178 * the SPE transformation is iterated many times. The small tables total 9K 179 * bytes, the large tables total 72K bytes. 180 * 181 * The transformations used are: 182 * IE3264: MSB->LSB conversion, initial permutation, and expansion. 183 * This is done by collecting the 32 even-numbered bits and applying 184 * a 32->64 bit transformation, and then collecting the 32 odd-numbered 185 * bits and applying the same transformation. Since there are only 186 * 32 input bits, the IE3264 transformation table is half the size of 187 * the usual table. 188 * CF6464: Compression, final permutation, and LSB->MSB conversion. 189 * This is done by two trivial 48->32 bit compressions to obtain 190 * a 64-bit block (the bit numbering is given in the "CIFP" table) 191 * followed by a 64->64 bit "cleanup" transformation. (It would 192 * be possible to group the bits in the 64-bit block so that 2 193 * identical 32->32 bit transformations could be used instead, 194 * saving a factor of 4 in space and possibly 2 in time, but 195 * byte-ordering and other complications rear their ugly head. 196 * Similar opportunities/problems arise in the key schedule 197 * transforms.) 198 * PC1ROT: MSB->LSB, PC1 permutation, rotate, and PC2 permutation. 199 * This admittedly baroque 64->64 bit transformation is used to 200 * produce the first code (in 8*(6+2) format) of the key schedule. 201 * PC2ROT[0]: Inverse PC2 permutation, rotate, and PC2 permutation. 202 * It would be possible to define 15 more transformations, each 203 * with a different rotation, to generate the entire key schedule. 204 * To save space, however, we instead permute each code into the 205 * next by using a transformation that "undoes" the PC2 permutation, 206 * rotates the code, and then applies PC2. Unfortunately, PC2 207 * transforms 56 bits into 48 bits, dropping 8 bits, so PC2 is not 208 * invertible. We get around that problem by using a modified PC2 209 * which retains the 8 otherwise-lost bits in the unused low-order 210 * bits of each byte. The low-order bits are cleared when the 211 * codes are stored into the key schedule. 212 * PC2ROT[1]: Same as PC2ROT[0], but with two rotations. 213 * This is faster than applying PC2ROT[0] twice, 214 * 215 * The Bell Labs "salt" (Bob Baldwin): 216 * 217 * The salting is a simple permutation applied to the 48-bit result of E. 218 * Specifically, if bit i (1 <= i <= 24) of the salt is set then bits i and 219 * i+24 of the result are swapped. The salt is thus a 24 bit number, with 220 * 16777216 possible values. (The original salt was 12 bits and could not 221 * swap bits 13..24 with 36..48.) 222 * 223 * It is possible, but ugly, to warp the SPE table to account for the salt 224 * permutation. Fortunately, the conditional bit swapping requires only 225 * about four machine instructions and can be done on-the-fly with about an 226 * 8% performance penalty. 227 */ 228 229 typedef union { 230 unsigned char b[8]; 231 struct { 232 int32_t i0; 233 int32_t i1; 234 } b32; 235 #if defined(B64) 236 B64 b64; 237 #endif 238 } C_block; 239 240 /* 241 * Convert twenty-four-bit long in host-order 242 * to six bits (and 2 low-order zeroes) per char little-endian format. 243 */ 244 #define TO_SIX_BIT(rslt, src) { \ 245 C_block cvt; \ 246 cvt.b[0] = src; src >>= 6; \ 247 cvt.b[1] = src; src >>= 6; \ 248 cvt.b[2] = src; src >>= 6; \ 249 cvt.b[3] = src; \ 250 rslt = (cvt.b32.i0 & 0x3f3f3f3fL) << 2; \ 251 } 252 253 /* 254 * These macros may someday permit efficient use of 64-bit integers. 255 */ 256 #define ZERO(d,d0,d1) d0 = 0, d1 = 0 257 #define LOAD(d,d0,d1,bl) d0 = (bl).b32.i0, d1 = (bl).b32.i1 258 #define LOADREG(d,d0,d1,s,s0,s1) d0 = s0, d1 = s1 259 #define OR(d,d0,d1,bl) d0 |= (bl).b32.i0, d1 |= (bl).b32.i1 260 #define STORE(s,s0,s1,bl) (bl).b32.i0 = s0, (bl).b32.i1 = s1 261 #define DCL_BLOCK(d,d0,d1) int32_t d0, d1 262 263 #if defined(LARGEDATA) 264 /* Waste memory like crazy. Also, do permutations in line */ 265 #define LGCHUNKBITS 3 266 #define CHUNKBITS (1<<LGCHUNKBITS) 267 #define PERM6464(d,d0,d1,cpp,p) \ 268 LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]); \ 269 OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]); \ 270 OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]); \ 271 OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]); \ 272 OR (d,d0,d1,(p)[(4<<CHUNKBITS)+(cpp)[4]]); \ 273 OR (d,d0,d1,(p)[(5<<CHUNKBITS)+(cpp)[5]]); \ 274 OR (d,d0,d1,(p)[(6<<CHUNKBITS)+(cpp)[6]]); \ 275 OR (d,d0,d1,(p)[(7<<CHUNKBITS)+(cpp)[7]]); 276 #define PERM3264(d,d0,d1,cpp,p) \ 277 LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]); \ 278 OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]); \ 279 OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]); \ 280 OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]); 281 #else 282 /* "small data" */ 283 #define LGCHUNKBITS 2 284 #define CHUNKBITS (1<<LGCHUNKBITS) 285 #define PERM6464(d,d0,d1,cpp,p) \ 286 { C_block tblk; permute(cpp,&tblk,p,8); LOAD (d,d0,d1,tblk); } 287 #define PERM3264(d,d0,d1,cpp,p) \ 288 { C_block tblk; permute(cpp,&tblk,p,4); LOAD (d,d0,d1,tblk); } 289 #endif /* LARGEDATA */ 290 291 STATIC init_des(void); 292 STATIC init_perm(C_block [64/CHUNKBITS][1<<CHUNKBITS], 293 const unsigned char [64], int, int); 294 #ifndef LARGEDATA 295 STATIC permute(const unsigned char *, C_block *, C_block *, int); 296 #endif 297 #ifdef DEBUG 298 STATIC prtab(const char *, unsigned char *, int); 299 #endif 300 301 302 #ifndef LARGEDATA 303 STATIC 304 permute(const unsigned char *cp, C_block *out, C_block *p, int chars_in) 305 { 306 DCL_BLOCK(D,D0,D1); 307 C_block *tp; 308 int t; 309 310 ZERO(D,D0,D1); 311 do { 312 t = *cp++; 313 tp = &p[t&0xf]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS); 314 tp = &p[t>>4]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS); 315 } while (--chars_in > 0); 316 STORE(D,D0,D1,*out); 317 } 318 #endif /* LARGEDATA */ 319 320 321 /* ===== (mostly) Standard DES Tables ==================== */ 322 323 static const unsigned char IP[] = { /* initial permutation */ 324 58, 50, 42, 34, 26, 18, 10, 2, 325 60, 52, 44, 36, 28, 20, 12, 4, 326 62, 54, 46, 38, 30, 22, 14, 6, 327 64, 56, 48, 40, 32, 24, 16, 8, 328 57, 49, 41, 33, 25, 17, 9, 1, 329 59, 51, 43, 35, 27, 19, 11, 3, 330 61, 53, 45, 37, 29, 21, 13, 5, 331 63, 55, 47, 39, 31, 23, 15, 7, 332 }; 333 334 /* The final permutation is the inverse of IP - no table is necessary */ 335 336 static const unsigned char ExpandTr[] = { /* expansion operation */ 337 32, 1, 2, 3, 4, 5, 338 4, 5, 6, 7, 8, 9, 339 8, 9, 10, 11, 12, 13, 340 12, 13, 14, 15, 16, 17, 341 16, 17, 18, 19, 20, 21, 342 20, 21, 22, 23, 24, 25, 343 24, 25, 26, 27, 28, 29, 344 28, 29, 30, 31, 32, 1, 345 }; 346 347 static const unsigned char PC1[] = { /* permuted choice table 1 */ 348 57, 49, 41, 33, 25, 17, 9, 349 1, 58, 50, 42, 34, 26, 18, 350 10, 2, 59, 51, 43, 35, 27, 351 19, 11, 3, 60, 52, 44, 36, 352 353 63, 55, 47, 39, 31, 23, 15, 354 7, 62, 54, 46, 38, 30, 22, 355 14, 6, 61, 53, 45, 37, 29, 356 21, 13, 5, 28, 20, 12, 4, 357 }; 358 359 static const unsigned char Rotates[] = {/* PC1 rotation schedule */ 360 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 361 }; 362 363 /* note: each "row" of PC2 is left-padded with bits that make it invertible */ 364 static const unsigned char PC2[] = { /* permuted choice table 2 */ 365 9, 18, 14, 17, 11, 24, 1, 5, 366 22, 25, 3, 28, 15, 6, 21, 10, 367 35, 38, 23, 19, 12, 4, 26, 8, 368 43, 54, 16, 7, 27, 20, 13, 2, 369 370 0, 0, 41, 52, 31, 37, 47, 55, 371 0, 0, 30, 40, 51, 45, 33, 48, 372 0, 0, 44, 49, 39, 56, 34, 53, 373 0, 0, 46, 42, 50, 36, 29, 32, 374 }; 375 376 static const unsigned char S[8][64] = { /* 48->32 bit substitution tables */ 377 /* S[1] */ 378 { 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, 379 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8, 380 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0, 381 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13 }, 382 /* S[2] */ 383 { 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10, 384 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5, 385 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15, 386 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9 }, 387 /* S[3] */ 388 { 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8, 389 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1, 390 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7, 391 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12 }, 392 /* S[4] */ 393 { 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15, 394 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9, 395 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4, 396 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14 }, 397 /* S[5] */ 398 { 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9, 399 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6, 400 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14, 401 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3 }, 402 /* S[6] */ 403 { 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11, 404 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8, 405 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6, 406 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13 }, 407 /* S[7] */ 408 { 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1, 409 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6, 410 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2, 411 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12 }, 412 /* S[8] */ 413 { 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7, 414 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2, 415 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8, 416 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11 } 417 }; 418 419 static const unsigned char P32Tr[] = { /* 32-bit permutation function */ 420 16, 7, 20, 21, 421 29, 12, 28, 17, 422 1, 15, 23, 26, 423 5, 18, 31, 10, 424 2, 8, 24, 14, 425 32, 27, 3, 9, 426 19, 13, 30, 6, 427 22, 11, 4, 25, 428 }; 429 430 static const unsigned char CIFP[] = { /* compressed/interleaved permutation */ 431 1, 2, 3, 4, 17, 18, 19, 20, 432 5, 6, 7, 8, 21, 22, 23, 24, 433 9, 10, 11, 12, 25, 26, 27, 28, 434 13, 14, 15, 16, 29, 30, 31, 32, 435 436 33, 34, 35, 36, 49, 50, 51, 52, 437 37, 38, 39, 40, 53, 54, 55, 56, 438 41, 42, 43, 44, 57, 58, 59, 60, 439 45, 46, 47, 48, 61, 62, 63, 64, 440 }; 441 442 static const unsigned char itoa64[] = /* 0..63 => ascii-64 */ 443 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 444 445 446 /* ===== Tables that are initialized at run time ==================== */ 447 448 449 /* Initial key schedule permutation */ 450 static C_block PC1ROT[64/CHUNKBITS][1<<CHUNKBITS]; 451 452 /* Subsequent key schedule rotation permutations */ 453 static C_block PC2ROT[2][64/CHUNKBITS][1<<CHUNKBITS]; 454 455 /* Initial permutation/expansion table */ 456 static C_block IE3264[32/CHUNKBITS][1<<CHUNKBITS]; 457 458 /* Table that combines the S, P, and E operations. */ 459 static int32_t SPE[2][8][64]; 460 461 /* compressed/interleaved => final permutation table */ 462 static C_block CF6464[64/CHUNKBITS][1<<CHUNKBITS]; 463 464 465 /* ==================================== */ 466 467 468 static C_block constdatablock; /* encryption constant */ 469 static char cryptresult[1+4+4+11+1]; /* encrypted result */ 470 471 /* 472 * We match the behavior of UFC-crypt on systems where "char" is signed by 473 * default (the majority), regardless of char's signedness on our system. 474 */ 475 static inline int 476 ascii_to_bin(char ch) 477 { 478 signed char sch = ch; 479 int retval; 480 481 if (sch >= 'a') 482 retval = sch - ('a' - 38); 483 else if (sch >= 'A') 484 retval = sch - ('A' - 12); 485 else 486 retval = sch - '.'; 487 488 return retval & 0x3f; 489 } 490 491 /* 492 * When we choose to "support" invalid salts, nevertheless disallow those 493 * containing characters that would violate the passwd file format. 494 */ 495 static inline int 496 ascii_is_unsafe(char ch) 497 { 498 return !ch || ch == '\n' || ch == ':'; 499 } 500 501 /* 502 * We extract the scheme from setting str to allow for 503 * full scheme name comparison 504 * Updated to reflect alc suggestion(s) 505 * 506 * returns boolean 0 on failure, 1 on success, 507 */ 508 static int 509 nondes_scheme_substr(const char * setting,char * scheme, unsigned int len) 510 { 511 const char * start; 512 const char * sep; 513 514 /* initialize head pointer */ 515 start = setting; 516 517 /* clear out scheme buffer regardless of result */ 518 memset(scheme, 0, len); 519 520 /* make sure we are working on non-des scheme string */ 521 if (*start != _PASSWORD_NONDES) { 522 return 0; 523 } 524 525 /* increment passed initial _PASSWORD_NONDES */ 526 start++; 527 528 if ((sep = memchr(start, _PASSWORD_NONDES,len-1)) == NULL) { 529 return 0; 530 } 531 532 /* if empty string, we are done */ 533 if (sep == start) { 534 return 1; 535 } 536 537 /* copy scheme substr to buffer */ 538 memcpy(scheme, start, (size_t)(sep - start)); 539 540 return 1; 541 } 542 543 /* 544 * Return a pointer to static data consisting of the "setting" 545 * followed by an encryption produced by the "key" and "setting". 546 */ 547 static char * 548 __crypt(const char *key, const char *setting) 549 { 550 char *encp; 551 char scheme[12]; 552 int32_t i; 553 int t; 554 int r; 555 int32_t salt; 556 int num_iter, salt_size; 557 C_block keyblock, rsltblock; 558 559 /* Non-DES encryption schemes hook in here. */ 560 if (setting[0] == _PASSWORD_NONDES) { 561 r = nondes_scheme_substr( 562 setting, scheme, sizeof(scheme)); 563 564 /* return NULL if we are unable to extract substring */ 565 if (!r) { 566 return NULL; 567 } 568 569 /* $2a$ found in bcrypt.c:encode_salt */ 570 if (strcmp(scheme, "2a") == 0) { 571 return (__bcrypt(key, setting)); 572 } else if (strcmp(scheme, "sha1") == 0) { 573 /* $sha1$ found in crypt.h:SHA1_MAGIC */ 574 return (__crypt_sha1(key, setting)); 575 } else if (strcmp(scheme, "1") == 0) { 576 /* $1$ found in pw_gensalt.c:__gensalt_md5 */ 577 return (__md5crypt(key, setting)); 578 #ifdef HAVE_ARGON2 579 /* explicit argon2 variant */ 580 } else if (strcmp(scheme, "argon2id") == 0) { 581 /* $argon2id$ found in pw_gensalt.c:__gensalt_argon2 */ 582 return (__crypt_argon2(key, setting)); 583 } else if (strcmp(scheme, "argon2i") == 0) { 584 /* $argon2i$ found in pw_gensalt.c:__gensalt_argon2 */ 585 return (__crypt_argon2(key, setting)); 586 } else if (strcmp(scheme, "argon2d") == 0) { 587 /* $argon2d$ found in pw_gensalt.c:__gensalt_argon2 */ 588 return (__crypt_argon2(key, setting)); 589 #endif /* HAVE_ARGON2 */ 590 } else { 591 /* invalid scheme, including empty string */ 592 return NULL; 593 } 594 } 595 /* End non-DES handling */ 596 597 for (i = 0; i < 8; i++) { 598 if ((t = 2*(unsigned char)(*key)) != 0) 599 key++; 600 keyblock.b[i] = t; 601 } 602 if (des_setkey((char *)keyblock.b)) 603 return (NULL); 604 605 encp = &cryptresult[0]; 606 switch (*setting) { 607 case _PASSWORD_EFMT1: 608 /* 609 * Involve the rest of the password 8 characters at a time. 610 */ 611 while (*key) { 612 if (des_cipher((char *)(void *)&keyblock, 613 (char *)(void *)&keyblock, 0L, 1)) 614 return (NULL); 615 for (i = 0; i < 8; i++) { 616 if ((t = 2*(unsigned char)(*key)) != 0) 617 key++; 618 keyblock.b[i] ^= t; 619 } 620 if (des_setkey((char *)keyblock.b)) 621 return (NULL); 622 } 623 624 *encp++ = *setting++; 625 626 /* get iteration count */ 627 num_iter = 0; 628 for (i = 4; --i >= 0; ) { 629 int value = ascii_to_bin(setting[i]); 630 if (itoa64[value] != setting[i]) 631 return NULL; 632 encp[i] = setting[i]; 633 num_iter = (num_iter << 6) | value; 634 } 635 if (num_iter == 0) 636 return NULL; 637 setting += 4; 638 encp += 4; 639 salt_size = 4; 640 break; 641 default: 642 num_iter = 25; 643 salt_size = 2; 644 if (ascii_is_unsafe(setting[0]) || ascii_is_unsafe(setting[1])) 645 return NULL; 646 } 647 648 salt = 0; 649 for (i = salt_size; --i >= 0; ) { 650 int value = ascii_to_bin(setting[i]); 651 if (salt_size > 2 && itoa64[value] != setting[i]) 652 return NULL; 653 encp[i] = setting[i]; 654 salt = (salt << 6) | value; 655 } 656 encp += salt_size; 657 if (des_cipher((char *)(void *)&constdatablock, 658 (char *)(void *)&rsltblock, salt, num_iter)) 659 return (NULL); 660 661 /* 662 * Encode the 64 cipher bits as 11 ascii characters. 663 */ 664 i = ((int32_t)((rsltblock.b[0]<<8) | rsltblock.b[1])<<8) | 665 rsltblock.b[2]; 666 encp[3] = itoa64[i&0x3f]; i >>= 6; 667 encp[2] = itoa64[i&0x3f]; i >>= 6; 668 encp[1] = itoa64[i&0x3f]; i >>= 6; 669 encp[0] = itoa64[i]; encp += 4; 670 i = ((int32_t)((rsltblock.b[3]<<8) | rsltblock.b[4])<<8) | 671 rsltblock.b[5]; 672 encp[3] = itoa64[i&0x3f]; i >>= 6; 673 encp[2] = itoa64[i&0x3f]; i >>= 6; 674 encp[1] = itoa64[i&0x3f]; i >>= 6; 675 encp[0] = itoa64[i]; encp += 4; 676 i = ((int32_t)((rsltblock.b[6])<<8) | rsltblock.b[7])<<2; 677 encp[2] = itoa64[i&0x3f]; i >>= 6; 678 encp[1] = itoa64[i&0x3f]; i >>= 6; 679 encp[0] = itoa64[i]; 680 681 encp[3] = 0; 682 683 return (cryptresult); 684 } 685 686 char * 687 crypt(const char *key, const char *salt) 688 { 689 char *res = __crypt(key, salt); 690 691 if (res) 692 return res; 693 /* How do I handle errors ? Return "*0" or "*1" */ 694 return __UNCONST(salt[0] == '*' && salt[1] == '0' ? "*1" : "*0"); 695 } 696 697 /* 698 * The Key Schedule, filled in by des_setkey() or setkey(). 699 */ 700 #define KS_SIZE 16 701 static C_block KS[KS_SIZE]; 702 703 /* 704 * Set up the key schedule from the key. 705 */ 706 int 707 des_setkey(const char *key) 708 { 709 DCL_BLOCK(K, K0, K1); 710 C_block *help, *ptabp; 711 int i; 712 static int des_ready = 0; 713 714 if (!des_ready) { 715 init_des(); 716 des_ready = 1; 717 } 718 719 PERM6464(K,K0,K1,(const unsigned char *)key,(C_block *)PC1ROT); 720 help = &KS[0]; 721 STORE(K&~0x03030303L, K0&~0x03030303L, K1, *help); 722 for (i = 1; i < 16; i++) { 723 help++; 724 STORE(K,K0,K1,*help); 725 ptabp = (C_block *)PC2ROT[Rotates[i]-1]; 726 PERM6464(K,K0,K1,(const unsigned char *)help,ptabp); 727 STORE(K&~0x03030303L, K0&~0x03030303L, K1, *help); 728 } 729 return (0); 730 } 731 732 /* 733 * Encrypt (or decrypt if num_iter < 0) the 8 chars at "in" with abs(num_iter) 734 * iterations of DES, using the given 24-bit salt and the pre-computed key 735 * schedule, and store the resulting 8 chars at "out" (in == out is permitted). 736 * 737 * NOTE: the performance of this routine is critically dependent on your 738 * compiler and machine architecture. 739 */ 740 int 741 des_cipher(const char *in, char *out, long salt, int num_iter) 742 { 743 /* variables that we want in registers, most important first */ 744 #if defined(pdp11) 745 int j; 746 #endif 747 int32_t L0, L1, R0, R1, k; 748 C_block *kp; 749 int ks_inc, loop_count; 750 C_block B; 751 752 L0 = salt; 753 TO_SIX_BIT(salt, L0); /* convert to 4*(6+2) format */ 754 755 #if defined(__vax__) || defined(pdp11) 756 salt = ~salt; /* "x &~ y" is faster than "x & y". */ 757 #define SALT (~salt) 758 #else 759 #define SALT salt 760 #endif 761 762 #if defined(MUST_ALIGN) 763 B.b[0] = in[0]; B.b[1] = in[1]; B.b[2] = in[2]; B.b[3] = in[3]; 764 B.b[4] = in[4]; B.b[5] = in[5]; B.b[6] = in[6]; B.b[7] = in[7]; 765 LOAD(L,L0,L1,B); 766 #else 767 LOAD(L,L0,L1,*(const C_block *)in); 768 #endif 769 LOADREG(R,R0,R1,L,L0,L1); 770 L0 &= 0x55555555L; 771 L1 &= 0x55555555L; 772 L0 = ((uint32_t)L0 << 1) | L1; /* L0 is the even-numbered input bits */ 773 R0 &= 0xaaaaaaaaL; 774 R1 = ((uint32_t)R1 >> 1) & 0x55555555L; 775 L1 = R0 | R1; /* L1 is the odd-numbered input bits */ 776 STORE(L,L0,L1,B); 777 PERM3264(L,L0,L1,B.b, (C_block *)IE3264); /* even bits */ 778 PERM3264(R,R0,R1,B.b+4,(C_block *)IE3264); /* odd bits */ 779 780 if (num_iter >= 0) 781 { /* encryption */ 782 kp = &KS[0]; 783 ks_inc = sizeof(*kp); 784 } 785 else 786 { /* decryption */ 787 num_iter = -num_iter; 788 kp = &KS[KS_SIZE-1]; 789 ks_inc = -(long)sizeof(*kp); 790 } 791 792 while (--num_iter >= 0) { 793 loop_count = 8; 794 do { 795 796 #define SPTAB(t, i) \ 797 (*(int32_t *)((unsigned char *)t + i*(sizeof(int32_t)/4))) 798 #if defined(gould) 799 /* use this if B.b[i] is evaluated just once ... */ 800 #define DOXOR(x,y,i) x^=SPTAB(SPE[0][i],B.b[i]); y^=SPTAB(SPE[1][i],B.b[i]); 801 #else 802 #if defined(pdp11) 803 /* use this if your "long" int indexing is slow */ 804 #define DOXOR(x,y,i) j=B.b[i]; x^=SPTAB(SPE[0][i],j); y^=SPTAB(SPE[1][i],j); 805 #else 806 /* use this if "k" is allocated to a register ... */ 807 #define DOXOR(x,y,i) k=B.b[i]; x^=SPTAB(SPE[0][i],k); y^=SPTAB(SPE[1][i],k); 808 #endif 809 #endif 810 811 #define CRUNCH(p0, p1, q0, q1) \ 812 k = (q0 ^ q1) & SALT; \ 813 B.b32.i0 = k ^ q0 ^ kp->b32.i0; \ 814 B.b32.i1 = k ^ q1 ^ kp->b32.i1; \ 815 kp = (C_block *)((char *)kp+ks_inc); \ 816 \ 817 DOXOR(p0, p1, 0); \ 818 DOXOR(p0, p1, 1); \ 819 DOXOR(p0, p1, 2); \ 820 DOXOR(p0, p1, 3); \ 821 DOXOR(p0, p1, 4); \ 822 DOXOR(p0, p1, 5); \ 823 DOXOR(p0, p1, 6); \ 824 DOXOR(p0, p1, 7); 825 826 CRUNCH(L0, L1, R0, R1); 827 CRUNCH(R0, R1, L0, L1); 828 } while (--loop_count != 0); 829 kp = (C_block *)((char *)kp-(ks_inc*KS_SIZE)); 830 831 832 /* swap L and R */ 833 L0 ^= R0; L1 ^= R1; 834 R0 ^= L0; R1 ^= L1; 835 L0 ^= R0; L1 ^= R1; 836 } 837 838 /* store the encrypted (or decrypted) result */ 839 L0 = (((uint32_t)L0 >> 3) & 0x0f0f0f0fL) | (((uint32_t)L1 << 1) & 0xf0f0f0f0L); 840 L1 = (((uint32_t)R0 >> 3) & 0x0f0f0f0fL) | (((uint32_t)R1 << 1) & 0xf0f0f0f0L); 841 STORE(L,L0,L1,B); 842 PERM6464(L,L0,L1,B.b, (C_block *)CF6464); 843 #if defined(MUST_ALIGN) 844 STORE(L,L0,L1,B); 845 out[0] = B.b[0]; out[1] = B.b[1]; out[2] = B.b[2]; out[3] = B.b[3]; 846 out[4] = B.b[4]; out[5] = B.b[5]; out[6] = B.b[6]; out[7] = B.b[7]; 847 #else 848 STORE(L,L0,L1,*(C_block *)out); 849 #endif 850 return (0); 851 } 852 853 854 /* 855 * Initialize various tables. This need only be done once. It could even be 856 * done at compile time, if the compiler were capable of that sort of thing. 857 */ 858 STATIC 859 init_des(void) 860 { 861 int i, j; 862 int32_t k; 863 int tableno; 864 static unsigned char perm[64], tmp32[32]; /* "static" for speed */ 865 866 /* 867 * PC1ROT - bit reverse, then PC1, then Rotate, then PC2. 868 */ 869 for (i = 0; i < 64; i++) 870 perm[i] = 0; 871 for (i = 0; i < 64; i++) { 872 if ((k = PC2[i]) == 0) 873 continue; 874 k += Rotates[0]-1; 875 if ((k%28) < Rotates[0]) k -= 28; 876 k = PC1[k]; 877 if (k > 0) { 878 k--; 879 k = (k|07) - (k&07); 880 k++; 881 } 882 perm[i] = k; 883 } 884 #ifdef DEBUG 885 prtab("pc1tab", perm, 8); 886 #endif 887 init_perm(PC1ROT, perm, 8, 8); 888 889 /* 890 * PC2ROT - PC2 inverse, then Rotate (once or twice), then PC2. 891 */ 892 for (j = 0; j < 2; j++) { 893 unsigned char pc2inv[64]; 894 for (i = 0; i < 64; i++) 895 perm[i] = pc2inv[i] = 0; 896 for (i = 0; i < 64; i++) { 897 if ((k = PC2[i]) == 0) 898 continue; 899 pc2inv[k-1] = i+1; 900 } 901 for (i = 0; i < 64; i++) { 902 if ((k = PC2[i]) == 0) 903 continue; 904 k += j; 905 if ((k%28) <= j) k -= 28; 906 perm[i] = pc2inv[k]; 907 } 908 #ifdef DEBUG 909 prtab("pc2tab", perm, 8); 910 #endif 911 init_perm(PC2ROT[j], perm, 8, 8); 912 } 913 914 /* 915 * Bit reverse, then initial permutation, then expansion. 916 */ 917 for (i = 0; i < 8; i++) { 918 for (j = 0; j < 8; j++) { 919 k = (j < 2)? 0: IP[ExpandTr[i*6+j-2]-1]; 920 if (k > 32) 921 k -= 32; 922 else if (k > 0) 923 k--; 924 if (k > 0) { 925 k--; 926 k = (k|07) - (k&07); 927 k++; 928 } 929 perm[i*8+j] = k; 930 } 931 } 932 #ifdef DEBUG 933 prtab("ietab", perm, 8); 934 #endif 935 init_perm(IE3264, perm, 4, 8); 936 937 /* 938 * Compression, then final permutation, then bit reverse. 939 */ 940 for (i = 0; i < 64; i++) { 941 k = IP[CIFP[i]-1]; 942 if (k > 0) { 943 k--; 944 k = (k|07) - (k&07); 945 k++; 946 } 947 perm[k-1] = i+1; 948 } 949 #ifdef DEBUG 950 prtab("cftab", perm, 8); 951 #endif 952 init_perm(CF6464, perm, 8, 8); 953 954 /* 955 * SPE table 956 */ 957 for (i = 0; i < 48; i++) 958 perm[i] = P32Tr[ExpandTr[i]-1]; 959 for (tableno = 0; tableno < 8; tableno++) { 960 for (j = 0; j < 64; j++) { 961 k = (((j >> 0) &01) << 5)| 962 (((j >> 1) &01) << 3)| 963 (((j >> 2) &01) << 2)| 964 (((j >> 3) &01) << 1)| 965 (((j >> 4) &01) << 0)| 966 (((j >> 5) &01) << 4); 967 k = S[tableno][k]; 968 k = (((k >> 3)&01) << 0)| 969 (((k >> 2)&01) << 1)| 970 (((k >> 1)&01) << 2)| 971 (((k >> 0)&01) << 3); 972 for (i = 0; i < 32; i++) 973 tmp32[i] = 0; 974 for (i = 0; i < 4; i++) 975 tmp32[4 * tableno + i] = (k >> i) & 01; 976 k = 0; 977 for (i = 24; --i >= 0; ) 978 k = (k<<1) | tmp32[perm[i]-1]; 979 TO_SIX_BIT(SPE[0][tableno][j], k); 980 k = 0; 981 for (i = 24; --i >= 0; ) 982 k = (k<<1) | tmp32[perm[i+24]-1]; 983 TO_SIX_BIT(SPE[1][tableno][j], k); 984 } 985 } 986 } 987 988 /* 989 * Initialize "perm" to represent transformation "p", which rearranges 990 * (perhaps with expansion and/or contraction) one packed array of bits 991 * (of size "chars_in" characters) into another array (of size "chars_out" 992 * characters). 993 * 994 * "perm" must be all-zeroes on entry to this routine. 995 */ 996 STATIC 997 init_perm(C_block perm[64/CHUNKBITS][1<<CHUNKBITS], const unsigned char p[64], 998 int chars_in, int chars_out) 999 { 1000 int i, j, k, l; 1001 1002 for (k = 0; k < chars_out*8; k++) { /* each output bit position */ 1003 l = p[k] - 1; /* where this bit comes from */ 1004 if (l < 0) 1005 continue; /* output bit is always 0 */ 1006 i = l>>LGCHUNKBITS; /* which chunk this bit comes from */ 1007 l = 1<<(l&(CHUNKBITS-1)); /* mask for this bit */ 1008 for (j = 0; j < (1<<CHUNKBITS); j++) { /* each chunk value */ 1009 if ((j & l) != 0) 1010 perm[i][j].b[k>>3] |= 1<<(k&07); 1011 } 1012 } 1013 } 1014 1015 /* 1016 * "setkey" routine (for backwards compatibility) 1017 */ 1018 int 1019 setkey(const char *key) 1020 { 1021 int i, j, k; 1022 C_block keyblock; 1023 1024 for (i = 0; i < 8; i++) { 1025 k = 0; 1026 for (j = 0; j < 8; j++) { 1027 k <<= 1; 1028 k |= (unsigned char)*key++; 1029 } 1030 keyblock.b[i] = k; 1031 } 1032 return (des_setkey((char *)keyblock.b)); 1033 } 1034 1035 /* 1036 * "encrypt" routine (for backwards compatibility) 1037 */ 1038 int 1039 encrypt(char *block, int flag) 1040 { 1041 int i, j, k; 1042 C_block cblock; 1043 1044 for (i = 0; i < 8; i++) { 1045 k = 0; 1046 for (j = 0; j < 8; j++) { 1047 k <<= 1; 1048 k |= (unsigned char)*block++; 1049 } 1050 cblock.b[i] = k; 1051 } 1052 if (des_cipher((char *)&cblock, (char *)&cblock, 0L, (flag ? -1: 1))) 1053 return (1); 1054 for (i = 7; i >= 0; i--) { 1055 k = cblock.b[i]; 1056 for (j = 7; j >= 0; j--) { 1057 *--block = k&01; 1058 k >>= 1; 1059 } 1060 } 1061 return (0); 1062 } 1063 1064 #ifdef DEBUG 1065 STATIC 1066 prtab(const char *s, unsigned char *t, int num_rows) 1067 { 1068 int i, j; 1069 1070 (void)printf("%s:\n", s); 1071 for (i = 0; i < num_rows; i++) { 1072 for (j = 0; j < 8; j++) { 1073 (void)printf("%3d", t[i*8+j]); 1074 } 1075 (void)printf("\n"); 1076 } 1077 (void)printf("\n"); 1078 } 1079 #endif 1080 1081 #if defined(MAIN) || defined(UNIT_TEST) 1082 #include <err.h> 1083 1084 int 1085 main(int argc, char *argv[]) 1086 { 1087 if (argc < 2) { 1088 fprintf(stderr, "Usage: %s password [salt]\n", getprogname()); 1089 return EXIT_FAILURE; 1090 } 1091 1092 printf("%s\n", crypt(argv[1], (argc > 2) ? argv[2] : argv[1])); 1093 return EXIT_SUCCESS; 1094 } 1095 #endif 1096