MD5为现在应用最广泛的Hash算法之一
本文作者为北师大的大三学生张俏，女Geek，在CSDN等各大网站的用户数据被泄露之后，她就MD5加密问题写下此文，发表了自己的看法，如果有读者想要跟作者进一步探讨，可以在新浪微博@阿豆拉。
MD5为现在应用最广泛的Hash算法之一，在1992年由MIT的RonaldL.Riverst提出，由MD4演化而来。该算法广泛应用于互联网网站的用户数据加密，能够将用户密码加密为128位的长整数。数据库并不明文存储用户密码，而是在用户登录时将输入密码字符串进行MD5加密，与数据库中所存储的MD5值匹配，从而降低密码数据库被盗取后用户损失的风险。
但由于Hash碰撞的存在，MD5加密的数据并不安全，可以由生成相同Hash值的字符串破解，所以提出了加入随机数salt的MD5加密方法，一定程度上增大了字典攻击的难度。
问题提出
前一阵在新浪微博上，有一个人发布了这样一条微博：“出道互联网安全常识数学题……假设你的网站所有用户密码都是md5加密（单向散列，非可逆）的，假设你网站有10万会员，如果你的用户库丢了，会有多少会员密码被破解？想想看。”当时我的一位朋友认为10万个密码全部都会被破解，我却不这样认为，因为根据我的先验知识：
（1）MD5加密算法在互联网应用中广泛被使用，MD5不是简单的古典加密算法，不能通过逆向Decrypt解密，只能通过Hash碰撞破解（Hack）；
（2）我曾经看过对同一个字符串进行MD5加密的结果，产生结果是随机的字符串（后来经过查找资料发现我所看到的不是简单的MD5加密，而是加盐后的结果）；
（3）MD5用作密码加密算法并不是绝对安全的，因为可能产生Hash碰撞，简单密码的MD5加密可以通过彩虹表查找到；
（4）我曾见过几个破解MD5加密的网站（http://www.cmd5.com/），大多数的做法是先免费为用户暴力破解，积累起足够的数据库可以破解简单密码后，解密服务便开始收费，所以MD5密码的破解不应该那么简单。
在经过对这个问题激烈的讨论过后，没过多久便发生了CSDN的数据库泄露事件，600万条数据库记录被任意传播。紧接着天涯论坛的数据库也泄露了，2000万条数据库记录被证实几乎均可以登录。而这两个网站的数据库中所保存的用户密码都没有经过加密，即为明文存储的。这种事情的发生更加证实了对网站数据库中所保存的用户密码进行加密的重要性。
现今流行的对用户密码加密算法中，MD5加密是最为广泛使用的算法之一。
背景知识
对于散列函数h(x)，必须满足下列特性[1]：
压缩：对于给定输入x，输出长度y=h(x)很小；
效率：对于给定输入x，计算y=h(x)很容易；
单向：该散列函数H是一个单向函数，即对于几乎所有的x，已知H(x)的值y求x是不可行的；
弱无碰撞：已知x，求出x’使得H(x’)==H(x)在计算上是不可行的；
强无碰撞：对于任意x≠x’，H(x’)==H(x)在计算上是不可行的。
MD5的全称是Message-DigestAlgorithm5，在1991年由MIT的RonaldL.Riverst提出，由MD4演化而来，最终生成128位（4个32位的16进制数）的信息摘要算法。[2]MD5算法是一个不可逆的字符串变换算法，即看到源程序和算法描述，也无法将一个MD5的值变换回原始的字符串。
1993年，DenBoer和Bosselaers给出了一个有限的“伪碰撞”结果；
1996年，MD5算法的设计被发现有缺陷，虽然当时并未被证明该缺陷是致命的，密码学专家建议使用其它加密算法（如SHA-1）。
2004年，MD5算法被证明不安全，原因是会产生Hash碰撞。[3]
2007年，研究人员发现使用Chosen-prefixCollision方法，可以使包含恶意代码的程序产生合法的MD5值。
2008年，研究人员发现了产生相同MD5Hash值的两个可执行文件。
以上实例证明，MD5算法的安全性并不高，不能应用于对安全性要求很高的SSL加密及数字签名之中。目前最被推荐的Hash加密算法应为SHA-2加密算法。
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所泄露的数据库，只能以果壳网的数据为基准，并且由于国壳网所提供的数据量很小，估计方法也并不准确，只是进行粗略估计，最终结果只是一个定性结论。该问题还可以进行定量的后续研究。）
网友评论