Fix typo in MLINK name.
[dragonfly.git] / lib / libcipher / crypt.c
blob85273e4eadddfbda624e876b59da13096f3ca2dc
1 /*
2 * FreeSec: libcrypt for NetBSD
4 * Copyright (c) 1994 David Burren
5 * All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
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
29 * SUCH DAMAGE.
31 * $FreeBSD: src/secure/lib/libcipher/crypt.c,v 1.6 1999/08/28 01:30:21 peter Exp $
33 * This is an original implementation of the DES and the crypt(3) interfaces
34 * by David Burren <davidb@werj.com.au>.
36 * An excellent reference on the underlying algorithm (and related
37 * algorithms) is:
39 * B. Schneier, Applied Cryptography: protocols, algorithms,
40 * and source code in C, John Wiley & Sons, 1994.
42 * Note that in that book's description of DES the lookups for the initial,
43 * pbox, and final permutations are inverted (this has been brought to the
44 * attention of the author). A list of errata for this book has been
45 * posted to the sci.crypt newsgroup by the author and is available for FTP.
47 * ARCHITECTURE ASSUMPTIONS:
48 * This code assumes that u_longs are 32 bits. It will probably not
49 * operate on 64-bit machines without modifications.
50 * It is assumed that the 8-byte arrays passed by reference can be
51 * addressed as arrays of u_longs (ie. the CPU is not picky about
52 * alignment).
54 #include <sys/types.h>
55 #include <sys/param.h>
56 #include <pwd.h>
58 #ifdef DEBUG
59 # include <stdio.h>
60 #endif
63 static u_char IP[64] = {
64 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
65 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
66 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
67 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7
70 static u_char inv_key_perm[64];
71 static u_char u_key_perm[56];
72 static u_char key_perm[56] = {
73 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
74 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
75 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
76 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
79 static u_char key_shifts[16] = {
80 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
83 static u_char inv_comp_perm[56];
84 static u_char comp_perm[48] = {
85 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
86 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
87 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
88 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
92 * No E box is used, as it's replaced by some ANDs, shifts, and ORs.
95 static u_char u_sbox[8][64];
96 static u_char 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
104 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
105 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
106 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
107 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9
110 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
111 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
112 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
113 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12
116 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
117 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
118 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
119 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14
122 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
123 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
124 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
125 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3
128 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
129 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
130 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
131 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13
134 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
135 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
136 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
137 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12
140 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
141 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
142 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
143 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
147 static u_char un_pbox[32];
148 static u_char pbox[32] = {
149 16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
150 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
153 static u_long bits32[32] =
155 0x80000000, 0x40000000, 0x20000000, 0x10000000,
156 0x08000000, 0x04000000, 0x02000000, 0x01000000,
157 0x00800000, 0x00400000, 0x00200000, 0x00100000,
158 0x00080000, 0x00040000, 0x00020000, 0x00010000,
159 0x00008000, 0x00004000, 0x00002000, 0x00001000,
160 0x00000800, 0x00000400, 0x00000200, 0x00000100,
161 0x00000080, 0x00000040, 0x00000020, 0x00000010,
162 0x00000008, 0x00000004, 0x00000002, 0x00000001
165 static u_char bits8[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
167 static u_long saltbits;
168 static long old_salt;
169 static u_long *bits28, *bits24;
170 static u_char init_perm[64], final_perm[64];
171 static u_long en_keysl[16], en_keysr[16];
172 static u_long de_keysl[16], de_keysr[16];
173 static int des_initialised = 0;
174 static u_char m_sbox[4][4096];
175 static u_long psbox[4][256];
176 static u_long ip_maskl[8][256], ip_maskr[8][256];
177 static u_long fp_maskl[8][256], fp_maskr[8][256];
178 static u_long key_perm_maskl[8][128], key_perm_maskr[8][128];
179 static u_long comp_maskl[8][128], comp_maskr[8][128];
180 static u_long old_rawkey0, old_rawkey1;
182 static inline int
183 ascii_to_bin(char ch)
185 if (ch > 'z')
186 return(0);
187 if (ch >= 'a')
188 return(ch - 'a' + 38);
189 if (ch > 'Z')
190 return(0);
191 if (ch >= 'A')
192 return(ch - 'A' + 12);
193 if (ch > '9')
194 return(0);
195 if (ch >= '.')
196 return(ch - '.');
197 return(0);
201 static void
202 des_init(void)
204 int i, j, b, k, inbit, obit;
205 u_long *p, *il, *ir, *fl, *fr;
207 old_rawkey0 = old_rawkey1 = 0L;
208 saltbits = 0L;
209 old_salt = 0L;
210 bits24 = (bits28 = bits32 + 4) + 4;
213 * Invert the S-boxes, reordering the input bits.
215 for (i = 0; i < 8; i++)
216 for (j = 0; j < 64; j++) {
217 b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
218 u_sbox[i][j] = sbox[i][b];
222 * Convert the inverted S-boxes into 4 arrays of 8 bits.
223 * Each will handle 12 bits of the S-box input.
225 for (b = 0; b < 4; b++)
226 for (i = 0; i < 64; i++)
227 for (j = 0; j < 64; j++)
228 m_sbox[b][(i << 6) | j] =
229 (u_sbox[(b << 1)][i] << 4) |
230 u_sbox[(b << 1) + 1][j];
233 * Set up the initial & final permutations into a useful form, and
234 * initialise the inverted key permutation.
236 for (i = 0; i < 64; i++) {
237 init_perm[final_perm[i] = IP[i] - 1] = i;
238 inv_key_perm[i] = 255;
242 * Invert the key permutation and initialise the inverted key
243 * compression permutation.
245 for (i = 0; i < 56; i++) {
246 u_key_perm[i] = key_perm[i] - 1;
247 inv_key_perm[key_perm[i] - 1] = i;
248 inv_comp_perm[i] = 255;
252 * Invert the key compression permutation.
254 for (i = 0; i < 48; i++) {
255 inv_comp_perm[comp_perm[i] - 1] = i;
259 * Set up the OR-mask arrays for the initial and final permutations,
260 * and for the key initial and compression permutations.
262 for (k = 0; k < 8; k++) {
263 for (i = 0; i < 256; i++) {
264 *(il = &ip_maskl[k][i]) = 0L;
265 *(ir = &ip_maskr[k][i]) = 0L;
266 *(fl = &fp_maskl[k][i]) = 0L;
267 *(fr = &fp_maskr[k][i]) = 0L;
268 for (j = 0; j < 8; j++) {
269 inbit = 8 * k + j;
270 if (i & bits8[j]) {
271 if ((obit = init_perm[inbit]) < 32)
272 *il |= bits32[obit];
273 else
274 *ir |= bits32[obit-32];
275 if ((obit = final_perm[inbit]) < 32)
276 *fl |= bits32[obit];
277 else
278 *fr |= bits32[obit - 32];
282 for (i = 0; i < 128; i++) {
283 *(il = &key_perm_maskl[k][i]) = 0L;
284 *(ir = &key_perm_maskr[k][i]) = 0L;
285 for (j = 0; j < 7; j++) {
286 inbit = 8 * k + j;
287 if (i & bits8[j + 1]) {
288 if ((obit = inv_key_perm[inbit]) == 255)
289 continue;
290 if (obit < 28)
291 *il |= bits28[obit];
292 else
293 *ir |= bits28[obit - 28];
296 *(il = &comp_maskl[k][i]) = 0L;
297 *(ir = &comp_maskr[k][i]) = 0L;
298 for (j = 0; j < 7; j++) {
299 inbit = 7 * k + j;
300 if (i & bits8[j + 1]) {
301 if ((obit=inv_comp_perm[inbit]) == 255)
302 continue;
303 if (obit < 24)
304 *il |= bits24[obit];
305 else
306 *ir |= bits24[obit - 24];
313 * Invert the P-box permutation, and convert into OR-masks for
314 * handling the output of the S-box arrays setup above.
316 for (i = 0; i < 32; i++)
317 un_pbox[pbox[i] - 1] = i;
319 for (b = 0; b < 4; b++)
320 for (i = 0; i < 256; i++) {
321 *(p = &psbox[b][i]) = 0L;
322 for (j = 0; j < 8; j++) {
323 if (i & bits8[j])
324 *p |= bits32[un_pbox[8 * b + j]];
328 des_initialised = 1;
332 static void
333 setup_salt(long salt)
335 u_long obit, saltbit;
336 int i;
338 if (salt == old_salt)
339 return;
340 old_salt = salt;
342 saltbits = 0L;
343 saltbit = 1;
344 obit = 0x800000;
345 for (i = 0; i < 24; i++) {
346 if (salt & saltbit)
347 saltbits |= obit;
348 saltbit <<= 1;
349 obit >>= 1;
355 des_setkey(const char *key)
357 u_long k0, k1, rawkey0, rawkey1;
358 int shifts, round;
360 if (!des_initialised)
361 des_init();
363 rawkey0 = ntohl(*(u_long *) key);
364 rawkey1 = ntohl(*(u_long *) (key + 4));
366 if ((rawkey0 | rawkey1)
367 && rawkey0 == old_rawkey0
368 && rawkey1 == old_rawkey1) {
370 * Already setup for this key.
371 * This optimisation fails on a zero key (which is weak and
372 * has bad parity anyway) in order to simplify the starting
373 * conditions.
375 return(0);
377 old_rawkey0 = rawkey0;
378 old_rawkey1 = rawkey1;
381 * Do key permutation and split into two 28-bit subkeys.
383 k0 = key_perm_maskl[0][rawkey0 >> 25]
384 | key_perm_maskl[1][(rawkey0 >> 17) & 0x7f]
385 | key_perm_maskl[2][(rawkey0 >> 9) & 0x7f]
386 | key_perm_maskl[3][(rawkey0 >> 1) & 0x7f]
387 | key_perm_maskl[4][rawkey1 >> 25]
388 | key_perm_maskl[5][(rawkey1 >> 17) & 0x7f]
389 | key_perm_maskl[6][(rawkey1 >> 9) & 0x7f]
390 | key_perm_maskl[7][(rawkey1 >> 1) & 0x7f];
391 k1 = key_perm_maskr[0][rawkey0 >> 25]
392 | key_perm_maskr[1][(rawkey0 >> 17) & 0x7f]
393 | key_perm_maskr[2][(rawkey0 >> 9) & 0x7f]
394 | key_perm_maskr[3][(rawkey0 >> 1) & 0x7f]
395 | key_perm_maskr[4][rawkey1 >> 25]
396 | key_perm_maskr[5][(rawkey1 >> 17) & 0x7f]
397 | key_perm_maskr[6][(rawkey1 >> 9) & 0x7f]
398 | key_perm_maskr[7][(rawkey1 >> 1) & 0x7f];
400 * Rotate subkeys and do compression permutation.
402 shifts = 0;
403 for (round = 0; round < 16; round++) {
404 u_long t0, t1;
406 shifts += key_shifts[round];
408 t0 = (k0 << shifts) | (k0 >> (28 - shifts));
409 t1 = (k1 << shifts) | (k1 >> (28 - shifts));
411 de_keysl[15 - round] =
412 en_keysl[round] = comp_maskl[0][(t0 >> 21) & 0x7f]
413 | comp_maskl[1][(t0 >> 14) & 0x7f]
414 | comp_maskl[2][(t0 >> 7) & 0x7f]
415 | comp_maskl[3][t0 & 0x7f]
416 | comp_maskl[4][(t1 >> 21) & 0x7f]
417 | comp_maskl[5][(t1 >> 14) & 0x7f]
418 | comp_maskl[6][(t1 >> 7) & 0x7f]
419 | comp_maskl[7][t1 & 0x7f];
421 de_keysr[15 - round] =
422 en_keysr[round] = comp_maskr[0][(t0 >> 21) & 0x7f]
423 | comp_maskr[1][(t0 >> 14) & 0x7f]
424 | comp_maskr[2][(t0 >> 7) & 0x7f]
425 | comp_maskr[3][t0 & 0x7f]
426 | comp_maskr[4][(t1 >> 21) & 0x7f]
427 | comp_maskr[5][(t1 >> 14) & 0x7f]
428 | comp_maskr[6][(t1 >> 7) & 0x7f]
429 | comp_maskr[7][t1 & 0x7f];
431 return(0);
435 static int
436 do_des( u_long l_in, u_long r_in, u_long *l_out, u_long *r_out, int count)
439 * l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
441 u_long l, r, *kl, *kr, *kl1, *kr1;
442 u_long f, r48l, r48r;
443 int round;
445 if (count == 0) {
446 return(1);
447 } else if (count > 0) {
449 * Encrypting
451 kl1 = en_keysl;
452 kr1 = en_keysr;
453 } else {
455 * Decrypting
457 count = -count;
458 kl1 = de_keysl;
459 kr1 = de_keysr;
463 * Do initial permutation (IP).
465 l = ip_maskl[0][l_in >> 24]
466 | ip_maskl[1][(l_in >> 16) & 0xff]
467 | ip_maskl[2][(l_in >> 8) & 0xff]
468 | ip_maskl[3][l_in & 0xff]
469 | ip_maskl[4][r_in >> 24]
470 | ip_maskl[5][(r_in >> 16) & 0xff]
471 | ip_maskl[6][(r_in >> 8) & 0xff]
472 | ip_maskl[7][r_in & 0xff];
473 r = ip_maskr[0][l_in >> 24]
474 | ip_maskr[1][(l_in >> 16) & 0xff]
475 | ip_maskr[2][(l_in >> 8) & 0xff]
476 | ip_maskr[3][l_in & 0xff]
477 | ip_maskr[4][r_in >> 24]
478 | ip_maskr[5][(r_in >> 16) & 0xff]
479 | ip_maskr[6][(r_in >> 8) & 0xff]
480 | ip_maskr[7][r_in & 0xff];
482 while (count--) {
484 * Do each round.
486 kl = kl1;
487 kr = kr1;
488 round = 16;
489 while (round--) {
491 * Expand R to 48 bits (simulate the E-box).
493 r48l = ((r & 0x00000001) << 23)
494 | ((r & 0xf8000000) >> 9)
495 | ((r & 0x1f800000) >> 11)
496 | ((r & 0x01f80000) >> 13)
497 | ((r & 0x001f8000) >> 15);
499 r48r = ((r & 0x0001f800) << 7)
500 | ((r & 0x00001f80) << 5)
501 | ((r & 0x000001f8) << 3)
502 | ((r & 0x0000001f) << 1)
503 | ((r & 0x80000000) >> 31);
505 * Do salting for crypt() and friends, and
506 * XOR with the permuted key.
508 f = (r48l ^ r48r) & saltbits;
509 r48l ^= f ^ *kl++;
510 r48r ^= f ^ *kr++;
512 * Do sbox lookups (which shrink it back to 32 bits)
513 * and do the pbox permutation at the same time.
515 f = psbox[0][m_sbox[0][r48l >> 12]]
516 | psbox[1][m_sbox[1][r48l & 0xfff]]
517 | psbox[2][m_sbox[2][r48r >> 12]]
518 | psbox[3][m_sbox[3][r48r & 0xfff]];
520 * Now that we've permuted things, complete f().
522 f ^= l;
523 l = r;
524 r = f;
526 r = l;
527 l = f;
530 * Do final permutation (inverse of IP).
532 *l_out = fp_maskl[0][l >> 24]
533 | fp_maskl[1][(l >> 16) & 0xff]
534 | fp_maskl[2][(l >> 8) & 0xff]
535 | fp_maskl[3][l & 0xff]
536 | fp_maskl[4][r >> 24]
537 | fp_maskl[5][(r >> 16) & 0xff]
538 | fp_maskl[6][(r >> 8) & 0xff]
539 | fp_maskl[7][r & 0xff];
540 *r_out = fp_maskr[0][l >> 24]
541 | fp_maskr[1][(l >> 16) & 0xff]
542 | fp_maskr[2][(l >> 8) & 0xff]
543 | fp_maskr[3][l & 0xff]
544 | fp_maskr[4][r >> 24]
545 | fp_maskr[5][(r >> 16) & 0xff]
546 | fp_maskr[6][(r >> 8) & 0xff]
547 | fp_maskr[7][r & 0xff];
548 return(0);
553 des_cipher(const char *in, char *out, long salt, int count)
555 u_long l_out, r_out, rawl, rawr;
556 int retval;
558 if (!des_initialised)
559 des_init();
561 setup_salt(salt);
563 rawl = ntohl(*((u_long *) in));
564 rawr = ntohl(*(((u_long *) in) + 1));
566 retval = do_des(rawl, rawr, &l_out, &r_out, count);
568 *((u_long *) out) = htonl(l_out);
569 *(((u_long *) out) + 1) = htonl(r_out);
570 return(retval);
575 setkey(char *key)
577 int i, j;
578 u_long packed_keys[2];
579 u_char *p;
581 p = (u_char *) packed_keys;
583 for (i = 0; i < 8; i++) {
584 p[i] = 0;
585 for (j = 0; j < 8; j++)
586 if (*key++ & 1)
587 p[i] |= bits8[j];
589 return(des_setkey(p));
594 encrypt(char *block, int flag)
596 u_long io[2];
597 u_char *p;
598 int i, j, retval;
600 if (!des_initialised)
601 des_init();
603 setup_salt(0L);
604 p = block;
605 for (i = 0; i < 2; i++) {
606 io[i] = 0L;
607 for (j = 0; j < 32; j++)
608 if (*p++ & 1)
609 io[i] |= bits32[j];
611 retval = do_des(io[0], io[1], io, io + 1, flag ? -1 : 1);
612 for (i = 0; i < 2; i++)
613 for (j = 0; j < 32; j++)
614 block[(i << 5) | j] = (io[i] & bits32[j]) ? 1 : 0;
615 return(retval);