des.c

samba最新软件

/*
 * Copyright (c) 2005 Kungliga Tekniska H鰃skolan
 * (Royal Institute of Technology, Stockholm, Sweden).
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 
 * 3. Neither the name of the Institute nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*
 * The document that got me started for real was "Efficient
 * Implementation of the Data Encryption Standard" by Dag Arne Osvik.
 * I never got to the PC1 transformation was working, instead I used
 * table-lookup was used for all key schedule setup. The document was
 * very useful since it de-mystified other implementations for me.
 *
 * The core DES function (SBOX + P transformation) is from Richard
 * Outerbridge public domain DES implementation. My sanity is saved
 * thanks to his work. Thank you Richard.
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
RCSID("$Id: des.c 17211 2006-04-24 14:26:19Z lha $");
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <krb5-types.h>
#include <assert.h>

#include "des.h"
#include "ui.h"

static void desx(uint32_t [2], DES_key_schedule *, int);
static void IP(uint32_t [2]);
static void FP(uint32_t [2]);

#include "des-tables.h"

#define ROTATE_LEFT28(x,one)				\
    if (one) {						\
	x = ( ((x)<<(1)) & 0xffffffe) | ((x) >> 27);	\
    } else {						\
	x = ( ((x)<<(2)) & 0xffffffc) | ((x) >> 26);	\
    }

/*
 *
 */

int
DES_set_odd_parity(DES_cblock *key)
{
    int i;
    for (i = 0; i < DES_CBLOCK_LEN; i++)
	(*key)[i] = odd_parity[(*key)[i]];
    return 0;
}

/*
 *
 */

/* FIPS 74 */
static DES_cblock weak_keys[] = {
    {0x01,0x01,0x01,0x01,0x01,0x01,0x01,0x01}, /* weak keys */
    {0xFE,0xFE,0xFE,0xFE,0xFE,0xFE,0xFE,0xFE},
    {0x1F,0x1F,0x1F,0x1F,0x0E,0x0E,0x0E,0x0E},
    {0xE0,0xE0,0xE0,0xE0,0xF1,0xF1,0xF1,0xF1},
    {0x01,0xFE,0x01,0xFE,0x01,0xFE,0x01,0xFE}, /* semi-weak keys */
    {0xFE,0x01,0xFE,0x01,0xFE,0x01,0xFE,0x01},
    {0x1F,0xE0,0x1F,0xE0,0x0E,0xF1,0x0E,0xF1},
    {0xE0,0x1F,0xE0,0x1F,0xF1,0x0E,0xF1,0x0E},
    {0x01,0xE0,0x01,0xE0,0x01,0xF1,0x01,0xF1},
    {0xE0,0x01,0xE0,0x01,0xF1,0x01,0xF1,0x01},
    {0x1F,0xFE,0x1F,0xFE,0x0E,0xFE,0x0E,0xFE},
    {0xFE,0x1F,0xFE,0x1F,0xFE,0x0E,0xFE,0x0E},
    {0x01,0x1F,0x01,0x1F,0x01,0x0E,0x01,0x0E},
    {0x1F,0x01,0x1F,0x01,0x0E,0x01,0x0E,0x01},
    {0xE0,0xFE,0xE0,0xFE,0xF1,0xFE,0xF1,0xFE},
    {0xFE,0xE0,0xFE,0xE0,0xFE,0xF1,0xFE,0xF1}
};

int
DES_is_weak_key(DES_cblock *key)
{
    int i;

    for (i = 0; i < sizeof(weak_keys)/sizeof(weak_keys[0]); i++) {
	if (memcmp(weak_keys[i], key, DES_CBLOCK_LEN) == 0)
	    return 1;
    }
    return 0;
}


/*
 *
 */

