2 * FreeSec: libcrypt for NetBSD
4 * Copyright (c) 1994 David Burren
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 4. Neither the name of the author nor the names of other contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * $FreeBSD: src/secure/lib/libcipher/crypt.c,v 1.6 1999/08/28 01:30:21 peter Exp $
32 * $DragonFly: src/secure/lib/libcipher/crypt.c,v 1.3 2005/05/21 10:31:08 corecode Exp $
34 * This is an original implementation of the DES and the crypt(3) interfaces
35 * by David Burren <davidb@werj.com.au>.
37 * An excellent reference on the underlying algorithm (and related
40 * B. Schneier, Applied Cryptography: protocols, algorithms,
41 * and source code in C, John Wiley & Sons, 1994.
43 * Note that in that book's description of DES the lookups for the initial,
44 * pbox, and final permutations are inverted (this has been brought to the
45 * attention of the author). A list of errata for this book has been
46 * posted to the sci.crypt newsgroup by the author and is available for FTP.
48 * ARCHITECTURE ASSUMPTIONS:
49 * This code assumes that u_longs are 32 bits. It will probably not
50 * operate on 64-bit machines without modifications.
51 * It is assumed that the 8-byte arrays passed by reference can be
52 * addressed as arrays of u_longs (ie. the CPU is not picky about
55 #include <sys/types.h>
56 #include <sys/param.h>
64 static u_char IP
[64] = {
65 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
66 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
67 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
68 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7
71 static u_char inv_key_perm
[64];
72 static u_char u_key_perm
[56];
73 static u_char key_perm
[56] = {
74 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
75 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
76 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
77 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
80 static u_char key_shifts
[16] = {
81 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
84 static u_char inv_comp_perm
[56];
85 static u_char comp_perm
[48] = {
86 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
87 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
88 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
89 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
93 * No E box is used, as it's replaced by some ANDs, shifts, and ORs.
96 static u_char u_sbox
[8][64];
97 static u_char sbox
[8][64] = {
99 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
100 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
101 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
102 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
105 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
106 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
107 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
108 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9
111 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
112 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
113 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
114 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12
117 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
118 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
119 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
120 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14
123 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
124 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
125 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
126 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3
129 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
130 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
131 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
132 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13
135 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
136 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
137 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
138 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12
141 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
142 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
143 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
144 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
148 static u_char un_pbox
[32];
149 static u_char pbox
[32] = {
150 16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
151 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
154 static u_long bits32
[32] =
156 0x80000000, 0x40000000, 0x20000000, 0x10000000,
157 0x08000000, 0x04000000, 0x02000000, 0x01000000,
158 0x00800000, 0x00400000, 0x00200000, 0x00100000,
159 0x00080000, 0x00040000, 0x00020000, 0x00010000,
160 0x00008000, 0x00004000, 0x00002000, 0x00001000,
161 0x00000800, 0x00000400, 0x00000200, 0x00000100,
162 0x00000080, 0x00000040, 0x00000020, 0x00000010,
163 0x00000008, 0x00000004, 0x00000002, 0x00000001
166 static u_char bits8
[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
168 static u_long saltbits
;
169 static long old_salt
;
170 static u_long
*bits28
, *bits24
;
171 static u_char init_perm
[64], final_perm
[64];
172 static u_long en_keysl
[16], en_keysr
[16];
173 static u_long de_keysl
[16], de_keysr
[16];
174 static int des_initialised
= 0;
175 static u_char m_sbox
[4][4096];
176 static u_long psbox
[4][256];
177 static u_long ip_maskl
[8][256], ip_maskr
[8][256];
178 static u_long fp_maskl
[8][256], fp_maskr
[8][256];
179 static u_long key_perm_maskl
[8][128], key_perm_maskr
[8][128];
180 static u_long comp_maskl
[8][128], comp_maskr
[8][128];
181 static u_long old_rawkey0
, old_rawkey1
;
183 static u_char ascii64
[] =
184 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
185 /* 0000000000111111111122222222223333333333444444444455555555556666 */
186 /* 0123456789012345678901234567890123456789012345678901234567890123 */
189 ascii_to_bin(char ch
)
194 return(ch
- 'a' + 38);
198 return(ch
- 'A' + 12);
210 int i
, j
, b
, k
, inbit
, obit
;
211 u_long
*p
, *il
, *ir
, *fl
, *fr
;
213 old_rawkey0
= old_rawkey1
= 0L;
216 bits24
= (bits28
= bits32
+ 4) + 4;
219 * Invert the S-boxes, reordering the input bits.
221 for (i
= 0; i
< 8; i
++)
222 for (j
= 0; j
< 64; j
++) {
223 b
= (j
& 0x20) | ((j
& 1) << 4) | ((j
>> 1) & 0xf);
224 u_sbox
[i
][j
] = sbox
[i
][b
];
228 * Convert the inverted S-boxes into 4 arrays of 8 bits.
229 * Each will handle 12 bits of the S-box input.
231 for (b
= 0; b
< 4; b
++)
232 for (i
= 0; i
< 64; i
++)
233 for (j
= 0; j
< 64; j
++)
234 m_sbox
[b
][(i
<< 6) | j
] =
235 (u_sbox
[(b
<< 1)][i
] << 4) |
236 u_sbox
[(b
<< 1) + 1][j
];
239 * Set up the initial & final permutations into a useful form, and
240 * initialise the inverted key permutation.
242 for (i
= 0; i
< 64; i
++) {
243 init_perm
[final_perm
[i
] = IP
[i
] - 1] = i
;
244 inv_key_perm
[i
] = 255;
248 * Invert the key permutation and initialise the inverted key
249 * compression permutation.
251 for (i
= 0; i
< 56; i
++) {
252 u_key_perm
[i
] = key_perm
[i
] - 1;
253 inv_key_perm
[key_perm
[i
] - 1] = i
;
254 inv_comp_perm
[i
] = 255;
258 * Invert the key compression permutation.
260 for (i
= 0; i
< 48; i
++) {
261 inv_comp_perm
[comp_perm
[i
] - 1] = i
;
265 * Set up the OR-mask arrays for the initial and final permutations,
266 * and for the key initial and compression permutations.
268 for (k
= 0; k
< 8; k
++) {
269 for (i
= 0; i
< 256; i
++) {
270 *(il
= &ip_maskl
[k
][i
]) = 0L;
271 *(ir
= &ip_maskr
[k
][i
]) = 0L;
272 *(fl
= &fp_maskl
[k
][i
]) = 0L;
273 *(fr
= &fp_maskr
[k
][i
]) = 0L;
274 for (j
= 0; j
< 8; j
++) {
277 if ((obit
= init_perm
[inbit
]) < 32)
280 *ir
|= bits32
[obit
-32];
281 if ((obit
= final_perm
[inbit
]) < 32)
284 *fr
|= bits32
[obit
- 32];
288 for (i
= 0; i
< 128; i
++) {
289 *(il
= &key_perm_maskl
[k
][i
]) = 0L;
290 *(ir
= &key_perm_maskr
[k
][i
]) = 0L;
291 for (j
= 0; j
< 7; j
++) {
293 if (i
& bits8
[j
+ 1]) {
294 if ((obit
= inv_key_perm
[inbit
]) == 255)
299 *ir
|= bits28
[obit
- 28];
302 *(il
= &comp_maskl
[k
][i
]) = 0L;
303 *(ir
= &comp_maskr
[k
][i
]) = 0L;
304 for (j
= 0; j
< 7; j
++) {
306 if (i
& bits8
[j
+ 1]) {
307 if ((obit
=inv_comp_perm
[inbit
]) == 255)
312 *ir
|= bits24
[obit
- 24];
319 * Invert the P-box permutation, and convert into OR-masks for
320 * handling the output of the S-box arrays setup above.
322 for (i
= 0; i
< 32; i
++)
323 un_pbox
[pbox
[i
] - 1] = i
;
325 for (b
= 0; b
< 4; b
++)
326 for (i
= 0; i
< 256; i
++) {
327 *(p
= &psbox
[b
][i
]) = 0L;
328 for (j
= 0; j
< 8; j
++) {
330 *p
|= bits32
[un_pbox
[8 * b
+ j
]];
339 setup_salt(long salt
)
341 u_long obit
, saltbit
;
344 if (salt
== old_salt
)
351 for (i
= 0; i
< 24; i
++) {
361 des_setkey(const char *key
)
363 u_long k0
, k1
, rawkey0
, rawkey1
;
364 int shifts
, i
, b
, round
;
366 if (!des_initialised
)
369 rawkey0
= ntohl(*(u_long
*) key
);
370 rawkey1
= ntohl(*(u_long
*) (key
+ 4));
372 if ((rawkey0
| rawkey1
)
373 && rawkey0
== old_rawkey0
374 && rawkey1
== old_rawkey1
) {
376 * Already setup for this key.
377 * This optimisation fails on a zero key (which is weak and
378 * has bad parity anyway) in order to simplify the starting
383 old_rawkey0
= rawkey0
;
384 old_rawkey1
= rawkey1
;
387 * Do key permutation and split into two 28-bit subkeys.
389 k0
= key_perm_maskl
[0][rawkey0
>> 25]
390 | key_perm_maskl
[1][(rawkey0
>> 17) & 0x7f]
391 | key_perm_maskl
[2][(rawkey0
>> 9) & 0x7f]
392 | key_perm_maskl
[3][(rawkey0
>> 1) & 0x7f]
393 | key_perm_maskl
[4][rawkey1
>> 25]
394 | key_perm_maskl
[5][(rawkey1
>> 17) & 0x7f]
395 | key_perm_maskl
[6][(rawkey1
>> 9) & 0x7f]
396 | key_perm_maskl
[7][(rawkey1
>> 1) & 0x7f];
397 k1
= key_perm_maskr
[0][rawkey0
>> 25]
398 | key_perm_maskr
[1][(rawkey0
>> 17) & 0x7f]
399 | key_perm_maskr
[2][(rawkey0
>> 9) & 0x7f]
400 | key_perm_maskr
[3][(rawkey0
>> 1) & 0x7f]
401 | key_perm_maskr
[4][rawkey1
>> 25]
402 | key_perm_maskr
[5][(rawkey1
>> 17) & 0x7f]
403 | key_perm_maskr
[6][(rawkey1
>> 9) & 0x7f]
404 | key_perm_maskr
[7][(rawkey1
>> 1) & 0x7f];
406 * Rotate subkeys and do compression permutation.
409 for (round
= 0; round
< 16; round
++) {
413 shifts
+= key_shifts
[round
];
415 t0
= (k0
<< shifts
) | (k0
>> (28 - shifts
));
416 t1
= (k1
<< shifts
) | (k1
>> (28 - shifts
));
418 de_keysl
[15 - round
] =
419 en_keysl
[round
] = comp_maskl
[0][(t0
>> 21) & 0x7f]
420 | comp_maskl
[1][(t0
>> 14) & 0x7f]
421 | comp_maskl
[2][(t0
>> 7) & 0x7f]
422 | comp_maskl
[3][t0
& 0x7f]
423 | comp_maskl
[4][(t1
>> 21) & 0x7f]
424 | comp_maskl
[5][(t1
>> 14) & 0x7f]
425 | comp_maskl
[6][(t1
>> 7) & 0x7f]
426 | comp_maskl
[7][t1
& 0x7f];
428 de_keysr
[15 - round
] =
429 en_keysr
[round
] = comp_maskr
[0][(t0
>> 21) & 0x7f]
430 | comp_maskr
[1][(t0
>> 14) & 0x7f]
431 | comp_maskr
[2][(t0
>> 7) & 0x7f]
432 | comp_maskr
[3][t0
& 0x7f]
433 | comp_maskr
[4][(t1
>> 21) & 0x7f]
434 | comp_maskr
[5][(t1
>> 14) & 0x7f]
435 | comp_maskr
[6][(t1
>> 7) & 0x7f]
436 | comp_maskr
[7][t1
& 0x7f];
443 do_des( u_long l_in
, u_long r_in
, u_long
*l_out
, u_long
*r_out
, int count
)
446 * l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
448 u_long mask
, rawl
, rawr
, l
, r
, *kl
, *kr
, *kl1
, *kr1
;
449 u_long f
, r48l
, r48r
;
454 } else if (count
> 0) {
470 * Do initial permutation (IP).
472 l
= ip_maskl
[0][l_in
>> 24]
473 | ip_maskl
[1][(l_in
>> 16) & 0xff]
474 | ip_maskl
[2][(l_in
>> 8) & 0xff]
475 | ip_maskl
[3][l_in
& 0xff]
476 | ip_maskl
[4][r_in
>> 24]
477 | ip_maskl
[5][(r_in
>> 16) & 0xff]
478 | ip_maskl
[6][(r_in
>> 8) & 0xff]
479 | ip_maskl
[7][r_in
& 0xff];
480 r
= ip_maskr
[0][l_in
>> 24]
481 | ip_maskr
[1][(l_in
>> 16) & 0xff]
482 | ip_maskr
[2][(l_in
>> 8) & 0xff]
483 | ip_maskr
[3][l_in
& 0xff]
484 | ip_maskr
[4][r_in
>> 24]
485 | ip_maskr
[5][(r_in
>> 16) & 0xff]
486 | ip_maskr
[6][(r_in
>> 8) & 0xff]
487 | ip_maskr
[7][r_in
& 0xff];
498 * Expand R to 48 bits (simulate the E-box).
500 r48l
= ((r
& 0x00000001) << 23)
501 | ((r
& 0xf8000000) >> 9)
502 | ((r
& 0x1f800000) >> 11)
503 | ((r
& 0x01f80000) >> 13)
504 | ((r
& 0x001f8000) >> 15);
506 r48r
= ((r
& 0x0001f800) << 7)
507 | ((r
& 0x00001f80) << 5)
508 | ((r
& 0x000001f8) << 3)
509 | ((r
& 0x0000001f) << 1)
510 | ((r
& 0x80000000) >> 31);
512 * Do salting for crypt() and friends, and
513 * XOR with the permuted key.
515 f
= (r48l
^ r48r
) & saltbits
;
519 * Do sbox lookups (which shrink it back to 32 bits)
520 * and do the pbox permutation at the same time.
522 f
= psbox
[0][m_sbox
[0][r48l
>> 12]]
523 | psbox
[1][m_sbox
[1][r48l
& 0xfff]]
524 | psbox
[2][m_sbox
[2][r48r
>> 12]]
525 | psbox
[3][m_sbox
[3][r48r
& 0xfff]];
527 * Now that we've permuted things, complete f().
537 * Do final permutation (inverse of IP).
539 *l_out
= fp_maskl
[0][l
>> 24]
540 | fp_maskl
[1][(l
>> 16) & 0xff]
541 | fp_maskl
[2][(l
>> 8) & 0xff]
542 | fp_maskl
[3][l
& 0xff]
543 | fp_maskl
[4][r
>> 24]
544 | fp_maskl
[5][(r
>> 16) & 0xff]
545 | fp_maskl
[6][(r
>> 8) & 0xff]
546 | fp_maskl
[7][r
& 0xff];
547 *r_out
= fp_maskr
[0][l
>> 24]
548 | fp_maskr
[1][(l
>> 16) & 0xff]
549 | fp_maskr
[2][(l
>> 8) & 0xff]
550 | fp_maskr
[3][l
& 0xff]
551 | fp_maskr
[4][r
>> 24]
552 | fp_maskr
[5][(r
>> 16) & 0xff]
553 | fp_maskr
[6][(r
>> 8) & 0xff]
554 | fp_maskr
[7][r
& 0xff];
560 des_cipher(const char *in
, char *out
, long salt
, int count
)
562 u_long l_out
, r_out
, rawl
, rawr
;
565 if (!des_initialised
)
570 rawl
= ntohl(*((u_long
*) in
));
571 rawr
= ntohl(*(((u_long
*) in
) + 1));
573 retval
= do_des(rawl
, rawr
, &l_out
, &r_out
, count
);
575 *((u_long
*) out
) = htonl(l_out
);
576 *(((u_long
*) out
) + 1) = htonl(r_out
);
585 u_long packed_keys
[2];
588 p
= (u_char
*) packed_keys
;
590 for (i
= 0; i
< 8; i
++) {
592 for (j
= 0; j
< 8; j
++)
596 return(des_setkey(p
));
601 encrypt(char *block
, int flag
)
607 if (!des_initialised
)
612 for (i
= 0; i
< 2; i
++) {
614 for (j
= 0; j
< 32; j
++)
618 retval
= do_des(io
[0], io
[1], io
, io
+ 1, flag
? -1 : 1);
619 for (i
= 0; i
< 2; i
++)
620 for (j
= 0; j
< 32; j
++)
621 block
[(i
<< 5) | j
] = (io
[i
] & bits32
[j
]) ? 1 : 0;