安全科普：密码学之碰撞攻击

前言

密码学贯穿于网络信息安全整个过程，在解决信息安全的机密性保护、可鉴别性、完整性保护和信息抗抵赖等方面发挥着极其重要的作用，可以毫不夸张地说“对密码学或密码技术一无所知的人是不可能从技术层面上完全理解信息安全的！”

最近SSL中间人证书攻击根本停不下来，真正的数字证书伪造有多难？有人会提起当年引起世界轩然大波的“Flema(火焰)”病毒事件，火焰病毒正是利用碰撞攻击对自身进行数字签名，伪造了证书，杀软对其证书鉴定时以为是来自微软。而这种碰撞攻击在计算上是不可行的！但是又是不可避免的(下面将解释为什么）

走近哈希函数

散列函数又称HASH函数或杂凑函数，它是一种单向加密函数算法，从明文到密文不可逆的映射，也就是说只有加密过程，不能破解的。

1、H(m)算法公开，不需要密钥；
2、将任意长度输入数据转换成一个固定长度输出；
3、对任意m，H(m)易于计算，这也是使用普遍的原因之一。

由上面题意可知，任意长度字符串进过哈希算法的变换可以输出一个固定长度的字符串，并且本身具有抗弱碰撞性和抗强碰撞性，简单说就是找到两个不同字符串m和m',要想H(m)=H(m')在计算上是不可行的！由此我们可以想象散列函数在计算机上的应用。

哈希函数的应用

1、保证数据的完整性

就是用散列函数对数据或文件进行转换，生成一个散列码并保存，下次使用该数据和文件，同样进行散列函数计算得出结果与之比较，如果数据或文件被恶意篡改的，这两个值就不同了。以此发现病毒或入侵者。因为一个比特或几个比特被改变，它的hash结果就被改变。如图例。

2、单向数据加密

例子有口令加密，将用户口令的散列码存到一个表中，使用时将用户输入口令进行散列运算然后与准备好的散列表值进行对比，从而完成口令的有效验证。如图例。

3、数字签名

所谓数字签名(Digital Signature)（又称公钥数字签名、电子签章）是一种类似写在纸上的普通的物理签名，但是使用了公钥加密领域的技术实现，用于鉴别数字信息的方法。一套数字签名通常定义两种互补的运算，一个用于签名，另一个用于验证。

一般而言数字签名还应该满足下列要求：

1、签名不可伪造性；
2、签名不可抵赖的（简直通俗易懂~）；
3、签名可信性，签名的识别和应用相对容易，任何人都可以验证签名的有效性；
4、签名是不可复制的，签名与原文是不可分割的整体；
5、签名消息不可篡改，因为任意比特数据被篡改，其签名便被随之改变，那么任何人可以验证而拒绝接受此签名。

对散列函数的攻击是不可避免的

对散列函数的攻击是不可避免的，所以在设计算法函数时就要让它的破解在计算上不可行！这里的计算上不可行大概就是指用现有的设备理论上在多少年时间内都不可破解之。碰撞攻击不可避免听上去根本就不安全嘛！但没关系，评价散列函数的有效方法就是看一个攻击者找到一对产生碰撞的字符串所花的代价有多高。这方面的研究或许都是国家层面的，火焰病毒就是找到了一种哈希碰撞，成功对自身数字签名，杀软识别就是来自微软，据说火焰病毒可能是某个国家开发的网络战武器。过多这里不做讨论（有识之士在下面探讨= =）。

目前散列函数的攻击方法

第一类称为穷举攻击（或暴力攻击）：它能对任何类型的散列函数进行攻击，其中最典型的方法就是“生日攻击”。下面贴出生日悖论：

生日悖论：在一个会场参加会议的人中，找一个与某人生日相同的概率超过0.5时，所需参会人员为183人。但要问使参会人员中至少有两个同日生的概率超过0.5的参会人数仅为23人。
这是因为，对于与某个已知生日的人同日生的概率为1/365，若房中有t人，则至少找到一人与此人同日生的概率为多少？
第一个人在特定日生的概率为1/365，
而第二人不在该日生的概率为(1-1/365)；
类似地第三人与前两位不同日生的概率为(1-2/365)；
以此类推，t个人都不同时生日概率为Pt=(1-1/365)(1-2/365)…(1-(t-1)/365)；
因此，至少有两人于同日生的概率为1-Pt.
解之，当t³23时，p>0.5。

第二类称为密码分析法：这类攻击方法依赖于对散列函数的结构和代数性质分析，采用针对散列函数弱性质的方法进行攻击。这类攻击方法有中间相遇攻击、差分分析等。

散列函数之MD5的破解

MD5就是这样一个在国内外有着广泛的应用的杂凑函数算法，它曾一度被认为是非常安全的。然而，2005年美国密码会议上，我国山东大学王小云教授公开了自己多年研究散列函数的成果，她给出了计算MD5等散列算法的碰撞的方法，可以很快的找到MD5的“碰撞”，就是两个文件可以产生相同的“指纹”。这意味着，当你在网络上使用电子签名签署一份合同后，还可能找到另外一份具有相同签名但内容迥异的合同，此处“破解”不能顾名思义以为是从密文到明文的逆向重现哦。这项研究引发密码学界的轩然大波，这真是一种令人印象极深的卓越成就啊！

安全算法简史

•MD5、SHA－1是当前国际通行的两大密码标准。MD5由国际著名密码学家图灵奖获得者兼公钥加密算法RSA的创始人Rivest设计，SHA－1是由美国专门制定密码算法的标准机构——美国国家标准技术研究院（NIST）与美国国家安全局（NSA）设计。目前两种算法均被破解，取而代之的是更安全SHA-3，但是如果说现在就迅速普及似乎是不可能的，这其中还是有许多缘由的，比如商业利益等。

•两大算法是目前国际电子签名及许多其它密码应用领域的关键技术，广泛应用于金融、证券等电子商务领域。

•SHA-3：2007年—2012年。

几大著名工程

RIPE工程（1988-1992）–组织单位：EuropeanCommunity–设计目标：身份识别算法，杂凑函数，消息认证码和数字签名算法

NESSIE工程（2000-2002）–组织单位：EuropeanCommunity–设计目标：数字签名、杂凑函数、分组密码等各类密码算法SHA-3征集计划（2007-2012）–组织单位：美国国家标准与技术研究所–设计目标：杂凑函数

SHA-3征集计划：

2005、2006年：召开两次杂凑函数研讨会；
2007年：制定新的杂凑函数的安全需求、性能要求和评估标准；
2007-11-2：开展新的杂凑函数标准算法（SHA-3）的公开征集；
2008-10-31：提交过程截止； 
2008-11—2009-07：第一轮评估提交64个算法，51个算法进入第一轮；
2009-08—2010-08：第二轮评估14个算法进入第二轮；
2011年：最后一轮评估–2012年：确定最终获选算法，制定杂凑函数标准草案。

对散列函数碰撞攻击的破解现状

写在后面

密码学历史悠久，更安全更难破解算法也一直是我们的追求，有时正是因为“道高一尺魔高一丈”才促进了信息安全的发展。同时想提及，网络上的MD5破解网站，其实并无破解之本义，与其说“破解”，不如说“查询”，就是你要破解的MD5，其对应的明文消息(或说字符串）与MD5值已经被收录。因为还没有一种算法，可以通过输出加密后的散列值算出原始明文。

对了！此文为本小白班门弄斧，密码学算法原理还是挺复杂，本文简单科普，如有不对之处望不吝指正！

[本文由[凌晨几度i]所撰写，如有不对之处望不吝指正哈，转载请注明出自FreeBuf.COM]