int
DES_set_key(DES_cblock *key, DES_key_schedule *ks)
{
    uint32_t t1, t2;
    uint32_t c, d;
    int shifts[16] = { 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 };
    uint32_t *k = &ks->ks[0];
    int i;

    t1 = (*key)[0] << 24 | (*key)[1] << 16 | (*key)[2] << 8 | (*key)[3];
    t2 = (*key)[4] << 24 | (*key)[5] << 16 | (*key)[6] << 8 | (*key)[7];

    c =   (pc1_c_3[(t1 >> (5            )) & 0x7] << 3)
	| (pc1_c_3[(t1 >> (5 + 8        )) & 0x7] << 2)
	| (pc1_c_3[(t1 >> (5 + 8 + 8    )) & 0x7] << 1)
	| (pc1_c_3[(t1 >> (5 + 8 + 8 + 8)) & 0x7] << 0)
	| (pc1_c_4[(t2 >> (4            )) & 0xf] << 3)
	| (pc1_c_4[(t2 >> (4 + 8        )) & 0xf] << 2)
	| (pc1_c_4[(t2 >> (4 + 8 + 8    )) & 0xf] << 1)
	| (pc1_c_4[(t2 >> (4 + 8 + 8 + 8)) & 0xf] << 0);

    
    d =   (pc1_d_3[(t2 >> (1            )) & 0x7] << 3)
	| (pc1_d_3[(t2 >> (1 + 8        )) & 0x7] << 2)
	| (pc1_d_3[(t2 >> (1 + 8 + 8    )) & 0x7] << 1)
	| (pc1_d_3[(t2 >> (1 + 8 + 8 + 8)) & 0x7] << 0)
	| (pc1_d_4[(t1 >> (1            )) & 0xf] << 3)
	| (pc1_d_4[(t1 >> (1 + 8        )) & 0xf] << 2)
	| (pc1_d_4[(t1 >> (1 + 8 + 8    )) & 0xf] << 1)
	| (pc1_d_4[(t1 >> (1 + 8 + 8 + 8)) & 0xf] << 0);

    for (i = 0; i < 16; i++) {
	uint32_t kc, kd;
	
	ROTATE_LEFT28(c, shifts[i]);
	ROTATE_LEFT28(d, shifts[i]);
	
	kc = pc2_c_1[(c >> 22) & 0x3f] |
	    pc2_c_2[((c >> 16) & 0x30) | ((c >> 15) & 0xf)] |
	    pc2_c_3[((c >> 9 ) & 0x3c) | ((c >> 8 ) & 0x3)] |
	    pc2_c_4[((c >> 2 ) & 0x20) | ((c >> 1) & 0x18) | (c & 0x7)];
	kd = pc2_d_1[(d >> 22) & 0x3f] |
	    pc2_d_2[((d >> 15) & 0x30) | ((d >> 14) & 0xf)] |
	    pc2_d_3[ (d >> 7 ) & 0x3f] |
	    pc2_d_4[((d >> 1 ) & 0x3c) | ((d      ) & 0x3)];

	/* Change to byte order used by the S boxes */
	*k  =    (kc & 0x00fc0000L) << 6;
	*k |=    (kc & 0x00000fc0L) << 10;
	*k |=    (kd & 0x00fc0000L) >> 10;
	*k++  |= (kd & 0x00000fc0L) >> 6;
	*k  =    (kc & 0x0003f000L) << 12;
	*k |=    (kc & 0x0000003fL) << 16;
	*k |=    (kd & 0x0003f000L) >> 4;
	*k++  |= (kd & 0x0000003fL);
    }

    return 0;
}

/*
 *
 */

int
DES_set_key_checked(DES_cblock *key, DES_key_schedule *ks)
{
    if (DES_is_weak_key(key)) {
	memset(ks, 0, sizeof(*ks));
	return 1;
    }
    return DES_set_key(key, ks);
}

/*
 * Compatibility function for eay libdes
 */

int
DES_key_sched(DES_cblock *key, DES_key_schedule *ks)
{
    return DES_set_key(key, ks);
}

/*
 *
 */

static void
load(const unsigned char *b, uint32_t v[2])
{
    v[0] =  b[0] << 24;
    v[0] |= b[1] << 16;
    v[0] |= b[2] << 8;
    v[0] |= b[3] << 0;
    v[1] =  b[4] << 24;
    v[1] |= b[5] << 16;
    v[1] |= b[6] << 8;
    v[1] |= b[7] << 0;
}

