算法还原之SHA1

一 sha1算法原理

SHA1算法是Hash算法的一种。SHA1算法的最大输入长度小于2^64比特的消息，输入消息（明文）以512比特的分组为单位处理，输出160比特的消息摘要（密文）

整个算法的核心是一个包含4轮循环的模块，每轮循环由20个步骤组成。

具体实现步骤如下：

1 附加填充位

消息必须进行填充，以使其长度在对512取模以后的余数是448。也就是说，（填充后的消息长度）%512 = 448。即使长度已经满足对512取模后余数是448，填充也必须要进行。填充的规则是填充一个“1”和若干个“0”使其长度模512和448同余。然后附加64比特的无符号整数，其值为原始消息的长度（这块和MD5是一样的）

2 附加长度信息

后面的64比特位，用来填充长度信息，长度单位为比特。（这块和MD5一样）

3 信息分组处理

经过添加位数处理的明文，其长度正好为512位的整数倍，然后按512位的长度进行分组，可以得到一定数量的明文分组，这块可以用Y0,Y1,Y2,…,YN-1来表示，对于每一个分组，进行处理。（这块和MD5一样）

而对于每个512位的明文分组，SHA1将其再分成16个更小的明文分组，称为子明文分组，每个子明文分组为32位，这块使用 Mt来表示着16个子明文分组。然后需要将这16个子明文分组扩充到80个子明文分组，分别将其记为 Wt，扩充的具体方法为：

4 初始化链接向量

和MD5有些类似，将5个32比特的固定数赋值给5个32比特的寄存器（和汇编里面的寄存器不同，可以理解为变量）A、B、C、D、E作为第一次迭代的链接变量输入：

• A = 0x67452301
• B = 0xEFCDAB89
• C = 0x98BADCFE
• D = 0x10325476
• E = 0xC3D2E1F0

5 运算

经过前面的准备，接下来就是计算信息摘要。SHA1有4轮运算，每一轮包括20个步骤，一共80步。最终产生160位的信息摘要，这160位的信息摘要直接存放在5个32位的链接变量中。

在SHA1的4轮运算中，虽然进行的具体操作函数不同，但是逻辑过程是一致的。首先，定义5个变量，假设为H0、H1、H2、H3、H4，对其分别进行如下操作：

• 将A左移5位与函数的结果求和，再与其对应的子明文分组、E以及计算常数求和后的结果赋值给H0
• 将A的值赋予H1
• 将B左移30位，并赋予H2
• 将C的值赋予H3
• 将D的值赋予H4
• 最后将H0、H1、H2、H3、H4值分别赋予A、B、C、D、E

K值的获取（MD5中也有K表，只不过 len(md5_k)=64，而 len(sha1_k)=64）

下面是80轮循环的简易代码：

//第一轮R1[a,b,c,d,e,j]表示e = e + F1(b,c,d)+rol(a,5)+W[j]+K1;b=rol(b,30)
R1(a, b, c, d, e, 0),R1(e, a, b, c, d, 1),R1(d, e, a, b, c, 2),R1(c, d, e, a, b, 3)
R1(b, c, d, e, a, 4),R1(a, b, c, d, e, 5),R1(e, a, b, c, d, 6),R1(d, e, a, b, c, 7)
R1(c, d, e, a, b, 8),R1(b, c, d, e, a, 9),R1(a, b, c, d, e, 10),R1(e, a, b, c, d, 11)
R1(d, e, a, b, c, 12),R1(c, d, e, a, b, 13),R1(b, c, d, e, a, 14),R1(a, b, c, d, e, 15)
R1(e, a, b, c, d, 16),R1(d, e, a, b, c, 17),R1(c, d, e, a, b, 18),R1(b, c, d, e, a, 19)

//第二轮R2[a,b,c,d,e,j]表示e = e + F2(b,c,d)+rol(a,5)+W[j]+K2;b=rol(b,30)
R2(a, b, c, d, e, 20);R2(e, a, b, c, d, 21);R2(d, e, a, b, c, 22);R2(c, d, e, a, b, 23);
R2(b, c, d, e, a, 24);R2(a, b, c, d, e, 25);R2(e, a, b, c, d, 26);R2(d, e, a, b, c, 27);
R2(c, d, e, a, b, 28);R2(b, c, d, e, a, 29);R2(a, b, c, d, e, 30);R2(e, a, b, c, d, 31);
R2(d, e, a, b, c, 32);R2(c, d, e, a, b, 33);R2(b, c, d, e, a, 34);R2(a, b, c, d, e, 35);
R2(e, a, b, c, d, 36);R2(d, e, a, b, c, 37);R2(c, d, e, a, b, 38);R2(b, c, d, e, a, 39);

