彩虹表-如何暴力破解Md5

由于哈希算法的不可逆性，破解密码只能采取匹配加密结果的暴力破解方式，但是时间成本较高，如果构建一个明文和密码的键值对数据库，随着原始字符串的长度增加，密码库的大小将指数级增加，非人类资源可满足。

彩虹表算法是通过字典法的基础上进行改进，在时间和空间取得平衡点的一种算法。

彩虹表的前身–预先计算的散列链

何为预先计算的散列链

既然存储所有的明文密码对需要的空间太大，密码学家们想出了一种以计算时间降低存储空间的办法：“预计算的哈希链集”（Precomputed hash chains）。这是一条k=2哈希链：

H函数就是要破解的哈希函数。 R函数(约简函数reduction function是构建这条链的时候定义的一个函数：它的值域和定义域与H函数相反。通过该函数可以将哈希值约简为一个与原文相同格式的值。这条链是这样生成的：

随机选择一个明文aaaaaa
对其求哈希得到281DAF40
R(281DAF40) 得到另外一个明文sgfnyd。
继续重复2,3步骤存储的时候，不需要存储所有的节点，只需要存储每条链的头尾节点（这里是aaaaaa和kiebgt）

以大量的随机明文作为起节点，通过上述步骤计算出哈希链并将终节点进行储存，可得到一张哈希链集。

预先计算的散列链的使用

假设其刚好是920ECF10：首先对其进行一次R运算，得到kiebgt，然后发现刚好命中了哈希链集中的（aaaaaa,kiebgt）链条。可以确定其极大概率在这个链条中。于是从aaaaaa开始重复哈希链的计算过程，发现sgfnyd的哈希结果刚好是920ECF10,于是破解成功。
密文不是“920ECF10”而是“281DAF40”：第一次R运算后的结果并未在末节点中找到，则再重复一次H运算+R运算，这时又得到了末节点中的值“kiebgt”。于是再从头开始运算，可知aaaaaa刚好可哈希值为281DAF40。
如是重复了k（=2）次之后，仍然没有在末节点中找到对应的值，则破解失败。

预先计算的散列链的意义

对于一个长度为k的预计算的哈希链集，每次破解计算次数不超过k，因此比暴力破解大大节约时间。每条链只保存起节点和末节点，储存空间只需约1/k，因而大大节约了空间。

R函数的问题

要发挥预计算的哈希链集的左右，需要一个分布均匀的R函数。当出现碰撞时，就会出现下面这种情况 111 –H–> EDEDED –R–> 222 –H–> FEDEFE –R–> 333 –H–> FEFEDC –R–> 444 454 –H–> FEDECE –R–> 333 –H–> FEFEDC –R–> 444 -H–> FEGEDC –R–> 555

两条链出现了重叠。这两条哈希链能解密的明文数量就远小于理论上的明文数2×k。由于集合只保存链条的首末节点，因此这样的重复链条并不能被迅速地发现。

彩虹表的改进

彩虹表的出现，针对性的解决了R函数导致的链重叠问题：它在各步的运算中，并不使用统一的R函数，而是分别使用R1…Rk共k个不同的R函数（下划线表示下标）。

这样一来，即使发生碰撞，通常会是下面的情况： 111 –H–> EDEDED –R1–> 222 –H–> FEDEFE –R2–> 333 –H–> FEFEDC –R3–> 444 454 –H–> FEDECE –R1–> 333 –H–> FEFEDC –R2–> 474 -H–> FERFDC –R3–> 909 即使在极端情况下，两个链条同一序列位置上发生碰撞，导致后续链条完全一致，这样的链条也会因为末节点相同而检测出来，可以丢弃其中一条而不浪费存储空间。

防御彩虹表

加盐防御

彩虹表在生成的过程中，针对的是特定的函数H，H如果发生了改变，则已有的彩虹表数据就完全无法使用。如果每个用户都用一个不同的盐值，那么每个用户的H函数都不同，则必须要为每个用户都生成一个不同的彩虹表。大大提高了破解难度。

如何加盐

为每个明文生成不同随机数作为盐，加密时使用任意字符串拼接方式将明文和盐拼在一起，使加密算法对于不同明文串加密细节不同。而且，加盐同时可以提高密码长度，提高破解难度。

彩虹表