des_bs.c

解Unix密码的程序john1.

/*
 * This file is part of John the Ripper password cracker,
 * Copyright (c) 1996-2000 by Solar Designer
 */

#include <string.h>

#include "arch.h"
#include "common.h"
#include "DES_std.h"
#include "DES_bs.h"

#if DES_BS_VECTOR
#define DEPTH				[depth]
#define START				[0]
#define init_depth() \
	register int depth; \
	depth = index >> ARCH_BITS_LOG; \
	index &= (ARCH_BITS - 1);
#define for_each_depth() \
	for (depth = 0; depth < DES_BS_VECTOR; depth++)
#else
#define DEPTH
#define START
#define init_depth()
#define for_each_depth()
#endif

#if !DES_BS_ASM
DES_bs_combined CC_CACHE_ALIGN DES_bs_all;
#endif

static unsigned char DES_LM_KP[56] = {
	1, 2, 3, 4, 5, 6, 7,
	10, 11, 12, 13, 14, 15, 0,
	19, 20, 21, 22, 23, 8, 9,
	28, 29, 30, 31, 16, 17, 18,
	37, 38, 39, 24, 25, 26, 27,
	46, 47, 32, 33, 34, 35, 36,
	55, 40, 41, 42, 43, 44, 45,
	48, 49, 50, 51, 52, 53, 54
};

static unsigned char DES_LM_reverse[16] = {
	0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
};

#if DES_BS_ASM
extern void DES_bs_init_asm(void);
#endif

void DES_bs_init(int LM)
{
	ARCH_WORD **k;
	int round, index, bit;
	int p, q, s;

#if DES_BS_EXPAND
	if (LM)
		k = DES_bs_all.KS.p;
	else
		k = DES_bs_all.KSp;
#else
	k = DES_bs_all.KS.p;
#endif

	s = 0;
	for (round = 0; round < 16; round++) {
		s += DES_ROT[round];
		for (index = 0; index < 48; index++) {
			p = DES_PC2[index];
			q = p < 28 ? 0 : 28;
			p += s;
			while (p >= 28) p -= 28;
			bit = DES_PC1[p + q];
			bit ^= 070;
			bit -= bit >> 3;
			bit = 55 - bit;
			if (LM) bit = DES_LM_KP[bit];
			*k++ = &DES_bs_all.K[bit] START;
		}
	}

/* Initialize the array with right shifts needed to get past the first
 * non-zero bit in the index. */
	for (bit = 0; bit < 7; bit++)
	for (index = 1 << bit; index < 0x100; index += 2 << bit)
		DES_bs_all.s[index] = bit + 1;

/* Special case: instead of doing an extra check in the loop below, we
 * might instead overrun into DES_bs_all.B, which is harmless, as long
 * as the order of fields is unchanged. */
	DES_bs_all.s[0] = 57;

#if DES_BS_ASM
	DES_bs_init_asm();
#endif
}

void DES_bs_set_salt(ARCH_WORD salt)
{
	register ARCH_WORD mask;
	register int src, dst;

	mask = 1;
	for (dst = 0; dst < 48; dst++) {
		if (dst == 24) mask = 1;

		if (salt & mask) {
			if (dst < 24) src = dst + 24; else src = dst - 24;
		} else src = dst;

		DES_bs_all.E[dst] = &DES_bs_all.B[DES_E[src]] START;
		DES_bs_all.E[dst + 48] = &DES_bs_all.B[DES_E[src] + 32] START;

		mask <<= 1;
	}
}

void DES_bs_clear_keys(void)
{
	memset(DES_bs_all.K, 0, sizeof(DES_bs_all.K));
}

void DES_bs_set_key(char *key, int index)
{
	register ARCH_WORD value, mask;
	register char *ptr;
	register int ofs, bit, shift;

	init_depth();

	mask = (ARCH_WORD)1 << index;
	ofs = -1;
	for (ptr = key; *ptr && ofs < 55; ptr++) {
		bit = ofs; ofs += 7;
		value = *ptr & 0x7F;

		do {
			shift = DES_bs_all.s[value];
			DES_bs_all.K[bit += shift] DEPTH |= mask;
		} while (value >>= shift);
	}
}

void DES_bs_set_key_LM(char *key, int index)
{
	register ARCH_WORD value, mask;
	register char *ptr;
	register int ofs, bit, shift;

	init_depth();

	mask = (ARCH_WORD)1 << index;
	ofs = -1;
	for (ptr = key; *ptr && ofs < 55; ptr++) {
		bit = ofs; ofs += 8;
		value = *(unsigned char *)ptr;

		do {
			shift = DES_bs_all.s[value];
			DES_bs_all.K[bit += shift] DEPTH |= mask;
		} while (value >>= shift);
	}
}

