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
* $FreeBSD: src/secure/lib/libcrypt/crypt-des.c,v 1.12 1999/09/20 12:39:20 markm Exp $
41
* This is an original implementation of the DES and the crypt(3) interfaces
42
* by David Burren <davidb@werj.com.au>.
44
* An excellent reference on the underlying algorithm (and related
47
* B. Schneier, Applied Cryptography: protocols, algorithms,
48
* and source code in C, John Wiley & Sons, 1994.
50
* Note that in that book's description of DES the lookups for the initial,
51
* pbox, and final permutations are inverted (this has been brought to the
52
* attention of the author). A list of errata for this book has been
53
* posted to the sci.crypt newsgroup by the author and is available for FTP.
55
* ARCHITECTURE ASSUMPTIONS:
56
* It is assumed that the 8-byte arrays passed by reference can be
57
* addressed as arrays of uint32's (ie. the CPU is not picky about
67
#include <netinet/in.h>
68
#include <arpa/inet.h>
70
#define _PASSWORD_EFMT1 '_'
72
static uint8 IP[64] = {
73
58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
74
62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
75
57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
76
61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7
79
static uint8 inv_key_perm[64];
80
static uint8 u_key_perm[56];
81
static uint8 key_perm[56] = {
82
57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
83
10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
84
63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
85
14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
88
static uint8 key_shifts[16] = {
89
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
92
static uint8 inv_comp_perm[56];
93
static uint8 comp_perm[48] = {
94
14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
95
23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
96
41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
97
44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
101
* No E box is used, as it's replaced by some ANDs, shifts, and ORs.
104
static uint8 u_sbox[8][64];
105
static uint8 sbox[8][64] = {
107
14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
108
0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
109
4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
110
15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
113
15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
114
3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
115
0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
116
13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9
119
10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
120
13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
121
13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
122
1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12
125
7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
126
13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
127
10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
128
3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14
131
2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
132
14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
133
4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
134
11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3
137
12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
138
10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
139
9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
140
4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13
143
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
144
13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
145
1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
146
6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12
149
13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
150
1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
151
7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
152
2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
156
static uint8 un_pbox[32];
157
static uint8 pbox[32] = {
158
16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
159
2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
162
static uint32 _crypt_bits32[32] =
164
0x80000000, 0x40000000, 0x20000000, 0x10000000,
165
0x08000000, 0x04000000, 0x02000000, 0x01000000,
166
0x00800000, 0x00400000, 0x00200000, 0x00100000,
167
0x00080000, 0x00040000, 0x00020000, 0x00010000,
168
0x00008000, 0x00004000, 0x00002000, 0x00001000,
169
0x00000800, 0x00000400, 0x00000200, 0x00000100,
170
0x00000080, 0x00000040, 0x00000020, 0x00000010,
171
0x00000008, 0x00000004, 0x00000002, 0x00000001
174
static uint8 _crypt_bits8[8] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
176
static uint32 saltbits;
177
static long old_salt;
178
static uint32 *bits28,
180
static uint8 init_perm[64],
182
static uint32 en_keysl[16],
184
static uint32 de_keysl[16],
186
static int des_initialised = 0;
187
static uint8 m_sbox[4][4096];
188
static uint32 psbox[4][256];
189
static uint32 ip_maskl[8][256],
191
static uint32 fp_maskl[8][256],
193
static uint32 key_perm_maskl[8][128],
194
key_perm_maskr[8][128];
195
static uint32 comp_maskl[8][128],
197
static uint32 old_rawkey0,
201
ascii_to_bin(char ch)
206
return (ch - 'a' + 38);
210
return (ch - 'A' + 12);
233
old_rawkey0 = old_rawkey1 = 0L;
236
bits24 = (bits28 = _crypt_bits32 + 4) + 4;
239
* Invert the S-boxes, reordering the input bits.
241
for (i = 0; i < 8; i++)
242
for (j = 0; j < 64; j++)
244
b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
245
u_sbox[i][j] = sbox[i][b];
249
* Convert the inverted S-boxes into 4 arrays of 8 bits. Each will
250
* handle 12 bits of the S-box input.
252
for (b = 0; b < 4; b++)
253
for (i = 0; i < 64; i++)
254
for (j = 0; j < 64; j++)
255
m_sbox[b][(i << 6) | j] =
256
(u_sbox[(b << 1)][i] << 4) |
257
u_sbox[(b << 1) + 1][j];
260
* Set up the initial & final permutations into a useful form, and
261
* initialise the inverted key permutation.
263
for (i = 0; i < 64; i++)
265
init_perm[final_perm[i] = IP[i] - 1] = i;
266
inv_key_perm[i] = 255;
270
* Invert the key permutation and initialise the inverted key
271
* compression permutation.
273
for (i = 0; i < 56; i++)
275
u_key_perm[i] = key_perm[i] - 1;
276
inv_key_perm[key_perm[i] - 1] = i;
277
inv_comp_perm[i] = 255;
281
* Invert the key compression permutation.
283
for (i = 0; i < 48; i++)
284
inv_comp_perm[comp_perm[i] - 1] = i;
287
* Set up the OR-mask arrays for the initial and final permutations,
288
* and for the key initial and compression permutations.
290
for (k = 0; k < 8; k++)
292
for (i = 0; i < 256; i++)
294
*(il = &ip_maskl[k][i]) = 0L;
295
*(ir = &ip_maskr[k][i]) = 0L;
296
*(fl = &fp_maskl[k][i]) = 0L;
297
*(fr = &fp_maskr[k][i]) = 0L;
298
for (j = 0; j < 8; j++)
301
if (i & _crypt_bits8[j])
303
if ((obit = init_perm[inbit]) < 32)
304
*il |= _crypt_bits32[obit];
306
*ir |= _crypt_bits32[obit - 32];
307
if ((obit = final_perm[inbit]) < 32)
308
*fl |= _crypt_bits32[obit];
310
*fr |= _crypt_bits32[obit - 32];
314
for (i = 0; i < 128; i++)
316
*(il = &key_perm_maskl[k][i]) = 0L;
317
*(ir = &key_perm_maskr[k][i]) = 0L;
318
for (j = 0; j < 7; j++)
321
if (i & _crypt_bits8[j + 1])
323
if ((obit = inv_key_perm[inbit]) == 255)
328
*ir |= bits28[obit - 28];
331
*(il = &comp_maskl[k][i]) = 0L;
332
*(ir = &comp_maskr[k][i]) = 0L;
333
for (j = 0; j < 7; j++)
336
if (i & _crypt_bits8[j + 1])
338
if ((obit = inv_comp_perm[inbit]) == 255)
343
*ir |= bits24[obit - 24];
350
* Invert the P-box permutation, and convert into OR-masks for
351
* handling the output of the S-box arrays setup above.
353
for (i = 0; i < 32; i++)
354
un_pbox[pbox[i] - 1] = i;
356
for (b = 0; b < 4; b++)
357
for (i = 0; i < 256; i++)
359
*(p = &psbox[b][i]) = 0L;
360
for (j = 0; j < 8; j++)
362
if (i & _crypt_bits8[j])
363
*p |= _crypt_bits32[un_pbox[8 * b + j]];
371
setup_salt(long salt)
377
if (salt == old_salt)
384
for (i = 0; i < 24; i++)
394
des_setkey(const char *key)
403
if (!des_initialised)
406
rawkey0 = ntohl(*(uint32 *) key);
407
rawkey1 = ntohl(*(uint32 *) (key + 4));
409
if ((rawkey0 | rawkey1)
410
&& rawkey0 == old_rawkey0
411
&& rawkey1 == old_rawkey1)
414
* Already setup for this key. This optimisation fails on a zero
415
* key (which is weak and has bad parity anyway) in order to
416
* simplify the starting conditions.
420
old_rawkey0 = rawkey0;
421
old_rawkey1 = rawkey1;
424
* Do key permutation and split into two 28-bit subkeys.
426
k0 = key_perm_maskl[0][rawkey0 >> 25]
427
| key_perm_maskl[1][(rawkey0 >> 17) & 0x7f]
428
| key_perm_maskl[2][(rawkey0 >> 9) & 0x7f]
429
| key_perm_maskl[3][(rawkey0 >> 1) & 0x7f]
430
| key_perm_maskl[4][rawkey1 >> 25]
431
| key_perm_maskl[5][(rawkey1 >> 17) & 0x7f]
432
| key_perm_maskl[6][(rawkey1 >> 9) & 0x7f]
433
| key_perm_maskl[7][(rawkey1 >> 1) & 0x7f];
434
k1 = key_perm_maskr[0][rawkey0 >> 25]
435
| key_perm_maskr[1][(rawkey0 >> 17) & 0x7f]
436
| key_perm_maskr[2][(rawkey0 >> 9) & 0x7f]
437
| key_perm_maskr[3][(rawkey0 >> 1) & 0x7f]
438
| key_perm_maskr[4][rawkey1 >> 25]
439
| key_perm_maskr[5][(rawkey1 >> 17) & 0x7f]
440
| key_perm_maskr[6][(rawkey1 >> 9) & 0x7f]
441
| key_perm_maskr[7][(rawkey1 >> 1) & 0x7f];
444
* Rotate subkeys and do compression permutation.
447
for (round = 0; round < 16; round++)
452
shifts += key_shifts[round];
454
t0 = (k0 << shifts) | (k0 >> (28 - shifts));
455
t1 = (k1 << shifts) | (k1 >> (28 - shifts));
457
de_keysl[15 - round] =
458
en_keysl[round] = comp_maskl[0][(t0 >> 21) & 0x7f]
459
| comp_maskl[1][(t0 >> 14) & 0x7f]
460
| comp_maskl[2][(t0 >> 7) & 0x7f]
461
| comp_maskl[3][t0 & 0x7f]
462
| comp_maskl[4][(t1 >> 21) & 0x7f]
463
| comp_maskl[5][(t1 >> 14) & 0x7f]
464
| comp_maskl[6][(t1 >> 7) & 0x7f]
465
| comp_maskl[7][t1 & 0x7f];
467
de_keysr[15 - round] =
468
en_keysr[round] = comp_maskr[0][(t0 >> 21) & 0x7f]
469
| comp_maskr[1][(t0 >> 14) & 0x7f]
470
| comp_maskr[2][(t0 >> 7) & 0x7f]
471
| comp_maskr[3][t0 & 0x7f]
472
| comp_maskr[4][(t1 >> 21) & 0x7f]
473
| comp_maskr[5][(t1 >> 14) & 0x7f]
474
| comp_maskr[6][(t1 >> 7) & 0x7f]
475
| comp_maskr[7][t1 & 0x7f];
481
do_des(uint32 l_in, uint32 r_in, uint32 *l_out, uint32 *r_out, int count)
484
* l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
518
* Do initial permutation (IP).
520
l = ip_maskl[0][l_in >> 24]
521
| ip_maskl[1][(l_in >> 16) & 0xff]
522
| ip_maskl[2][(l_in >> 8) & 0xff]
523
| ip_maskl[3][l_in & 0xff]
524
| ip_maskl[4][r_in >> 24]
525
| ip_maskl[5][(r_in >> 16) & 0xff]
526
| ip_maskl[6][(r_in >> 8) & 0xff]
527
| ip_maskl[7][r_in & 0xff];
528
r = ip_maskr[0][l_in >> 24]
529
| ip_maskr[1][(l_in >> 16) & 0xff]
530
| ip_maskr[2][(l_in >> 8) & 0xff]
531
| ip_maskr[3][l_in & 0xff]
532
| ip_maskr[4][r_in >> 24]
533
| ip_maskr[5][(r_in >> 16) & 0xff]
534
| ip_maskr[6][(r_in >> 8) & 0xff]
535
| ip_maskr[7][r_in & 0xff];
548
* Expand R to 48 bits (simulate the E-box).
550
r48l = ((r & 0x00000001) << 23)
551
| ((r & 0xf8000000) >> 9)
552
| ((r & 0x1f800000) >> 11)
553
| ((r & 0x01f80000) >> 13)
554
| ((r & 0x001f8000) >> 15);
556
r48r = ((r & 0x0001f800) << 7)
557
| ((r & 0x00001f80) << 5)
558
| ((r & 0x000001f8) << 3)
559
| ((r & 0x0000001f) << 1)
560
| ((r & 0x80000000) >> 31);
563
* Do salting for crypt() and friends, and XOR with the
566
f = (r48l ^ r48r) & saltbits;
571
* Do sbox lookups (which shrink it back to 32 bits) and do
572
* the pbox permutation at the same time.
574
f = psbox[0][m_sbox[0][r48l >> 12]]
575
| psbox[1][m_sbox[1][r48l & 0xfff]]
576
| psbox[2][m_sbox[2][r48r >> 12]]
577
| psbox[3][m_sbox[3][r48r & 0xfff]];
580
* Now that we've permuted things, complete f().
591
* Do final permutation (inverse of IP).
593
*l_out = fp_maskl[0][l >> 24]
594
| fp_maskl[1][(l >> 16) & 0xff]
595
| fp_maskl[2][(l >> 8) & 0xff]
596
| fp_maskl[3][l & 0xff]
597
| fp_maskl[4][r >> 24]
598
| fp_maskl[5][(r >> 16) & 0xff]
599
| fp_maskl[6][(r >> 8) & 0xff]
600
| fp_maskl[7][r & 0xff];
601
*r_out = fp_maskr[0][l >> 24]
602
| fp_maskr[1][(l >> 16) & 0xff]
603
| fp_maskr[2][(l >> 8) & 0xff]
604
| fp_maskr[3][l & 0xff]
605
| fp_maskr[4][r >> 24]
606
| fp_maskr[5][(r >> 16) & 0xff]
607
| fp_maskr[6][(r >> 8) & 0xff]
608
| fp_maskr[7][r & 0xff];
613
des_cipher(const char *in, char *out, long salt, int count)
622
if (!des_initialised)
627
/* copy data to avoid assuming input is word-aligned */
628
memcpy(buffer, in, sizeof(buffer));
630
rawl = ntohl(buffer[0]);
631
rawr = ntohl(buffer[1]);
633
retval = do_des(rawl, rawr, &l_out, &r_out, count);
635
buffer[0] = htonl(l_out);
636
buffer[1] = htonl(r_out);
638
/* copy data to avoid assuming output is word-aligned */
639
memcpy(out, buffer, sizeof(buffer));
645
px_crypt_des(const char *key, const char *setting)
656
static uint8 output[21];
658
if (!des_initialised)
663
* Copy the key, shifting each character up by one bit and padding
666
q = (uint8 *) keybuf;
667
while (q - (uint8 *) keybuf - 8)
669
if ((*q++ = *key << 1))
672
if (des_setkey((uint8 *) keybuf))
676
if (*setting == _PASSWORD_EFMT1)
679
* "new"-style: setting - underscore, 4 bytes of count, 4 bytes of
680
* salt key - unlimited characters
682
for (i = 1, count = 0L; i < 5; i++)
683
count |= ascii_to_bin(setting[i]) << (i - 1) * 6;
685
for (i = 5, salt = 0L; i < 9; i++)
686
salt |= ascii_to_bin(setting[i]) << (i - 5) * 6;
691
* Encrypt the key with itself.
693
if (des_cipher((uint8 *) keybuf, (uint8 *) keybuf, 0L, 1))
697
* And XOR with the next 8 characters of the key.
699
q = (uint8 *) keybuf;
700
while (q - (uint8 *) keybuf - 8 && *key)
703
if (des_setkey((uint8 *) keybuf))
706
strncpy(output, setting, 9);
709
* Double check that we weren't given a short setting. If we were,
710
* the above code will probably have created wierd values for
711
* count and salt, but we don't really care. Just make sure the
712
* output string doesn't have an extra NUL in it.
715
p = output + strlen(output);
718
#endif /* !DISABLE_XDES */
721
* "old"-style: setting - 2 bytes of salt key - up to 8 characters
725
salt = (ascii_to_bin(setting[1]) << 6)
726
| ascii_to_bin(setting[0]);
728
output[0] = setting[0];
731
* If the encrypted password that the salt was extracted from is
732
* only 1 character long, the salt will be corrupted. We need to
733
* ensure that the output string doesn't have an extra NUL in it!
735
output[1] = setting[1] ? setting[1] : output[0];
744
if (do_des(0L, 0L, &r0, &r1, count))
748
* Now encode the result...
751
*p++ = _crypt_a64[(l >> 18) & 0x3f];
752
*p++ = _crypt_a64[(l >> 12) & 0x3f];
753
*p++ = _crypt_a64[(l >> 6) & 0x3f];
754
*p++ = _crypt_a64[l & 0x3f];
756
l = (r0 << 16) | ((r1 >> 16) & 0xffff);
757
*p++ = _crypt_a64[(l >> 18) & 0x3f];
758
*p++ = _crypt_a64[(l >> 12) & 0x3f];
759
*p++ = _crypt_a64[(l >> 6) & 0x3f];
760
*p++ = _crypt_a64[l & 0x3f];
763
*p++ = _crypt_a64[(l >> 12) & 0x3f];
764
*p++ = _crypt_a64[(l >> 6) & 0x3f];
765
*p++ = _crypt_a64[l & 0x3f];