2 * FreeSec: libcrypt for NetBSD
4 * Copyright (c) 1994 David Burren
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
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.
15 * Redistribution and use in source and binary forms, with or without
16 * modification, are permitted provided that the following conditions
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.
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
39 * This is an original implementation of the DES and the crypt(3) interfaces
40 * by David Burren <davidb@werj.com.au>.
42 * An excellent reference on the underlying algorithm (and related
45 * B. Schneier, Applied Cryptography: protocols, algorithms,
46 * and source code in C, John Wiley & Sons, 1994.
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.
53 * ARCHITECTURE ASSUMPTIONS:
54 * It is assumed that the 8-byte arrays passed by reference can be
55 * addressed as arrays of u_int32_t's (ie. the CPU is not picky about
59 #include <sys/cdefs.h>
60 #include <sys/types.h>
61 #include <sys/param.h>
62 #include <netinet/in.h>
67 #include "des_tables.c"
69 /* Re-entrantify me -- all this junk needs to be in
70 * struct crypt_data to make this really reentrant... */
71 static u_int32_t en_keysl
[16], en_keysr
[16];
72 static u_int32_t de_keysl
[16], de_keysr
[16];
73 static u_int32_t saltbits
;
74 static u_int32_t old_salt
;
75 static u_int32_t old_rawkey0
, old_rawkey1
;
78 static const u_char ascii64
[] = "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
80 static const u_char key_shifts
[16] = {
81 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
84 static const u_int32_t bits32
[32] =
86 0x80000000, 0x40000000, 0x20000000, 0x10000000,
87 0x08000000, 0x04000000, 0x02000000, 0x01000000,
88 0x00800000, 0x00400000, 0x00200000, 0x00100000,
89 0x00080000, 0x00040000, 0x00020000, 0x00010000,
90 0x00008000, 0x00004000, 0x00002000, 0x00001000,
91 0x00000800, 0x00000400, 0x00000200, 0x00000100,
92 0x00000080, 0x00000040, 0x00000020, 0x00000010,
93 0x00000008, 0x00000004, 0x00000002, 0x00000001
96 static const u_char bits8
[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
100 ascii_to_bin(char ch
)
105 return(ch
- 'a' + 38);
109 return(ch
- 'A' + 12);
120 static int des_initialised
= 0;
122 if (des_initialised
==1)
125 old_rawkey0
= old_rawkey1
= 0L;
133 setup_salt(u_int32_t salt
)
135 u_int32_t obit
, saltbit
;
138 if (salt
== old_salt
)
145 for (i
= 0; i
< 24; i
++) {
155 des_setkey(const char *key
)
157 u_int32_t k0
, k1
, rawkey0
, rawkey1
;
162 rawkey0
= ntohl(*(const u_int32_t
*) key
);
163 rawkey1
= ntohl(*(const u_int32_t
*) (key
+ 4));
165 if ((rawkey0
| rawkey1
)
166 && rawkey0
== old_rawkey0
167 && rawkey1
== old_rawkey1
) {
169 * Already setup for this key.
170 * This optimisation fails on a zero key (which is weak and
171 * has bad parity anyway) in order to simplify the starting
176 old_rawkey0
= rawkey0
;
177 old_rawkey1
= rawkey1
;
180 * Do key permutation and split into two 28-bit subkeys.
182 k0
= key_perm_maskl
[0][rawkey0
>> 25]
183 | key_perm_maskl
[1][(rawkey0
>> 17) & 0x7f]
184 | key_perm_maskl
[2][(rawkey0
>> 9) & 0x7f]
185 | key_perm_maskl
[3][(rawkey0
>> 1) & 0x7f]
186 | key_perm_maskl
[4][rawkey1
>> 25]
187 | key_perm_maskl
[5][(rawkey1
>> 17) & 0x7f]
188 | key_perm_maskl
[6][(rawkey1
>> 9) & 0x7f]
189 | key_perm_maskl
[7][(rawkey1
>> 1) & 0x7f];
190 k1
= key_perm_maskr
[0][rawkey0
>> 25]
191 | key_perm_maskr
[1][(rawkey0
>> 17) & 0x7f]
192 | key_perm_maskr
[2][(rawkey0
>> 9) & 0x7f]
193 | key_perm_maskr
[3][(rawkey0
>> 1) & 0x7f]
194 | key_perm_maskr
[4][rawkey1
>> 25]
195 | key_perm_maskr
[5][(rawkey1
>> 17) & 0x7f]
196 | key_perm_maskr
[6][(rawkey1
>> 9) & 0x7f]
197 | key_perm_maskr
[7][(rawkey1
>> 1) & 0x7f];
199 * Rotate subkeys and do compression permutation.
202 for (round
= 0; round
< 16; round
++) {
205 shifts
+= key_shifts
[round
];
207 t0
= (k0
<< shifts
) | (k0
>> (28 - shifts
));
208 t1
= (k1
<< shifts
) | (k1
>> (28 - shifts
));
210 de_keysl
[15 - round
] =
211 en_keysl
[round
] = comp_maskl
[0][(t0
>> 21) & 0x7f]
212 | comp_maskl
[1][(t0
>> 14) & 0x7f]
213 | comp_maskl
[2][(t0
>> 7) & 0x7f]
214 | comp_maskl
[3][t0
& 0x7f]
215 | comp_maskl
[4][(t1
>> 21) & 0x7f]
216 | comp_maskl
[5][(t1
>> 14) & 0x7f]
217 | comp_maskl
[6][(t1
>> 7) & 0x7f]
218 | comp_maskl
[7][t1
& 0x7f];
220 de_keysr
[15 - round
] =
221 en_keysr
[round
] = comp_maskr
[0][(t0
>> 21) & 0x7f]
222 | comp_maskr
[1][(t0
>> 14) & 0x7f]
223 | comp_maskr
[2][(t0
>> 7) & 0x7f]
224 | comp_maskr
[3][t0
& 0x7f]
225 | comp_maskr
[4][(t1
>> 21) & 0x7f]
226 | comp_maskr
[5][(t1
>> 14) & 0x7f]
227 | comp_maskr
[6][(t1
>> 7) & 0x7f]
228 | comp_maskr
[7][t1
& 0x7f];
234 do_des( u_int32_t l_in
, u_int32_t r_in
, u_int32_t
*l_out
, u_int32_t
*r_out
, int count
)
236 /* l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format. */
237 u_int32_t l
, r
, *kl
, *kr
, *kl1
, *kr1
;
238 u_int32_t f
, r48l
, r48r
;
255 /* Do initial permutation (IP). */
256 l
= ip_maskl
[0][l_in
>> 24]
257 | ip_maskl
[1][(l_in
>> 16) & 0xff]
258 | ip_maskl
[2][(l_in
>> 8) & 0xff]
259 | ip_maskl
[3][l_in
& 0xff]
260 | ip_maskl
[4][r_in
>> 24]
261 | ip_maskl
[5][(r_in
>> 16) & 0xff]
262 | ip_maskl
[6][(r_in
>> 8) & 0xff]
263 | ip_maskl
[7][r_in
& 0xff];
264 r
= ip_maskr
[0][l_in
>> 24]
265 | ip_maskr
[1][(l_in
>> 16) & 0xff]
266 | ip_maskr
[2][(l_in
>> 8) & 0xff]
267 | ip_maskr
[3][l_in
& 0xff]
268 | ip_maskr
[4][r_in
>> 24]
269 | ip_maskr
[5][(r_in
>> 16) & 0xff]
270 | ip_maskr
[6][(r_in
>> 8) & 0xff]
271 | ip_maskr
[7][r_in
& 0xff];
279 /* Expand R to 48 bits (simulate the E-box). */
280 r48l
= ((r
& 0x00000001) << 23)
281 | ((r
& 0xf8000000) >> 9)
282 | ((r
& 0x1f800000) >> 11)
283 | ((r
& 0x01f80000) >> 13)
284 | ((r
& 0x001f8000) >> 15);
285 r48r
= ((r
& 0x0001f800) << 7)
286 | ((r
& 0x00001f80) << 5)
287 | ((r
& 0x000001f8) << 3)
288 | ((r
& 0x0000001f) << 1)
289 | ((r
& 0x80000000) >> 31);
291 * Do salting for crypt() and friends, and
292 * XOR with the permuted key.
294 f
= (r48l
^ r48r
) & saltbits
;
298 * Do sbox lookups (which shrink it back to 32 bits)
299 * and do the pbox permutation at the same time.
301 f
= psbox
[0][m_sbox
[0][r48l
>> 12]]
302 | psbox
[1][m_sbox
[1][r48l
& 0xfff]]
303 | psbox
[2][m_sbox
[2][r48r
>> 12]]
304 | psbox
[3][m_sbox
[3][r48r
& 0xfff]];
305 /* Now that we've permuted things, complete f(). */
313 /* Do final permutation (inverse of IP). */
314 *l_out
= fp_maskl
[0][l
>> 24]
315 | fp_maskl
[1][(l
>> 16) & 0xff]
316 | fp_maskl
[2][(l
>> 8) & 0xff]
317 | fp_maskl
[3][l
& 0xff]
318 | fp_maskl
[4][r
>> 24]
319 | fp_maskl
[5][(r
>> 16) & 0xff]
320 | fp_maskl
[6][(r
>> 8) & 0xff]
321 | fp_maskl
[7][r
& 0xff];
322 *r_out
= fp_maskr
[0][l
>> 24]
323 | fp_maskr
[1][(l
>> 16) & 0xff]
324 | fp_maskr
[2][(l
>> 8) & 0xff]
325 | fp_maskr
[3][l
& 0xff]
326 | fp_maskr
[4][r
>> 24]
327 | fp_maskr
[5][(r
>> 16) & 0xff]
328 | fp_maskr
[6][(r
>> 8) & 0xff]
329 | fp_maskr
[7][r
& 0xff];
336 des_cipher(const char *in
, char *out
, u_int32_t salt
, int count
)
338 u_int32_t l_out
, r_out
, rawl
, rawr
;
350 rawl
= ntohl(*trans
.ui32
++);
351 rawr
= ntohl(*trans
.ui32
);
353 retval
= do_des(rawl
, rawr
, &l_out
, &r_out
, count
);
356 *trans
.ui32
++ = htonl(l_out
);
357 *trans
.ui32
= htonl(r_out
);
364 setkey(const char *key
)
367 u_int32_t packed_keys
[2];
370 p
= (u_char
*) packed_keys
;
372 for (i
= 0; i
< 8; i
++) {
374 for (j
= 0; j
< 8; j
++)
378 des_setkey((char *)p
);
383 encrypt(char *block
, int flag
)
393 for (i
= 0; i
< 2; i
++) {
395 for (j
= 0; j
< 32; j
++)
399 do_des(io
[0], io
[1], io
, io
+ 1, flag
? -1 : 1);
400 for (i
= 0; i
< 2; i
++)
401 for (j
= 0; j
< 32; j
++)
402 block
[(i
<< 5) | j
] = (io
[i
] & bits32
[j
]) ? 1 : 0;
405 char *__des_crypt(const unsigned char *key
, const unsigned char *setting
)
407 u_int32_t count
, salt
, l
, r0
, r1
, keybuf
[2];
409 static char output
[21];
414 * Copy the key, shifting each character up by one bit
415 * and padding with zeros.
417 q
= (u_char
*)keybuf
;
418 while (q
- (u_char
*)keybuf
- 8) {
423 des_setkey((char *)keybuf
);
426 if (*setting
== _PASSWORD_EFMT1
) {
430 * setting - underscore, 4 bytes of count, 4 bytes of salt
431 * key - unlimited characters
433 for (i
= 1, count
= 0L; i
< 5; i
++)
434 count
|= ascii_to_bin(setting
[i
]) << ((i
- 1) * 6);
436 for (i
= 5, salt
= 0L; i
< 9; i
++)
437 salt
|= ascii_to_bin(setting
[i
]) << ((i
- 5) * 6);
441 * Encrypt the key with itself.
443 if (des_cipher((char *)keybuf
, (char *)keybuf
, 0L, 1))
446 * And XOR with the next 8 characters of the key.
448 q
= (u_char
*)keybuf
;
449 while (q
- (u_char
*)keybuf
- 8 && *key
)
452 des_setkey((char *)keybuf
);
454 strncpy(output
, setting
, 9);
457 * Double check that we weren't given a short setting.
458 * If we were, the above code will probably have created
459 * wierd values for count and salt, but we don't really care.
460 * Just make sure the output string doesn't have an extra
464 p
= (u_char
*)output
+ strlen(output
);
470 * setting - 2 bytes of salt
471 * key - up to 8 characters
475 salt
= (ascii_to_bin(setting
[1]) << 6)
476 | ascii_to_bin(setting
[0]);
478 output
[0] = setting
[0];
480 * If the encrypted password that the salt was extracted from
481 * is only 1 character long, the salt will be corrupted. We
482 * need to ensure that the output string doesn't have an extra
485 output
[1] = setting
[1] ? setting
[1] : output
[0];
487 p
= (u_char
*)output
+ 2;
493 if (do_des(0L, 0L, &r0
, &r1
, (int)count
))
496 * Now encode the result...
499 *p
++ = ascii64
[(l
>> 18) & 0x3f];
500 *p
++ = ascii64
[(l
>> 12) & 0x3f];
501 *p
++ = ascii64
[(l
>> 6) & 0x3f];
502 *p
++ = ascii64
[l
& 0x3f];
504 l
= (r0
<< 16) | ((r1
>> 16) & 0xffff);
505 *p
++ = ascii64
[(l
>> 18) & 0x3f];
506 *p
++ = ascii64
[(l
>> 12) & 0x3f];
507 *p
++ = ascii64
[(l
>> 6) & 0x3f];
508 *p
++ = ascii64
[l
& 0x3f];
511 *p
++ = ascii64
[(l
>> 12) & 0x3f];
512 *p
++ = ascii64
[(l
>> 6) & 0x3f];
513 *p
++ = ascii64
[l
& 0x3f];