常见hash算法

hash加密算法

逆向中常常出现一些加密算法，如果我们能对这些加密算法进行快速识别则会大大减少我们逆向的难度，虽然IDA已有密码分析神器Findcrypt，但掌握手动分析方法能帮助我们应对更多的情况。

以下文章大部分来自《加密与解密》段刚著。

前言

做逆向一遇到复杂的加密就不会了，还没能系统的学习密码学吧，之后准备看看《深入浅出密码学》，这里汇总一下 各类加密算法吧加上逆向的例子便于理解。

hash的前奏

Hash存储
Hash存储的意思是：对用户输入的密码按照Hash算法得到Hash值，然后将Hash值存到数据库中。
为什么说是 “Hash存储”，而不是 “加密存储”？因为这本来就不算是加密解密的过程，而且很容易对人造成误解。Hash算法是将目标文本转换成具有相同长度的、不可逆的杂凑字符串（或叫做消息摘要），而加密（Encrypt）是将目标文本转换成具有不同长度的、可逆的密文。

转换算法目前主流的就是哈希算法，也叫译摘要算法，是一种散列算法。哈希算法是不可逆的，这里的不可逆有两层含义，一是“给定一个哈希结果R，没有方法将R转换成原目标文本S”，二是“给定哈希结果R，即使知道一段文本S的哈希结果为R，也不能断言当初的目标文本就是S”(但可以Hash碰撞)。

为什么需要单向的算法？回到之前的那句话：“最完美的方法就是确保该密码只有用户自己知道”。单向的，就意味着对于每一个固定的明文，经过Hash算法转换后可以得到固定的Hash值，但是根据Hash值，却无法得到明文。数据库最高管理员可以看到不同用户密码对应的Hash值，但因为Hash算法是不可逆的，所以，他也无法知道用户的文明，没有明文，就无法登录系统进行危险操作。

但是仔细想想，上面的方案还是会有一些问题。我们知道，根据固定的明文，按照一定的Hash算法可以得到固定的Hash值。用户设置密码的时候，又基本上不会设置泰国负载的密码，那就有可能通过穷举法来实现破解，将常见密码的的Hash值全部算出来，然后拿用户的Hash值一一匹对，虽然，根据不同的明文生成的 hash 值可能相同(Hash碰撞)，但这只会让破解更简单。

盐值
为了解决上面的问题，hash 方案迎来的第一个改造是对引入一个“随机的因子”来掺杂进明文中进行 hash 计算，这样的随机因子通常被称之为盐 （salt）。salt 一般是用户相关的，每个用户持有各自的 salt。此时两个用户的密码即使相同，由于 salt 的影响，存储在数据库中的密码也是不同的。

但现在的计算机能力越来越强，虽然破解 salted hash 比较麻烦，却并非不可行。一些新型的单向 hash 算法被研究了出来。其中就包括：Bcrypt，PBKDF2，Scrypt，Argon2。

单项散列算法

单项散列算法也是hash算法，是将一种将任意长度压缩到固定长度的函数（不可逆）。hash函数可用于数字签名、消息完整性检测、消息起源的认证检测等。常见的hash算法有MD5、SHA、RIPE-MD、HAVAL、N-Hash等。

MD5和SHA。SHA又包括 SHA-1 和 SHA-2(SHA-224、SHA-256、SHA-384、SHA-512) 和SHA-3。

• MD5是输入不定长度信息，输出固定长度128-bits的算法。经过程序流程，生成四个32位数据，最后联合起来成为一个128-bits散列。基本方式为，求余、取余、调整长度、与链接变量进行循环运算。得出结果。
• SHA-1在许多安全协议中广为使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被视为是MD5（更早之前被广为使用的散列函数）的后继者。
• SHA-2它的算法跟SHA-1基本上仍然相似；因此有些人开始发展其他替代的散列算法。
• 由于对MD5出现成功的破解，以及对SHA-0和SHA-1出现理论上破解的方法，NIST感觉需要一个与之前算法不同的，可替换的加密杂凑算法，也就是现在的SHA-3。

MD5

MD5（Message Digest Algorithm）消息摘要算法对输入的任意长度的消息进行运算，产生一个128位的消息摘要。是由R. Rivest 设计的
MD5的特征是会出现下图中 A,B,C,D 这四个常量。

A = 01234567h , B = 89abcdefh , C =fedcba98h , D = 76543210h

算法原理

1.数据填充

填充消息使得长度在448模512同余，即长度 ≡ 448 mod 512,。也就是说消息长度比512的倍数仅小64位，即使消息长度已满足也要填充，填充方法是：附一个1在消息后，然后用0来补充。直到与448模512同余。至少填一位，最多512位。

