密码破解技术小结(1)

1) Brute-Force-Attack：
也就是常说的"暴力破解"，这是一种"时间消耗型"的password reverse方式，确定了密文的加密方式的前提下，使用相同的加密算法，计算
M = H(P)
P为所有的明文空间
H为加密算法
M为密文
然后将计算得到的M和待破解的密文进行比较，如果匹配成功，则对应的明文P即为待破解密文的明文。值得注意的是，这个枚举P和比较M的过程往往是在内存中进行的，
也即在计算的过程中一边产生，一边比较，这次破解结束后，下一次破解又要重新开始从头枚举，效率不太高

典型的Brute-Force-Attack如图

2) Directory-Based-Attack

字典破解本质上还是"暴力破解"的一种，我觉得它是"Brute-Force-Attack"的另一个极端，"Brute-Force-Attack"是一种纯的"时间消耗型"的攻击方式，它所有的开销都是时间，
而"Directory-Based-Attack"是一种纯的"空间消耗型"的攻击方式。
在"Directory-Based-Attack"中，攻击者是对所有的明文(M)进行预计算(PreConputation)，将所有的明文的HASH都事先计算好，并保存起来。典型的MD5字典如下:
....
password　　5f4dcc3b5aa765d61d8327deb882cf99
admin　　　　21232f297a57a5a743894a0e4a801fc3
cnblog　　　　efbc3548e65e7225dcf43d3918d94e6f
....
在进行破解的时候，破解程序将字典映射Mapping到内存中，然后将HASH和待破解的密文进行逐条比较(这点和Brute-Force是一样的)，直到找到某条HASH和待破解的密文相同为止。
值得注意的是，基于字典的暴力破解时间上比单纯的内存计算型暴力破解更有效率，只要一次的"字典生成"花费一定的时间，后续的多次破解都可以重复使用这个字典。
注意，这里说的"字典"指的对应某个算法的字典: MD5 Directory、SHA1 Directory、NTLM Directory等等。
总的来说，字典攻击是对单纯的内存型暴力破解的一个改进，它引入了PreComputation的思想，但缺点也很明显，需要占用及其庞大的磁盘空间，以至于对于长度16以上的密码字典，
完整存储根本不可能

典型的"Directory-Based-Attack"如图

3) Rainbow-Table-Attack
这是对"Brute-Force"和"Directory-Base"的一种折中的破解技术，在2003年瑞典的Philippe Oechslin 在Making a Faster Cryptanalytic Time-Memory Trade-Off一文
(文章开头有给出链接)中首次被提出，它有效的利用了PreComputation的优点，同时又克服了Diecretory-Based消耗太空磁盘空间的缺点，在这两者中找到了一个平衡点。
不过，它也有缺点，即:
　1) password+salt: 加盐
　2) key stretching: 密码扩展，包括轮数扩展和长度扩展
接下来，我们的文章会重点分析这个彩虹表破解的技术原理

1) 远程破解场景
攻击者面对的是一个远程的服务器，并且目标服务器存储密码的生成算法也不知道，此时，我们只能使用Hydra等工具进行穷举破解(Brute-Force)、
或者字典破解(Diretory-Attack)

2) 本地破解场景
攻击者知道远程服务器的密码生成算法(常常发生在一些常见的CMS系统后中)、通过hashdump抓到了内存中的HASH密码(LM、NTLM)、或者已经拿到了密码的HASH值(脱库中常见)，
攻击者可以在本地自己的计算机上进行本地计算，这个时候，相比暴力破解(Brute-Force-Attack)、字典破解(Directory-Attacj)来说，彩虹表破解就是一个更好的选择了。

Rainbow Table相比Directory做的第一个改进就是将庞大的明文密文对"分成"了"明-密文对链chain"，链条的长度越长，空间的缩减效果就越大。为了使用彩虹表技术，需要事先确定两个
函数：
H(HASH函数): 密码的加密方式，不同的彩虹表对应于不同的加密方式(这点和Directory-Based的道理是一样的)
常见的H函数有: MD4、MD5、SHA1、