//第三轮R3[a,b,c,d,e,j]表示e = e + F3(b,c,d)+rol(a,5)+W[j]+K3;b=rol(b,30)
R3(a, b, c, d, e, 40);R3(e, a, b, c, d, 41);R3(d, e, a, b, c, 42);R3(c, d, e, a, b, 43);
R3(b, c, d, e, a, 44);R3(a, b, c, d, e, 45);R3(e, a, b, c, d, 46);R3(d, e, a, b, c, 47);
R3(c, d, e, a, b, 48);R3(b, c, d, e, a, 49);R3(a, b, c, d, e, 50);R3(e, a, b, c, d, 51);
R3(d, e, a, b, c, 52);R3(c, d, e, a, b, 53);R3(b, c, d, e, a, 54);R3(a, b, c, d, e, 55);
R3(e, a, b, c, d, 56);R3(d, e, a, b, c, 57);R3(c, d, e, a, b, 58);R3(b, c, d, e, a, 59);

//第四轮R4[a,b,c,d,e,j]表示e = e + F4(b,c,d)+rol(a,5)+W[j]+K4;b=rol(b,30)
R4(a, b, c, d, e, 60);R4(e, a, b, c, d, 61);R4(d, e, a, b, c, 62);R4(c, d, e, a, b, 63);
R4(b, c, d, e, a, 64);R4(a, b, c, d, e, 65);R4(e, a, b, c, d, 66);R4(d, e, a, b, c, 67);
R4(c, d, e, a, b, 68);R4(b, c, d, e, a, 69);R4(a, b, c, d, e, 70);R4(e, a, b, c, d, 71);
R4(d, e, a, b, c, 72);R4(c, d, e, a, b, 73);R4(b, c, d, e, a, 74);R4(a, b, c, d, e, 75);
R4(e, a, b, c, d, 76);R4(d, e, a, b, c, 77);R4(c, d, e, a, b, 78);R4(b, c, d, e, a, 79);

6 输出

运算结束，将ABCDE合并输出

二 源码实现

sha1.h

#ifndef SHA1_H
#define SHA1_H

#ifdef __cplusplus
extern "C" {
#endif

#define SHA1HANDSOFF
#define LITTLE_ENDIAN

typedef struct
{
	unsigned long state[5];			/* 160(5×32)比特的消息摘要（即SHA-1算法要得出的） */
	unsigned long count[2];			/* 储存消息的长度（单位：比特） */
	unsigned char buffer[64];		/* 512(64×8)比特（位）的消息块（由原始消息经处理得出） */
} SHA1_CTX;


void SHA1Init(SHA1_CTX *context);

void SHA1Update(SHA1_CTX *context, unsigned char *data, unsigned int len);

void SHA1Final(unsigned char digest[20], SHA1_CTX *context);

#ifdef __cplusplus
}
#endif

#endif

sha1.c

#include <stdio.h>
#include <string.h>
#include "sha1.h"

typedef union {
	unsigned char c[64];
	unsigned long l[16];
} CHAR64LONG16;

#define rol(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits))))

/*   blk0()   and   blk()   perform   the   initial   expand.   */
/*   I   got   the   idea   of   expanding   during   the   round   function   from   SSLeay   */
#ifdef LITTLE_ENDIAN
	#define blk0(i) (block->l[i] = (rol(block->l[i], 24) & 0xFF00FF00) | (rol(block->l[i], 8) & 0x00FF00FF))
#else
	#define blk0(i) block->l[i]
#endif

#define blk(i) (block->l[i & 15] = rol(block->l[(i + 13) & 15] ^ block->l[(i + 8) & 15] ^ block->l[(i + 2) & 15] ^ block->l[i & 15], 1))

/*   (R0+R1),   R2,   R3,   R4   are   the   different   operations   used   in   SHA1   */
#define R0(v, w, x, y, z, i)                                     \
	z += ((w & (x ^ y)) ^ y) + blk0(i) + 0x5A827999 + rol(v, 5); \
	w = rol(w, 30);

#define R1(v, w, x, y, z, i)                                    \
	z += ((w & (x ^ y)) ^ y) + blk(i) + 0x5A827999 + rol(v, 5); \
	w = rol(w, 30);

