1 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */ 2 /* lib/crypto/builtin/des/f_tables.h */ 3 /* 4 * Copyright (C) 1990 by the Massachusetts Institute of Technology. 5 * All rights reserved. 6 * 7 * Export of this software from the United States of America may 8 * require a specific license from the United States Government. 9 * It is the responsibility of any person or organization contemplating 10 * export to obtain such a license before exporting. 11 * 12 * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and 13 * distribute this software and its documentation for any purpose and 14 * without fee is hereby granted, provided that the above copyright 15 * notice appear in all copies and that both that copyright notice and 16 * this permission notice appear in supporting documentation, and that 17 * the name of M.I.T. not be used in advertising or publicity pertaining 18 * to distribution of the software without specific, written prior 19 * permission. Furthermore if you modify this software you must label 20 * your software as modified software and not distribute it in such a 21 * fashion that it might be confused with the original M.I.T. software. 22 * M.I.T. makes no representations about the suitability of 23 * this software for any purpose. It is provided "as is" without express 24 * or implied warranty. 25 */ 26 27 /* 28 * DES implementation donated by Dennis Ferguson 29 */ 30 31 /* 32 * des_tables.h - declarations to import the DES tables, used internally 33 * by some of the library routines. 34 */ 35 #ifndef __DES_TABLES_H__ 36 #define __DES_TABLES_H__ /* nothing */ 37 38 #include "k5-platform.h" 39 /* 40 * These may be declared const if you wish. Be sure to change the 41 * declarations in des_tables.c as well. 42 */ 43 extern const unsigned DES_INT32 des_IP_table[256]; 44 extern const unsigned DES_INT32 des_FP_table[256]; 45 extern const unsigned DES_INT32 des_SP_table[8][64]; 46 47 /* 48 * Use standard shortforms to reference these to save typing 49 */ 50 #define IP des_IP_table 51 #define FP des_FP_table 52 #define SP des_SP_table 53 54 #ifdef DEBUG 55 #define DEB(foofraw) printf foofraw 56 #else 57 #define DEB(foofraw) /* nothing */ 58 #endif 59 60 /* 61 * Code to do a DES round using the tables. Note that the E expansion 62 * is easy to compute algorithmically, especially if done out-of-order. 63 * Take a look at its form and compare it to everything involving temp 64 * below. Since SP[0-7] don't have any bits in common set it is okay 65 * to do the successive xor's. 66 * 67 * Note too that the SP table has been reordered to match the order of 68 * the keys (if the original order of SP was 12345678, the reordered 69 * table is 71354682). This is unnecessary, but was done since some 70 * compilers seem to like you going through the matrix from beginning 71 * to end. 72 * 73 * There is a difference in the best way to do this depending on whether 74 * one is encrypting or decrypting. If encrypting we move forward through 75 * the keys and hence should move forward through the table. If decrypting 76 * we go back. Part of the need for this comes from trying to emulate 77 * existing software which generates a single key schedule and uses it 78 * both for encrypting and decrypting. Generating separate encryption 79 * and decryption key schedules would allow one to use the same code 80 * for both. 81 * 82 * left, right and temp should be unsigned DES_INT32 values. left and right 83 * should be the high and low order parts of the cipher block at the 84 * current stage of processing (this makes sense if you read the spec). 85 * kp should be an unsigned DES_INT32 pointer which points at the current 86 * set of subkeys in the key schedule. It is advanced to the next set 87 * (i.e. by 8 bytes) when this is done. 88 * 89 * This occurs in the innermost loop of the DES function. The four 90 * variables should really be in registers. 91 * 92 * When using this, the inner loop of the DES function might look like: 93 * 94 * for (i = 0; i < 8; i++) { 95 * DES_SP_{EN,DE}CRYPT_ROUND(left, right, temp, kp); 96 * DES_SP_{EN,DE}CRYPT_ROUND(right, left, temp, kp); 97 * } 98 * 99 * Note the trick above. You are supposed to do 16 rounds, swapping 100 * left and right at the end of each round. By doing two rounds at 101 * a time and swapping left and right in the code we can avoid the 102 * swaps altogether. 103 */ 104 #define DES_SP_ENCRYPT_ROUND(left, right, temp, kp) do { \ 105 (temp) = (((right) >> 11) | ((right) << 21)) ^ *(kp)++; \ 106 (left) ^= SP[0][((temp) >> 24) & 0x3f] \ 107 | SP[1][((temp) >> 16) & 0x3f] \ 108 | SP[2][((temp) >> 8) & 0x3f] \ 109 | SP[3][((temp) ) & 0x3f]; \ 110 (temp) = (((right) >> 23) | ((right) << 9)) ^ *(kp)++; \ 111 (left) ^= SP[4][((temp) >> 24) & 0x3f] \ 112 | SP[5][((temp) >> 16) & 0x3f] \ 113 | SP[6][((temp) >> 8) & 0x3f] \ 114 | SP[7][((temp) ) & 0x3f]; \ 115 } while(0); 116 117 #define DES_SP_DECRYPT_ROUND(left, right, temp, kp) do { \ 118 (temp) = (((right) >> 23) | ((right) << 9)) ^ *(--(kp)); \ 119 (left) ^= SP[7][((temp) ) & 0x3f] \ 120 | SP[6][((temp) >> 8) & 0x3f] \ 121 | SP[5][((temp) >> 16) & 0x3f] \ 122 | SP[4][((temp) >> 24) & 0x3f]; \ 123 (temp) = (((right) >> 11) | ((right) << 21)) ^ *(--(kp)); \ 124 (left) ^= SP[3][((temp) ) & 0x3f] \ 125 | SP[2][((temp) >> 8) & 0x3f] \ 126 | SP[1][((temp) >> 16) & 0x3f] \ 127 | SP[0][((temp) >> 24) & 0x3f]; \ 128 } while (0); 129 130 /* 131 * Macros to help deal with the initial permutation table. Note 132 * the IP table only deals with 32 bits at a time, allowing us to 133 * collect the bits we need to deal with each half into an unsigned 134 * DES_INT32. By carefully selecting how the bits are ordered we also 135 * take advantages of symmetries in the table so that we can use a 136 * single table to compute the permutation of all bytes. This sounds 137 * complicated, but if you go through the process of designing the 138 * table you'll find the symmetries fall right out. 139 * 140 * The follow macros compute the set of bits used to index the 141 * table for produce the left and right permuted result. 142 * 143 * The inserted cast to unsigned DES_INT32 circumvents a bug in 144 * the Macintosh MPW 3.2 C compiler which loses the unsignedness and 145 * propagates the high-order bit in the shift. 146 */ 147 #define DES_IP_LEFT_BITS(left, right) \ 148 ((((left) & 0x55555555) << 1) | ((right) & 0x55555555)) 149 #define DES_IP_RIGHT_BITS(left, right) \ 150 (((left) & 0xaaaaaaaa) | \ 151 ( ( (unsigned DES_INT32) ((right) & 0xaaaaaaaa) ) >> 1)) 152 153 /* 154 * The following macro does an in-place initial permutation given 155 * the current left and right parts of the block and a single 156 * temporary. Use this more as a guide for rolling your own, though. 157 * The best way to do the IP depends on the form of the data you 158 * are dealing with. If you use this, though, try to make left, 159 * right and temp unsigned DES_INT32s. 160 */ 161 #define DES_INITIAL_PERM(left, right, temp) do { \ 162 (temp) = DES_IP_RIGHT_BITS((left), (right)); \ 163 (right) = DES_IP_LEFT_BITS((left), (right)); \ 164 (left) = IP[((right) >> 24) & 0xff] \ 165 | (IP[((right) >> 16) & 0xff] << 1) \ 166 | (IP[((right) >> 8) & 0xff] << 2) \ 167 | (IP[(right) & 0xff] << 3); \ 168 (right) = IP[((temp) >> 24) & 0xff] \ 169 | (IP[((temp) >> 16) & 0xff] << 1) \ 170 | (IP[((temp) >> 8) & 0xff] << 2) \ 171 | (IP[(temp) & 0xff] << 3); \ 172 } while(0); 173 174 /* 175 * Now the final permutation stuff. The same comments apply to 176 * this as to the initial permutation, except that we use different 177 * bits and shifts. 178 * 179 * The inserted cast to unsigned DES_INT32 circumvents a bug in 180 * the Macintosh MPW 3.2 C compiler which loses the unsignedness and 181 * propagates the high-order bit in the shift. 182 */ 183 #define DES_FP_LEFT_BITS(left, right) \ 184 ((((left) & 0x0f0f0f0f) << 4) | ((right) & 0x0f0f0f0f)) 185 #define DES_FP_RIGHT_BITS(left, right) \ 186 (((left) & 0xf0f0f0f0) | \ 187 ( ( (unsigned DES_INT32) ((right) & 0xf0f0f0f0) ) >> 4)) 188 189 190 /* 191 * Here is a sample final permutation. Note that there is a trick 192 * here. DES requires swapping the left and right parts after the 193 * last cipher round but before the final permutation. We do this 194 * swapping internally, which is why left and right are confused 195 * at the beginning. 196 */ 197 #define DES_FINAL_PERM(left, right, temp) do { \ 198 (temp) = DES_FP_RIGHT_BITS((right), (left)); \ 199 (right) = DES_FP_LEFT_BITS((right), (left)); \ 200 (left) = (FP[((right) >> 24) & 0xff] << 6) \ 201 | (FP[((right) >> 16) & 0xff] << 4) \ 202 | (FP[((right) >> 8) & 0xff] << 2) \ 203 | FP[(right) & 0xff]; \ 204 (right) = (FP[((temp) >> 24) & 0xff] << 6) \ 205 | (FP[((temp) >> 16) & 0xff] << 4) \ 206 | (FP[((temp) >> 8) & 0xff] << 2) \ 207 | FP[temp & 0xff]; \ 208 } while(0); 209 210 211 /* 212 * Finally, as a sample of how all this might be held together, the 213 * following two macros do in-place encryptions and decryptions. left 214 * and right are two unsigned DES_INT32 variables which at the beginning 215 * are expected to hold the clear (encrypted) block in host byte order 216 * (left the high order four bytes, right the low order). At the end 217 * they will contain the encrypted (clear) block. temp is an unsigned DES_INT32 218 * used as a temporary. kp is an unsigned DES_INT32 pointer pointing at 219 * the start of the key schedule. All these should be in registers. 220 * 221 * You can probably do better than these by rewriting for particular 222 * situations. These aren't bad, though. 223 * 224 * The DEB macros enable debugging when this code breaks (typically 225 * when a buggy compiler breaks it), by printing the intermediate values 226 * at each stage of the encryption, so that by comparing the output to 227 * a known good machine, the location of the first error can be found. 228 */ 229 #define DES_DO_ENCRYPT_1(left, right, kp) \ 230 do { \ 231 int i; \ 232 unsigned DES_INT32 temp1; \ 233 DEB (("do_encrypt %8lX %8lX \n", left, right)); \ 234 DES_INITIAL_PERM((left), (right), (temp1)); \ 235 DEB ((" after IP %8lX %8lX\n", left, right)); \ 236 for (i = 0; i < 8; i++) { \ 237 DES_SP_ENCRYPT_ROUND((left), (right), (temp1), (kp)); \ 238 DEB ((" round %2d %8lX %8lX \n", i*2, left, right)); \ 239 DES_SP_ENCRYPT_ROUND((right), (left), (temp1), (kp)); \ 240 DEB ((" round %2d %8lX %8lX \n", 1+i*2, left, right)); \ 241 } \ 242 DES_FINAL_PERM((left), (right), (temp1)); \ 243 (kp) -= (2 * 16); \ 244 DEB ((" after FP %8lX %8lX \n", left, right)); \ 245 } while (0) 246 247 #define DES_DO_DECRYPT_1(left, right, kp) \ 248 do { \ 249 int i; \ 250 unsigned DES_INT32 temp2; \ 251 DES_INITIAL_PERM((left), (right), (temp2)); \ 252 (kp) += (2 * 16); \ 253 for (i = 0; i < 8; i++) { \ 254 DES_SP_DECRYPT_ROUND((left), (right), (temp2), (kp)); \ 255 DES_SP_DECRYPT_ROUND((right), (left), (temp2), (kp)); \ 256 } \ 257 DES_FINAL_PERM((left), (right), (temp2)); \ 258 } while (0) 259 260 #if defined(CONFIG_SMALL) && !defined(CONFIG_SMALL_NO_CRYPTO) 261 extern void krb5int_des_do_encrypt_2(unsigned DES_INT32 *l, 262 unsigned DES_INT32 *r, 263 const unsigned DES_INT32 *k); 264 extern void krb5int_des_do_decrypt_2(unsigned DES_INT32 *l, 265 unsigned DES_INT32 *r, 266 const unsigned DES_INT32 *k); 267 #define DES_DO_ENCRYPT(L,R,K) krb5int_des_do_encrypt_2(&(L), &(R), (K)) 268 #define DES_DO_DECRYPT(L,R,K) krb5int_des_do_decrypt_2(&(L), &(R), (K)) 269 #else 270 #define DES_DO_ENCRYPT DES_DO_ENCRYPT_1 271 #define DES_DO_DECRYPT DES_DO_DECRYPT_1 272 #endif 273 274 /* 275 * These are handy dandy utility thingies for straightening out bytes. 276 * Included here because they're used a couple of places. 277 */ 278 #define GET_HALF_BLOCK(lr, ip) ((lr) = load_32_be(ip), (ip) += 4) 279 #define PUT_HALF_BLOCK(lr, op) (store_32_be(lr, op), (op) += 4) 280 281 /* Shorthand that we'll need in several places, for creating values that 282 really can hold 32 bits regardless of the prevailing int size. */ 283 #define FF_UINT32 ((unsigned DES_INT32) 0xFF) 284 285 #endif /* __DES_TABLES_H__ */ 286