2.添加长度
在上一步的结果之后附上 64 位的消息长度。如果填充前消息的长度大于 2的64次方，则只使用其低 64位。添加填充位和消息长度之后，最终消息的长度正好是 512 的整数倍。
令M[0…N-1]表示最终的消息，其中N是16的倍数。

随书文件MD5KeyGenMe.exe来分析

发现需要有name和Serial Number

qmemcpy(v9, aWwwPediyCom, 0x15u);
 strcpy(v10, "23456789ABCDEFGHJKLMNPQRSTUVWXYZ");
 *(_DWORD *)&String1[1] = 0;
 *(_DWORD *)&String1[5] = 0;
 *(_DWORD *)&String1[9] = 0;
 *(_DWORD *)&String1[13] = 0;
 v7 = 0;
 String1[0] = 0;
 v8 = 0;
 v1 = GetDlgItemTextA(hDlg, 1000, &String, 201);
 if ( !v1 )
   goto LABEL_10;
 if ( GetDlgItemTextA(hDlg, 1001, v11, 201) != 19 )
   goto LABEL_10;
 if ( v12 != 45 )
   goto LABEL_10;
 if ( v14 != 45 )
   goto LABEL_10;
 if ( v16 != 45 )
   goto LABEL_10;
 *(_DWORD *)&String1[4] = v13;
 *(_DWORD *)String1 = *(_DWORD *)v11;
 *(_DWORD *)&String1[8] = v15;
 *(_DWORD *)&String1[12] = v17;
 sub_4012B0(v20);
 sub_4012E0(v20, &String, v1);
 v2 = lstrlenA(v9);
 sub_4012E0(v20, v9, v2);
 sub_401390(&v21, v20);
 for ( i = 0; i < 16; *(&v28 + i) = v10[v4] )
   v4 = *(&v21 + i++) & 0x1F;
 if ( !lstrcmpA(String1, &String2) )
 {
   SetDlgItemTextA(hDlg, 1001, aSuccess);
   result = 1;
 }

发现特征值

_DWORD *__cdecl sub_4012B0(_DWORD *a1)
{
  _DWORD *result; // eax

  result = a1;
  a1[5] = 0;
  a1[4] = 0;
  *a1 = 0x67452301;
  a1[1] = 0xEFCDAB89;
  a1[2] = 0x98BADCFE;
  a1[3] = 0x10325476;
  return result;
}

还原符号，需要注意的一点是连续调用两次MD5_Update相当于把两次的输入拼接后调用一次MD5_Update的结果

qmemcpy(v9, aWwwPediyCom, 0x15u);
  strcpy(v10, "23456789ABCDEFGHJKLMNPQRSTUVWXYZ");
  *(_DWORD *)&String1[1] = 0;
  *(_DWORD *)&String1[5] = 0;
  *(_DWORD *)&String1[9] = 0;
  *(_DWORD *)&String1[13] = 0;
  v7 = 0;
  String1[0] = 0;
  v8 = 0;
  v1 = GetDlgItemTextA(hDlg, 1000, &name, 201);
  if ( !v1 )
    goto LABEL_10;
  if ( GetDlgItemTextA(hDlg, 1001, serial_number, 201) != 19 )
    goto LABEL_10;
  if ( v12 != '-' )
    goto LABEL_10;
  if ( v14 != '-' )
    goto LABEL_10;
  if ( v16 != '-' )
    goto LABEL_10;
  *(_DWORD *)&String1[4] = v13;
  *(_DWORD *)String1 = *(_DWORD *)serial_number;
  *(_DWORD *)&String1[8] = v15;
  *(_DWORD *)&String1[12] = v17;
  MD5_init(v20);
  MD5_Update((int)v20, (int)&name, v1);
  v2 = lstrlenA(v9);
  MD5_Update((int)v20, (int)v9, v2);
  MD5_Final((int)&v21, (int)v20);
  for ( i = 0; i < 16; *(&v28 + i) = v10[v4] )
    v4 = *(&v21 + i++) & 31;
  if ( !lstrcmpA(String1, &String2) )
  {
    SetDlgItemTextA(hDlg, 1001, String);
    result = 1;
  }

注册机

from hashlib import md5
 
name = b'pediy'
digest = md5(name + b'www.pediy.com').digest()
a2345 = '23456789ABCDEFGHJKLMNPQRSTUVWXYZ'
serial_number = ''
for b in digest:
    serial_number += a2345[b % 32] //for ( i = 0; i < 16; *(&v28 + i) = v10[v4] )
    								// v4 = *(&v21 + i++) & 31;
print(serial_number[0:4]+'-'+serial_number[4:8]+'-'+serial_number[8:12]+'-'+serial_number[12:16])

查看FindCrypt，只有MD5

