Hash

一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数，常用的哈希算法有MD5，SHA-1等等

(另一版本的解释,或许相对容易理解一些)

哈希（Hash）算法就是单向散列算法，它把某个较大的集合P映射到另一个较小的集合Q中，假如这个算法叫H，那么就有Q = H（P）。对于P中任何一个值p都有唯一确定的q与之对应，但是一个q可以对应多个p。作为一个有用的Hash算法，H还应该满足：H(p)速度比较快； 给出一个q，很难算出一个p满足q = H(p)；给出一个p1，很难算出一个不等于p1的p2使得 H(p1)=H(p2)。正因为有这样的特性，Hash算法经常被用来保存密码————这样不会泄露密码明文，又可以校验输入的密码是否正确。常用的 Hash算法有MD5、SHA1等。

MD5消息摘要算法（MD5 Message-Digest Algorithm）

一种被广泛使用的密码散列函数，可以产生出一个128位（16字节）的散列值（hash value），用于确保信息传输完整一致。MD5由美国密码学家罗纳德·李维斯特（RonaldLinn Rivest）设计，于1992年公开，用以取代MD4算法

 

破解Hash的任务就是，对于给出的一个q，反算出一个p来满足q = H(p)。通常我们能想到的两种办法，一种就是暴力破解法，把P中的每一个p都算一下H(p)，直到结果等于q；另一种办法是查表法，搞一个很大的数据 库，把每个p和对应的q都记录下来，按q做一下索引，到时候查一下就知道了。这两种办法理论上都是可以的，但是前一种可能需要海量的时间，后一种需要海量 的存储空间，以至于以目前的人类资源无法实现

正因为如此，我们一直都认为Hash是足够安全的，十几位的密码也是强度足够的，直到彩虹表的出现

 

彩虹表的根本原理就是组合了暴力法和查表法，并在这两者之中取得一个折中，用我们可以承受的时间和存储空间进行破解。它的做法是，对于一个Q = H（P），建立另一个算法R使得 P = R(Q)，然后对于一个p，这样进行计算：

p0 -H-> q1 -R->p1 -H-> q2 -R->p2 -H-> q3 -R->p3  … -H-> q(n-1) -R->p(n-1) -H-> qn -R->pn

简单的说，就是把q用H、R依次迭代运算，最后得到pn，n可能比较大。最后我们把p0和pn都存储下来，把其他的结果都丢弃。然后用不同的p0代入计算，得到多个这样的p的对子。

我们在做破解的时候，给出了一个q，我们来寻找p。我们先把q做一次R运算得到一个值例如叫c1，然后把c1和每一个p对的最后一个做比较，假如和某一个 pn相等，那么有可能这个pn所对应的p(n-1)就是我们在追寻的q，为了验证我们把pn对应的p0再做一次链式计算，比对qn是否就是给出的q，如果 是，很明显p(n-1)就是我们在追寻的p，因为 p(n-1) -H-> qn。如果不是就继续寻找直到遍历所有的q0qn对。

事情还刚刚开始，我们再算q -R-> c1 -H-> -R-> c2，再比对c2是否是qn，如果是，那么p(n-2)就可能是p；再算c3、c4直到c（n-1）

总的来说，就是用一个p0pn对来存储了一个链子的数据，如果n很大，就可以大大减小了存储的空间。这样带来的问题是必须做n次比对，时间更长，但是我们不需要瞬间破解，等待几秒乃至几天破解一个密码都是可以接受的

(Hash的部分解释以及彩虹表原理摘自https://www.cnblogs.com/bokun-wang/p/3887463.html)

 

接下来，根据哈希加密与彩虹表的基本知识进行彩虹表的攻防实验

 

首先我们使用任意一种语言(这里选用Python)，对特定的四位数字进行MD5加密，输出加密后的结果

 

然后我们开始构建彩虹表对其进行破解，这里我们使用给定的彩虹表生成工具RainbowCrack，生成破解四位数字组合MD5值的彩虹表，并对上文中的MD5字符串进行破解

生成彩虹表：

使用命令：rtgen md5 numeric 4 4 0 3000 400000  0

 

等待彩虹表生成完毕

 

 

彩虹表是一串彩虹链，每条彩虹链都有一个起点和一个终点。rtsort程序通过终点对彩虹链进行排序，使二进制搜索成为可能

运行以下命令对当前目录中的所有.rt彩虹表进行排序:

命令: rtsort .

 

注意，切勿中断rtsort程序; 否则被分类的彩虹表可能会被损坏，如果可用内存大小小于正在排序的彩虹表的大小，则需要与彩虹表大小一样大的临时硬盘空间来存储中间结果

对前文中的MD5密文进行彩虹表破解:

附命令示例，破解单个哈希:（.为彩虹表在当前目录的写法，不在当前目录直接写路径）

rcrack . -h MD5密文

rcrack_cuda . -h MD5密文

rcrack_cl . -h MD5密文

破解多个哈希：

rcrack . -l hash_list_file

rcrack_cuda . -l hash_list_file

rcrack_cl . -l hash_list_file

对于单个的哈希值，我们可以直接用rcrack.exe . -h hashnum来进行破解:

以’3839’为例:

MD5（3839） = 9b2f00f37307f2c2f372acafe55843f3

 

彩虹表攻击是高效的，但是存储彩虹表所要花费的代价也是高昂的，以MD5哈希算法为例，我们仅仅4位数字组合的彩虹表便用去了6M左右的空间，而10位小写字母与数字的组合便需要花费316GB的内存空间

但无论怎样，彩虹表在空间上的花销是一定要优于字典对的

 

通常，我们对彩虹表攻击的防御措施有两种：

①“加盐”: 彩虹表只能通过有限密码集合生成查找表——当密码集合扩大，彩虹表占用的空间将以指数速度增加。因此目前最常用的方式是将用户密码添加一段字符串（盐化）后再做散列。

        即: saltedhash(password) =hash(password+salt)

如果将用户密码后添加一段随机字符串，然后将随机字符串和散列后的哈希值存储在密码数据库中,彩虹表将不得不计算出盐化后的密码，而盐化后的密码会大大增加散列前的长度，从而使密码集合过大而变得不可能生成彩虹表。

  例如:我们直接在之前‘4529’的MD5值后面增加‘abcd’的盐值，试试能不能通过彩虹表破解

 

  不难看出，彩虹表无法破解该密文

 

②已知彩虹表是应用于主流的哈希算法的，那么通过对哈希算法进行修改，自然能够防御彩虹表破解。

  但这样存在某些隐患，例如，黑客可以将产品的算法通过逆向工程提取出来，通过算法生成特定的彩虹表。如果私有加密算法强度不够或是有设计缺陷的，届时密码破解将比使用彩虹表更加容易