MD5算法针对不定长的输入
MD5算法描述
MD5算法针对不定长的输入，可以输出固定128位长度的加密信息。MD5以512位来分组输入的信息，每一分组又被划分为16个32位子分组，经过算法流程最终生成四个32位数据联合成为128位的散列。算法的具体过程如下[4]：
（1）信息进行填充，使其位长对512求余的结果等于448。将信息的长度扩展至N*512+448，其中N为一个非负整数，N可以是零。填充的方法为在信息的后面填充一个1和无数个0，直到满足条件。
（2）在这个结果后面附加一个以64位二进制表示的填充前信息长度。经过这两步的处理，现在的信息的位长=N*512+448+64=(N+1)*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。MD5中有四个32位被称作链接变量（ChainingVariable）的整数参数，他们的初始值分别为：A=0×67452301，B=0xefcdab89，C=0x98badcfe，D=0×10325476。
（3）进入算法的四轮主循环运算。循环的次数是信息中512位信息分组的数目。主循环有四轮，每轮循环都很相似。第一轮进行16次操作。每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向左环移一个不定的数，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。
（4）经过四轮逐位运算完成之后，将A、B、C、D分别加上a、b、c、d。然后用下一分组数据继续运行算法，最后的输出是A、B、C和D的级联。
存在问题
虽然MD5为单向Hash加密，是不可逆的，但根据鸽巢原理，MD5算法所产生的32位输出所能够表示的空间大小为1632，即当样本大于1632≈3.4×1038时就会产生Hash碰撞。由这一结论可知，我们可以生成大量密码样本的哈希值，得到密码和哈希值的一一对应关系，然后根据这个对应关系反查就可以得到哈希值所对应的密码。但在破解密码的MD5值之前，我们需要预先计算出大量数据所对应的MD5值。
而在互联网应用方面，如果如文章开始所提出的问题一样，只是对用户密码进行简单MD5加密，是有可能通过查表入侵用户账户的（尽管密码可能不是用户的原始密码）。然而对于强密码来说，通过暴力穷举破解MD5值的代价也是相当大的。但根据统计结论[5]，有相当多的用户会使用弱密码[6]，因此可以根据统计规律建立简单密码所对应的MD5值表，从而入侵使用简单密码的用户账户。
改进方法
由于对于密码学Hash函数还需要的特性是具有雪崩效应，或者严格雪崩效应。其目标是对于输入任何小的改动将使输出变化很大。理想情况下改变任何输入所得到的输出结果都不相关，那么攻击者寻找碰撞就必须进行穷举搜索[1]。由于MD5算法的这一效应，我们可以在用户密码创建时生成一个随机字符串（称之为Salt，在另一个数据表或数据库中存储）与用户口令连接在一起，然后再用散列函数对这个字符串进行MD5加密，之后将MD5加密结果结果存入数据库中。如果Salt值的数目足够大的话，它实际上就消除了对常用口令采用的字典式攻击，因为黑客不可能在数据库中存储那么多Salt和用户密码组合后的MD5值。当然，如果黑客获得了数据库的所有信息（包括Salt表），他们仍可以对单个用户的密码进行暴力枚举破解。但将每个密码后加一随机串，无疑增加了暴力枚举的难度，且不存在弱口令的问题了。更加安全的做法是，我们可以给每个密码设置一个随机的Salt值，这样即使使用暴力枚举破解了一个用户的密码，也很难再破解其他用户的密码了。
除了给MD5算法加盐，其它的增强用户密码安全性的主动措施有使用更加耗时的加密算法，这样使破解的时间也大大增加了；或者更换更安全的加密算法如SHA-2算法；还可以像Twitter一样强制用户使用复杂密码等等。
结论
回到文章起始提出的问题，如果我的网站存有10万MD5密码的数据库落入了黑客手中，根据最近对CSDN密码泄露事件的统计规律：600万账号中有239万个账号和其它账号的密码相同[5]，进行最乐观的假设，假设这些账号使用的都是弱密码，且我们手中有所有这些弱密码所对应的明文信息，则约有40%的密码将被破解。对于文章起始处提出的问题来说，就是约4万名用户的密码将被破解。而进行较保守的假设，以CSDN事件中排名前10的弱密码为例，共有748350人使用了排名前10的弱密码，比例为0.1%，假设真实使用排名前1000的弱密码的人数为100*0.1%=10%，且我们手中有80%的弱密码所对应的明文信息，则对于文章起始处提出的问题来说，就是约8千名用户的密码将被破解。由此可见，只对用户密码进行简单的MD5加密并不能保证全部用户的密码安全，大约会有8000~40000名用户的密码将被查表破解。
（该估计方法存在一定问题：由于本人并未找到更好的基于真实情况的弱密码使用统计结论，且没有CSDN所泄露的数据库，只能以果壳网的数据为基准，并且由于国壳网所提供的数据量很小，估计方法也并不准确，只是进行粗略估计，最终结果只是一个定性结论。该问题还可以进行定量的后续研究。）
网友评论