算法识别之Sha1

又打了几天鱼晒了几天终于干了点什么,记录一下。

废了。

SHA1算法简介

简介

安全哈希算法(Secure Hash Algorithm)主要适用于数字签名标准(Digital Signature Standard DSS)里面定义的数字签名算法(Digital Signature Algorithm DSA)。对于长度小于2^64位的消息,SHA1会产生一个160位的消息摘要。当接收到消息的时候,这个消息摘要可以用来验证数据的完整性。在传输的过程中,数据很可能会发生变化,那么这时候就会产生不同的消息摘要。

SHA1有如下特性:不可以从消息摘要中复原信息;两个不同的消息不会产生同样的消息摘要。

术语和概念

位(Bit),字节(Byte)和字(Word)

SHA1始终把消息当成一个位(bit)字符串来处理。本文中,一个“字”(Word)是32位,而一个“字节”(Byte)是8位。比如,字符串“abc”可以被转换成一个位字符串:01100001 01100010 01100011。它也可以被表示成16进制字符串: 0x616263.

运算符和符号

下面的逻辑运算符都被运用于“字”(Word)

X^Y = X, Y逻辑与

X // Y = X, Y逻辑或

X XOR Y= X, Y逻辑异或

~X = X逻辑取反

X+Y定义如下:

字 X 和 Y 代表两个整数 x 和y, 其中 0 <= x < 2^32 且 0 <= y < 2^32. 令整数z = (x + y) mod 2^32. 这时候 0 <= z < 2^32. 将z转换成字Z, 那么就是 Z = X + Y.

循环左移位操作符Sn(X)。X是一个字,n是一个整数,0<=n<=32。Sn(X) = (X<>32-n)

X<>n是抛弃右边的n位,将各个位依次向右移动n位,然后在左边的n位填0。因此可以叫Sn(X)位循环移位运算

SHA1算法描述

在SHA1算法中,我们必须把原始消息(字符串,文件等)转换成位字符串。SHA1算法只接受位作为输入。假设我们对字符串“abc”产生消息摘要。首先,我们将它转换成位字符串如下:

01100001 01100010 01100011

―――――――――――――

‘a’=97 ‘b’=98 ‘c’=99

这个位字符串的长度为24。下面我们需要5个步骤来计算MD5。

补位

消息必须进行补位,以使其长度在对512取模以后的余数是448。也就是说,(补位后的消息长度)%512 = 448。即使长度已经满足对512取模后余数是448,补位也必须要进行。

补位是这样进行的:先补一个1,然后再补0,直到长度满足对512取模后余数是448。总而言之,补位是至少补一位,最多补512位。还是以前面的“abc”为例显示补位的过程。

原始信息: 01100001 01100010 01100011

补位第一步:01100001 01100010 01100011 1

首先补一个“1”

补位第二步:01100001 01100010 01100011 10…..0

然后补423个“0”

我们可以把最后补位完成后的数据用16进制写成下面的样子

61626380 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000

现在,数据的长度是448了,我们可以进行下一步操作。

补长度

所谓的补长度是将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于2^64,那么第一个字就是0。在进行了补长度的操作以后,整个消息就变成下面这样了(16进制格式)

61626380 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000018

如果原始的消息长度超过了512,我们需要将它补成512的倍数。然后我们把整个消息分成一个一个512位的数据块,分别处理每一个数据块,从而得到消息摘要。

使用的常量

一系列的常量字K(0), K(1), … , K(79),如果以16进制给出。它们如下:

Kt = 0x5A827999 (0 <= t <= 19)

Kt = 0x6ED9EBA1 (20 <= t <= 39)

Kt = 0x8F1BBCDC (40 <= t <= 59)

Kt = 0xCA62C1D6 (60 <= t <= 79).

需要使用的函数

在SHA1中我们需要一系列的函数。每个函数ft (0 <= t <= 79)都操作32位字B,C,D并且产生32位字作为输出。ft(B,C,D)可以如下定义

ft(B,C,D) = (B AND C) or ((NOT B) AND D) ( 0 <= t <= 19)

ft(B,C,D) = B XOR C XOR D (20 <= t <= 39)

