彩虹表

彩虹表

1.定义：

彩虹表（Rainbow Table）是一种破解哈希算法的技术，是一款跨平台密码攻击手段，主要可以破解MD5、HASH等多种密码。它的性能非常让人震惊，在一台普通PC上辅以NVidia CUDA技术，对于NTLM算法可以达到最高每秒103,820,000,000次明文尝试（超过一千亿次），对于广泛使用的MD5也接近一千亿次。更神奇的是，彩虹表技术并非针对某种哈希算法的漏洞进行攻击，而是类似暴力破解，对于任何哈希算法都有效。

2.原理：

首先定义哈希加密函数H，Q=H(P)表示将明文密码P加密成哈希串Q；然后定义规约函数R，p=R(Q)表示将哈希串Q转换成明文p，注意p不是真正的密码P。将一个可能的密码p0交替带入H和Q两个函数进行运算，先后得到q1，p1，q2，p2，...，q(n-1)，p(n-1)，qn，pn。其中p是明文，q是哈希串，它们组成的链称为哈希链，n是哈希链的长度，一般大于2000。将哈希链的首尾元素p0和pn做为一个数对存入表中，中间的其它元素全部删除。由多个数对组成的表称为彩虹表。

示例图：

3.密码攻击：

密码攻击就是找到哈希串Q对应的明文密码P，利用彩虹表进行密码攻击的过程如下：c1=R(Q)，将c1与彩虹表中每一个pn进行比对，如果相等，则P=p(n-1)，由于彩虹表中只保存了p0和pn，因此需要重新计算该哈希链得到p(n-1)；如果没找到相等的pn，计算c2=R(H(c1))，将c2与彩虹表中所有pn进行比对，如果相等，则P=p(n-2)，重新计算该哈希链得到p(n-2)；如果没找到相等的pn，继续计算c3...以此类推。

彩虹表的关键是构造R函数，优秀的R函数要保证计算结果均匀分布，即避免出现相同的明文密码。然而想构造优秀的R函数是件非常困难的事，不同的哈希链中可能会出现大量的重复数据，严重影响了密码攻击的效率。改良后的彩虹表在哈希链的计算过程中引入不同的R函数，有效减少不同哈希链中的重复节点，进一步提高了攻击效率。如果将不同的R函数用不同的颜色表示，众多的哈希链就会像彩虹一样，从里到外呈现出颜色变化，这就是彩虹表名称的由来。

4.防御彩虹表攻击：

虽然彩虹表有着如此惊人的破解效率，但网站的安全人员仍然有办法防御彩虹表。最有效的方法就是“加盐”，即在密码的特定位置插入特定的字符串，这个特定字符串就是“盐”，加盐后的密码经过哈希加密得到的哈希串与加盐前的哈希串完全不同，黑客用彩虹表得到的密码根本就不是真正的密码。即使黑客知道了“盐”的内容、加盐的位置，还需要对H函数和R函数进行修改，彩虹表也需要重新生成，因此加盐能大大增加利用彩虹表攻击的难度。