md5_std.c

UNIX、linux密码的破密程序源代码实现

/*
 * This file is part of John the Ripper password cracker,
 * Copyright (c) 1996-2001,2003 by Solar Designer
 *
 * Based on the RSA Data Security, Inc. MD5 Message-Digest Algorithm and
 * FreeBSD MD5-based crypt(3) by Poul-Henning Kamp <phk at login.dknet.dk>.
 * My implementation supports passwords of up to 15 characters long only,
 * since this allows using a significantly faster algorithm -- SD.
 */

#include <string.h>

#include "arch.h"
#include "common.h"
#include "MD5_std.h"

MD5_std_combined CC_CACHE_ALIGN MD5_std_all;

#if !MD5_IMM
static MD5_data MD5_data_init = {
	{
		0xd76aa477, 0xf8fa0bcc, 0xbcdb4dd9, 0xb18b7a77,
		0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
		0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
		0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
		0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
		0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
		0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
		0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
		0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
		0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
		0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
		0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
		0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
		0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
		0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
		0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
	}, {
		0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476
	}, {
		0x77777777, 0x00ff00ff
	}
};
#endif

#if !MD5_ASM

#define S11				7
#define S12				12
#define S13				17
#define S14				22
#define S21				5
#define S22				9
#define S23				14
#define S24				20
#define S31				4
#define S32				11
#define S33				16
#define S34				23
#define S41				6
#define S42				10
#define S43				15
#define S44				21

#if MD5_IMM

/*
 * Using immediate values is good for CISC.
 */

#define AC1				0xd76aa477
#define AC2pCd				0xf8fa0bcc
#define AC3pCc				0xbcdb4dd9
#define AC4pCb				0xb18b7a77
#define AC5				0xf57c0faf
#define AC6				0x4787c62a
#define AC7				0xa8304613
#define AC8				0xfd469501
#define AC9				0x698098d8
#define AC10				0x8b44f7af
#define AC11				0xffff5bb1
#define AC12				0x895cd7be
#define AC13				0x6b901122
#define AC14				0xfd987193
#define AC15				0xa679438e
#define AC16				0x49b40821
#define AC17				0xf61e2562
#define AC18				0xc040b340
#define AC19				0x265e5a51
#define AC20				0xe9b6c7aa
#define AC21				0xd62f105d
#define AC22				0x02441453
#define AC23				0xd8a1e681
#define AC24				0xe7d3fbc8
#define AC25				0x21e1cde6
#define AC26				0xc33707d6
#define AC27				0xf4d50d87
#define AC28				0x455a14ed
#define AC29				0xa9e3e905
#define AC30				0xfcefa3f8
#define AC31				0x676f02d9
#define AC32				0x8d2a4c8a
#define AC33				0xfffa3942
#define AC34				0x8771f681
#define AC35				0x6d9d6122
#define AC36				0xfde5380c
#define AC37				0xa4beea44
#define AC38				0x4bdecfa9
#define AC39				0xf6bb4b60
#define AC40				0xbebfbc70
#define AC41				0x289b7ec6
#define AC42				0xeaa127fa
#define AC43				0xd4ef3085
#define AC44				0x04881d05
#define AC45				0xd9d4d039
#define AC46				0xe6db99e5
#define AC47				0x1fa27cf8
#define AC48				0xc4ac5665
#define AC49				0xf4292244
#define AC50				0x432aff97
#define AC51				0xab9423a7
#define AC52				0xfc93a039
#define AC53				0x655b59c3
#define AC54				0x8f0ccc92
#define AC55				0xffeff47d
#define AC56				0x85845dd1
#define AC57				0x6fa87e4f
#define AC58				0xfe2ce6e0
#define AC59				0xa3014314
#define AC60				0x4e0811a1
#define AC61				0xf7537e82
#define AC62				0xbd3af235
#define AC63				0x2ad7d2bb
#define AC64				0xeb86d391

