项目中遇到一次使用MD5的数据安全风险,发现很多同学不明白为什么MD5有泄露用户信息风险,故而分享一下
MD5全称为 消息摘要算法版本5 （Message Digest Algorithm 5）
是一种Hash算法,MD5 算法把任意长度的原始数据映射成128 bit 的数据。
所以Hash算法有两个特性:①会损失部分信息,所以算法不可逆.②因为将大范围的原值映射到小范围Hash值,所以有碰撞.
因为不可逆,所以攻击者只能通过暴力攻击的方法来破解Hash值.
之前我以为Rainbow-Tables只是一个漂亮的名字,实际就是一张保存了Hash密文-->明文 的一张大表,破解时通过Hash密文查到明文.
直到有一天了解了彩虹表的细节,才发现原理是一个巧妙的time-memory trade-off.在时间和空间之中找到一个平衡.
彩虹表的前身: “预计算的哈希链集”（Precomputed hash chains）:
当面对要破解的哈希函数H，首先要定义一个约简函数（reduction function）R，该函数的定义域和值域 需要和Hash函数相反，通过该函数可以将哈希值约简为一个与原文相同格式的值。 需要强调的是，由于哈希函数H是不可逆的，所以对于密文进行R运算几乎不可能得到明文原文。
6位字母明文“anjuke”进行H运算后得到了“D2A82C9A”，而对“D2A82C9A”进行R运算后得到另一个6位字母格式的值“abcdef”。因为这个值落在H的定义域中，因此可以对它继续进行H运算。将H运算、R运算、H运算……这个过程反复地重复下去，重复一个特定的次数k以后，就得到一条 哈希链，例如k为2时得到：
anjuke --H--> D2A82C9A --R--> abcdef --H--> E2E111ZX --R--> zombie
这条链条并不需要完整地保存下来，只需要保存其起节点和末节点即可，例如上例中只需要保存起节点 “anjuke”和末节点“zombie”。以大量的随机明文作为起节点，通过上述步骤计算出哈希链并将终节点进行储存，即可得到一张哈希链集。
这张表每一组明文,只需要保留起节点和末节点.每条链可以保存K个原值。
这张集合需要如何使用呢？
例如，我们知道哈希运算后的密文为“E2E111ZX”，则先对其进行一次R运算，得到“zombie”。 正巧在本例中，它等于集合中的一个末节点，因此我们可以猜测，明文有极大的可能存在于以起节点“anjuke”开头、末节点“zombie”结尾的这条哈希链中。（注意可能性并不是100%，因为函数H和R均有可能发生碰撞，从不同的输入值得到相同的输出值。）
为了验证我们的猜测，可以从起节点“anjuke”开始重复哈希链的计算过程： 算到这里我们发现，“abcdef”进行哈希运算的结果正是密文“E2E111ZX ”，这样就找到了所需的明文。
如果密文不是“E2E111ZX”而是“D2A82C9A”，第一次R运算后的结果并未在末节点中找到，则再重复 一次H运算+R运算，这时又得到了末节点中的值“zombie”，则我们还是从起节点“anjuke”开始计算，这 次可得到“D2A82C9A”对应的明文为“anjuke”。
如果如是重复了k（=2）次之后，仍然没有在末节点中找到对应的值，则可以断定，所需的明文不在这张集合中。
R函数
在构造哈希链的时候，需要一个好的R函数。首先R需要能将值域限定H函数的定义域内。其次R也应该和H函数一样,尽量保证输出均匀,减少碰撞概率。实际上很难找到完美的R，经常会发生碰撞。如下
anjuke --H--> D2A82C9A --R--> abcdef --H--> E2E111ZX --R--> zombie --H--> Y9USCHO1 --R--> yiersa
youger--H--> E22Q8CO8 --R--> poiuyt--H--> A02UR7Z --R-->abcdef --H--> E2E111ZX --R--> zombie
加粗的部分，所涉及到的明文是完全重复的，因此这两条哈希链能解密的明文数量就远小于理论上的 明文数2×k。由于集合只保存链条的首末节点，因此这样的重复链条并不能被迅速地发现。重复链条会逐渐造成严重的冗余和浪费。
Rainbow-Tables
对于这个问题，2003年提出的彩虹表算法进行了针对性的改进。它在各步的运算中，并不使用统一的R函数，而是分别使用R1…Rk共k个不同的R函数.这样一来，如果发生碰撞，通常会是如下情况:
当两个链条发生碰撞的位置并非相同的序列位置时，后续的R函数的不一致使得链条的后续部分也不相同，从而最大程度地减小了链条中的重复节点，保证了链条的有效性。
同时，如果在极端情况下，两个链条在同一序列位置上发生碰撞，导致后续链条完全一致，这 样的链条也会因为末节点相同而检测出来，可以丢弃其中一条而不浪费存储空间。
彩虹表的使用比哈希链集稍微麻烦一些。首先，假设要破解的密文位于任一链条的k-1位置处，对其进行Rk运算，看是否能够在末节点中找到对应的值。如果找到，则可以如前所述，使用起节点验证其正确性。否则，需要继续假设密文位于k-2位置处，这时就需要进行Rk-1、H、Rk两步运算，然后在末节点中查找结果。如是反复，最不利条件下需要将密文进行完整的R1、H、…Rk运算后，才能得知密文是否存在于彩虹表之中。
时间和空间的平衡
上例一条链包含了三个原值,原值为C时计算次数最小,R3(密文) =D,R2(H(R1(H(A)))) =C ,需要5次计算,1次查表.
原值为B时,需要R3(密文)-->查表 -->R3(H(R2(密文))) -->查表,R1(H(A)) =B,需要6次计算,2次查表.
原值为A时,需要R3(密文)-->查表 -->R3(H(R2(密文))) -->查表 --> R3(H(R2(H(R1(密文))))) --> 查表,需要9次计算,3次查表.
当原值为k链中倒数第n个时,时间为:(1+3+5...+(2n+1)) * H + 2(K-n) * H + n * g = 2(n²+k) * H + n * g
平均时间为:(1/6 * (k+1)(2k+1) +2k) * H + (1+k)/2 * g
防御: 提高暴力破解的难度
①加盐(salt)
Hash(原值),只需知道Hash函数,如果是常用的Hash函数,则用已有的彩虹表破解即可.
Hash(原值+盐值),加盐值后,攻击的门槛变高了,需要知道Hash函数,盐值,原值+盐值重新生成彩虹表.
②提高Hash函数的计算难度
比如Hash函数设计为对原值计算100次MD5,生成彩虹表的计算代价就提高了100倍.
设计一个内存使用很高的Hash函数.让内存访问速度变成瓶颈,更加拖慢了生成彩虹表的时间.例如Scrypt算法.
对比Scrypt与MD5来说明Scrypt如何提高了内存的使用
MD5算法步骤:
①补位:首先将原始数据补位,最终的位数对512求模的结果为448.再将一个表示数据原始长度的64 bit数补再最后,结果数据长度正好是512的整数倍.
②初始化4个32位的寄存器
③定义4个非线性函数F、G、H、I.每512位做4轮处理,每次输入都是寄存器中的中间结果+当前512位为输入.
④读完即输出
Scrypt
具体思想大概是:要求计算时,需要保存一个足够大的数组.
第一位是你要加密的原文作为seed(比如是你的手机号),后面每一位都是前一位的Hash.
第一次取出固定Index的值,取出值后再做另一个Hash,得到下一次需要的Index,然后再做Hash找下一个Index.
取出N个Hash值后,再合在一起取Hash.
这样需要保留一个数组,而且需要多次访问内存.
如果不保留数组的话,每次取数还得重新计算一次数组,计算复杂度直线增加.
REFERENCE:
https://www.zhihu.com/question/19790488/answer/19290308