#define R2(v, w, x, y, z, i)                            \
	z += (w ^ x ^ y) + blk(i) + 0x6ED9EBA1 + rol(v, 5); \
	w = rol(w, 30);

#define R3(v, w, x, y, z, i)                                          \
	z += (((w | x) & y) | (w & x)) + blk(i) + 0x8F1BBCDC + rol(v, 5); \
	w = rol(w, 30);

#define R4(v, w, x, y, z, i)                            \
	z += (w ^ x ^ y) + blk(i) + 0xCA62C1D6 + rol(v, 5); \
	w = rol(w, 30);


static void SHA1Transform(unsigned long state[5], unsigned char buffer[64]);


/*   Hash   a   single   512-bit   block.   This   is   the   core   of   the   algorithm.   */
static void SHA1Transform(unsigned long state[5], unsigned char buffer[64])
{
	unsigned long a, b, c, d, e;
	CHAR64LONG16 *block;

#ifdef SHA1HANDSOFF
	static unsigned char workspace[64];
	block = (CHAR64LONG16 *)workspace;
	memcpy(block, buffer, 64);
#else
	block = (CHAR64LONG16 *)buffer;
#endif

	/*   Copy   context-> state[]   to   working   vars   */
	a = state[0];
	b = state[1];
	c = state[2];
	d = state[3];
	e = state[4];

	/* 完成的就是RFC文档中的H0～H4赋值给ABCDE的操作。接下来就是80轮运算的代码。每20轮为一组，共分四组 */
	/* 第一组比较特殊，使用了R0和R1两个宏函数，其原因前面已经介绍了。因为第0~15轮运算和16~79轮运算的时候消息块M(i)和字块W(i)的转换是不一样的。后面的20~39轮，40~59轮，60~79轮就是依次使用的R2，R3，R4来运算了 */
	/*   4   rounds   of   20   operations   each.   Loop   unrolled.   */
	R0(a, b, c, d, e, 0);
	R0(e, a, b, c, d, 1);
	R0(d, e, a, b, c, 2);
	R0(c, d, e, a, b, 3);

	R0(b, c, d, e, a, 4);
	R0(a, b, c, d, e, 5);
	R0(e, a, b, c, d, 6);
	R0(d, e, a, b, c, 7);

	R0(c, d, e, a, b, 8);
	R0(b, c, d, e, a, 9);
	R0(a, b, c, d, e, 10);
	R0(e, a, b, c, d, 11);

	R0(d, e, a, b, c, 12);
	R0(c, d, e, a, b, 13);
	R0(b, c, d, e, a, 14);
	R0(a, b, c, d, e, 15);

	R1(e, a, b, c, d, 16);
	R1(d, e, a, b, c, 17);
	R1(c, d, e, a, b, 18);
	R1(b, c, d, e, a, 19);

	R2(a, b, c, d, e, 20);
	R2(e, a, b, c, d, 21);
	R2(d, e, a, b, c, 22);
	R2(c, d, e, a, b, 23);

	R2(b, c, d, e, a, 24);
	R2(a, b, c, d, e, 25);
	R2(e, a, b, c, d, 26);
	R2(d, e, a, b, c, 27);

	R2(c, d, e, a, b, 28);
	R2(b, c, d, e, a, 29);
	R2(a, b, c, d, e, 30);
	R2(e, a, b, c, d, 31);

	R2(d, e, a, b, c, 32);
	R2(c, d, e, a, b, 33);
	R2(b, c, d, e, a, 34);
	R2(a, b, c, d, e, 35);

	R2(e, a, b, c, d, 36);
	R2(d, e, a, b, c, 37);
	R2(c, d, e, a, b, 38);
	R2(b, c, d, e, a, 39);

	R3(a, b, c, d, e, 40);
	R3(e, a, b, c, d, 41);
	R3(d, e, a, b, c, 42);
	R3(c, d, e, a, b, 43);

	R3(b, c, d, e, a, 44);
	R3(a, b, c, d, e, 45);
	R3(e, a, b, c, d, 46);
	R3(d, e, a, b, c, 47);

	R3(c, d, e, a, b, 48);
	R3(b, c, d, e, a, 49);
	R3(a, b, c, d, e, 50);
	R3(e, a, b, c, d, 51);

	R3(d, e, a, b, c, 52);
	R3(c, d, e, a, b, 53);
	R3(b, c, d, e, a, 54);
	R3(a, b, c, d, e, 55);

	R3(e, a, b, c, d, 56);
	R3(d, e, a, b, c, 57);
	R3(c, d, e, a, b, 58);
	R3(b, c, d, e, a, 59);

	R4(a, b, c, d, e, 60);
	R4(e, a, b, c, d, 61);
	R4(d, e, a, b, c, 62);
	R4(c, d, e, a, b, 63);

	R4(b, c, d, e, a, 64);
	R4(a, b, c, d, e, 65);
	R4(e, a, b, c, d, 66);
	R4(d, e, a, b, c, 67);

	R4(c, d, e, a, b, 68);
	R4(b, c, d, e, a, 69);
	R4(a, b, c, d, e, 70);
	R4(e, a, b, c, d, 71);

	R4(d, e, a, b, c, 72);
	R4(c, d, e, a, b, 73);
	R4(b, c, d, e, a, 74);
	R4(a, b, c, d, e, 75);

	R4(e, a, b, c, d, 76);
	R4(d, e, a, b, c, 77);
	R4(c, d, e, a, b, 78);
	R4(b, c, d, e, a, 79);

	/* 完成的就是更新缓冲区H0～H4的内容。然后把a～e清空为0 */
	/*   Add   the   working   vars   back   into   context.state[]   */
	state[0] += a;
	state[1] += b;
	state[2] += c;
	state[3] += d;
	state[4] += e;
	/*   Wipe   variables   */
	a = b = c = d = e = 0;
}