#define Ca				0x67452301
#define Cb				0xefcdab89
#define Cc				0x98badcfe
#define Cd				0x10325476

#define MASK1				0x77777777

#define OOFFOOFF			0x00ff00ff

#else

/*
 * If we used immediate values on RISC with 32-bit instruction size, it would
 * take about twice more instructions to load all the values.
 */

#define MD5_AC				MD5_std_all.data.AC
#define AC1				MD5_AC[0]
#define AC2pCd				MD5_AC[1]
#define AC3pCc				MD5_AC[2]
#define AC4pCb				MD5_AC[3]
#define AC5				MD5_AC[4]
#define AC6				MD5_AC[5]
#define AC7				MD5_AC[6]
#define AC8				MD5_AC[7]
#define AC9				MD5_AC[8]
#define AC10				MD5_AC[9]
#define AC11				MD5_AC[10]
#define AC12				MD5_AC[11]
#define AC13				MD5_AC[12]
#define AC14				MD5_AC[13]
#define AC15				MD5_AC[14]
#define AC16				MD5_AC[15]
#define AC17				MD5_AC[16]
#define AC18				MD5_AC[17]
#define AC19				MD5_AC[18]
#define AC20				MD5_AC[19]
#define AC21				MD5_AC[20]
#define AC22				MD5_AC[21]
#define AC23				MD5_AC[22]
#define AC24				MD5_AC[23]
#define AC25				MD5_AC[24]
#define AC26				MD5_AC[25]
#define AC27				MD5_AC[26]
#define AC28				MD5_AC[27]
#define AC29				MD5_AC[28]
#define AC30				MD5_AC[29]
#define AC31				MD5_AC[30]
#define AC32				MD5_AC[31]
#define AC33				MD5_AC[32]
#define AC34				MD5_AC[33]
#define AC35				MD5_AC[34]
#define AC36				MD5_AC[35]
#define AC37				MD5_AC[36]
#define AC38				MD5_AC[37]
#define AC39				MD5_AC[38]
#define AC40				MD5_AC[39]
#define AC41				MD5_AC[40]
#define AC42				MD5_AC[41]
#define AC43				MD5_AC[42]
#define AC44				MD5_AC[43]
#define AC45				MD5_AC[44]
#define AC46				MD5_AC[45]
#define AC47				MD5_AC[46]
#define AC48				MD5_AC[47]
#define AC49				MD5_AC[48]
#define AC50				MD5_AC[49]
#define AC51				MD5_AC[50]
#define AC52				MD5_AC[51]
#define AC53				MD5_AC[52]
#define AC54				MD5_AC[53]
#define AC55				MD5_AC[54]
#define AC56				MD5_AC[55]
#define AC57				MD5_AC[56]
#define AC58				MD5_AC[57]
#define AC59				MD5_AC[58]
#define AC60				MD5_AC[59]
#define AC61				MD5_AC[60]
#define AC62				MD5_AC[61]
#define AC63				MD5_AC[62]
#define AC64				MD5_AC[63]

#define MD5_IV				MD5_std_all.data.IV
#define Ca				MD5_IV[0]
#define Cb				MD5_IV[1]
#define Cc				MD5_IV[2]
#define Cd				MD5_IV[3]

#define MASK1				MD5_std_all.data.masks[0]

#define OOFFOOFF			MD5_std_all.data.masks[1]

#endif

/*
 * F, G, H and I are basic MD5 functions.
 */
#define F(x, y, z)			((z) ^ ((x) & ((y) ^ (z))))
#define G(x, y, z)			((y) ^ ((z) & ((x) ^ (y))))
#define H(x, y, z)			((x) ^ (y) ^ (z))
#define I(x, y, z)			((y) ^ ((x) | ~(z)))

/*
 * ROTATE_LEFT rotates x left n bits.
 */