ft(B,C,D) = (B AND C) or (B AND D) or (C AND D) (40 <= t <= 59)

ft(B,C,D) = B XOR C XOR D (60 <= t <= 79).

计算消息摘要

必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区,每个都由5个32位的字组成,还需要一个80个32位字的缓冲区。第一个5个字的缓冲区被标识为A,B,C,D,E。第一个5个字的缓冲区被标识为H0, H1, H2, H3, H4

。80个字的缓冲区被标识为W0, W1,…, W79

另外还需要一个一个字的TEMP缓冲区。

为了产生消息摘要,在第4部分中定义的16个字的数据块M1, M2,…, Mn

会依次进行处理,处理每个数据块Mi 包含80个步骤。

在处理每个数据块之前,缓冲区{Hi} 被初始化为下面的值(16进制)

H0 = 0x67452301

H1 = 0xEFCDAB89

H2 = 0x98BADCFE

H3 = 0x10325476

H4 = 0xC3D2E1F0.
现在开始处理M1, M2, … , Mn。为了处理 Mi,需要进行下面的步骤

(1). 将 Mi 分成 16 个字 W0, W1, … , W15, W0 是最左边的字

(2). 对于 t = 16 到 79 令 Wt = S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-16).

(3). 令 A = H0, B = H1, C = H2, D = H3, E = H4.

(4) 对于 t = 0 到 79,执行下面的循环

TEMP = S5(A) + ft(B,C,D) + E + Wt + Kt;

E = D; D = C; C = S30(B); B = A; A = TEMP;

(5). 令 H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E.
在处理完所有的 Mn, 后,消息摘要是一个160位的字符串,以下面的顺序标识

H0 H1 H2 H3 H4.

对于SHA256,SHA384,SHA512。你也可以用相似的办法来计算消息摘要。对消息进行补位的算法完全是一样的。

实例分析

