MD5加密算法在网站数据库安全方面的应用与查表攻击

     <div id="news_body">     <p> 编者按：本文作者为北师大的大三学生张俏，女 Geek，在 CSDN 等各大网站的用户数据被泄露之后，她就 MD5 加密问题写下此文，发表了自己的看法，如果有读者想要跟作者进一步探讨，可以在新浪微博<a href="/misc/goto?guid=4958322431386437461">@阿豆拉</a>。</p>     <p> MD5为现在应用最广泛的 Hash 算法之一，在 1992 年由 MIT 的 Ronald L. Riverst 提出，由 MD4 演化而来。该算法广泛应用于互联网网站的用户数据加密，能够将用户密码加密为 128 位的长整数。数据库并不明文存储用户密码，而是在用户登录时将输入密码字符串进行 MD5 加密，与数据库中所存储的 MD5 值匹配，从而降低密码数据库被盗取后用户损失的风险。</p>     <p> 但由于 Hash 碰撞的存在，MD5加密的数据并不安全，可以由生成相同 Hash 值的字符串破解，所以提出了加入随机数 salt 的 MD5 加密方法，一定程度上增大了字典攻击的难度。</p>     <p> <strong>问题提出</strong></p>     <p> 前一阵在新浪微博上，有一个人发布了这样一条微博：“<em>出道互联网安全常识数学题</em><em>……</em><em>假设你的网站所有用户密码都是</em><em>md5</em><em>加密（单向散列，非可逆）的，假设你网站有</em><em>10</em><em>万会员，如果你的用户库丢了，会有多少会员密码被破解？想想看。</em>”当时我的一位朋友认为 10 万个密码全部都会被破解，我却不这样认为，因为根据我的先验知识：</p>     <p> （1）    MD5 加密算法在互联网应用中广泛被使用，MD5不是简单的古典加密算法，不能通过逆向 Decrypt 解密，只能通过 Hash 碰撞破解（Hack）；</p>     <p> （2）    我曾经看过对同一个字符串进行 MD5 加密的结果，产生结果是随机的字符串（后来经过查找资料发现我所看到的不是简单的 MD5 加密，而是加盐后的结果）；</p>     <p> （3）    MD5 用作密码加密算法并不是绝对安全的，因为可能产生 Hash 碰撞，简单密码的 MD5 加密可以通过彩虹表查找到；</p>     <p> （4）    我曾见过几个破解 MD5 加密的网站（<a href="/misc/goto?guid=4958322432196113956">http://www.cmd5.com/</a>），大多数的做法是先免费为用户暴力破解，积累起足够的数据库可以破解简单密码后，解密服务便开始收费，所以 MD5 密码的破解不应该那么简单。</p>     <p> 在经过对这个问题激烈的讨论过后，没过多久便发生了 CSDN 的数据库泄露事件，600万条数据库记录被任意传播。紧接着天涯论坛的数据库也泄露了，2000万条数据库记录被证实几乎均可以登录。而这两个网站的数据库中所保存的用户密码都没有经过加密，即为明文存储的。这种事情的发生更加证实了对网站数据库中所保存的用户密码进行加密的重要性。</p>     <p> 现今流行的对用户密码加密算法中，MD5加密是最为广泛使用的算法之一。</p>     <p> <strong>背景知识</strong></p>     <p> 对于散列函数h(x)，必须满足下列特性<sup>[1]</sup>：</p>     <ol>      <li>压缩：对于给定输入x，输出长度y=h(x)很小；</li>      <li>效率：对于给定输入x，计算y=h(x)很容易；</li>      <li>单向：该散列函数H是一个单向函数，即对于几乎所有的x，已知H(x)的值y求x是不可行的；</li>      <li>弱无碰撞：已知x，求出x’使得H(x’)==H(x)在计算上是不可行的；</li>      <li>强无碰撞：对于任意x≠x’，H(x’)==H(x)在计算上是不可行的。</li>     </ol>     <p> MD5的全称是 Message-Digest Algorithm 5，在 1991 年由 MIT 的 Ronald L. Riverst 提出，由 MD4 演化而来，最终生成 128 位（4个 32 位的 16 进制数）的信息摘要算法。<sup>[2] </sup>MD5算法是一个不可逆的字符串变换算法，即看到源程序和算法描述，也无法将一个 MD5 的值变换回原始的字符串。</p>     <p> 1993年，Den Boer 和 Bosselaers 给出了一个有限的“伪碰撞”结果；</p>     <p> 1996年，MD5算法的设计被发现有缺陷，虽然当时并未被证明该缺陷是致命的，密码学专家建议使用其它加密算法（如 SHA-1）。</p>     <p> 2004年，MD5算法被证明不安全，原因是会产生 Hash 碰撞。<sup>[3]</sup></p>     <p> 2007年，研究人员发现使用 Chosen-prefix Collision 方法，可以使包含恶意代码的程序产生合法的 MD5 值。</p>     <p> 2008年，研究人员发现了产生相同 MD5 Hash 值的两个可执行文件。</p>     <p> 以上实例证明，MD5算法的安全性并不高，不能应用于对安全性要求很高的 SSL 加密及数字签名之中。目前最被推荐的 Hash 加密算法应为 SHA-2加密算法。</p>     <p> <strong>MD5算法描述</strong></p>     <p> MD5算法针对不定长的输入，可以输出固定 128 位长度的加密信息。MD5以 512 位来分组输入的信息，每一分组又被划分为 16 个 32 位子分组，经过算法流程最终生成四个 32 位数据联合成为 128 位的散列。算法的具体过程如下<sup>[4]</sup>：</p>     <p> （1）信息进行填充，使其位长对 512 求余的结果等于 448。将信息的长度扩展至N*512+448，其中N为一个非负整数，N可以是零。填充的方法为在信息的后面填充一个 1 和无数个0，直到满足条件。</p>     <p> （2）在这个结果后面附加一个以 64 位二进制表示的填充前信息长度。经过这两步的处理，现在的信息的位长=N*512+448+64=(N+1)*512，即长度恰好是 512 的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。MD5中有四个 32 位被称作链接变量（Chaining Variable）的整数参数，他们的初始值分别为：A=0×67452301，B=0xefcdab89，C=0x98badcfe，D=0×10325476。</p>     <p> （3）进入算法的四轮主循环运算。循环的次数是信息中 512 位信息分组的数目。主循环有四轮，每轮循环都很相似。第一轮进行 16 次操作。每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向左环移一个不定的数，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。</p>     <p> （4）经过四轮逐位运算完成之后，将A、B、C、D分别加上a、b、c、d。然后用下一分组数据继续运行算法，最后的输出是A、B、C和D的级联。</p>     <p> <strong>存在问题</strong></p>     <p> 虽然 MD5 为单向 Hash 加密，是不可逆的，但根据鸽巢原理，MD5算法所产生的 32 位输出所能够表示的空间大小为 16<sup>32</sup>，即当样本大于 16<sup>32</sup>≈3.4 × 10<sup>38</sup>时就会产生 Hash 碰撞。由这一结论可知，我们可以生成大量密码样本的哈希值，得到密码和哈希值的一一对应关系，然后根据这个对应关系反查就可以得到哈希值所对应的密码。但在破解密码的 MD5 值之前，我们需要预先计算出大量数据所对应的 MD5 值。</p>     <p> 而在互联网应用方面，如果如文章开始所提出的问题一样，只是对用户密码进行简单 MD5 加密，是有可能通过查表入侵用户账户的（尽管密码可能不是用户的原始密码）。然而对于强密码来说，通过暴力穷举破解 MD5 值的代价也是相当大的。但根据统计结论<sup>[5]</sup>，有相当多的用户会使用弱密码<sup>[6]</sup>，因此可以根据统计规律建立简单密码所对应的 MD5 值表，从而入侵使用简单密码的用户账户。</p>     <p> <strong>改进方法</strong></p>     <p> 由于对于密码学 Hash 函数还需要的特性是具有雪崩效应，或者严格雪崩效应。其目标是对于输入任何小的改动将使输出变化很大。理想情况下改变任何输入所得到的输出结果都不相关，那么攻击者寻找碰撞就必须进行穷举搜索<sup>[1]</sup>。由于 MD5 算法的这一效应，我们可以在用户密码创建时生成一个随机字符串（称之为 Salt，在另一个数据表或数据库中存储）与用户口令连接在一起，然后再用散列函数对这个字符串进行 MD5 加密，之后将 MD5 加密结果结果存入数据库中。如果 Salt 值的数目足够大的话，它实际上就消除了对常用口令采用的字典式攻击，因为黑客不可能在数据库中存储那么多 Salt 和用户密码组合后的 MD5 值。当然，如果黑客获得了数据库的所有信息（包括 Salt 表），他们仍可以对单个用户的密码进行暴力枚举破解。但将每个密码后加一随机串，无疑增加了暴力枚举的难度，且不存在弱口令的问题了。更加安全的做法是，我们可以给每个密码设置一个随机的 Salt 值，这样即使使用暴力枚举破解了一个用户的密码，也很难再破解其他用户的密码了。</p>     <p> 除了给 MD5 算法加盐，其它的增强用户密码安全性的主动措施有使用更加耗时的加密算法，这样使破解的时间也大大增加了；或者更换更安全的加密算法如 SHA-2算法；还可以像 推ter 一样强制用户使用复杂密码等等。</p>     <p> <strong>结论</strong></p>     <p> 回到文章起始提出的问题，如果我的网站存有 10 万 MD5 密码的数据库落入了黑客手中，根据最近对 CSDN 密码泄露事件的统计规律：600万账号中有 239 万个账号和其它账号的密码相同<sup>[5]</sup>，进行最乐观的假设，假设这些账号使用的都是弱密码，且我们手中有所有这些弱密码所对应的明文信息，则约有 40% 的密码将被破解。对于文章起始处提出的问题来说，就是约 4 万名用户的密码将被破解。而进行较保守的假设，以 CSDN 事件中排名前 10 的弱密码为例，共有 748350 人使用了排名前 10 的弱密码，比例为0.1%，假设真实使用排名前 1000 的弱密码的人数为 100*0.1%=10%，且我们手中有 80% 的弱密码所对应的明文信息，则对于文章起始处提出的问题来说，就是约 8 千名用户的密码将被破解。由此可见，只对用户密码进行简单的 MD5 加密并不能保证全部用户的密码安全，大约会有 8000~40000名用户的密码将被查表破解。</p>     <p> （该估计方法存在一定问题：由于本人并未找到更好的基于真实情况的弱密码使用统计结论，且没有 CSDN 所泄露的数据库，只能以果壳网的数据为基准，并且由于国壳网所提供的数据量很小，估计方法也并不准确，只是进行粗略估计，最终结果只是一个定性结论。该问题还可以进行定量的后续研究。）</p>     <p> via <a href="/misc/goto?guid=4958322432980044441">adora</a></p>     <div id="come_from">           来自:      <a id="link_source2" href="/misc/goto?guid=4958322433782132004" target="_blank">www.leiphone.com</a>     </div>    </div>