SHA

安全散列算法（Secure Hash Algorithm，SHA）包括SHA-1、SHA-256、SHA-384和SHA-512，分别产生160位、256位、384位和512位的散列值。
类似于MD5，SHA算法使用了一系列的常数：

SHA-1算法产生160位的消息摘要，在对消息进行处理之前，初试hash值H用5个32

用随书文件做分析SHA1KeyGenMe.exe 来分析

还是通过导入表定位关键代码

发现在sub_401000函数中出现了SHA1算法用到的常量

int __cdecl sub_401000(_DWORD *a1)
{
  int result; // eax

  result = 0;
  memset(a1 + 10, 0, 0x140u);
  a1[1] = 0;
  *a1 = 0;
  a1[2] = 0x67452301;
  a1[3] = -271733879;
  a1[4] = -1732584194;
  a1[5] = 271733878;
  a1[6] = -1009589776;
  return result;
}
_DWORD *__cdecl SHA1_update(_DWORD *a1, unsigned __int8 a2)
{
  _DWORD *result; // eax
  bool v3; // zf
  int v4; // ecx

  result = a1;
  a1[((*a1 >> 5) & 0xF) + 10] = a2 | (a1[((*a1 >> 5) & 0xF) + 10] << 8);
  v3 = *a1 == -8;
  *a1 += 8;
  if ( v3 )
  {
    v4 = a1[1];
    *a1 = 0;
    a1[1] = v4 + 1;
  }
  if ( (*a1 & 0x1FF) == 0 )
    result = (_DWORD *)sub_401090(a1);
  return result;
}
int __cdecl SHA1_Final(int *a1, int a2)
{
  int v2; // edi
  int v3; // ebx
  int i; // edi
  unsigned int v5; // eax

  v2 = *a1;
  v3 = a1[1];
  SHA1_update(a1, 0x80u);
  while ( (*a1 & 0x1FF) != 448 )
    SHA1_update(a1, 0);
  a1[24] = v3;
  a1[25] = v2;
  sub_401090(a1);
  for ( i = 0; i < 20; *(_BYTE *)(i + a2 - 1) = v5 )
  {
    v5 = (unsigned int)a1[i / 4 + 2] >> (24 - 8 * (i % 4));
    ++i;
  }
  return SHA1_init(a1);
}

还原

strcpy(aPEDIY, "PEDIY Forum");
strcpy(apediy, "pediy.com");
v11 = 0;
v12 = 0;
v13 = 0;
v14 = 0;
v15 = 0;
v16 = 0;
String1 = 0;
v17 = 0;
v1 = GetDlgItemTextA(hDlg, 1000, &name, 201);
if ( !v1 || GetDlgItemTextA(hDlg, 1001, &serial_number, 201) != 20 )
  goto LABEL_13;
SHA1_init(v34);
for ( i = 0; i < v1; ++i )
  SHA1_update(v34, *(&name + i));
SHA1_Final(v34, (int)sha1_digest);
for ( j = 0; j < 17; ++j )
  key[j] = sha1_digest[j] ^ aPEDIY[j];
for ( ; j < 20; aPEDIY[j + 11] = v4 )
{
  v4 = sha1_digest[j] ^ *((_BYTE *)&v9 + j + 23);// apeidy
  ++j;
}
v5 = 0;
v6 = &String1;
do
{
  v7 = key[v5 + 10] ^ key[v5];
  key[v5] = v7;
  wsprintfA(v6, "%02X", v7);
  ++v5;
  v6 += 2;
}
while ( v5 < 10 );
if ( !lstrcmpA(&String1, &serial_number) )
{
  SetDlgItemTextA(hDlg, 1001, success);
  result = 1;
}

注册机如下

from hashlib import sha1
 
name = b'admin'
digest = sha1(name).digest()
aPEDIY = b'PEDIY Forum'
apediy = b'pediy.com'
key = bytearray(digest)
for i in range(11):
    key[i] ^= aPEDIY[i]  // key[j] = sha1_digest[j] ^ aPEDIY[j];
for i in range(12,17):
    key[i] ^= key[i - 12] //或者 key[i] ^= 0 或者根本不要执行 ，感觉有点奇怪
for i in range(17,20):
    key[i] ^= apediy[i - 17]
        /*
        for ( ; j < 20; aPEDIY[j + 11] = v4 )
		{
  			v4 = sha1_digest[j] ^ *((_BYTE *)&v9 + j + 23);// apeidy
    		++j;
  		}
        */
serial_number = ''
for i in range(10):
    serial_number += hex(key[i] ^ key[i + 10])[2:].zfill(2).upper()
print(serial_number)

使用FindCrypt查看，发现是RIPEMD160和SHA1加密，之前好像见过