以前一直以为彩虹表就是一个大的数据库,破解的时候直接通过查表获得明文。今天发现我错了,彩虹表的原理还是挺有趣的。

如果直接暴力破解 Hash 的明文太费时,如果通过查表的方法则太耗存储。彩虹表则是暴力破解与查表破解的折中。

原理

假设有这么一个函数R,可以将 Hash 值转化与字符串(非明文,而是另一个字符串),称其为衰减函数。假设p为明文,h为明文的 Hash 值,H为 Hash 函数。彩虹表在建表时,先选一个p[0],做如下计算:

h[0] = H(p[0])
p[1] = R(h[0])
h[1] = H(p[1])
...
h[k]  = H(p[k])
...
h[n - 1] = H(p[n - 1])
p[n] = R(h[n - 1])

其中n为迭代的次数。

经过,这种运算之后,会形成一条 Hash 链:

p[0]--->h[0]--->p[1]--->...--->p[k]--->h[k]--->...--->p[n]

这条链上已经有n对明文到 Hash 值的对应关系了,但我们只保存首尾p[0]p[n],因为中间的值可以用p[0]重新通过上述的计算运算出来。

彩虹表中有好多条这样的链p[0]-->p[n]n值取足够大。这样就可以用p[0]p[n]的存储空间,存储n对的明文到 Hash 值的对应关系。

破解

假设待破解的 Hash 值为h',那么我们可以反复地迭代运算 p' = R(h'), h‘= H(p'),直到p'与彩虹表中的某个p[n]相等。

该链为p[0]-->p[n],那么h'的明文很有可能在这条链中,因为这条链是通过p[0]反复迭代得到p[n]的,h'也是通过反复迭代得到p[n]

我们只要知道h'迭代到p[n]的次数,只在找到链中迭代到p[n]相同次数的h[k],就可以获得其明文p[k](在链中,h[k] = H(p[k]))。