static void
store(const uint32_t v[2], unsigned char *b)
{
    b[0] = (v[0] >> 24) & 0xff;
    b[1] = (v[0] >> 16) & 0xff;
    b[2] = (v[0] >>  8) & 0xff;
    b[3] = (v[0] >>  0) & 0xff;
    b[4] = (v[1] >> 24) & 0xff;
    b[5] = (v[1] >> 16) & 0xff;
    b[6] = (v[1] >>  8) & 0xff;
    b[7] = (v[1] >>  0) & 0xff;
}

/*
 *
 */

void
DES_encrypt(uint32_t u[2], DES_key_schedule *ks, int forward_encrypt)
{
    IP(u);
    desx(u, ks, forward_encrypt);
    FP(u);
}

/*
 *
 */

void
DES_ecb_encrypt(DES_cblock *input, DES_cblock *output,
		DES_key_schedule *ks, int forward_encrypt)
{
    uint32_t u[2];
    load(*input, u);
    DES_encrypt(u, ks, forward_encrypt);
    store(u, *output);
}

/*
 *
 */

void
DES_cbc_encrypt(const void *in, void *out, long length,
		DES_key_schedule *ks, DES_cblock *iv, int forward_encrypt)
{
    const unsigned char *input = in;
    unsigned char *output = out;
    uint32_t u[2];
    uint32_t uiv[2];

    load(*iv, uiv);

    if (forward_encrypt) {
	while (length >= DES_CBLOCK_LEN) {
	    load(input, u);
	    u[0] ^= uiv[0]; u[1] ^= uiv[1];
	    DES_encrypt(u, ks, 1);
	    uiv[0] = u[0]; uiv[1] = u[1];
	    store(u, output);

	    length -= DES_CBLOCK_LEN;
	    input += DES_CBLOCK_LEN;
	    output += DES_CBLOCK_LEN;
	}
	if (length) {
	    unsigned char tmp[DES_CBLOCK_LEN];
	    memcpy(tmp, input, length);
	    memset(tmp + length, 0, DES_CBLOCK_LEN - length);
	    load(tmp, u);
	    u[0] ^= uiv[0]; u[1] ^= uiv[1];
	    DES_encrypt(u, ks, 1);
	    store(u, output);
	}
    } else {
	uint32_t t[2];
	while (length >= DES_CBLOCK_LEN) {
	    load(input, u);
	    t[0] = u[0]; t[1] = u[1];
	    DES_encrypt(u, ks, 0);
	    u[0] ^= uiv[0]; u[1] ^= uiv[1];
	    store(u, output);
	    uiv[0] = t[0]; uiv[1] = t[1];

	    length -= DES_CBLOCK_LEN;
	    input += DES_CBLOCK_LEN;
	    output += DES_CBLOCK_LEN;
	}
	if (length) {
	    unsigned char tmp[DES_CBLOCK_LEN];
	    memcpy(tmp, input, length);
	    memset(tmp + length, 0, DES_CBLOCK_LEN - length);
	    load(tmp, u);
	    DES_encrypt(u, ks, 0);
	    u[0] ^= uiv[0]; u[1] ^= uiv[1];
	    store(u, output);
	}
    }
    uiv[0] = 0; u[0] = 0; uiv[1] = 0; u[1] = 0;
}

/*
 *
 */

