|
Packit |
fd8b60 |
/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
|
|
Packit |
fd8b60 |
/* lib/crypto/builtin/des/f_tables.h */
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* Copyright (C) 1990 by the Massachusetts Institute of Technology.
|
|
Packit |
fd8b60 |
* All rights reserved.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* Export of this software from the United States of America may
|
|
Packit |
fd8b60 |
* require a specific license from the United States Government.
|
|
Packit |
fd8b60 |
* It is the responsibility of any person or organization contemplating
|
|
Packit |
fd8b60 |
* export to obtain such a license before exporting.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
|
|
Packit |
fd8b60 |
* distribute this software and its documentation for any purpose and
|
|
Packit |
fd8b60 |
* without fee is hereby granted, provided that the above copyright
|
|
Packit |
fd8b60 |
* notice appear in all copies and that both that copyright notice and
|
|
Packit |
fd8b60 |
* this permission notice appear in supporting documentation, and that
|
|
Packit |
fd8b60 |
* the name of M.I.T. not be used in advertising or publicity pertaining
|
|
Packit |
fd8b60 |
* to distribution of the software without specific, written prior
|
|
Packit |
fd8b60 |
* permission. Furthermore if you modify this software you must label
|
|
Packit |
fd8b60 |
* your software as modified software and not distribute it in such a
|
|
Packit |
fd8b60 |
* fashion that it might be confused with the original M.I.T. software.
|
|
Packit |
fd8b60 |
* M.I.T. makes no representations about the suitability of
|
|
Packit |
fd8b60 |
* this software for any purpose. It is provided "as is" without express
|
|
Packit |
fd8b60 |
* or implied warranty.
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* DES implementation donated by Dennis Ferguson
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* des_tables.h - declarations to import the DES tables, used internally
|
|
Packit |
fd8b60 |
* by some of the library routines.
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
#ifndef __DES_TABLES_H__
|
|
Packit |
fd8b60 |
#define __DES_TABLES_H__ /* nothing */
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
#include "k5-platform.h"
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* These may be declared const if you wish. Be sure to change the
|
|
Packit |
fd8b60 |
* declarations in des_tables.c as well.
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
extern const unsigned DES_INT32 des_IP_table[256];
|
|
Packit |
fd8b60 |
extern const unsigned DES_INT32 des_FP_table[256];
|
|
Packit |
fd8b60 |
extern const unsigned DES_INT32 des_SP_table[8][64];
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* Use standard shortforms to reference these to save typing
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
#define IP des_IP_table
|
|
Packit |
fd8b60 |
#define FP des_FP_table
|
|
Packit |
fd8b60 |
#define SP des_SP_table
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
#ifdef DEBUG
|
|
Packit |
fd8b60 |
#define DEB(foofraw) printf foofraw
|
|
Packit |
fd8b60 |
#else
|
|
Packit |
fd8b60 |
#define DEB(foofraw) /* nothing */
|
|
Packit |
fd8b60 |
#endif
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* Code to do a DES round using the tables. Note that the E expansion
|
|
Packit |
fd8b60 |
* is easy to compute algorithmically, especially if done out-of-order.
|
|
Packit |
fd8b60 |
* Take a look at its form and compare it to everything involving temp
|
|
Packit |
fd8b60 |
* below. Since SP[0-7] don't have any bits in common set it is okay
|
|
Packit |
fd8b60 |
* to do the successive xor's.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* Note too that the SP table has been reordered to match the order of
|
|
Packit |
fd8b60 |
* the keys (if the original order of SP was 12345678, the reordered
|
|
Packit |
fd8b60 |
* table is 71354682). This is unnecessary, but was done since some
|
|
Packit |
fd8b60 |
* compilers seem to like you going through the matrix from beginning
|
|
Packit |
fd8b60 |
* to end.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* There is a difference in the best way to do this depending on whether
|
|
Packit |
fd8b60 |
* one is encrypting or decrypting. If encrypting we move forward through
|
|
Packit |
fd8b60 |
* the keys and hence should move forward through the table. If decrypting
|
|
Packit |
fd8b60 |
* we go back. Part of the need for this comes from trying to emulate
|
|
Packit |
fd8b60 |
* existing software which generates a single key schedule and uses it
|
|
Packit |
fd8b60 |
* both for encrypting and decrypting. Generating separate encryption
|
|
Packit |
fd8b60 |
* and decryption key schedules would allow one to use the same code
|
|
Packit |
fd8b60 |
* for both.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* left, right and temp should be unsigned DES_INT32 values. left and right
|
|
Packit |
fd8b60 |
* should be the high and low order parts of the cipher block at the
|
|
Packit |
fd8b60 |
* current stage of processing (this makes sense if you read the spec).
|
|
Packit |
fd8b60 |
* kp should be an unsigned DES_INT32 pointer which points at the current
|
|
Packit |
fd8b60 |
* set of subkeys in the key schedule. It is advanced to the next set
|
|
Packit |
fd8b60 |
* (i.e. by 8 bytes) when this is done.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* This occurs in the innermost loop of the DES function. The four
|
|
Packit |
fd8b60 |
* variables should really be in registers.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* When using this, the inner loop of the DES function might look like:
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* for (i = 0; i < 8; i++) {
|
|
Packit |
fd8b60 |
* DES_SP_{EN,DE}CRYPT_ROUND(left, right, temp, kp);
|
|
Packit |
fd8b60 |
* DES_SP_{EN,DE}CRYPT_ROUND(right, left, temp, kp);
|
|
Packit |
fd8b60 |
* }
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* Note the trick above. You are supposed to do 16 rounds, swapping
|
|
Packit |
fd8b60 |
* left and right at the end of each round. By doing two rounds at
|
|
Packit |
fd8b60 |
* a time and swapping left and right in the code we can avoid the
|
|
Packit |
fd8b60 |
* swaps altogether.
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
#define DES_SP_ENCRYPT_ROUND(left, right, temp, kp) do { \
|
|
Packit |
fd8b60 |
(temp) = (((right) >> 11) | ((right) << 21)) ^ *(kp)++; \
|
|
Packit |
fd8b60 |
(left) ^= SP[0][((temp) >> 24) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[1][((temp) >> 16) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[2][((temp) >> 8) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[3][((temp) ) & 0x3f]; \
|
|
Packit |
fd8b60 |
(temp) = (((right) >> 23) | ((right) << 9)) ^ *(kp)++; \
|
|
Packit |
fd8b60 |
(left) ^= SP[4][((temp) >> 24) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[5][((temp) >> 16) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[6][((temp) >> 8) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[7][((temp) ) & 0x3f]; \
|
|
Packit |
fd8b60 |
} while(0);
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
#define DES_SP_DECRYPT_ROUND(left, right, temp, kp) do { \
|
|
Packit |
fd8b60 |
(temp) = (((right) >> 23) | ((right) << 9)) ^ *(--(kp)); \
|
|
Packit |
fd8b60 |
(left) ^= SP[7][((temp) ) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[6][((temp) >> 8) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[5][((temp) >> 16) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[4][((temp) >> 24) & 0x3f]; \
|
|
Packit |
fd8b60 |
(temp) = (((right) >> 11) | ((right) << 21)) ^ *(--(kp)); \
|
|
Packit |
fd8b60 |
(left) ^= SP[3][((temp) ) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[2][((temp) >> 8) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[1][((temp) >> 16) & 0x3f] \
|
|
Packit |
fd8b60 |
| SP[0][((temp) >> 24) & 0x3f]; \
|
|
Packit |
fd8b60 |
} while (0);
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* Macros to help deal with the initial permutation table. Note
|
|
Packit |
fd8b60 |
* the IP table only deals with 32 bits at a time, allowing us to
|
|
Packit |
fd8b60 |
* collect the bits we need to deal with each half into an unsigned
|
|
Packit |
fd8b60 |
* DES_INT32. By carefully selecting how the bits are ordered we also
|
|
Packit |
fd8b60 |
* take advantages of symmetries in the table so that we can use a
|
|
Packit |
fd8b60 |
* single table to compute the permutation of all bytes. This sounds
|
|
Packit |
fd8b60 |
* complicated, but if you go through the process of designing the
|
|
Packit |
fd8b60 |
* table you'll find the symmetries fall right out.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* The follow macros compute the set of bits used to index the
|
|
Packit |
fd8b60 |
* table for produce the left and right permuted result.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* The inserted cast to unsigned DES_INT32 circumvents a bug in
|
|
Packit |
fd8b60 |
* the Macintosh MPW 3.2 C compiler which loses the unsignedness and
|
|
Packit |
fd8b60 |
* propagates the high-order bit in the shift.
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
#define DES_IP_LEFT_BITS(left, right) \
|
|
Packit |
fd8b60 |
((((left) & 0x55555555) << 1) | ((right) & 0x55555555))
|
|
Packit |
fd8b60 |
#define DES_IP_RIGHT_BITS(left, right) \
|
|
Packit |
fd8b60 |
(((left) & 0xaaaaaaaa) | \
|
|
Packit |
fd8b60 |
( ( (unsigned DES_INT32) ((right) & 0xaaaaaaaa) ) >> 1))
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* The following macro does an in-place initial permutation given
|
|
Packit |
fd8b60 |
* the current left and right parts of the block and a single
|
|
Packit |
fd8b60 |
* temporary. Use this more as a guide for rolling your own, though.
|
|
Packit |
fd8b60 |
* The best way to do the IP depends on the form of the data you
|
|
Packit |
fd8b60 |
* are dealing with. If you use this, though, try to make left,
|
|
Packit |
fd8b60 |
* right and temp unsigned DES_INT32s.
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
#define DES_INITIAL_PERM(left, right, temp) do { \
|
|
Packit |
fd8b60 |
(temp) = DES_IP_RIGHT_BITS((left), (right)); \
|
|
Packit |
fd8b60 |
(right) = DES_IP_LEFT_BITS((left), (right)); \
|
|
Packit |
fd8b60 |
(left) = IP[((right) >> 24) & 0xff] \
|
|
Packit |
fd8b60 |
| (IP[((right) >> 16) & 0xff] << 1) \
|
|
Packit |
fd8b60 |
| (IP[((right) >> 8) & 0xff] << 2) \
|
|
Packit |
fd8b60 |
| (IP[(right) & 0xff] << 3); \
|
|
Packit |
fd8b60 |
(right) = IP[((temp) >> 24) & 0xff] \
|
|
Packit |
fd8b60 |
| (IP[((temp) >> 16) & 0xff] << 1) \
|
|
Packit |
fd8b60 |
| (IP[((temp) >> 8) & 0xff] << 2) \
|
|
Packit |
fd8b60 |
| (IP[(temp) & 0xff] << 3); \
|
|
Packit |
fd8b60 |
} while(0);
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* Now the final permutation stuff. The same comments apply to
|
|
Packit |
fd8b60 |
* this as to the initial permutation, except that we use different
|
|
Packit |
fd8b60 |
* bits and shifts.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* The inserted cast to unsigned DES_INT32 circumvents a bug in
|
|
Packit |
fd8b60 |
* the Macintosh MPW 3.2 C compiler which loses the unsignedness and
|
|
Packit |
fd8b60 |
* propagates the high-order bit in the shift.
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
#define DES_FP_LEFT_BITS(left, right) \
|
|
Packit |
fd8b60 |
((((left) & 0x0f0f0f0f) << 4) | ((right) & 0x0f0f0f0f))
|
|
Packit |
fd8b60 |
#define DES_FP_RIGHT_BITS(left, right) \
|
|
Packit |
fd8b60 |
(((left) & 0xf0f0f0f0) | \
|
|
Packit |
fd8b60 |
( ( (unsigned DES_INT32) ((right) & 0xf0f0f0f0) ) >> 4))
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* Here is a sample final permutation. Note that there is a trick
|
|
Packit |
fd8b60 |
* here. DES requires swapping the left and right parts after the
|
|
Packit |
fd8b60 |
* last cipher round but before the final permutation. We do this
|
|
Packit |
fd8b60 |
* swapping internally, which is why left and right are confused
|
|
Packit |
fd8b60 |
* at the beginning.
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
#define DES_FINAL_PERM(left, right, temp) do { \
|
|
Packit |
fd8b60 |
(temp) = DES_FP_RIGHT_BITS((right), (left)); \
|
|
Packit |
fd8b60 |
(right) = DES_FP_LEFT_BITS((right), (left)); \
|
|
Packit |
fd8b60 |
(left) = (FP[((right) >> 24) & 0xff] << 6) \
|
|
Packit |
fd8b60 |
| (FP[((right) >> 16) & 0xff] << 4) \
|
|
Packit |
fd8b60 |
| (FP[((right) >> 8) & 0xff] << 2) \
|
|
Packit |
fd8b60 |
| FP[(right) & 0xff]; \
|
|
Packit |
fd8b60 |
(right) = (FP[((temp) >> 24) & 0xff] << 6) \
|
|
Packit |
fd8b60 |
| (FP[((temp) >> 16) & 0xff] << 4) \
|
|
Packit |
fd8b60 |
| (FP[((temp) >> 8) & 0xff] << 2) \
|
|
Packit |
fd8b60 |
| FP[temp & 0xff]; \
|
|
Packit |
fd8b60 |
} while(0);
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* Finally, as a sample of how all this might be held together, the
|
|
Packit |
fd8b60 |
* following two macros do in-place encryptions and decryptions. left
|
|
Packit |
fd8b60 |
* and right are two unsigned DES_INT32 variables which at the beginning
|
|
Packit |
fd8b60 |
* are expected to hold the clear (encrypted) block in host byte order
|
|
Packit |
fd8b60 |
* (left the high order four bytes, right the low order). At the end
|
|
Packit |
fd8b60 |
* they will contain the encrypted (clear) block. temp is an unsigned DES_INT32
|
|
Packit |
fd8b60 |
* used as a temporary. kp is an unsigned DES_INT32 pointer pointing at
|
|
Packit |
fd8b60 |
* the start of the key schedule. All these should be in registers.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* You can probably do better than these by rewriting for particular
|
|
Packit |
fd8b60 |
* situations. These aren't bad, though.
|
|
Packit |
fd8b60 |
*
|
|
Packit |
fd8b60 |
* The DEB macros enable debugging when this code breaks (typically
|
|
Packit |
fd8b60 |
* when a buggy compiler breaks it), by printing the intermediate values
|
|
Packit |
fd8b60 |
* at each stage of the encryption, so that by comparing the output to
|
|
Packit |
fd8b60 |
* a known good machine, the location of the first error can be found.
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
#define DES_DO_ENCRYPT_1(left, right, kp) \
|
|
Packit |
fd8b60 |
do { \
|
|
Packit |
fd8b60 |
int i; \
|
|
Packit |
fd8b60 |
unsigned DES_INT32 temp1; \
|
|
Packit |
fd8b60 |
DEB (("do_encrypt %8lX %8lX \n", left, right)); \
|
|
Packit |
fd8b60 |
DES_INITIAL_PERM((left), (right), (temp1)); \
|
|
Packit |
fd8b60 |
DEB ((" after IP %8lX %8lX\n", left, right)); \
|
|
Packit |
fd8b60 |
for (i = 0; i < 8; i++) { \
|
|
Packit |
fd8b60 |
DES_SP_ENCRYPT_ROUND((left), (right), (temp1), (kp)); \
|
|
Packit |
fd8b60 |
DEB ((" round %2d %8lX %8lX \n", i*2, left, right)); \
|
|
Packit |
fd8b60 |
DES_SP_ENCRYPT_ROUND((right), (left), (temp1), (kp)); \
|
|
Packit |
fd8b60 |
DEB ((" round %2d %8lX %8lX \n", 1+i*2, left, right)); \
|
|
Packit |
fd8b60 |
} \
|
|
Packit |
fd8b60 |
DES_FINAL_PERM((left), (right), (temp1)); \
|
|
Packit |
fd8b60 |
(kp) -= (2 * 16); \
|
|
Packit |
fd8b60 |
DEB ((" after FP %8lX %8lX \n", left, right)); \
|
|
Packit |
fd8b60 |
} while (0)
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
#define DES_DO_DECRYPT_1(left, right, kp) \
|
|
Packit |
fd8b60 |
do { \
|
|
Packit |
fd8b60 |
int i; \
|
|
Packit |
fd8b60 |
unsigned DES_INT32 temp2; \
|
|
Packit |
fd8b60 |
DES_INITIAL_PERM((left), (right), (temp2)); \
|
|
Packit |
fd8b60 |
(kp) += (2 * 16); \
|
|
Packit |
fd8b60 |
for (i = 0; i < 8; i++) { \
|
|
Packit |
fd8b60 |
DES_SP_DECRYPT_ROUND((left), (right), (temp2), (kp)); \
|
|
Packit |
fd8b60 |
DES_SP_DECRYPT_ROUND((right), (left), (temp2), (kp)); \
|
|
Packit |
fd8b60 |
} \
|
|
Packit |
fd8b60 |
DES_FINAL_PERM((left), (right), (temp2)); \
|
|
Packit |
fd8b60 |
} while (0)
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
#if defined(CONFIG_SMALL) && !defined(CONFIG_SMALL_NO_CRYPTO)
|
|
Packit |
fd8b60 |
extern void krb5int_des_do_encrypt_2(unsigned DES_INT32 *l,
|
|
Packit |
fd8b60 |
unsigned DES_INT32 *r,
|
|
Packit |
fd8b60 |
const unsigned DES_INT32 *k);
|
|
Packit |
fd8b60 |
extern void krb5int_des_do_decrypt_2(unsigned DES_INT32 *l,
|
|
Packit |
fd8b60 |
unsigned DES_INT32 *r,
|
|
Packit |
fd8b60 |
const unsigned DES_INT32 *k);
|
|
Packit |
fd8b60 |
#define DES_DO_ENCRYPT(L,R,K) krb5int_des_do_encrypt_2(&(L), &(R), (K))
|
|
Packit |
fd8b60 |
#define DES_DO_DECRYPT(L,R,K) krb5int_des_do_decrypt_2(&(L), &(R), (K))
|
|
Packit |
fd8b60 |
#else
|
|
Packit |
fd8b60 |
#define DES_DO_ENCRYPT DES_DO_ENCRYPT_1
|
|
Packit |
fd8b60 |
#define DES_DO_DECRYPT DES_DO_DECRYPT_1
|
|
Packit |
fd8b60 |
#endif
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
/*
|
|
Packit |
fd8b60 |
* These are handy dandy utility thingies for straightening out bytes.
|
|
Packit |
fd8b60 |
* Included here because they're used a couple of places.
|
|
Packit |
fd8b60 |
*/
|
|
Packit |
fd8b60 |
#define GET_HALF_BLOCK(lr, ip) ((lr) = load_32_be(ip), (ip) += 4)
|
|
Packit |
fd8b60 |
#define PUT_HALF_BLOCK(lr, op) (store_32_be(lr, op), (op) += 4)
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
/* Shorthand that we'll need in several places, for creating values that
|
|
Packit |
fd8b60 |
really can hold 32 bits regardless of the prevailing int size. */
|
|
Packit |
fd8b60 |
#define FF_UINT32 ((unsigned DES_INT32) 0xFF)
|
|
Packit |
fd8b60 |
|
|
Packit |
fd8b60 |
#endif /* __DES_TABLES_H__ */
|