熬夜探讨：玩转密码破解艺术——攻克HASH算法加密之谜，详解如何破译哈希
1.彩虹表（Rainbow Tables）
一般使用彩虹表的方式来破解，彩虹表的原理是什么呢？彩虹表是一种以空间换时间的技术。与查表法相似，只是它为了使查询表更小，牺牲了破解速度。因为彩虹表更小，所以在单位空间可以存储更多的哈希值，从而使攻击更有效。能够破解任何最多8位长度的 MD5 值的彩虹表已经出现。
我们先来了解下如何进行HASH碰撞。单向HASH算法由于不能进行解密运算，只能通过建表、查表的方式进行碰撞，即将常用的密码及其对应的HASH值全计算出来并存储，当获取到HASH值是，直接查表获取原始密码，假设用MD5算法来保护6位数字密码，可以建如下表：
| 原始密码 | MD5值 |
|---|---|
| 000000 | 670B14728AD9902AECBA32E22FA4F6BD |
| 000001 | 04FC711301F3C784D66955D98D399AFB |
| … | … |
| 999999 | 52C69E3A57331081823331C4E69D3F2E |
全表共100W条记录，因为数据量不大，这种情况建表、查表都非常容易。但是当密码并不是6位纯数字密码，而是数字、大小写字母结合的10位密码时，建立一个这样的表需要（26+26+10）^ 10 ≈ 83亿亿（条记录），存储在硬盘上至少要占用2000W TB的空间，这么大的存储空间，成本太大，几乎不可行。有什么办法可以减少存储空间？一种方法是“预计算哈希链”，“预计算哈希链”可以大幅减少HASH表的存储空间，但相应的增加了查表时的计算量，其原理大致如下：
建表过程：
先对原始数据“000000”进行一次HASH运算得到“670B1E”，再对HASH值进行一次R运算，R是一个定制的算法可以将HASH值映射到明文空间上（这里我们的明文空间是000000~999999），R运算后得到“283651”，再对“283651”进行hash运算得到“1A99CD”，然后在进行R运算得到“819287”，如此重复多次，得到一条哈希链。然后再选用其它原始数据建立多条哈希链。最终仅将链头和链尾保存下来，中间节点全都去掉。
查表过程：
假设拿到了一条HASH值“670B1E”，首先进行一次R运算，得到了“283651”，查询所有链尾是否有命中，如果没有，则再进行一次HASH、一次R，得到了“819287”，再次所有链尾，可以得到看出已经命中。这样我们就可以基本确认“670B1E”对应的明文就在这条链上，然后我们把这条链的生成过程进行重新计算，计算过程中可以发现“000000”的HASH值就是“670B1E”，这样就完成了整个查表过程。这种表就是“预计算哈希链”。这种方式存在一个问题，多条链之间可能存在大量的重复数据，如下图所示：
为了解决这个问题，我们将R算法进行扩展，一条链上的多次R运算采用不同的算法,如下图：
一条链上的每个R算法都不一样，就像彩虹的每层颜色一样，因此取名的为彩虹表。
当然彩虹表除了可以用户破解HASH算法外，理论上还可以用于破解对称加密算法，比如DES算法，由于DES算法密钥比较短，建立彩虹表破解是完全可行的；但对于AES算法，由于密钥比较长，建表几乎不可行（需要耗时N亿年）。
2.字典攻击和暴力攻击（ Dictionary and Brute Force Attacks）
| 字典攻击 | 暴力攻击 |
|---|---|
| Trying apple : failed | Trying aaaa : failed |
| Trying blueberry : failed | Trying blueberry : failed |
| Trying justinbeiber : failed | Trying aaac : failed |
| … | … |
| Trying letmein : failed | Trying acdb : failed |
| Trying s3cr3t : success! | Trying acdc : success! |
破解哈希加密最简单的方法是尝试猜测密码，哈希每个猜测的密码，并对比猜测密码的哈希值是否等于被破解的哈希值。如果相等，则猜中。猜测密码攻击的两种最常见的方法是字典攻击和暴力攻击 。
字典攻击使用包含单词、短语、常用密码和其他可能用做密码的字符串的字典文件。对文件中的每个词都进行哈希加密，将这些哈希值和要破解的密码哈希值比较。如果它们相同，这个词就是密码。字典文件是通过大段文本中提取的单词构成，甚至还包括一些数据库中真实的密码。还可以对字典文件进一步处理以使其更为有效：如单词 “hello” 按网络用语写法转成 “h3110” 。
暴力攻击是对于给定的密码长度，尝试每一种可能的字符组合。这种方式会消耗大量的计算，也是破解哈希加密效率最低的办法，但最终会找出正确的密码。因此密码应该足够长，以至于遍历所有可能的字符组合，耗费的时间太长令人无法承受，从而放弃破解。
目前没有办法来组织字典攻击或暴力攻击。只能想办法让它们变得低效。如果密码哈希系统设计是安全的，破解哈希的唯一方法就是进行字典攻击或暴力攻击遍历每一个哈希值了。
3.查表法（ Lookup Tables）
Searching: 5f4dcc3b5aa765d61d8327deb882cf99: FOUND: password5
Searching: 6cbe615c106f422d23669b610b564800: not in database
Searching: 630bf032efe4507f2c57b280995925a9: FOUND: letMEin12
Searching: 386f43fab5d096a7a66d67c8f213e5ec: FOUND: mcd0nalds
Searching: d5ec75d5fe70d428685510fae36492d9: FOUND: p@ssw0rd!
对于破解相同类型的哈希值，查表法是一种非常高效的方式。主要理念是预先计算（ pre-compute）出密码字典中的每个密码的哈希值，然后把他们相应的密码存储到一个表里。一个设计良好的查询表结构，即使包含了数十亿个哈希值，仍然可以实现每秒钟查询数百次哈希。
如果你想感受查表法的速度有多快，尝试一下用 CrackStation 的 free hash cracker 来破解下面的 SHA256。
c11083b4b0a7743af748c85d343dfee9fbb8b2576c05f3a7f0d632b0926aadfc
08eac03b80adc33dc7d8fbe44b7c7b05d3a2c511166bdb43fcb710b03ba919e7
e4ba5cbd251c98e6cd1c23f126a3b81d8d8328abc95387229850952b3ef9f904
5206b8b8a996cf5320cb12ca91c7b790fba9f030408efe83ebb83548dc3007bd
4.反向查表法（ Reverse Lookup Tables）
Searching for hash(apple) in users' hash list... : Matches [alice3, 0bob0, charles8]
Searching for hash(blueberry) in users' hash list... : Matches [usr10101, timmy, john91]
Searching for hash(letmein) in users' hash list... : Matches [wilson10, dragonslayerX, joe1984]
Searching for hash(s3cr3t) in users' hash list... : Matches [bruce19, knuth1337, john87]
Searching for hash(z@29hjja) in users' hash list... : No users used this password
这种攻击允许攻击者无需预先计算好查询表的情况下同时对多个哈希值发起字典攻击或暴力攻击。
首先，攻击者从被黑的用户帐号数据库创建一个用户名和对应的密码哈希表，然后，攻击者猜测一系列哈希值并使用该查询表来查找使用此密码的用户。通常许多用户都会使用相同的密码，因此这种攻击方式特别有效。
接下来，我们来看一种谓之“加盐（ salting）”的技术，能够让查表法和彩虹表都失效。
5.加盐（ Adding Salt）
hash("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
hash("hello" + "QxLUF1bgIAdeQX") = 9e209040c863f84a31e719795b2577523954739fe5ed3b58a75cff2127075ed1
hash("hello" + "bv5PehSMfV11Cd") = d1d3ec2e6f20fd420d50e2642992841d8338a314b8ea157c9e18477aaef226ab
hash("hello" + "YYLmfY6IehjZMQ") = a49670c3c18b9e079b9cfaf51634f563dc8ae3070db2c4a8544305df1b60f007
查表法和彩虹表只有在所有密码都以完全相同的方式进行哈希加密才有效。如果两个用户有相同的密码，他们将有相同的密码哈希值。我们可以通过“随机化”哈希，当同一个密码哈希两次后，得到的哈希值是不一样的，从而避免了这种攻击。
我们可以通过在密码中加入一段随机字符串再进行哈希加密，这个被加的字符串称之为盐值。如上例所示，这使得相同的密码每次都被加密为完全不同的字符串。我们需要盐值来校验密码是否正确。通常和密码哈希值一同存储在帐号数据库中，或者作为哈希字符串的一部分。
盐值无需加密。由于随机化了哈希值，查表法、反向查表法和彩虹表都会失效。因为攻击者无法事先知道盐值，所以他们就没有办法预先计算查询表或彩虹表。如果每个用户的密码用不同的盐再进行哈希加密，那么反向查表法攻击也将不能奏效。
温馨提醒：
采用PBKDF2、bcrypt、scrypt等算法可以有效抵御彩虹表攻击，即使数据泄露，最关键的“用户密码”仍然可以得到有效的保护，黑客无法大批量破解用户密码，从而切断撞库扫号的根源。当然，对于已经泄露的密码，还是需要用户尽快修改密码，不要再使用已泄露的密码。