void
DES_pcbc_encrypt(const void *in, void *out, long length,
		 DES_key_schedule *ks, DES_cblock *iv, int forward_encrypt)
{
    const unsigned char *input = in;
    unsigned char *output = out;
    uint32_t u[2];
    uint32_t uiv[2];

    load(*iv, uiv);

    if (forward_encrypt) {
	uint32_t t[2];
	while (length >= DES_CBLOCK_LEN) {
	    load(input, u);
	    t[0] = u[0]; t[1] = u[1];
	    u[0] ^= uiv[0]; u[1] ^= uiv[1];
	    DES_encrypt(u, ks, 1);
	    uiv[0] = u[0] ^ t[0]; uiv[1] = u[1] ^ t[1];
	    store(u, output);

	    length -= DES_CBLOCK_LEN;
	    input += DES_CBLOCK_LEN;
	    output += DES_CBLOCK_LEN;
	}
	if (length) {
	    unsigned char tmp[DES_CBLOCK_LEN];
	    memcpy(tmp, input, length);
	    memset(tmp + length, 0, DES_CBLOCK_LEN - length);
	    load(tmp, u);
	    u[0] ^= uiv[0]; u[1] ^= uiv[1];
	    DES_encrypt(u, ks, 1);
	    store(u, output);
	}
    } else {
	uint32_t t[2];
	while (length >= DES_CBLOCK_LEN) {
	    load(input, u);
	    t[0] = u[0]; t[1] = u[1];
	    DES_encrypt(u, ks, 0);
	    u[0] ^= uiv[0]; u[1] ^= uiv[1];
	    store(u, output);
	    uiv[0] = t[0] ^ u[0]; uiv[1] = t[1] ^ u[1];

	    length -= DES_CBLOCK_LEN;
	    input += DES_CBLOCK_LEN;
	    output += DES_CBLOCK_LEN;
	}
	if (length) {
	    unsigned char tmp[DES_CBLOCK_LEN];
	    memcpy(tmp, input, length);
	    memset(tmp + length, 0, DES_CBLOCK_LEN - length);
	    load(tmp, u);
	    DES_encrypt(u, ks, 0);
	    u[0] ^= uiv[0]; u[1] ^= uiv[1];
	}
    }
    uiv[0] = 0; u[0] = 0; uiv[1] = 0; u[1] = 0;
}

/*
 *
 */

static void
_des3_encrypt(uint32_t u[2], DES_key_schedule *ks1, DES_key_schedule *ks2, 
	      DES_key_schedule *ks3, int forward_encrypt)
{
    IP(u);
    if (forward_encrypt) {
	desx(u, ks1, 1); /* IP + FP cancel out each other */
	desx(u, ks2, 0);
	desx(u, ks3, 1);
    } else {
	desx(u, ks3, 0);
	desx(u, ks2, 1);
	desx(u, ks1, 0);
    }
    FP(u);
}

/*
 *
 */

void
DES_ecb3_encrypt(DES_cblock *input,
		 DES_cblock *output,
		 DES_key_schedule *ks1,
		 DES_key_schedule *ks2,
		 DES_key_schedule *ks3,
		 int forward_encrypt)
{
    uint32_t u[2];
    load(*input, u);
    _des3_encrypt(u, ks1, ks2, ks3, forward_encrypt);
    store(u, *output);
    return;
}

/*
 *
 */

void
DES_ede3_cbc_encrypt(const void *in, void *out,
		     long length, DES_key_schedule *ks1, 
		     DES_key_schedule *ks2, DES_key_schedule *ks3,
		     DES_cblock *iv, int forward_encrypt)
{
    const unsigned char *input = in;
    unsigned char *output = out;
    uint32_t u[2];
    uint32_t uiv[2];

    load(*iv, uiv);

    if (forward_encrypt) {
	while (length >= DES_CBLOCK_LEN) {
	    load(input, u);
	    u[0] ^= uiv[0]; u[1] ^= uiv[1];
	    _des3_encrypt(u, ks1, ks2, ks3, 1);
	    uiv[0] = u[0]; uiv[1] = u[1];
	    store(u, output);

	    length -= DES_CBLOCK_LEN;
	    input += DES_CBLOCK_LEN;
	    output += DES_CBLOCK_LEN;
	}
	if (length) {
	    unsigned char tmp[DES_CBLOCK_LEN];
	    memcpy(tmp, input, length);
	    memset(tmp + length, 0, DES_CBLOCK_LEN - length);
	    load(tmp, u);
	    u[0] ^= uiv[0]; u[1] ^= uiv[1];
	    _des3_encrypt(u, ks1, ks2, ks3, 1);
	    store(u, output);
	}
    } else {
	uint32_t t[2];
	while (length >= DES_CBLOCK_LEN) {
	    load(input, u);
	    t[0] = u[0]; t[1] = u[1];
	    _des3_encrypt(u, ks1, ks2, ks3, 0);
	    u[0] ^= uiv[0]; u[1] ^= uiv[1];
	    store(u, output);
	    uiv[0] = t[0]; uiv[1] = t[1];

	    length -= DES_CBLOCK_LEN;
	    input += DES_CBLOCK_LEN;
	    output += DES_CBLOCK_LEN;