#define ROTATE_LEFT(x, n) \
	(x) = (((x) << (n)) | ((MD5_word)(x) >> (32 - (n))))

/*
 * FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
 * Rotation is separate from addition to prevent recomputation.
 */

#define FF(a, b, c, d, x, s, ac) \
	(a) += F ((b), (c), (d)) + (x) + (ac); \
	ROTATE_LEFT ((a), (s)); \
	(a) += (b);

#define GG(a, b, c, d, x, s, ac) \
	(a) += G ((b), (c), (d)) + (x) + (ac); \
	ROTATE_LEFT ((a), (s)); \
	(a) += (b);

#define HH(a, b, c, d, x, s, ac) \
	(a) += H ((b), (c), (d)) + (x) + (ac); \
	ROTATE_LEFT ((a), (s)); \
	(a) += (b);

#define II(a, b, c, d, x, s, ac) \
	(a) += I ((b), (c), (d)) + (x) + (ac); \
	ROTATE_LEFT ((a), (s)); \
	(a) += (b);

#if MD5_X2
static void MD5_body(MD5_word x0[15], MD5_word x1[15],
	MD5_word out0[4], MD5_word out1[4]);
#else
static void MD5_body(MD5_word x[15], MD5_word out[4]);
#endif

#else

extern void MD5_body(MD5_word x[15], MD5_word out[4]);

#endif