/*   SHA1Init   -   Initialize   new   context   */
void SHA1Init(SHA1_CTX *context)
{
	/*   SHA1   initialization   constants   */
	context->state[0] = 0x67452301;

	context->state[1] = 0xEFCDAB89;

	context->state[2] = 0x98BADCFE;

	context->state[3] = 0x10325476;

	context->state[4] = 0xC3D2E1F0;

	context->count[0] = context->count[1] = 0;
}

/*   Run   your   data   through   this.   */
void SHA1Update(SHA1_CTX *context, unsigned char *data, unsigned int len)
{
	unsigned int i, j;

	/*   j>>3获得的就是字节数，j = (j >> 3) & 63得到的就是低6位的值，也就是代表64个字节（512位）长度的消息。，因为我们每次进行计算都是处理512位的消息数据。 */
	j = (context->count[0] >> 3) & 63;

	/* context->count[ ]存储的是消息的长度，超出context->count[0]的存储范围的部分存储在context->count[1]中。len<<3就是len*8的意思，因为len的单位是字节，而context->count[ ]存储的长度的单位是位，所以要乘以8。 if ((context->count[0] += len << 3) < j) 的意思就是说如果加上len*8个位，context->count[0]溢出了，那么就要：context->count[1]++；进位。
	len<<3的单位是位，len>>29（len<<3 >>32）表示的就是len中要存储在context->count[1]中的部分。 */
	if ((context->count[0] += len << 3) < (len << 3))
		context->count[1]++;

	context->count[1] += (len >> 29);

	/* 如果j+len的长度大于63个字节，就分开处理，每64个字节处理一次，然后再处理后面的64个字节，重复这个过程；否则就直接将数据附加到buffer末尾 */
	if ((j + len) > 63)
	{
		memcpy(&context->buffer[j], data, (i = 64 - j));		/* i=64-j，然后从data中复制i个字节的数据附加到context->buffer[j]末尾，也就是说给buffer凑成了64个字节 */
		SHA1Transform(context->state, context->buffer);			/* 执行SHA1Transform()来开始一次消息摘要的计算 */
		/* 每64个字节处理一次 */
		for (; i + 63 < len; i += 64)
		{
			SHA1Transform(context->state, &data[i]);
		}
		j = 0;
	}
	else
	{
		i = 0;
	}

	/* 如果前面的if不成立，那么也就是说原始数据context->buffer加上新的数据data的长度还不足以凑成64个字节，所以直接附加上data就行了。相当于：memcpy(&context->buffer[j], &data[i], 0);
	如果前面的if成立，那么j是等于0的，而 i 所指向的偏移位置是 (└ len/64┘×64,len)之间。 └   ┘表示向下取整。*/

	memcpy(&context->buffer[j], &data[i], len - i);
}

