密码破解的利器.docx

《密码破解的利器.docx》由会员分享，可在线阅读，更多相关《密码破解的利器.docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、密码破解的利器彩虹表(rainbow table )目录： 如何存储密码才是安全的？ 彩虹表不是密码- 明文的简单存储 彩虹表的前身-预先计算的散列链 彩虹表 为什么加盐哈希可以抵御彩虹表如何存储密码才是安全的?密码存储有几种方式： 直接存储密码明文m 存储密码明文的哈希值hash(m)存储密码明文的加盐哈希hash(m+salt),这里的salt可以是用户名，手机号等， 但必须保证每个用户的salt都不一样才是安全的。如果数据库被入侵。第一方式，明文存储，无安全性可言。第二种方式，虽然是入侵者得到的是hash值，但由于彩虹表的存在，也很容易批量还原 出密码明文来。只有第三种方式才是相对安全的

2、。彩虹表不是密码，明文的简单存储要从c=hash(m)逆向得到原始明文m,有三种方法: 暴力破解法：时间本钱太高。 字典法：提前构建一个“明文，密文”对应关系的一个大型数据库，破解时通过 密文直接反查明文。但存储一个这样的数据库，空间本钱是惊人的。 构建彩虹表：在字典法的基础上改进，以时间换空间。是现在破解哈希常用的 方法。彩虹表的前身预先计算的散列链既然存储所有的明文密码对需要的空间太大，密码学家们想出了一种以计算时间降低存储空间的方法：”预计算的哈希链集(Precomputed hash chains)。这是一条k=2哈希链：aaaaaa 281DAF4O sgfnyd 920ECF10

3、kiebgtHRHR哈希链H函数就是要破解的哈希函数。约简函数(reduction funclion) R函数是构建这条链的时候定义的一个函数：它的值域和定义域与H函数相反。通过该函数可以将哈希值约简为一个与原文相同格式的值。这条链是这样生成的： 随机选择一个明文aaaaaa 对其求哈希得到28IDAF40 RQ8IDAF40)得到另外一个明文sgfnydo 继续重复2,3步骤存储的时候，不需要存储所有的节点，只需要存储每条链的头尾节点(这里是aaaaaa 和 kiebgt)以大量的随机明文作为起节点，通过上述步骤计算出哈希链并将终节点进行储存，可得到 一张哈希链集。预计算的哈希链集的使用要破

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

5、应的值，那么破解失 败。预计算的哈希链集的意义对于一个长度为k的预计算的哈希链集，每次破解计算次数不超过k,因此比暴力破解大 大节约时间。每条链只保存起节点和末节点，储存空间只需约1/k,因而大大节约了空间。R函数的问题要发挥预计算的哈希链集的左右，需要一个分布均匀的R函数。当出现碰撞时，就会出 现下面这种情况111 -H- EDEDED -R- 222 -H- FEDEFE -R- 333 -H- FEFEDC -R- 444454 -H- FEDECE -R- 333 -H- FEFEDC -R- 444 -H- FEGEDC -R- 555两条链出现了重叠。这两条哈希链能解密的明文数量就

6、远小于理论上的明文数2xk。由于 集合只保存链条的首末节点，因此这样的重复链条并不能被迅速地发现。彩虹表彩虹表的出现，针对性的解决了 R函数导致的链重叠问题：它在各步的运算中，并不使用统一的R函数，而是分别使用RL.Rk共k个不同的R函数 （下划线表示下标）。w ik ipedia ； CZ! ao4k d J ! s ecretH、仪 r彳 H、/R r?,-% H ._一 I弋】一, abcdefgh ；E=(yn6sbemie，, H，一 Iq2 ，：=： kols1 / 小Zurich H Ri .8mpy ：=：my name passwd ：E( dlcrnl c-：culture

7、Rl :L. linuxZ39kpmwjimbo :vOcftxrootroot彩虹表这样一来，及时发生碰撞，通常会是下面的情况：111 -H- EDEDED -Rl- 222 -H- FEDEFE -R2- 333 -H- FEFEDC -R3- 444454 -H- FEDECE -Rl- 333 -H- FEFEDC -R2- 474 -H- FERFDC -R3- 909即使在极端情况下，两个链条同一序列位置上发生碰撞，导致后续链条完全一致，这样的 链条也会因为末节点相同而检测出来，可以丢弃其中一条而不浪费存储空间。彩虹表的使用比哈希链集稍微麻烦一些。 首先，假设要破解的密文位于某一链

8、条的k-1位置处，对其进行Rk运算，看是 否能够在末节点中找到对应的值。如果找到，那么可以如前所述，使用起节点验 证其正确性。 否那么，继续假设密文位于k-2位置处，这时就需要进行Rk-1、H、Rk两步运 算，然后在末节点中查找结果。 如是反复，最不利条件下需要将密文进行完整的RI、H、Rk运算后，才能得知密文是否存在于彩虹表之中。彩虹表中时间、空间的平衡对于哈希链集，最大计算次数为k,平均计算次数为k/2彩虹表的最大计算次数为1+2+3+k = k(k-l)/2,平均计算次数为(k+2)*(k+l)/6。可见，要解相同个数的明文，彩虹表的代价会高于哈希链集。无论哈希链集还是彩虹表：当k越大时，破解时间就越长，但彩虹表所占用的空间就越小；相反，k越小时，彩虹表本身就越大，相应的破解时间就越短。常见的彩虹表和R函数举例1)常见的彩虹表： :projcct-rainbowcrack /tablc.htm2) R函数举例：假设明文为5位数字，那么R函数是取哈希值中前5个数字。参见 hltps: 为什么加盐哈希可以抵御彩虹表彩虹表在生成的过程中，针对的是特定的函数H, H如果发生了改变，那么已有的彩虹表数 据就完全无法使用。如果每个用户都用一个不同的盐值，那么每个用户的H函数都不同，那么必须要为每个用 户都生成一个不同的彩虹表。大大提高了破解难度。