static unsigned char PADDING[56] = {
	0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

#if ARCH_LITTLE_ENDIAN

#define MD5_swap(x, y, count)

#else

static void MD5_swap(MD5_word *x, MD5_word *y, int count)
{
	register MD5_word tmp, mask;

	mask = OOFFOOFF;
	do {
		tmp = *x++;
		ROTATE_LEFT(tmp, 16);
		*y++ = ((tmp & mask) << 8) | ((tmp >> 8) & mask);
	} while (--count);
}

#endif

#define order				MD5_std_all._order
#define pool				MD5_std_all._pool
#define block				MD5_std_all._block

static void init_line(int line, int index, MD5_block *even, MD5_block *odd)
{
	order[line][index].even = even;
	order[line][index].odd = odd;
}

void MD5_std_init(void)
{
	int index;
	MD5_pool *current;

#if !MD5_IMM
	MD5_std_all.data = MD5_data_init;
#endif

	for (index = 0, current = pool; index < MD5_N; index++, current++) {
		init_line(0, index, &current->e.p, &current->o.psp);
		init_line(1, index, &current->e.spp, &current->o.pp);
		init_line(2, index, &current->e.spp, &current->o.psp);
		init_line(3, index, &current->e.pp, &current->o.ps);
		init_line(4, index, &current->e.spp, &current->o.pp);
		init_line(5, index, &current->e.spp, &current->o.psp);
		init_line(6, index, &current->e.pp, &current->o.psp);
		init_line(7, index, &current->e.sp, &current->o.pp);
		init_line(8, index, &current->e.spp, &current->o.psp);
		init_line(9, index, &current->e.pp, &current->o.psp);
		init_line(10, index, &current->e.spp, &current->o.p);
		init_line(11, index, &current->e.spp, &current->o.psp);
		init_line(12, index, &current->e.pp, &current->o.psp);
		init_line(13, index, &current->e.spp, &current->o.pp);
		init_line(14, index, &current->e.sp, &current->o.psp);
		init_line(15, index, &current->e.pp, &current->o.psp);
		init_line(16, index, &current->e.spp, &current->o.pp);
		init_line(17, index, &current->e.spp, &current->o.ps);
		init_line(18, index, &current->e.pp, &current->o.psp);
		init_line(19, index, &current->e.spp, &current->o.pp);
		init_line(20, index, &current->e.spp, &current->o.psp);
	}
}

void MD5_std_set_salt(char *salt)
{
	int length;

	for (length = 0; length < 8 && salt[length]; length++);

	memcpy(pool[0].s, salt, pool[0].l.s = length);
#if MD5_X2
	memcpy(pool[1].s, salt, pool[1].l.s = length);
#endif
}

void MD5_std_set_key(char *key, int index)
{
	int length;
	MD5_pool *current;

	for (length = 0; key[length] && length < 15; length++);
	current = &pool[index];

	memcpy(current->o.p.b, key, current->l.p = length);
	memcpy(&current->o.p.b[length + 16], PADDING, 40 - length);
	current->o.p.w[14] = (length + 16) << 3;

	memcpy(current->o.pp.b, key, length);
	memcpy(&current->o.pp.b[length], key, length);
	current->l.pp = length << 1;
	memcpy(&current->o.pp.b[current->l.pp + 16], PADDING,
		40 - current->l.pp);
	current->o.pp.w[14] = (current->l.pp + 16) << 3;

	memcpy(&current->e.p.b[16], key, length);
	memcpy(&current->e.p.b[16 + length], PADDING, 40 - length);
	current->e.p.w[14] = (length + 16) << 3;
	MD5_swap(current->e.p.w, current->e.p.w, 14);

	memcpy(&current->e.pp.b[16], current->o.pp.b, current->l.pp);
	memcpy(&current->e.pp.b[16 + current->l.pp], PADDING,
		40 - current->l.pp);
	current->e.pp.w[14] = (current->l.pp + 16) << 3;
	MD5_swap(current->e.pp.w, current->e.pp.w, 14);

	order[1][index].length = current->l.pp;
	order[4][index].length = current->l.pp;
	order[7][index].length = current->l.pp;
	order[10][index].length = length;
	order[13][index].length = current->l.pp;
	order[16][index].length = current->l.pp;
	order[19][index].length = current->l.pp;
}

void MD5_std_crypt(void)
{
	int length, index, mask;
	MD5_pattern *line;
#if ARCH_LITTLE_ENDIAN
	MD5_word *last0;
#endif
#if MD5_X2
	MD5_pool *key;
#if ARCH_LITTLE_ENDIAN
	MD5_word *last1;
#endif
#endif

#if MD5_X2
	for (index = 0, key = pool; index < MD5_N; index++, key++) {
#else
#define index	0
#define key	pool
#endif
		memcpy(key->o.ps.b, key->o.p.b, key->l.p);
		memcpy(&key->o.ps.b[key->l.p], key->s, key->l.s);
		key->l.ps = key->l.p + key->l.s;
		memcpy(&key->o.ps.b[key->l.ps + 16], PADDING,
			40 - key->l.ps);
		key->o.ps.w[14] = (key->l.ps + 16) << 3;

		memcpy(key->o.psp.b, key->o.ps.b, key->l.ps);
		memcpy(&key->o.psp.b[key->l.ps], key->o.p.b, key->l.p);
		key->l.psp = key->l.ps + key->l.p;
		memcpy(&key->o.psp.b[key->l.psp + 16], PADDING,
			40 - key->l.psp);
		key->o.psp.w[14] = (key->l.psp + 16) << 3;

		memcpy(&key->e.sp.b[16], key->s, key->l.s);
		memcpy(&key->e.sp.b[16 + key->l.s], key->o.p.b,
			key->l.p);
		memcpy(&key->e.sp.b[16 + key->l.ps], PADDING,
			40 - key->l.ps);
		key->e.sp.w[14] = (key->l.ps + 16) << 3;
		MD5_swap(key->e.sp.w, key->e.sp.w, 14);

		memcpy(&key->e.spp.b[16], key->s, key->l.s);
		memcpy(&key->e.spp.b[16 + key->l.s], key->o.pp.b,
			key->l.pp);
		memcpy(&key->e.spp.b[16 + key->l.psp], PADDING,
			40 - key->l.psp);
		key->e.spp.w[14] = (key->l.psp + 16) << 3;
		MD5_swap(key->e.spp.w, key->e.spp.w, 14);