R(Reverse Hash函数): 逆HASH函数，并不是真的对HASH函数求逆(我们都知道HASH函数是不可逆的)，这里所谓的R函数，只是一个映射Mapping函数，将H()得到的密文再次映射回一个对应
的明文，不一定是原来的明文，只要是明文就行

H(wikiedia)=ao4kd -> R1(ao4kd)=secret -> H(secret)=9kpmw -> R2(9kpmw)=jimbo -> H(jimbo)=v0d$x -> R3(v0d$x)=rootroot
H(abcdefgh)=1vn6s-> R1(1vn6s)=bernie-> H(bernie)=kolscx-> R2(kolscx)=zurich-> H(zurich)=8ntpy -> R3(8ntpy)=myname
....
H(passwd)=dlcm4-> R1(dlcm4)=culture-> H(culture)=re3xes-> R2(re3xes)=crypto-> H(crypto)=1tik0-> R3(1tik0)=linux23

假如R是不变的:
H(startpoint1)=median1 -> R(median1)=median12 ...... -> R(median1x)=same -> H(same)=same1 -> .... same_end
H(startpoint2)=median2 -> R(median1)=same -> H(same)=same1 -> .... same_end ...
注意这个重合一定是发生在不同链上的不同位置的节点，因为H的"非碰撞性"保证了这点(思考)，这个重合导致的是两条链中的某一段发生了"重合"

假如我们要破解的HASH密文为re3xes
1) 对密文re3xes进行Rk(k代表最后一个R函数，这里是R3)运算，得到一个临时结果 I，将这个临时结果I和每条链的尾节点进行比较，检测是否是某一条链的尾节点
　　1.1) 如果匹配成功，则破解成功，我们知道了这个待破解的密文属于某一条链，就可以利用这条链的头尾节点重现(再次计算)出这条链上的每个明密文对，自然也包括了待破解密文的明文
　　1.2) 如果匹配失败，在所有链的尾节点上都没有这个临时结果 I，则继续进行(2)
2) 对密文re3xes进行Rk-1(k-1代表倒数第二个R函数，这里是R2)，这里又得到一个临时结果: crypto，再对临时结果crypto进行H计算，得到: 1tik0，再对1tik0进行Rk
　　(k代表最后一个R函数，这里是R3)得到一个临时结果: linux23。将这个临时结果和每条链的尾节点进行比较，检测是否是某一条链的尾节点
　　1.1) 如果匹配成功，则破解成功，在这个例子中我们知道匹配成功，就可以利用这条链的头节点: passwd重现(再次计算)出这条链上的每个明密文对，自然也包括了待破解密文的
　　　　　明文: culture　　
　　2.1) 如果匹配失败，则继续调用Rk-2进行搜索，步骤都是类似的
...
直到完成了R1的搜索，如果还没有找到匹配的，则宣布本次破解失败，需要增大彩虹表文件大小、重组字典

1) 加盐
saltedhash(password) = hash(password+salt)
Or
saltedhash(password) = hash(hash(password)+salt)
需要对付这种加密方式，彩虹表就需要针对salt的每一种可能的取值都生成一套字典，当salt的长度很长时，彩虹表的生成成本和破解效率都会大幅下降
2) 密码增强 key stretching
是加密方式变化除了"加盐"，加密轮数也是一个可变化的点，MD5-Crypt and in bcryp中都使用了Crypt Loop技术，即使用同一个算法，或不同的算法组合对一个明文进行迭代的
多次(1000以上)加密，这样，加密的轮数和加密方式的组合本身也构成了一个"变化空间"
需要对付这种加密方式，彩虹表就需要针对每一个加密轮数+加密方式的组合都生成一套字典，同样，彩虹表的生成成本和破解效率都会大幅下降

http://files.cnblogs.com/LittleHann/MD5%E7%A0%B4%E8%A7%A3%E5%B7%A5%E5%85%B7.rar
MD5解密器个人加强版

LC5
http://ishare.iask.sina.com.cn/f/8862330.html

Ophcrack
http://www.objectif-securite.ch/ophcrack.php

SAMInside
http://www.insidepro.com/eng/saminside.shtml

Rainbowcrack
http://www.project-rainbowcrack.com/

彩虹表免费下载
https://www.freerainbowtables.com/en/tables/