#if DES_BS_EXPAND
void DES_bs_expand_keys(void)
{
	register int index;
#if DES_BS_VECTOR
	register int depth;
#endif

	for (index = 0; index < 0x300; index++)
	for_each_depth()
#if DES_BS_VECTOR
		DES_bs_all.KS.v[index] DEPTH = DES_bs_all.KSp[index] DEPTH;
#else
		DES_bs_all.KS.v[index] = *DES_bs_all.KSp[index];
#endif
}
#endif

static ARCH_WORD *DES_bs_get_binary_raw(ARCH_WORD *raw, int count)
{
	static ARCH_WORD out[2];
	int bit, index, value;

	out[0] = out[1] = 0;
	for (bit = 0; bit < 64; bit++) {
		index = bit >> 5;

/* Swap L and R here instead of doing it one more time in DES_bs_crypt() */
		if (count & 1) index ^= 1;

/* Get the bit */
		value = (raw[index] >> (bit & 0x1F)) & 1;

/* Pack the bits into two words */
		out[bit >> 5] |= value << (bit & 0x1F);
	}

	return out;
}

ARCH_WORD *DES_bs_get_binary(char *ciphertext)
{
	return DES_bs_get_binary_raw(
		DES_raw_get_binary(ciphertext),
		DES_raw_get_count(ciphertext));
}

ARCH_WORD *DES_bs_get_binary_LM(char *ciphertext)
{
	ARCH_WORD block[2], value;
	int l, h;
	int index;

	block[0] = block[1] = 0;
	for (index = 0; index < 16; index += 2) {
		l = atoi16[ARCH_INDEX(ciphertext[index])];
		h = atoi16[ARCH_INDEX(ciphertext[index + 1])];
		value = DES_LM_reverse[l] | (DES_LM_reverse[h] << 4);
		block[index >> 3] |= value << ((index << 2) & 0x18);
	}

	return DES_bs_get_binary_raw(DES_do_IP(block), 1);
}

int DES_bs_get_hash(int index, int count)
{
	register int result;

	init_depth();

	result = (DES_bs_all.B[0] DEPTH >> index) & 1;
	result |= ((DES_bs_all.B[1] DEPTH >> index) & 1) << 1;
	result |= ((DES_bs_all.B[2] DEPTH >> index) & 1) << 2;
	result |= ((DES_bs_all.B[3] DEPTH >> index) & 1) << 3;
	if (count == 4) return result;

	result |= ((DES_bs_all.B[4] DEPTH >> index) & 1) << 4;
	result |= ((DES_bs_all.B[5] DEPTH >> index) & 1) << 5;
	result |= ((DES_bs_all.B[6] DEPTH >> index) & 1) << 6;
	result |= ((DES_bs_all.B[7] DEPTH >> index) & 1) << 7;
	if (count == 8) return result;

	result |= ((DES_bs_all.B[8] DEPTH >> index) & 1) << 8;
	result |= ((DES_bs_all.B[9] DEPTH >> index) & 1) << 9;
	result |= ((DES_bs_all.B[10] DEPTH >> index) & 1) << 10;
	result |= ((DES_bs_all.B[11] DEPTH >> index) & 1) << 11;

	return result;
}

/*
 * The trick I used here allows to compare one ciphertext against all the
 * DES_bs_crypt() outputs in just O(log2(ARCH_BITS)) operations, assuming
 * that DES_BS_VECTOR is 0 or 1. This routine isn't vectorized, yet.
 */
int DES_bs_cmp_all(ARCH_WORD *binary)
{
	register ARCH_WORD value, mask;
	register int bit;
#if DES_BS_VECTOR
	register int depth;
#endif

	for_each_depth() {
		value = binary[0];

		mask = DES_bs_all.B[0] DEPTH ^ -(value & 1);
		mask |= DES_bs_all.B[1] DEPTH ^ -((value >> 1) & 1);
		if (mask == ~(ARCH_WORD)0) goto next_depth;
		mask |= DES_bs_all.B[2] DEPTH ^ -((value >> 2) & 1);
		mask |= DES_bs_all.B[3] DEPTH ^ -((value >> 3) & 1);
		if (mask == ~(ARCH_WORD)0) goto next_depth;
		value >>= 4;
		for (bit = 4; bit < 32; bit += 2) {
			mask |= DES_bs_all.B[bit] DEPTH ^
				-(value & 1);
			if (mask == ~(ARCH_WORD)0) goto next_depth;
			mask |= DES_bs_all.B[bit + 1] DEPTH ^
				-((value >> 1) & 1);
			if (mask == ~(ARCH_WORD)0) goto next_depth;
			value >>= 2;
		}

		return 1;
next_depth:
		;
	}

	return 0;
}

int DES_bs_cmp_one(ARCH_WORD *binary, int count, int index)
{
	register int bit;

	init_depth();

	for (bit = 0; bit < count; bit++)
	if (((DES_bs_all.B[bit] DEPTH >> index) ^
		(binary[bit >> 5] >> (bit & 0x1F))) & 1) return 0;

	return 1;
}