今天我删了我硬盘上的1.6TB彩虹表，那可是我下载了一整个星期才下来的。删的原因也很简单，第一，用不上，第二，我的彩虹表是针对MD5的且只能破解1-8位大小写字母数字符号组合与1-10位小写字母数字组合，到了现在已经不适用且很多人已经不单纯用MD5了。第三，磁盘空间不够了。
但是，虽然没用过这个表去破解什么，却懂得了如何设置密码才更安全。在无良网站继续使用MD5加密作为用户密码的存储方式时，你可以自己设置更长更复杂的密码来防止别人破解。更重要的是，彩虹表构建的这种思想是很值得借鉴的，虽然不知道以后什么地方会用上。
在彩虹表之前，很多人都想到了用空间换时间的方法，即将密码明文与相应的MD5加密密文作为一对数据，存起来，然后去查找密文，找到后即可知明文，我们把这个表格又称作字典，因为这个过程就和查字典类似，把这个方法叫做查表法。比如imnotfat的MD5加密是5f79d94eb5055db9b31e42795b62d65b，若在字典中找到5f79d94eb5055db9b31e42795b62d65b，即可知道其明文为imnotfat。但是，对于制作这样的字典来说，简直是不可能的，因为假设我们的明文是10位的，那么每一位都可能是26个大写字母中的一个，或26个小写字母中的一个，或10个数字中的一个，或n多符号中的一个（暂且算10个常用符号），这个可能性大概是(26*2+10+10)^10，结果是72的10次方，也就是3,743,906,242,624,487,424是374亿亿。目前存储这么大的字典和查找都不太现实，所以查表法不适用。
还有一种经典方法是枚举法，即一个一个的试，从1位密码试到10位甚至更多位，把结果和密文对比，目前计算机能力有限，这个方法也不怎么好用，或者说有时候根本不管用。
而彩虹表的思想就是，平衡这两种方法。先自造一个Rx函数集，然后用H函数也就是是加密函数对一个明文加密，再用R1对密文进行进一步的变换，生成新明文，然后把所得的明文再通过H函数加密生成密文，密文再通过R2函数变换为新明文，新明文再通过H变为密文，如此反复就形成了一条链，这条链可以非常的长，比如几十万条，而最后我们只记录第一个明文和最后一个明文，中间的我们不管。啥？中间那么长的都不管了？是的，我们只需要知道我们的这个变换函数Rx的集合即可，其间的所有明文密文都可以经过计算得到。在查找的时候，只需要先用Rx对密文进行变换，然后去找字典里是否有对应项，若没有，继续使用Rx-1, H, Rx对密文进行变换，再查字典，若还没有则使用Rx-2,H, Rx-1, H, Rx对密文进行变换，再查。直到查到有匹配的，当发现匹配后，反推即可知道密文对应之明文。
下面我说个简单的例子，这里我们只有3条记录，绿色（如果你们看到的都是红色请火速联系我），蓝色，粉色，每条记录里有3个明文（可为原始密码），3个密文和1个最终结果（也是明文但不可为原始密码）。我们有3个变换函数R1, R2和R3，还有1个加密函数H。最终存储的实际只是wikipedia->rootroot. abcdefgh->myname, passwd->linux23这3条记录，中间的都省了。
比如我们要查找密文kolscx对应的明文，我们先假设kolscx是某条记录中最后一个密文，对kolscx做R3变换，假设kolscx的R3变换结果是iamthin，那么通过对比3条记录的结果，发现iamthin并不在rootroot, myname, linux23之中，所以kolscx应该不是某条记录中的最后的一个密文，那么再假设可能是某条记录中倒数第二个密文，所以我们对kolscx做R2, H, R3变换，结果得到了myname，发现在rootroot, myname, linux23之中，那么我们就知道了kolscx是在第二条记录即abcdefgh->myname中通过R2, H, R3变换得来。那么在此记录中，我们没有做的变换即R1变换，我们对原始数据abcdefgh进行H, R1变换即可得到kolscx所对应的明文bernie。这就是彩虹表查找的过程。而Rx函数的选取是大有学问的，搞不好就会让某些明文重复而导致查找失败，这里我不懂所以也不多谈了。
我个人非常欣赏这个算法，因为Rx函数的引入，使存储的数据量急剧减少，这多少有点稀疏表示与压缩感知的意思（强行装个逼）。搜索也非常有针对性，通过计算评估最终值，即使是几十万条的函数计算也很现实，当初始值最终值字典被索引后，查表动作应该会非常省时。
这就是我个人理解的彩虹表，希望对不懂彩虹表的同学有所启发，如果不对还请忽略。
Be First to Comment