/*   Add   padding   and   return   the   message   digest.   */
void SHA1Final(unsigned char digest[20], SHA1_CTX *context)
{
	unsigned long i, j;
	unsigned char finalcount[8];

	for (i = 0; i < 8; i++)
	{
		finalcount[i] = (unsigned char)((context->count[(i >= 4 ? 0 : 1)]
										 >> ((3 - (i & 3)) * 8)) &
										255); /*   Endian   independent   */
	}
	/* 填充的时候是以字节为单位的，最少1个字节，最多64个字节。并且第一位要填充1，后面都填充0。所以拿到一个消息我们首先要给他填充一个字节的10 000 000.SHA1Update() 函数就是完成的数据填充（附加）操作 */
	SHA1Update(context, (unsigned char *)"\200 ", 1);

	/* 循环测试数据模512是否与448同余。不满足条件就填充全一个字节0。 */
	/* 使用 while ((context->count[0] & 511) != 448) 貌似更合适。但是，504后三位全0,511后三位全1。context->count中存储的是消息的长度，它的单位是：位。前面我们提到了我们的数据是以字节来存储的，所以context->count[ ]中的数据肯定是8个倍数，所以后三位肯定是000。所以不管是000&000，还是000&111其结果都是0。 */
	while ((context->count[0] & 504) != 448)
	{
		SHA1Update(context, (unsigned char *)"\0 ", 1);
	}

	/* 这将触发SHA1Transform()函数的调用，该函数的功能就是进行运算，得出160位的消息摘要（message digest）并储存在context-state[ ]中，它是整个SHA-1算法的核心 */
	SHA1Update(context, finalcount, 8); /*   Should   cause   a   SHA1Transform()   */

	/* 最后的这步转换将消息摘要转换成单字节序列。用代码来解释就是：将context-state[5]中储存的20个字节（5×4字节）的消息摘要取出，将其存储在20个单字节的数组digest中。并且按大端序存储（与之前分析context->count[ ]到finalcount[ ]转换的思路相同） */
	for (i = 0; i < 20; i++)
	{
		digest[i] = (unsigned char)

			((context->state[i >> 2] >> ((3 - (i & 3)) * 8)) & 255);
	}

	/*   Wipe   variables   */
	i = j = 0;
	memset(context->buffer, 0, 64);
	memset(context->state, 0, 20);
	memset(context->count, 0, 8);
	memset(&finalcount, 0, 8);

#ifdef SHA1HANDSOFF /*   make   SHA1Transform   overwrite   it 's   own   static   vars   */
	SHA1Transform(context->state, context->buffer);
#endif
}

main.c

#include<stdio.h>
#include<string.h>
#include "sha1.h"

int main()
{
    SHA1_CTX ctx;
    unsigned char hash[20];
    unsigned char abc[] = "123456";
    /* 计算前，先初始化 */
    SHA1Init(&ctx);
    /* 多次调用 SHA1Update 循环计算多个包数据（如果有的话） */
    SHA1Update(&ctx, abc, strlen(abc));
    /* 最后调用 SHA1Final 获取最终结果 */
    SHA1Final(hash, &ctx);
    for (int i = 0; i < 20; i++)
        printf("%2.2x", hash[i]);
}

三 汇编分析识别sha1算法

参考如下文章：

逆向分析中的密码学—SHA1_sha1逆向-CSDN博客

---

使用PEid带的Krypto ANALyzer还是可以识别到程序使用了sha1

使用ida pro的插件Findcrypt能够识别到初始化常数ABCDE和主循环常数K

1 算法识别

main函数主要包括下面3个步骤。

1. SHA1init
2. SHA1Update
3. SHA1Final

SHA1init

初始化ABCDE，并将长度置为0

SHA1Update

循环将将每个512bit的chunk进行80轮的运算

SHA1Final

最后填充数据和添加消息长度，进入最后的hash计算

2 总结

sha1哈希计算，先进行数据填充，再补上消息长度，只后每512bit进行80轮的hash计算，最后将最后的ABCDE拼接得到160位的hash值

sha1特征

• 初始化常数ABCDE（0x67452301、0xEFCDAB89、0x98BADCFE、0x10325476、0xC3D2E1F0）
• 常数K1、K2、K2、K3、K4，0x5A827999、0x6ED9EBA1、0x8F1BBCDC、0x6ED9EBA1
• 80轮hash计算中W[i]的生成，前16轮由512位的输入得到，后W[16-79]由前面的W生成得到
• 4组基本轮函数F1,F2,F3,F4