例子很简单直接GetWindowTextA断点回溯即可找到验证函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
004014A4 |. 68 C9000000 push 0xC9 ; /Count = C9 (201.)
004014A9 |. 895424 40 mov dword ptr ss:[esp+0x40],edx ; |
004014AD |. 66:8B15 5C604>mov dx,word ptr ds:[0x40605C] ; |
004014B4 |. 51 push ecx ; |Buffer = 0019F5D4
004014B5 |. 66:894424 2D mov word ptr ss:[esp+0x2D],ax ; |
004014BA |. 68 E8030000 push 0x3E8 ; |ControlID = 3E8 (1000.)
004014BF |. 55 push ebp ; |hWnd = 00030A82 ('SHA1 *KeyGenMe*',class='#32770')
004014C0 |. 66:895424 40 mov word ptr ss:[esp+0x40],dx ; |
004014C5 |. 885C24 20 mov byte ptr ss:[esp+0x20],bl ; |
004014C9 |. 884424 37 mov byte ptr ss:[esp+0x37],al ; |
004014CD |. FFD7 call edi ; \GetDlgItemTextA
004014CF |. 8BF0 mov esi,eax ; 取用户名
004014D1 |. 3BF3 cmp esi,ebx ; user32.wsprintfA
004014D3 |. 0F84 11010000 je SHA1KeyG.004015EA
004014D9 |. 8D9424 980200>lea edx,dword ptr ss:[esp+0x298]
004014E0 |. 68 C9000000 push 0xC9 ; /Count = C9 (201.)
004014E5 |. 52 push edx ; |Buffer = 0019F34C
004014E6 |. 68 E9030000 push 0x3E9 ; |ControlID = 3E9 (1001.)
004014EB |. 55 push ebp ; |hWnd = 00030A82 ('SHA1 *KeyGenMe*',class='#32770')
004014EC |. FFD7 call edi ; \GetDlgItemTextA
004014EE |. 83F8 14 cmp eax,0x14 ; 取key,长度要为0x14
004014F1 |. 0F85 F3000000 jnz SHA1KeyG.004015EA
004014F7 |. 8D8424 600300>lea eax,dword ptr ss:[esp+0x360]
004014FE |. 50 push eax
004014FF |. E8 FCFAFFFF call SHA1KeyG.00401000 ; Sha1Init
00401504 |. 83C4 04 add esp,0x4
00401507 |. 33FF xor edi,edi
00401509 |. 3BF3 cmp esi,ebx ; user32.wsprintfA
0040150B |. 7E 1E jle short SHA1KeyG.0040152B
0040150D |> 0FBE8C3C D001>/movsx ecx,byte ptr ss:[esp+edi+0x1D0] ; 取用户名
00401515 |. 8D9424 600300>|lea edx,dword ptr ss:[esp+0x360]
0040151C |. 51 |push ecx
0040151D |. 52 |push edx
0040151E |. E8 1DFBFFFF |call SHA1KeyG.00401040 ; 消息填充
00401523 |. 83C4 08 |add esp,0x8
00401526 |. 47 |inc edi
00401527 |. 3BFE |cmp edi,esi
00401529 |.^ 7C E2 \jl short SHA1KeyG.0040150D
0040152B |> 8D8424 080100>lea eax,dword ptr ss:[esp+0x108]
00401532 |. 8D8C24 600300>lea ecx,dword ptr ss:[esp+0x360]
00401539 |. 50 push eax
0040153A |. 51 push ecx
0040153B |. E8 60FDFFFF call SHA1KeyG.004012A0 ; Sha1End
00401540 |. 83C4 08 add esp,0x8
00401543 |. 33C0 xor eax,eax
00401545 |> 8A5404 34 /mov dl,byte ptr ss:[esp+eax+0x34] ; pediy forum
00401549 |. 8A8C04 080100>|mov cl,byte ptr ss:[esp+eax+0x108] ; sha1值
00401550 |. 32D1 |xor dl,cl ; xor
00401552 |. 885404 40 |mov byte ptr ss:[esp+eax+0x40],dl ; endbuf
00401556 |. 40 |inc eax
00401557 |. 83F8 11 |cmp eax,0x11
0040155A |.^ 7C E9 \jl short SHA1KeyG.00401545
0040155C |. 83F8 14 cmp eax,0x14
0040155F |. 7D 1B jge short SHA1KeyG.0040157C
00401561 |. 8D4C24 28 lea ecx,dword ptr ss:[esp+0x28] ; pediy.com
00401565 |. 83E9 11 sub ecx,0x11
00401568 |> 8A1401 /mov dl,byte ptr ds:[ecx+eax]
0040156B |. 329404 080100>|xor dl,byte ptr ss:[esp+eax+0x108] ; 异或后三字节
00401572 |. 40 |inc eax
00401573 |. 83F8 14 |cmp eax,0x14
00401576 |. 885404 3F |mov byte ptr ss:[esp+eax+0x3F],dl
0040157A |.^ 7C EC \jl short SHA1KeyG.00401568
0040157C |> 8B1D A4504000 mov ebx,dword ptr ds:[<&USER32.wsprintfA>; user32.wsprintfA
00401582 |. 33F6 xor esi,esi
00401584 |. 8D7C24 10 lea edi,dword ptr ss:[esp+0x10]
00401588 |> 8A4434 4A /mov al,byte ptr ss:[esp+esi+0x4A]
0040158C |. 8A4C34 40 |mov cl,byte ptr ss:[esp+esi+0x40]
00401590 |. 32C8 |xor cl,al ; 十字节异或
00401592 |. 8AC1 |mov al,cl
00401594 |. 884C34 40 |mov byte ptr ss:[esp+esi+0x40],cl ; endbuf
00401598 |. 25 FF000000 |and eax,0xFF
0040159D |. 50 |push eax
0040159E |. 68 4C604000 |push SHA1KeyG.0040604C ; ASCII "%02X"
004015A3 |. 57 |push edi
004015A4 |. FFD3 |call ebx ; user32.wsprintfA
004015A6 |. 83C4 0C |add esp,0xC
004015A9 |. 46 |inc esi
004015AA |. 83C7 02 |add edi,0x2
004015AD |. 83FE 0A |cmp esi,0xA
004015B0 |.^ 7C D6 \jl short SHA1KeyG.00401588
004015B2 |. 8D8C24 980200>lea ecx,dword ptr ss:[esp+0x298]
004015B9 |. 8D5424 10 lea edx,dword ptr ss:[esp+0x10]
004015BD |. 51 push ecx ; /String2 = "1234567890abcdefghij"
004015BE |. 52 push edx ; |String1 = "F24CB1C3CDAE9D0F970D"
004015BF |. FF15 00504000 call dword ptr ds:[<&KERNEL32.lstrcmpA>] ; \lstrcmpA
004015C5 |. 85C0 test eax,eax
004015C7 |. 75 21 jnz short SHA1KeyG.004015EA
004015C9 |. 68 40604000 push SHA1KeyG.00406040 ; /Text = "Success!"
004015CE |. 68 E9030000 push 0x3E9 ; |ControlID = 3E9 (1001.)
004015D3 |. 55 push ebp ; |hWnd = 00030A82 ('SHA1 *KeyGenMe*',class='#32770')
004015D4 |. FF15 A8504000 call dword ptr ds:[<&USER32.SetDlgItemTe>; \SetDlgItemTextA
004015DA |. 5F pop edi ; 0019F34C
004015DB |. 5E pop esi ; 0019F34C
004015DC |. 5D pop ebp ; 0019F34C
004015DD |. B8 01000000 mov eax,0x1
004015E2 |. 5B pop ebx ; 0019F34C
004015E3 |. 81C4 B8040000 add esp,0x4B8
004015E9 |. C3 retn
004015EA |> 68 30604000 push SHA1KeyG.00406030 ; /Text = "Wrong Serial!"
004015EF |. 68 E9030000 push 0x3E9 ; |ControlID = 3E9 (1001.)
004015F4 |. 55 push ebp ; |hWnd = 00030A82 ('SHA1 *KeyGenMe*',class='#32770')
004015F5 |. FF15 A8504000 call dword ptr ds:[<&USER32.SetDlgItemTe>; \SetDlgItemTextA
004015FB |. 5F pop edi ; 0019F34C
004015FC |. 5E pop esi ; 0019F34C
004015FD |. 5D pop ebp ; 0019F34C
004015FE |. 33C0 xor eax,eax
00401600 |. 5B pop ebx ; 0019F34C
00401601 |. 81C4 B8040000 add esp,0x4B8
00401607 \. C3 retn
Sha1Init
00401000 /$ 8B5424 04 mov edx,dword ptr ss:[esp+0x4]
00401004 |. 57 push edi ; user32.GetDlgItemTextA
00401005 |. B9 50000000 mov ecx,0x50
0040100A |. 33C0 xor eax,eax
0040100C |. 8D7A 28 lea edi,dword ptr ds:[edx+0x28]
0040100F |. F3:AB rep stos dword ptr es:[edi]
00401011 |. 8942 04 mov dword ptr ds:[edx+0x4],eax
00401014 |. 8902 mov dword ptr ds:[edx],eax
00401016 |. C742 08 01234>mov dword ptr ds:[edx+0x8],0x67452301
0040101D |. C742 0C 89ABC>mov dword ptr ds:[edx+0xC],0xEFCDAB89
00401024 |. C742 10 FEDCB>mov dword ptr ds:[edx+0x10],0x98BADCFE
0040102B |. C742 14 76543>mov dword ptr ds:[edx+0x14],0x10325476
00401032 |. C742 18 F0E1D>mov dword ptr ds:[edx+0x18],0xC3D2E1F0
00401039 |. 5F pop edi ; 0019F69C
0040103A \. C3 retn

Sha1初始化后内存数据

进行消息填充后内存数据

以上就是分析流程,根据这就能写出注册机。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include "stdafx.h"
#include <string.h>
typedef struct {
unsigned int length[2];
unsigned int h[8];
unsigned int w[80];
} sha;
#define H0 0x67452301L
#define H1 0xefcdab89L
#define H2 0x98badcfeL
#define H3 0x10325476L
#define H4 0xc3d2e1f0L
#define K0 0x5a827999L
#define K1 0x6ed9eba1L
#define K2 0x8f1bbcdcL
#define K3 0xca62c1d6L
#define PAD 0x80
#define ZERO 0
/* functions */
#define S(n,x) (((x)<<n) | ((x)>>(32-n)))
#define F0(x,y,z) ((x&y)|((~x)&z))
#define F1(x,y,z) (x^y^z)
#define F2(x,y,z) ((x&y) | (x&z)|(y&z))
#define F3(x,y,z) (x^y^z)
static void sha1_transform(sha *sh)
{ /* basic transformation step */
unsigned int a, b, c, d, e, temp;
int t;
for (t = 16; t < 80; t++) sh->w[t] = S(1, sh->w[t - 3] ^ sh->w[t - 8] ^ sh->w[t - 14] ^ sh->w[t - 16]);
a = sh->h[0]; b = sh->h[1]; c = sh->h[2]; d = sh->h[3]; e = sh->h[4];
for (t = 0; t < 20; t++)
{ /* 20 times - mush it up */
temp = K0 + F0(b, c, d) + S(5, a) + e + sh->w[t];
e = d; d = c;
c = S(30, b);
b = a; a = temp;
}
for (t = 20; t < 40; t++)
{ /* 20 more times - mush it up */
temp = K1 + F1(b, c, d) + S(5, a) + e + sh->w[t];
e = d; d = c;
c = S(30, b);
b = a; a = temp;
}
for (t = 40; t < 60; t++)
{ /* 20 more times - mush it up */
temp = K2 + F2(b, c, d) + S(5, a) + e + sh->w[t];
e = d; d = c;
c = S(30, b);
b = a; a = temp;
}
for (t = 60; t < 80; t++)
{ /* 20 more times - mush it up */
temp = K3 + F3(b, c, d) + S(5, a) + e + sh->w[t];
e = d; d = c;
c = S(30, b);
b = a; a = temp;
}
sh->h[0] += a; sh->h[1] += b; sh->h[2] += c;
sh->h[3] += d; sh->h[4] += e;
}
void sha1_init(sha *sh)
{ /* re-initialise */
int i;
for (i = 0; i < 80; i++) sh->w[i] = 0L;
sh->length[0] = sh->length[1] = 0L;
sh->h[0] = H0;
sh->h[1] = H1;
sh->h[2] = H2;
sh->h[3] = H3;
sh->h[4] = H4;
}
void sha1_process(sha *sh, int byte)
{ /* process the next message byte */
int cnt;
cnt = (int)((sh->length[0] / 32) % 16);
sh->w[cnt] <<= 8;
sh->w[cnt] |= (unsigned int)(byte & 0xFF);
sh->length[0] += 8;
if (sh->length[0] == 0L) { sh->length[1]++; sh->length[0] = 0L; }
if ((sh->length[0] % 512) == 0) sha1_transform(sh);
}
void sha1_hash(sha *sh, char hash[20])
{ /* pad message and finish - supply digest */
int i;
unsigned int len0, len1;
len0 = sh->length[0];
len1 = sh->length[1];
sha1_process(sh, PAD);
while ((sh->length[0] % 512) != 448) sha1_process(sh, ZERO);
sh->w[14] = len1;
sh->w[15] = len0;
sha1_transform(sh);
for (i = 0; i < 20; i++)
{ /* convert to bytes */
hash[i] = ((sh->h[i / 4] >> (8 * (3 - i % 4))) & 0xffL);
}
sha1_init(sh);
}
int _tmain(int argc, _TCHAR* argv[])
{
sha sh;
sha1_init(&sh);
char *strName = "abcde" ;
for (int i = 0; i < strlen(strName); i++)
{
sha1_process(&sh, strName[i]);
}
char strRes[0x20] = { 0 };
sha1_hash(&sh, strRes);
char *str1 = "PEDIY Forum";
char strEnd[0x20] = { 0 };
int i = 0;
for (i = 0; i < 17; i++)
{
strEnd[i] = strRes[i] ^ str1[i];
}
char *str2 = "pediy.com";
for (; i < 0x14;i++)
{
strEnd[i] = str2[i] ^ strRes[i - 0x11];
}
for (i = 0; i < 0xa; i++)
{
strEnd[i] ^= strEnd[i + 0xa];
}
return 0;
}

总结一下识别Sha1的关键特征:
1)五个初始化的常量0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476,0xC3D2E1F0