From 3180bd48514226f373165769f98011875d69734b Mon Sep 17 00:00:00 2001 From: Mark Eichin Date: Fri, 10 Jun 1994 00:25:45 +0000 Subject: add ferguson des code, to simplify autoconf git-svn-id: svn://anonsvn.mit.edu/krb5/trunk@3693 dc483132-0cff-0310-8789-dd5450dbe970 --- src/lib/crypto/des/f_README | 69 +++++++++ src/lib/crypto/des/f_cbc.c | 198 ++++++++++++++++++++++++ src/lib/crypto/des/f_cksum.c | 108 +++++++++++++ src/lib/crypto/des/f_ecb.c | 95 ++++++++++++ src/lib/crypto/des/f_parity.c | 62 ++++++++ src/lib/crypto/des/f_pcbc.c | 207 +++++++++++++++++++++++++ src/lib/crypto/des/f_sched.c | 337 +++++++++++++++++++++++++++++++++++++++++ src/lib/crypto/des/f_tables.c | 342 ++++++++++++++++++++++++++++++++++++++++++ src/lib/crypto/des/f_tables.h | 229 ++++++++++++++++++++++++++++ 9 files changed, 1647 insertions(+) create mode 100644 src/lib/crypto/des/f_README create mode 100644 src/lib/crypto/des/f_cbc.c create mode 100644 src/lib/crypto/des/f_cksum.c create mode 100644 src/lib/crypto/des/f_ecb.c create mode 100644 src/lib/crypto/des/f_parity.c create mode 100644 src/lib/crypto/des/f_pcbc.c create mode 100644 src/lib/crypto/des/f_sched.c create mode 100644 src/lib/crypto/des/f_tables.c create mode 100644 src/lib/crypto/des/f_tables.h (limited to 'src') diff --git a/src/lib/crypto/des/f_README b/src/lib/crypto/des/f_README new file mode 100644 index 000000000..0d381e373 --- /dev/null +++ b/src/lib/crypto/des/f_README @@ -0,0 +1,69 @@ +/* + * Copyright (c) 1990 Dennis Ferguson. All rights reserved. + * + * Commercial use is permitted only if products which are derived from + * or include this software are made available for purchase and/or use + * in Canada. Otherwise, redistribution and use in source and binary + * forms are permitted. + */ + +Sorry about the poor quality of installation instructions. Included +here are replacements for the DES portions of Eric Young's kerberos +DES library replacement. To use this you will need his distribution. +Untar the latter and: + +(1) Copy all .c and .h files into the distribution directory. This will + overwrite some files and add others. + +(2) Apply the patch included here to set_key.c in the distribution directory. + +(3) Edit the Imakefile (or the Makefile) to include the following files + on the SRCS= line: + + des_tables.c ecb_buffer.c make_sched.c + + Add the following files to the OBJS= line: + + des_tables.o ecb_buffer.o make_sched.o + + Add the following file to the CODE= line: + + des_tables.h + +Recompile and you're done. + +The salient differences between this DES and Eric Young's are as follows: + +(1) There are no dependencies on byte ordering, the ability to do + unaligned loads and stores, or any other machine dependencies + that I know of. There are no #ifdef's. The code could probably + be made faster by adding such things, but not enough to be worth + it. + +(2) Combined S and P tables are used for the inner loop of the cipher + routine and the E expansion is computed on the fly, like Eric + Young's code, but the computation is reordered from the standard + to save instructions. + +(3) The initial and final permutations are table driven, and take + about the same amount of work as a single round of the inner + loop (i.e. only about 12% of the work done for an ecb encryption + is spent in the IP and FP code). + +(4) Since NTP (for which this DES was originally implemented) uses + lots of keys to encrypt small things, the key permutation code + has been well worked over and is quite speedy (the amount of + work required to permute a key is on the order of that required + to do a single ECB encryption, more or less). + +(5) Since the code required to do an ECB encryption using the tables + is actually fairly compact, even with lots of inlining, it was + implemented as a macro and is expanded in situ where needed. + +On the one machine I ran a comparison on this code ran 80% faster than +Eric's, compiled into a slightly smaller space, and did pass destest. +I suspect this stuff is also faster, and not a lot larger, than the +library MIT doesn't export with kerberos. You mileage may vary. + +The silly copyright was a (probably ineffective) afterthought. If it +really inconveniences you give me a call. diff --git a/src/lib/crypto/des/f_cbc.c b/src/lib/crypto/des/f_cbc.c new file mode 100644 index 000000000..c04f9053e --- /dev/null +++ b/src/lib/crypto/des/f_cbc.c @@ -0,0 +1,198 @@ +/* + * Copyright (c) 1990 Dennis Ferguson. All rights reserved. + * + * Commercial use is permitted only if products which are derived from + * or include this software are made available for purchase and/or use + * in Canada. Otherwise, redistribution and use in source and binary + * forms are permitted. + */ + +/* + * des_cbc_encrypt.c - an implementation of the DES cipher function in cbc mode + */ +#include "des.h" +#include "f_tables.h" + +/* + * des_cbc_encrypt - {en,de}crypt a stream in CBC mode + */ +int +mit_des_cbc_encrypt(in, out, length, schedule, ivec, encrypt) + des_cblock *in; + des_cblock *out; + long length; + des_key_schedule schedule; + des_cblock ivec; + int encrypt; +{ + register unsigned KRB_INT32 left, right; + register unsigned KRB_INT32 temp; + register unsigned KRB_INT32 *kp; + register unsigned char *ip, *op; + + /* + * Get key pointer here. This won't need to be reinitialized + */ + kp = (unsigned KRB_INT32 *)schedule; + + /* + * Deal with encryption and decryption separately. + */ + if (encrypt) { + /* + * Initialize left and right with the contents of the initial + * vector. + */ + ip = (unsigned char *)ivec; + GET_HALF_BLOCK(left, ip); + GET_HALF_BLOCK(right, ip); + + /* + * Suitably initialized, now work the length down 8 bytes + * at a time. + */ + ip = (unsigned char *)in; + op = (unsigned char *)out; + while (length > 0) { + /* + * Get more input, xor it in. If the length is + * greater than or equal to 8 this is straight + * forward. Otherwise we have to fart around. + */ + if (length >= 8) { + left ^= ((*ip++) & 0xff) << 24; + left ^= ((*ip++) & 0xff) << 16; + left ^= ((*ip++) & 0xff) << 8; + left ^= (*ip++) & 0xff; + right ^= ((*ip++) & 0xff) << 24; + right ^= ((*ip++) & 0xff) << 16; + right ^= ((*ip++) & 0xff) << 8; + right ^= (*ip++) & 0xff; + length -= 8; + } else { + /* + * Oh, shoot. We need to pad the + * end with zeroes. Work backwards + * to do this. + */ + ip += (int) length; + switch(length) { + case 7: + right ^= (*(--ip) & 0xff) << 8; + case 6: + right ^= (*(--ip) & 0xff) << 16; + case 5: + right ^= (*(--ip) & 0xff) << 24; + case 4: + left ^= *(--ip) & 0xff; + case 3: + left ^= (*(--ip) & 0xff) << 8; + case 2: + left ^= (*(--ip) & 0xff) << 16; + case 1: + left ^= (*(--ip) & 0xff) << 24; + break; + } + length = 0; + } + + /* + * Encrypt what we have + */ + DES_DO_ENCRYPT(left, right, temp, kp); + + /* + * Copy the results out + */ + PUT_HALF_BLOCK(left, op); + PUT_HALF_BLOCK(right, op); + } + } else { + /* + * Decrypting is harder than encrypting because of + * the necessity of remembering a lot more things. + * Should think about this a little more... + */ + unsigned KRB_INT32 ocipherl, ocipherr; + unsigned KRB_INT32 cipherl, cipherr; + + if (length <= 0) + return 0; + + /* + * Prime the old cipher with ivec. + */ + ip = (unsigned char *)ivec; + GET_HALF_BLOCK(ocipherl, ip); + GET_HALF_BLOCK(ocipherr, ip); + + /* + * Now do this in earnest until we run out of length. + */ + ip = (unsigned char *)in; + op = (unsigned char *)out; + for (;;) { /* check done inside loop */ + /* + * Read a block from the input into left and + * right. Save this cipher block for later. + */ + GET_HALF_BLOCK(left, ip); + GET_HALF_BLOCK(right, ip); + cipherl = left; + cipherr = right; + + /* + * Decrypt this. + */ + DES_DO_DECRYPT(left, right, temp, kp); + + /* + * Xor with the old cipher to get plain + * text. Output 8 or less bytes of this. + */ + left ^= ocipherl; + right ^= ocipherr; + if (length > 8) { + length -= 8; + PUT_HALF_BLOCK(left, op); + PUT_HALF_BLOCK(right, op); + /* + * Save current cipher block here + */ + ocipherl = cipherl; + ocipherr = cipherr; + } else { + /* + * Trouble here. Start at end of output, + * work backwards. + */ + op += (int) length; + switch(length) { + case 8: + *(--op) = right & 0xff; + case 7: + *(--op) = (right >> 8) & 0xff; + case 6: + *(--op) = (right >> 16) & 0xff; + case 5: + *(--op) = (right >> 24) & 0xff; + case 4: + *(--op) = left & 0xff; + case 3: + *(--op) = (left >> 8) & 0xff; + case 2: + *(--op) = (left >> 16) & 0xff; + case 1: + *(--op) = (left >> 24) & 0xff; + break; + } + break; /* we're done */ + } + } + } + + /* + * Done, return nothing. + */ + return 0; +} diff --git a/src/lib/crypto/des/f_cksum.c b/src/lib/crypto/des/f_cksum.c new file mode 100644 index 000000000..0497b9789 --- /dev/null +++ b/src/lib/crypto/des/f_cksum.c @@ -0,0 +1,108 @@ +/* + * Copyright (c) 1990 Dennis Ferguson. All rights reserved. + * + * Commercial use is permitted only if products which are derived from + * or include this software are made available for purchase and/or use + * in Canada. Otherwise, redistribution and use in source and binary + * forms are permitted. + */ + +/* + * des_cbc_cksum.c - compute an 8 byte checksum using DES in CBC mode + */ +#include "des.h" +#include "f_tables.h" + +unsigned long +mit_des_cbc_cksum(in, out, length, schedule, ivec) + des_cblock *in; + des_cblock *out; + long length; + des_key_schedule schedule; + des_cblock ivec; +{ + register unsigned KRB_INT32 left, right; + register unsigned KRB_INT32 temp; + register unsigned KRB_INT32 *kp; + register unsigned char *ip; + register KRB_INT32 len; + + /* + * Initialize left and right with the contents of the initial + * vector. + */ + ip = (unsigned char *)ivec; + GET_HALF_BLOCK(left, ip); + GET_HALF_BLOCK(right, ip); + + /* + * Suitably initialized, now work the length down 8 bytes + * at a time. + */ + ip = (unsigned char *)in; + len = length; + while (len > 0) { + /* + * Get more input, xor it in. If the length is + * greater than or equal to 8 this is straight + * forward. Otherwise we have to fart around. + */ + if (len >= 8) { + left ^= ((*ip++) & 0xff) << 24; + left ^= ((*ip++) & 0xff) << 16; + left ^= ((*ip++) & 0xff) << 8; + left ^= (*ip++) & 0xff; + right ^= ((*ip++) & 0xff) << 24; + right ^= ((*ip++) & 0xff) << 16; + right ^= ((*ip++) & 0xff) << 8; + right ^= (*ip++) & 0xff; + len -= 8; + } else { + /* + * Oh, shoot. We need to pad the + * end with zeroes. Work backwards + * to do this. + */ + ip += (int) len; + switch(len) { + case 7: + right ^= (*(--ip) & 0xff) << 8; + case 6: + right ^= (*(--ip) & 0xff) << 16; + case 5: + right ^= (*(--ip) & 0xff) << 24; + case 4: + left ^= *(--ip) & 0xff; + case 3: + left ^= (*(--ip) & 0xff) << 8; + case 2: + left ^= (*(--ip) & 0xff) << 16; + case 1: + left ^= (*(--ip) & 0xff) << 24; + break; + } + len = 0; + } + + /* + * Encrypt what we have + */ + kp = (unsigned KRB_INT32 *)schedule; + DES_DO_ENCRYPT(left, right, temp, kp); + } + + /* + * Done. Left and right have the checksum. Put it into + * the output. + */ + ip = (unsigned char *)out; + PUT_HALF_BLOCK(left, ip); + PUT_HALF_BLOCK(right, ip); + + /* + * Return right. I'll bet the MIT code returns this + * inconsistantly (with the low order byte of the checksum + * not always in the low order byte of the KRB_INT32). We won't. + */ + return right; +} diff --git a/src/lib/crypto/des/f_ecb.c b/src/lib/crypto/des/f_ecb.c new file mode 100644 index 000000000..f17073ebf --- /dev/null +++ b/src/lib/crypto/des/f_ecb.c @@ -0,0 +1,95 @@ +/* + * Copyright (c) 1990 Dennis Ferguson. All rights reserved. + * + * Commercial use is permitted only if products which are derived from + * or include this software are made available for purchase and/or use + * in Canada. Otherwise, redistribution and use in source and binary + * forms are permitted. + */ + +/* + * des_ecb_encrypt.c - do an encryption in ECB mode + */ +#include "des.h" +#include "f_tables.h" + +/* + * des_ecb_encrypt - {en,de}crypt a block in ECB mode + */ +int +mit_des_ecb_encrypt(in, out, schedule, encrypt) + des_cblock *in; + des_cblock *out; + des_key_schedule schedule; + int encrypt; +{ + register unsigned KRB_INT32 left, right; + register unsigned KRB_INT32 temp; + register int i; + + { + /* + * Need a temporary for copying the data in + */ + register unsigned char *datap; + + /* + * Copy the input block into the registers + */ + datap = (unsigned char *)in; + GET_HALF_BLOCK(left, datap); + GET_HALF_BLOCK(right, datap); + } + + /* + * Do the initial permutation. + */ + DES_INITIAL_PERM(left, right, temp); + + /* + * Now the rounds. Use different code depending on whether it + * is an encryption or a decryption (gross, should keep both + * sets of keys in the key schedule instead). + */ + if (encrypt) { + register unsigned KRB_INT32 *kp; + + kp = (unsigned KRB_INT32 *)schedule; + for (i = 0; i < 8; i++) { + DES_SP_ENCRYPT_ROUND(left, right, temp, kp); + DES_SP_ENCRYPT_ROUND(right, left, temp, kp); + } + } else { + register unsigned KRB_INT32 *kp; + + /* + * Point kp past end of schedule + */ + kp = ((unsigned KRB_INT32 *)schedule) + (2 * 16);; + for (i = 0; i < 8; i++) { + DES_SP_DECRYPT_ROUND(left, right, temp, kp); + DES_SP_DECRYPT_ROUND(right, left, temp, kp); + } + } + + /* + * Do the final permutation + */ + DES_FINAL_PERM(left, right, temp); + + /* + * Finally, copy the result out a byte at a time + */ + { + register unsigned char *datap; + + datap = (unsigned char *)out; + PUT_HALF_BLOCK(left, datap); + PUT_HALF_BLOCK(right, datap); + } + + /* + * return nothing + */ + return (0); +} diff --git a/src/lib/crypto/des/f_parity.c b/src/lib/crypto/des/f_parity.c new file mode 100644 index 000000000..a2e216dca --- /dev/null +++ b/src/lib/crypto/des/f_parity.c @@ -0,0 +1,62 @@ +/* + * These routines check and fix parity of encryption keys for the DES + * algorithm. + * + * They are a replacement for routines in key_parity.c, that don't require + * the table building that they do. + * + * Mark Eichin -- Cygnus Support + */ + +#ifndef lint +static char rcsid_f_parity_c[] = +"$Header$"; +#endif lint + +#include "des.h" + +/* + * des_fixup_key_parity: Forces odd parity per byte; parity is bits + * 8,16,...64 in des order, implies 0, 8, 16, ... + * vax order. + */ +#define smask(step) ((1<>step)&smask(step))) +#define parity_char(x) pstep(pstep(pstep((x),4),2),1) + +void +mit_des_fixup_key_parity(key) + register des_cblock key; +{ + int i; + for (i=0; i 0) { + /* + * Get block of input. If the length is + * greater than 8 this is straight + * forward. Otherwise we have to fart around. + */ + if (length > 8) { + GET_HALF_BLOCK(plainl, ip); + GET_HALF_BLOCK(plainr, ip); + left ^= plainl; + right ^= plainr; + length -= 8; + } else { + /* + * Oh, shoot. We need to pad the + * end with zeroes. Work backwards + * to do this. We know this is the + * last block, though, so we don't have + * to save the plain text. + */ + ip += (int) length; + switch(length) { + case 8: + right ^= *(--ip) & 0xff; + case 7: + right ^= (*(--ip) & 0xff) << 8; + case 6: + right ^= (*(--ip) & 0xff) << 16; + case 5: + right ^= (*(--ip) & 0xff) << 24; + case 4: + left ^= *(--ip) & 0xff; + case 3: + left ^= (*(--ip) & 0xff) << 8; + case 2: + left ^= (*(--ip) & 0xff) << 16; + case 1: + left ^= (*(--ip) & 0xff) << 24; + break; + } + length = 0; + } + + /* + * Encrypt what we have + */ + DES_DO_ENCRYPT(left, right, temp, kp); + + /* + * Copy the results out + */ + PUT_HALF_BLOCK(left, op); + PUT_HALF_BLOCK(right, op); + + /* + * Xor with the old plain text + */ + left ^= plainl; + right ^= plainr; + } + } else { + /* + * Decrypting is harder than encrypting because of + * the necessity of remembering a lot more things. + * Should think about this a little more... + */ + unsigned KRB_INT32 ocipherl, ocipherr; + unsigned KRB_INT32 cipherl, cipherr; + + if (length <= 0) + return 0; + + /* + * Prime the old cipher with ivec. + */ + ip = (unsigned char *)ivec; + GET_HALF_BLOCK(ocipherl, ip); + GET_HALF_BLOCK(ocipherr, ip); + + /* + * Now do this in earnest until we run out of length. + */ + ip = (unsigned char *)in; + op = (unsigned char *)out; + for (;;) { /* check done inside loop */ + /* + * Read a block from the input into left and + * right. Save this cipher block for later. + */ + GET_HALF_BLOCK(left, ip); + GET_HALF_BLOCK(right, ip); + cipherl = left; + cipherr = right; + + /* + * Decrypt this. + */ + DES_DO_DECRYPT(left, right, temp, kp); + + /* + * Xor with the old cipher to get plain + * text. Output 8 or less bytes of this. + */ + left ^= ocipherl; + right ^= ocipherr; + if (length > 8) { + length -= 8; + PUT_HALF_BLOCK(left, op); + PUT_HALF_BLOCK(right, op); + /* + * Save current cipher block here + */ + ocipherl = cipherl ^ left; + ocipherr = cipherr ^ right; + } else { + /* + * Trouble here. Start at end of output, + * work backwards. + */ + op += (int) length; + switch(length) { + case 8: + *(--op) = right & 0xff; + case 7: + *(--op) = (right >> 8) & 0xff; + case 6: + *(--op) = (right >> 16) & 0xff; + case 5: + *(--op) = (right >> 24) & 0xff; + case 4: + *(--op) = left & 0xff; + case 3: + *(--op) = (left >> 8) & 0xff; + case 2: + *(--op) = (left >> 16) & 0xff; + case 1: + *(--op) = (left >> 24) & 0xff; + break; + } + break; /* we're done */ + } + } + } + + /* + * Done, return nothing. + */ + return 0; +} diff --git a/src/lib/crypto/des/f_sched.c b/src/lib/crypto/des/f_sched.c new file mode 100644 index 000000000..6ba6079d6 --- /dev/null +++ b/src/lib/crypto/des/f_sched.c @@ -0,0 +1,337 @@ +/* + * Copyright (c) 1990 Dennis Ferguson. All rights reserved. + * + * Commercial use is permitted only if products which are derived from + * or include this software are made available for purchase and/or use + * in Canada. Otherwise, redistribution and use in source and binary + * forms are permitted. + */ + +/* + * des_make_sched.c - permute a DES key, returning the resulting key schedule + */ +#include "des.h" +#include +#include + +/* + * Permuted choice 1 tables. These are used to extract bits + * from the left and right parts of the key to form Ci and Di. + * The code that uses these tables knows which bits from which + * part of each key are used to form Ci and Di. + */ +static const unsigned KRB_INT32 PC1_CL[8] = { + 0x00000000, 0x00000010, 0x00001000, 0x00001010, + 0x00100000, 0x00100010, 0x00101000, 0x00101010 +}; + +static const unsigned KRB_INT32 PC1_DL[16] = { + 0x00000000, 0x00100000, 0x00001000, 0x00101000, + 0x00000010, 0x00100010, 0x00001010, 0x00101010, + 0x00000001, 0x00100001, 0x00001001, 0x00101001, + 0x00000011, 0x00100011, 0x00001011, 0x00101011 +}; + +static const unsigned KRB_INT32 PC1_CR[16] = { + 0x00000000, 0x00000001, 0x00000100, 0x00000101, + 0x00010000, 0x00010001, 0x00010100, 0x00010101, + 0x01000000, 0x01000001, 0x01000100, 0x01000101, + 0x01010000, 0x01010001, 0x01010100, 0x01010101 +}; + +static const unsigned KRB_INT32 PC1_DR[8] = { + 0x00000000, 0x01000000, 0x00010000, 0x01010000, + 0x00000100, 0x01000100, 0x00010100, 0x01010100 +}; + + +/* + * At the start of some iterations of the key schedule we do + * a circular left shift by one place, while for others we do a shift by + * two places. This has bits set for the iterations where we do 2 bit + * shifts, starting at the low order bit. + */ +#define TWO_BIT_SHIFTS 0x7efc + +/* + * Permuted choice 2 tables. The first actually produces the low order + * 24 bits of the subkey Ki from the 28 bit value of Ci. The second produces + * the high order 24 bits from Di. The tables are indexed by six bit + * segments of Ci and Di respectively. The code is handcrafted to compute + * the appropriate 6 bit chunks. + * + * Note that for ease of computation, the 24 bit values are produced with + * six bits going into each byte. Note also that the table has been byte + * rearranged to produce keys which match the order we will apply them + * in in the des code. + */ +static const unsigned KRB_INT32 PC2_C[4][64] = { + 0x00000000, 0x00000004, 0x00010000, 0x00010004, + 0x00000400, 0x00000404, 0x00010400, 0x00010404, + 0x00000020, 0x00000024, 0x00010020, 0x00010024, + 0x00000420, 0x00000424, 0x00010420, 0x00010424, + 0x01000000, 0x01000004, 0x01010000, 0x01010004, + 0x01000400, 0x01000404, 0x01010400, 0x01010404, + 0x01000020, 0x01000024, 0x01010020, 0x01010024, + 0x01000420, 0x01000424, 0x01010420, 0x01010424, + 0x00020000, 0x00020004, 0x00030000, 0x00030004, + 0x00020400, 0x00020404, 0x00030400, 0x00030404, + 0x00020020, 0x00020024, 0x00030020, 0x00030024, + 0x00020420, 0x00020424, 0x00030420, 0x00030424, + 0x01020000, 0x01020004, 0x01030000, 0x01030004, + 0x01020400, 0x01020404, 0x01030400, 0x01030404, + 0x01020020, 0x01020024, 0x01030020, 0x01030024, + 0x01020420, 0x01020424, 0x01030420, 0x01030424, + + 0x00000000, 0x02000000, 0x00000800, 0x02000800, + 0x00080000, 0x02080000, 0x00080800, 0x02080800, + 0x00000001, 0x02000001, 0x00000801, 0x02000801, + 0x00080001, 0x02080001, 0x00080801, 0x02080801, + 0x00000100, 0x02000100, 0x00000900, 0x02000900, + 0x00080100, 0x02080100, 0x00080900, 0x02080900, + 0x00000101, 0x02000101, 0x00000901, 0x02000901, + 0x00080101, 0x02080101, 0x00080901, 0x02080901, + 0x10000000, 0x12000000, 0x10000800, 0x12000800, + 0x10080000, 0x12080000, 0x10080800, 0x12080800, + 0x10000001, 0x12000001, 0x10000801, 0x12000801, + 0x10080001, 0x12080001, 0x10080801, 0x12080801, + 0x10000100, 0x12000100, 0x10000900, 0x12000900, + 0x10080100, 0x12080100, 0x10080900, 0x12080900, + 0x10000101, 0x12000101, 0x10000901, 0x12000901, + 0x10080101, 0x12080101, 0x10080901, 0x12080901, + + 0x00000000, 0x00040000, 0x00002000, 0x00042000, + 0x00100000, 0x00140000, 0x00102000, 0x00142000, + 0x20000000, 0x20040000, 0x20002000, 0x20042000, + 0x20100000, 0x20140000, 0x20102000, 0x20142000, + 0x00000008, 0x00040008, 0x00002008, 0x00042008, + 0x00100008, 0x00140008, 0x00102008, 0x00142008, + 0x20000008, 0x20040008, 0x20002008, 0x20042008, + 0x20100008, 0x20140008, 0x20102008, 0x20142008, + 0x00200000, 0x00240000, 0x00202000, 0x00242000, + 0x00300000, 0x00340000, 0x00302000, 0x00342000, + 0x20200000, 0x20240000, 0x20202000, 0x20242000, + 0x20300000, 0x20340000, 0x20302000, 0x20342000, + 0x00200008, 0x00240008, 0x00202008, 0x00242008, + 0x00300008, 0x00340008, 0x00302008, 0x00342008, + 0x20200008, 0x20240008, 0x20202008, 0x20242008, + 0x20300008, 0x20340008, 0x20302008, 0x20342008, + + 0x00000000, 0x00000010, 0x08000000, 0x08000010, + 0x00000200, 0x00000210, 0x08000200, 0x08000210, + 0x00000002, 0x00000012, 0x08000002, 0x08000012, + 0x00000202, 0x00000212, 0x08000202, 0x08000212, + 0x04000000, 0x04000010, 0x0c000000, 0x0c000010, + 0x04000200, 0x04000210, 0x0c000200, 0x0c000210, + 0x04000002, 0x04000012, 0x0c000002, 0x0c000012, + 0x04000202, 0x04000212, 0x0c000202, 0x0c000212, + 0x00001000, 0x00001010, 0x08001000, 0x08001010, + 0x00001200, 0x00001210, 0x08001200, 0x08001210, + 0x00001002, 0x00001012, 0x08001002, 0x08001012, + 0x00001202, 0x00001212, 0x08001202, 0x08001212, + 0x04001000, 0x04001010, 0x0c001000, 0x0c001010, + 0x04001200, 0x04001210, 0x0c001200, 0x0c001210, + 0x04001002, 0x04001012, 0x0c001002, 0x0c001012, + 0x04001202, 0x04001212, 0x0c001202, 0x0c001212 +}; + +static const unsigned KRB_INT32 PC2_D[4][64] = { + 0x00000000, 0x02000000, 0x00020000, 0x02020000, + 0x00000100, 0x02000100, 0x00020100, 0x02020100, + 0x00000008, 0x02000008, 0x00020008, 0x02020008, + 0x00000108, 0x02000108, 0x00020108, 0x02020108, + 0x00200000, 0x02200000, 0x00220000, 0x02220000, + 0x00200100, 0x02200100, 0x00220100, 0x02220100, + 0x00200008, 0x02200008, 0x00220008, 0x02220008, + 0x00200108, 0x02200108, 0x00220108, 0x02220108, + 0x00000200, 0x02000200, 0x00020200, 0x02020200, + 0x00000300, 0x02000300, 0x00020300, 0x02020300, + 0x00000208, 0x02000208, 0x00020208, 0x02020208, + 0x00000308, 0x02000308, 0x00020308, 0x02020308, + 0x00200200, 0x02200200, 0x00220200, 0x02220200, + 0x00200300, 0x02200300, 0x00220300, 0x02220300, + 0x00200208, 0x02200208, 0x00220208, 0x02220208, + 0x00200308, 0x02200308, 0x00220308, 0x02220308, + + 0x00000000, 0x00001000, 0x00000020, 0x00001020, + 0x00100000, 0x00101000, 0x00100020, 0x00101020, + 0x08000000, 0x08001000, 0x08000020, 0x08001020, + 0x08100000, 0x08101000, 0x08100020, 0x08101020, + 0x00000004, 0x00001004, 0x00000024, 0x00001024, + 0x00100004, 0x00101004, 0x00100024, 0x00101024, + 0x08000004, 0x08001004, 0x08000024, 0x08001024, + 0x08100004, 0x08101004, 0x08100024, 0x08101024, + 0x00000400, 0x00001400, 0x00000420, 0x00001420, + 0x00100400, 0x00101400, 0x00100420, 0x00101420, + 0x08000400, 0x08001400, 0x08000420, 0x08001420, + 0x08100400, 0x08101400, 0x08100420, 0x08101420, + 0x00000404, 0x00001404, 0x00000424, 0x00001424, + 0x00100404, 0x00101404, 0x00100424, 0x00101424, + 0x08000404, 0x08001404, 0x08000424, 0x08001424, + 0x08100404, 0x08101404, 0x08100424, 0x08101424, + + 0x00000000, 0x10000000, 0x00010000, 0x10010000, + 0x00000002, 0x10000002, 0x00010002, 0x10010002, + 0x00002000, 0x10002000, 0x00012000, 0x10012000, + 0x00002002, 0x10002002, 0x00012002, 0x10012002, + 0x00040000, 0x10040000, 0x00050000, 0x10050000, + 0x00040002, 0x10040002, 0x00050002, 0x10050002, + 0x00042000, 0x10042000, 0x00052000, 0x10052000, + 0x00042002, 0x10042002, 0x00052002, 0x10052002, + 0x20000000, 0x30000000, 0x20010000, 0x30010000, + 0x20000002, 0x30000002, 0x20010002, 0x30010002, + 0x20002000, 0x30002000, 0x20012000, 0x30012000, + 0x20002002, 0x30002002, 0x20012002, 0x30012002, + 0x20040000, 0x30040000, 0x20050000, 0x30050000, + 0x20040002, 0x30040002, 0x20050002, 0x30050002, + 0x20042000, 0x30042000, 0x20052000, 0x30052000, + 0x20042002, 0x30042002, 0x20052002, 0x30052002, + + 0x00000000, 0x04000000, 0x00000001, 0x04000001, + 0x01000000, 0x05000000, 0x01000001, 0x05000001, + 0x00000010, 0x04000010, 0x00000011, 0x04000011, + 0x01000010, 0x05000010, 0x01000011, 0x05000011, + 0x00080000, 0x04080000, 0x00080001, 0x04080001, + 0x01080000, 0x05080000, 0x01080001, 0x05080001, + 0x00080010, 0x04080010, 0x00080011, 0x04080011, + 0x01080010, 0x05080010, 0x01080011, 0x05080011, + 0x00000800, 0x04000800, 0x00000801, 0x04000801, + 0x01000800, 0x05000800, 0x01000801, 0x05000801, + 0x00000810, 0x04000810, 0x00000811, 0x04000811, + 0x01000810, 0x05000810, 0x01000811, 0x05000811, + 0x00080800, 0x04080800, 0x00080801, 0x04080801, + 0x01080800, 0x05080800, 0x01080801, 0x05080801, + 0x00080810, 0x04080810, 0x00080811, 0x04080811, + 0x01080810, 0x05080810, 0x01080811, 0x05080811 +}; + + + +/* + * Permute the key to give us our key schedule. + */ +int +make_key_sched(key, schedule) + mit_des_cblock key; + mit_des_key_schedule schedule; +{ + register unsigned KRB_INT32 c, d; + + { + /* + * Need a pointer for the keys and a temporary KRB_INT32 + */ + register unsigned char *k; + register unsigned KRB_INT32 tmp; + + /* + * Fetch the key into something we can work with + */ + k = (unsigned char *)key; + + /* + * The first permutted choice gives us the 28 bits for C0 and + * 28 for D0. C0 gets 12 bits from the left key and 16 from + * the right, while D0 gets 16 from the left and 12 from the + * right. The code knows which bits go where. + */ + tmp = ((unsigned KRB_INT32)(*(k)++)) << 24; + tmp |= ((unsigned KRB_INT32)(*(k)++)) << 16; + tmp |= ((unsigned KRB_INT32)(*(k)++)) << 8; + tmp |= (unsigned KRB_INT32)(*(k)++); /* left part of key */ + c = PC1_CL[(tmp >> 29) & 0x7] + | (PC1_CL[(tmp >> 21) & 0x7] << 1) + | (PC1_CL[(tmp >> 13) & 0x7] << 2) + | (PC1_CL[(tmp >> 5) & 0x7] << 3); + d = PC1_DL[(tmp >> 25) & 0xf] + | (PC1_DL[(tmp >> 17) & 0xf] << 1) + | (PC1_DL[(tmp >> 9) & 0xf] << 2) + | (PC1_DL[(tmp >> 1) & 0xf] << 3); + + tmp = ((unsigned KRB_INT32)(*(k)++)) << 24; + tmp |= ((unsigned KRB_INT32)(*(k)++)) << 16; + tmp |= ((unsigned KRB_INT32)(*(k)++)) << 8; + tmp |= (unsigned KRB_INT32)(*(k)++); /* right part of key */ + c |= PC1_CR[(tmp >> 28) & 0xf] + | (PC1_CR[(tmp >> 20) & 0xf] << 1) + | (PC1_CR[(tmp >> 12) & 0xf] << 2) + | (PC1_CR[(tmp >> 4) & 0xf] << 3); + d |= PC1_DR[(tmp >> 25) & 0x7] + | (PC1_DR[(tmp >> 17) & 0x7] << 1) + | (PC1_DR[(tmp >> 9) & 0x7] << 2) + | (PC1_DR[(tmp >> 1) & 0x7] << 3); + } + + { + /* + * Need several temporaries in here + */ + register unsigned KRB_INT32 ltmp, rtmp; + register unsigned KRB_INT32 *k; + register int two_bit_shifts; + register int i; + /* + * Now iterate to compute the key schedule. Note that we + * record the entire set of subkeys in 6 bit chunks since + * they are used that way. At 6 bits/char, we need + * 48/6 char's/subkey * 16 subkeys/encryption == 128 bytes. + * The schedule must be this big. + */ + k = (unsigned KRB_INT32 *)schedule; + two_bit_shifts = TWO_BIT_SHIFTS; + for (i = 16; i > 0; i--) { + /* + * Do the rotation. One bit and two bit rotations + * are done separately. Note C and D are 28 bits. + */ + if (two_bit_shifts & 0x1) { + c = ((c << 2) & 0xffffffc) | (c >> 26); + d = ((d << 2) & 0xffffffc) | (d >> 26); + } else { + c = ((c << 1) & 0xffffffe) | (c >> 27); + d = ((d << 1) & 0xffffffe) | (d >> 27); + } + two_bit_shifts >>= 1; + + /* + * Apply permutted choice 2 to C to get the first + * 24 bits worth of keys. Note that bits 9, 18, 22 + * and 25 (using DES numbering) in C are unused. The + * shift-mask stuff is done to delete these bits from + * the indices, since this cuts the table size in half. + * + * The table is torqued, by the way. If the standard + * byte order for this (high to low order) is 1234, + * the table actually gives us 4132. + */ + ltmp = PC2_C[0][((c >> 22) & 0x3f)] + | PC2_C[1][((c >> 15) & 0xf) | ((c >> 16) & 0x30)] + | PC2_C[2][((c >> 4) & 0x3) | ((c >> 9) & 0x3c)] + | PC2_C[3][((c ) & 0x7) | ((c >> 4) & 0x38)]; + /* + * Apply permutted choice 2 to D to get the other half. + * Here, bits 7, 10, 15 and 26 go unused. The sqeezing + * actually turns out to be cheaper here. + * + * This table is similarly torqued. If the standard + * byte order is 5678, the table has the bytes permuted + * to give us 7685. + */ + rtmp = PC2_D[0][((d >> 22) & 0x3f)] + | PC2_D[1][((d >> 14) & 0xf) | ((d >> 15) & 0x30)] + | PC2_D[2][((d >> 7) & 0x3f)] + | PC2_D[3][((d ) & 0x3) | ((d >> 1) & 0x3c)]; + + /* + * Make up two words of the key schedule, with a + * byte order which is convenient for the DES + * inner loop. The high order (first) word will + * hold bytes 7135 (high to low order) while the + * second holds bytes 4682. + */ + *k++ = (ltmp & 0x00ffff00) | (rtmp & 0xff0000ff); + *k++ = (ltmp & 0xff0000ff) | (rtmp & 0x00ffff00); + } + } + return (0); +} diff --git a/src/lib/crypto/des/f_tables.c b/src/lib/crypto/des/f_tables.c new file mode 100644 index 000000000..5fc3da3fb --- /dev/null +++ b/src/lib/crypto/des/f_tables.c @@ -0,0 +1,342 @@ +/* + * Copyright (c) 1990 Dennis Ferguson. All rights reserved. + * + * Commercial use is permitted only if products which are derived from + * or include this software are made available for purchase and/or use + * in Canada. Otherwise, redistribution and use in source and binary + * forms are permitted. + */ + +/* + * des_tables.c - precomputed tables used for the DES cipher function + */ + +/* + * Include the header file so something will complain if the + * declarations get out of sync + */ +#include "des.h" +#include "f_tables.h" + +/* + * These tables may be declared const if you want. Many compilers + * don't support this, though. + */ + +/* + * The DES algorithm which uses these is intended to be fairly speedy + * at the expense of some memory. All the standard hacks are used. + * The S boxes and the P permutation are precomputed into one table. + * The E box never actually appears explicitly since it is easy to apply + * this algorithmically as needed. The initial permutation and final + * (inverse initial) permutation are computed from tables designed to + * permute one byte at a time. This should run pretty fast on machines + * with 32 bit words and bit field/multiple bit shift instructions which + * are fast. + */ + +/* + * The initial permutation array. This is used to compute both the + * left and the right halves of the initial permutation using bytes + * from words made from the following operations: + * + * ((left & 0x55555555) << 1) | (right & 0x55555555) for left half + * (left & 0xaaaaaaaa) | ((right & 0xaaaaaaaa) >> 1) for right half + * + * The scheme is that we index into the table using each byte. The + * result from the high order byte is or'd with the result from the + * next byte shifted left once is or'd with the result from the next + * byte shifted left twice if or'd with the result from the low order + * byte shifted left by three. Clear? + */ + +const unsigned KRB_INT32 des_IP_table[256] = { + 0x00000000, 0x00000010, 0x00000001, 0x00000011, + 0x00001000, 0x00001010, 0x00001001, 0x00001011, + 0x00000100, 0x00000110, 0x00000101, 0x00000111, + 0x00001100, 0x00001110, 0x00001101, 0x00001111, + 0x00100000, 0x00100010, 0x00100001, 0x00100011, + 0x00101000, 0x00101010, 0x00101001, 0x00101011, + 0x00100100, 0x00100110, 0x00100101, 0x00100111, + 0x00101100, 0x00101110, 0x00101101, 0x00101111, + 0x00010000, 0x00010010, 0x00010001, 0x00010011, + 0x00011000, 0x00011010, 0x00011001, 0x00011011, + 0x00010100, 0x00010110, 0x00010101, 0x00010111, + 0x00011100, 0x00011110, 0x00011101, 0x00011111, + 0x00110000, 0x00110010, 0x00110001, 0x00110011, + 0x00111000, 0x00111010, 0x00111001, 0x00111011, + 0x00110100, 0x00110110, 0x00110101, 0x00110111, + 0x00111100, 0x00111110, 0x00111101, 0x00111111, + 0x10000000, 0x10000010, 0x10000001, 0x10000011, + 0x10001000, 0x10001010, 0x10001001, 0x10001011, + 0x10000100, 0x10000110, 0x10000101, 0x10000111, + 0x10001100, 0x10001110, 0x10001101, 0x10001111, + 0x10100000, 0x10100010, 0x10100001, 0x10100011, + 0x10101000, 0x10101010, 0x10101001, 0x10101011, + 0x10100100, 0x10100110, 0x10100101, 0x10100111, + 0x10101100, 0x10101110, 0x10101101, 0x10101111, + 0x10010000, 0x10010010, 0x10010001, 0x10010011, + 0x10011000, 0x10011010, 0x10011001, 0x10011011, + 0x10010100, 0x10010110, 0x10010101, 0x10010111, + 0x10011100, 0x10011110, 0x10011101, 0x10011111, + 0x10110000, 0x10110010, 0x10110001, 0x10110011, + 0x10111000, 0x10111010, 0x10111001, 0x10111011, + 0x10110100, 0x10110110, 0x10110101, 0x10110111, + 0x10111100, 0x10111110, 0x10111101, 0x10111111, + 0x01000000, 0x01000010, 0x01000001, 0x01000011, + 0x01001000, 0x01001010, 0x01001001, 0x01001011, + 0x01000100, 0x01000110, 0x01000101, 0x01000111, + 0x01001100, 0x01001110, 0x01001101, 0x01001111, + 0x01100000, 0x01100010, 0x01100001, 0x01100011, + 0x01101000, 0x01101010, 0x01101001, 0x01101011, + 0x01100100, 0x01100110, 0x01100101, 0x01100111, + 0x01101100, 0x01101110, 0x01101101, 0x01101111, + 0x01010000, 0x01010010, 0x01010001, 0x01010011, + 0x01011000, 0x01011010, 0x01011001, 0x01011011, + 0x01010100, 0x01010110, 0x01010101, 0x01010111, + 0x01011100, 0x01011110, 0x01011101, 0x01011111, + 0x01110000, 0x01110010, 0x01110001, 0x01110011, + 0x01111000, 0x01111010, 0x01111001, 0x01111011, + 0x01110100, 0x01110110, 0x01110101, 0x01110111, + 0x01111100, 0x01111110, 0x01111101, 0x01111111, + 0x11000000, 0x11000010, 0x11000001, 0x11000011, + 0x11001000, 0x11001010, 0x11001001, 0x11001011, + 0x11000100, 0x11000110, 0x11000101, 0x11000111, + 0x11001100, 0x11001110, 0x11001101, 0x11001111, + 0x11100000, 0x11100010, 0x11100001, 0x11100011, + 0x11101000, 0x11101010, 0x11101001, 0x11101011, + 0x11100100, 0x11100110, 0x11100101, 0x11100111, + 0x11101100, 0x11101110, 0x11101101, 0x11101111, + 0x11010000, 0x11010010, 0x11010001, 0x11010011, + 0x11011000, 0x11011010, 0x11011001, 0x11011011, + 0x11010100, 0x11010110, 0x11010101, 0x11010111, + 0x11011100, 0x11011110, 0x11011101, 0x11011111, + 0x11110000, 0x11110010, 0x11110001, 0x11110011, + 0x11111000, 0x11111010, 0x11111001, 0x11111011, + 0x11110100, 0x11110110, 0x11110101, 0x11110111, + 0x11111100, 0x11111110, 0x11111101, 0x11111111 +}; + +/* + * The final permutation array. Like the IP array, used + * to compute both the left and right results from the bytes + * of words computed from: + * + * ((left & 0x0f0f0f0f) << 4) | (right & 0x0f0f0f0f) for left result + * (left & 0xf0f0f0f0) | ((right & 0xf0f0f0f0) >> 4) for right result + * + * The result from the high order byte is shifted left 6 bits and + * or'd with the result from the next byte shifted left 4 bits, which + * is or'd with the result from the next byte shifted left 2 bits, + * which is or'd with the result from the low byte. + */ +const unsigned KRB_INT32 des_FP_table[256] = { + 0x00000000, 0x02000000, 0x00020000, 0x02020000, + 0x00000200, 0x02000200, 0x00020200, 0x02020200, + 0x00000002, 0x02000002, 0x00020002, 0x02020002, + 0x00000202, 0x02000202, 0x00020202, 0x02020202, + 0x01000000, 0x03000000, 0x01020000, 0x03020000, + 0x01000200, 0x03000200, 0x01020200, 0x03020200, + 0x01000002, 0x03000002, 0x01020002, 0x03020002, + 0x01000202, 0x03000202, 0x01020202, 0x03020202, + 0x00010000, 0x02010000, 0x00030000, 0x02030000, + 0x00010200, 0x02010200, 0x00030200, 0x02030200, + 0x00010002, 0x02010002, 0x00030002, 0x02030002, + 0x00010202, 0x02010202, 0x00030202, 0x02030202, + 0x01010000, 0x03010000, 0x01030000, 0x03030000, + 0x01010200, 0x03010200, 0x01030200, 0x03030200, + 0x01010002, 0x03010002, 0x01030002, 0x03030002, + 0x01010202, 0x03010202, 0x01030202, 0x03030202, + 0x00000100, 0x02000100, 0x00020100, 0x02020100, + 0x00000300, 0x02000300, 0x00020300, 0x02020300, + 0x00000102, 0x02000102, 0x00020102, 0x02020102, + 0x00000302, 0x02000302, 0x00020302, 0x02020302, + 0x01000100, 0x03000100, 0x01020100, 0x03020100, + 0x01000300, 0x03000300, 0x01020300, 0x03020300, + 0x01000102, 0x03000102, 0x01020102, 0x03020102, + 0x01000302, 0x03000302, 0x01020302, 0x03020302, + 0x00010100, 0x02010100, 0x00030100, 0x02030100, + 0x00010300, 0x02010300, 0x00030300, 0x02030300, + 0x00010102, 0x02010102, 0x00030102, 0x02030102, + 0x00010302, 0x02010302, 0x00030302, 0x02030302, + 0x01010100, 0x03010100, 0x01030100, 0x03030100, + 0x01010300, 0x03010300, 0x01030300, 0x03030300, + 0x01010102, 0x03010102, 0x01030102, 0x03030102, + 0x01010302, 0x03010302, 0x01030302, 0x03030302, + 0x00000001, 0x02000001, 0x00020001, 0x02020001, + 0x00000201, 0x02000201, 0x00020201, 0x02020201, + 0x00000003, 0x02000003, 0x00020003, 0x02020003, + 0x00000203, 0x02000203, 0x00020203, 0x02020203, + 0x01000001, 0x03000001, 0x01020001, 0x03020001, + 0x01000201, 0x03000201, 0x01020201, 0x03020201, + 0x01000003, 0x03000003, 0x01020003, 0x03020003, + 0x01000203, 0x03000203, 0x01020203, 0x03020203, + 0x00010001, 0x02010001, 0x00030001, 0x02030001, + 0x00010201, 0x02010201, 0x00030201, 0x02030201, + 0x00010003, 0x02010003, 0x00030003, 0x02030003, + 0x00010203, 0x02010203, 0x00030203, 0x02030203, + 0x01010001, 0x03010001, 0x01030001, 0x03030001, + 0x01010201, 0x03010201, 0x01030201, 0x03030201, + 0x01010003, 0x03010003, 0x01030003, 0x03030003, + 0x01010203, 0x03010203, 0x01030203, 0x03030203, + 0x00000101, 0x02000101, 0x00020101, 0x02020101, + 0x00000301, 0x02000301, 0x00020301, 0x02020301, + 0x00000103, 0x02000103, 0x00020103, 0x02020103, + 0x00000303, 0x02000303, 0x00020303, 0x02020303, + 0x01000101, 0x03000101, 0x01020101, 0x03020101, + 0x01000301, 0x03000301, 0x01020301, 0x03020301, + 0x01000103, 0x03000103, 0x01020103, 0x03020103, + 0x01000303, 0x03000303, 0x01020303, 0x03020303, + 0x00010101, 0x02010101, 0x00030101, 0x02030101, + 0x00010301, 0x02010301, 0x00030301, 0x02030301, + 0x00010103, 0x02010103, 0x00030103, 0x02030103, + 0x00010303, 0x02010303, 0x00030303, 0x02030303, + 0x01010101, 0x03010101, 0x01030101, 0x03030101, + 0x01010301, 0x03010301, 0x01030301, 0x03030301, + 0x01010103, 0x03010103, 0x01030103, 0x03030103, + 0x01010303, 0x03010303, 0x01030303, 0x03030303 +}; + + +/* + * The SP table is actually the S boxes and the P permutation + * table combined. This table is actually reordered from the + * spec, to match the order of key application we follow. + */ +const unsigned KRB_INT32 des_SP_table[8][64] = { + 0x00100000, 0x02100001, 0x02000401, 0x00000000, /* 7 */ + 0x00000400, 0x02000401, 0x00100401, 0x02100400, + 0x02100401, 0x00100000, 0x00000000, 0x02000001, + 0x00000001, 0x02000000, 0x02100001, 0x00000401, + 0x02000400, 0x00100401, 0x00100001, 0x02000400, + 0x02000001, 0x02100000, 0x02100400, 0x00100001, + 0x02100000, 0x00000400, 0x00000401, 0x02100401, + 0x00100400, 0x00000001, 0x02000000, 0x00100400, + 0x02000000, 0x00100400, 0x00100000, 0x02000401, + 0x02000401, 0x02100001, 0x02100001, 0x00000001, + 0x00100001, 0x02000000, 0x02000400, 0x00100000, + 0x02100400, 0x00000401, 0x00100401, 0x02100400, + 0x00000401, 0x02000001, 0x02100401, 0x02100000, + 0x00100400, 0x00000000, 0x00000001, 0x02100401, + 0x00000000, 0x00100401, 0x02100000, 0x00000400, + 0x02000001, 0x02000400, 0x00000400, 0x00100001, + + 0x00808200, 0x00000000, 0x00008000, 0x00808202, /* 1 */ + 0x00808002, 0x00008202, 0x00000002, 0x00008000, + 0x00000200, 0x00808200, 0x00808202, 0x00000200, + 0x00800202, 0x00808002, 0x00800000, 0x00000002, + 0x00000202, 0x00800200, 0x00800200, 0x00008200, + 0x00008200, 0x00808000, 0x00808000, 0x00800202, + 0x00008002, 0x00800002, 0x00800002, 0x00008002, + 0x00000000, 0x00000202, 0x00008202, 0x00800000, + 0x00008000, 0x00808202, 0x00000002, 0x00808000, + 0x00808200, 0x00800000, 0x00800000, 0x00000200, + 0x00808002, 0x00008000, 0x00008200, 0x00800002, + 0x00000200, 0x00000002, 0x00800202, 0x00008202, + 0x00808202, 0x00008002, 0x00808000, 0x00800202, + 0x00800002, 0x00000202, 0x00008202, 0x00808200, + 0x00000202, 0x00800200, 0x00800200, 0x00000000, + 0x00008002, 0x00008200, 0x00000000, 0x00808002, + + 0x00000104, 0x04010100, 0x00000000, 0x04010004, /* 3 */ + 0x04000100, 0x00000000, 0x00010104, 0x04000100, + 0x00010004, 0x04000004, 0x04000004, 0x00010000, + 0x04010104, 0x00010004, 0x04010000, 0x00000104, + 0x04000000, 0x00000004, 0x04010100, 0x00000100, + 0x00010100, 0x04010000, 0x04010004, 0x00010104, + 0x04000104, 0x00010100, 0x00010000, 0x04000104, + 0x00000004, 0x04010104, 0x00000100, 0x04000000, + 0x04010100, 0x04000000, 0x00010004, 0x00000104, + 0x00010000, 0x04010100, 0x04000100, 0x00000000, + 0x00000100, 0x00010004, 0x04010104, 0x04000100, + 0x04000004, 0x00000100, 0x00000000, 0x04010004, + 0x04000104, 0x00010000, 0x04000000, 0x04010104, + 0x00000004, 0x00010104, 0x00010100, 0x04000004, + 0x04010000, 0x04000104, 0x00000104, 0x04010000, + 0x00010104, 0x00000004, 0x04010004, 0x00010100, + + 0x00000080, 0x01040080, 0x01040000, 0x21000080, /* 5 */ + 0x00040000, 0x00000080, 0x20000000, 0x01040000, + 0x20040080, 0x00040000, 0x01000080, 0x20040080, + 0x21000080, 0x21040000, 0x00040080, 0x20000000, + 0x01000000, 0x20040000, 0x20040000, 0x00000000, + 0x20000080, 0x21040080, 0x21040080, 0x01000080, + 0x21040000, 0x20000080, 0x00000000, 0x21000000, + 0x01040080, 0x01000000, 0x21000000, 0x00040080, + 0x00040000, 0x21000080, 0x00000080, 0x01000000, + 0x20000000, 0x01040000, 0x21000080, 0x20040080, + 0x01000080, 0x20000000, 0x21040000, 0x01040080, + 0x20040080, 0x00000080, 0x01000000, 0x21040000, + 0x21040080, 0x00040080, 0x21000000, 0x21040080, + 0x01040000, 0x00000000, 0x20040000, 0x21000000, + 0x00040080, 0x01000080, 0x20000080, 0x00040000, + 0x00000000, 0x20040000, 0x01040080, 0x20000080, + + 0x80401000, 0x80001040, 0x80001040, 0x00000040, /* 4 */ + 0x00401040, 0x80400040, 0x80400000, 0x80001000, + 0x00000000, 0x00401000, 0x00401000, 0x80401040, + 0x80000040, 0x00000000, 0x00400040, 0x80400000, + 0x80000000, 0x00001000, 0x00400000, 0x80401000, + 0x00000040, 0x00400000, 0x80001000, 0x00001040, + 0x80400040, 0x80000000, 0x00001040, 0x00400040, + 0x00001000, 0x00401040, 0x80401040, 0x80000040, + 0x00400040, 0x80400000, 0x00401000, 0x80401040, + 0x80000040, 0x00000000, 0x00000000, 0x00401000, + 0x00001040, 0x00400040, 0x80400040, 0x80000000, + 0x80401000, 0x80001040, 0x80001040, 0x00000040, + 0x80401040, 0x80000040, 0x80000000, 0x00001000, + 0x80400000, 0x80001000, 0x00401040, 0x80400040, + 0x80001000, 0x00001040, 0x00400000, 0x80401000, + 0x00000040, 0x00400000, 0x00001000, 0x00401040, + + 0x10000008, 0x10200000, 0x00002000, 0x10202008, /* 6 */ + 0x10200000, 0x00000008, 0x10202008, 0x00200000, + 0x10002000, 0x00202008, 0x00200000, 0x10000008, + 0x00200008, 0x10002000, 0x10000000, 0x00002008, + 0x00000000, 0x00200008, 0x10002008, 0x00002000, + 0x00202000, 0x10002008, 0x00000008, 0x10200008, + 0x10200008, 0x00000000, 0x00202008, 0x10202000, + 0x00002008, 0x00202000, 0x10202000, 0x10000000, + 0x10002000, 0x00000008, 0x10200008, 0x00202000, + 0x10202008, 0x00200000, 0x00002008, 0x10000008, + 0x00200000, 0x10002000, 0x10000000, 0x00002008, + 0x10000008, 0x10202008, 0x00202000, 0x10200000, + 0x00202008, 0x10202000, 0x00000000, 0x10200008, + 0x00000008, 0x00002000, 0x10200000, 0x00202008, + 0x00002000, 0x00200008, 0x10002008, 0x00000000, + 0x10202000, 0x10000000, 0x00200008, 0x10002008, + + 0x08000820, 0x00000800, 0x00020000, 0x08020820, /* 8 */ + 0x08000000, 0x08000820, 0x00000020, 0x08000000, + 0x00020020, 0x08020000, 0x08020820, 0x00020800, + 0x08020800, 0x00020820, 0x00000800, 0x00000020, + 0x08020000, 0x08000020, 0x08000800, 0x00000820, + 0x00020800, 0x00020020, 0x08020020, 0x08020800, + 0x00000820, 0x00000000, 0x00000000, 0x08020020, + 0x08000020, 0x08000800, 0x00020820, 0x00020000, + 0x00020820, 0x00020000, 0x08020800, 0x00000800, + 0x00000020, 0x08020020, 0x00000800, 0x00020820, + 0x08000800, 0x00000020, 0x08000020, 0x08020000, + 0x08020020, 0x08000000, 0x00020000, 0x08000820, + 0x00000000, 0x08020820, 0x00020020, 0x08000020, + 0x08020000, 0x08000800, 0x08000820, 0x00000000, + 0x08020820, 0x00020800, 0x00020800, 0x00000820, + 0x00000820, 0x00020020, 0x08000000, 0x08020800, + + 0x40084010, 0x40004000, 0x00004000, 0x00084010, /* 2 */ + 0x00080000, 0x00000010, 0x40080010, 0x40004010, + 0x40000010, 0x40084010, 0x40084000, 0x40000000, + 0x40004000, 0x00080000, 0x00000010, 0x40080010, + 0x00084000, 0x00080010, 0x40004010, 0x00000000, + 0x40000000, 0x00004000, 0x00084010, 0x40080000, + 0x00080010, 0x40000010, 0x00000000, 0x00084000, + 0x00004010, 0x40084000, 0x40080000, 0x00004010, + 0x00000000, 0x00084010, 0x40080010, 0x00080000, + 0x40004010, 0x40080000, 0x40084000, 0x00004000, + 0x40080000, 0x40004000, 0x00000010, 0x40084010, + 0x00084010, 0x00000010, 0x00004000, 0x40000000, + 0x00004010, 0x40084000, 0x00080000, 0x40000010, + 0x00080010, 0x40004010, 0x40000010, 0x00080010, + 0x00084000, 0x00000000, 0x40004000, 0x00004010, + 0x40000000, 0x40080010, 0x40084010, 0x00084000 +}; diff --git a/src/lib/crypto/des/f_tables.h b/src/lib/crypto/des/f_tables.h new file mode 100644 index 000000000..a9c63dcc1 --- /dev/null +++ b/src/lib/crypto/des/f_tables.h @@ -0,0 +1,229 @@ +/* + * Copyright (c) 1990 Dennis Ferguson. All rights reserved. + * + * Commercial use is permitted only if products which are derived from + * or include this software are made available for purchase and/or use + * in Canada. Otherwise, redistribution and use in source and binary + * forms are permitted. + */ + +/* + * des_tables.h - declarations to import the DES tables, used internally + * by some of the library routines. + */ +#ifndef __DES_TABLES_H__ +#define __DES_TABLES_H__ /* nothing */ + +#ifndef const +#ifndef __STDC__ +#define const /* nothing */ +#endif +#endif + +/* + * These may be declared const if you wish. Be sure to change the + * declarations in des_tables.c as well. + */ +extern const unsigned KRB_INT32 des_IP_table[256]; +extern const unsigned KRB_INT32 des_FP_table[256]; +extern const unsigned KRB_INT32 des_SP_table[8][64]; + +/* + * Use standard shortforms to reference these to save typing + */ +#define IP des_IP_table +#define FP des_FP_table +#define SP des_SP_table + +/* + * Code to do a DES round using the tables. Note that the E expansion + * is easy to compute algorithmically, especially if done out-of-order. + * Take a look at its form and compare it to everything involving temp + * below. Since SP[0-7] don't have any bits in common set it is okay + * to do the successive xor's. + * + * Note too that the SP table has been reordered to match the order of + * the keys (if the original order of SP was 12345678, the reordered + * table is 71354682). This is unnecessary, but was done since some + * compilers seem to like you going through the matrix from beginning + * to end. + * + * There is a difference in the best way to do this depending on whether + * one is encrypting or decrypting. If encrypting we move forward through + * the keys and hence should move forward through the table. If decrypting + * we go back. Part of the need for this comes from trying to emulate + * existing software which generates a single key schedule and uses it + * both for encrypting and decrypting. Generating separate encryption + * and decryption key schedules would allow one to use the same code + * for both. + * + * left, right and temp should be unsigned KRB_INT32 values. left and right + * should be the high and low order parts of the cipher block at the + * current stage of processing (this makes sense if you read the spec). + * kp should be an unsigned KRB_INT32 pointer which points at the current + * set of subkeys in the key schedule. It is advanced to the next set + * (i.e. by 8 bytes) when this is done. + * + * This occurs in the innermost loop of the DES function. The four + * variables should really be in registers. + * + * When using this, the inner loop of the DES function might look like: + * + * for (i = 0; i < 8; i++) { + * DES_SP_{EN,DE}CRYPT_ROUND(left, right, temp, kp); + * DES_SP_{EN,DE}CRYPT_ROUND(right, left, temp, kp); + * } + * + * Note the trick above. You are supposed to do 16 rounds, swapping + * left and right at the end of each round. By doing two rounds at + * a time and swapping left and right in the code we can avoid the + * swaps altogether. + */ +#define DES_SP_ENCRYPT_ROUND(left, right, temp, kp) \ + (temp) = (((right) >> 11) | ((right) << 21)) ^ *(kp)++; \ + (left) ^= SP[0][((temp) >> 24) & 0x3f] \ + | SP[1][((temp) >> 16) & 0x3f] \ + | SP[2][((temp) >> 8) & 0x3f] \ + | SP[3][((temp) ) & 0x3f]; \ + (temp) = (((right) >> 23) | ((right) << 9)) ^ *(kp)++; \ + (left) ^= SP[4][((temp) >> 24) & 0x3f] \ + | SP[5][((temp) >> 16) & 0x3f] \ + | SP[6][((temp) >> 8) & 0x3f] \ + | SP[7][((temp) ) & 0x3f] + +#define DES_SP_DECRYPT_ROUND(left, right, temp, kp) \ + (temp) = (((right) >> 23) | ((right) << 9)) ^ *(--(kp)); \ + (left) ^= SP[7][((temp) ) & 0x3f] \ + | SP[6][((temp) >> 8) & 0x3f] \ + | SP[5][((temp) >> 16) & 0x3f] \ + | SP[4][((temp) >> 24) & 0x3f]; \ + (temp) = (((right) >> 11) | ((right) << 21)) ^ *(--(kp)); \ + (left) ^= SP[3][((temp) ) & 0x3f] \ + | SP[2][((temp) >> 8) & 0x3f] \ + | SP[1][((temp) >> 16) & 0x3f] \ + | SP[0][((temp) >> 24) & 0x3f] + +/* + * Macros to help deal with the initial permutation table. Note + * the IP table only deals with 32 bits at a time, allowing us to + * collect the bits we need to deal with each half into an unsigned + * KRB_INT32. By carefully selecting how the bits are ordered we also + * take advantages of symmetries in the table so that we can use a + * single table to compute the permutation of all bytes. This sounds + * complicated, but if you go through the process of designing the + * table you'll find the symmetries fall right out. + * + * The follow macros compute the set of bits used to index the + * table for produce the left and right permuted result. + */ +#define DES_IP_LEFT_BITS(left, right) \ + ((((left) & 0x55555555) << 1) | ((right) & 0x55555555)) +#define DES_IP_RIGHT_BITS(left, right) \ + (((left) & 0xaaaaaaaa) | (((right) & 0xaaaaaaaa) >> 1)) + +/* + * The following macro does an in-place initial permutation given + * the current left and right parts of the block and a single + * temporary. Use this more as a guide for rolling your own, though. + * The best way to do the IP depends on the form of the data you + * are dealing with. If you use this, though, try to make left, + * right and temp register unsigned KRB_INT32s. + */ +#define DES_INITIAL_PERM(left, right, temp) \ + (temp) = DES_IP_RIGHT_BITS((left), (right)); \ + (right) = DES_IP_LEFT_BITS((left), (right)); \ + (left) = IP[((right) >> 24) & 0xff] \ + | (IP[((right) >> 16) & 0xff] << 1) \ + | (IP[((right) >> 8) & 0xff] << 2) \ + | (IP[(right) & 0xff] << 3); \ + (right) = IP[((temp) >> 24) & 0xff] \ + | (IP[((temp) >> 16) & 0xff] << 1) \ + | (IP[((temp) >> 8) & 0xff] << 2) \ + | (IP[(temp) & 0xff] << 3) + + +/* + * Now the final permutation stuff. The same comments apply to + * this as to the initial permutation, except that we use different + * bits and shifts. + */ +#define DES_FP_LEFT_BITS(left, right) \ + ((((left) & 0x0f0f0f0f) << 4) | ((right) & 0x0f0f0f0f)) +#define DES_FP_RIGHT_BITS(left, right) \ + (((left) & 0xf0f0f0f0) | (((right) & 0xf0f0f0f0) >> 4)) + + +/* + * Here is a sample final permutation. Note that there is a trick + * here. DES requires swapping the left and right parts after the + * last cipher round but before the final permutation. We do this + * swapping internally, which is why left and right are confused + * at the beginning. + */ +#define DES_FINAL_PERM(left, right, temp) \ + (temp) = DES_FP_RIGHT_BITS((right), (left)); \ + (right) = DES_FP_LEFT_BITS((right), (left)); \ + (left) = (FP[((right) >> 24) & 0xff] << 6) \ + | (FP[((right) >> 16) & 0xff] << 4) \ + | (FP[((right) >> 8) & 0xff] << 2) \ + | FP[(right) & 0xff]; \ + (right) = (FP[((temp) >> 24) & 0xff] << 6) \ + | (FP[((temp) >> 16) & 0xff] << 4) \ + | (FP[((temp) >> 8) & 0xff] << 2) \ + | FP[temp & 0xff] + + +/* + * Finally, as a sample of how all this might be held together, the + * following two macros do in-place encryptions and decryptions. left + * and right are two unsigned KRB_INT32 variables which at the beginning + * are expected to hold the clear (encrypted) block in host byte order + * (left the high order four bytes, right the low order). At the end + * they will contain the encrypted (clear) block. temp is an unsigned KRB_INT32 + * used as a temporary. kp is an unsigned KRB_INT32 pointer pointing at + * the start of the key schedule. All these should be in registers. + * + * You can probably do better than these by rewriting for particular + * situations. These aren't bad, though. + */ +#define DES_DO_ENCRYPT(left, right, temp, kp) \ + do { \ + register int i; \ + DES_INITIAL_PERM((left), (right), (temp)); \ + for (i = 0; i < 8; i++) { \ + DES_SP_ENCRYPT_ROUND((left), (right), (temp), (kp)); \ + DES_SP_ENCRYPT_ROUND((right), (left), (temp), (kp)); \ + } \ + DES_FINAL_PERM((left), (right), (temp)); \ + (kp) -= (2 * 16); \ + } while (0) + +#define DES_DO_DECRYPT(left, right, temp, kp) \ + do { \ + register int i; \ + DES_INITIAL_PERM((left), (right), (temp)); \ + (kp) += (2 * 16); \ + for (i = 0; i < 8; i++) { \ + DES_SP_DECRYPT_ROUND((left), (right), (temp), (kp)); \ + DES_SP_DECRYPT_ROUND((right), (left), (temp), (kp)); \ + } \ + DES_FINAL_PERM((left), (right), (temp)); \ + } while (0) + +/* + * These are handy dandy utility thingies for straightening out bytes. + * Included here because they're used a couple of places. + */ +#define GET_HALF_BLOCK(lr, ip) \ + (lr) = ((unsigned KRB_INT32)(*(ip)++)) << 24; \ + (lr) |= ((unsigned KRB_INT32)(*(ip)++)) << 16; \ + (lr) |= ((unsigned KRB_INT32)(*(ip)++)) << 8; \ + (lr) |= (unsigned KRB_INT32)(*(ip)++) + +#define PUT_HALF_BLOCK(lr, op) \ + *(op)++ = ((lr) >> 24) & 0xff; \ + *(op)++ = ((lr) >> 16) & 0xff; \ + *(op)++ = ((lr) >> 8) & 0xff; \ + *(op)++ = (lr) & 0xff + +#endif /* __DES_TABLES_H__ */ -- cgit