安全哈希函数简介.doc

安全哈希函数一、 哈希函数定义Hash，一般翻译做“散列”，也有直接音译为”哈希”的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来 唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。二、 性质基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。但反过来不同的原始输入不一定能得到相同的散列值，即发生了碰撞。哈希函数的定义域无限，而值域有限，因此理论上来讲每个哈希函数都可以找到碰撞。一个“优良”的hash函数 f 应当满足以下三个条件：任意y，找x，使得f(x)=y，非常困难。此为哈希函数的单向性，或抗原像性（preimage resistant）。 给定x1，找x2，使得f(x1)=f(x2)，非常困难。弱抗碰撞性，或抗第二原像性（second preimage resistant）。 找x1，x2，使得f(x1)=f(x2)，非常困难。强抗碰撞性（Collision Resistant）。 三、 分类哈希函数有字符串哈希函数，一般用于数据存储；安全哈希函数安全哈希函数的分类：根据安全水平：弱抗碰撞哈希函数和强抗碰撞哈希函数，后者是包含前者的。在保护口令的应用中，只需弱抗碰撞性就够了，但在数字签名中，必须有强抗碰撞性。根据是否使用密钥：带密钥的哈希函数：消息的散列值由只有通信双方知道的秘密密钥K来控制，此时散列值称作MAC(Message Authentication Code)不带密钥的哈希函数：消息的散列值的产生无需使用密钥，此时散列值称作MDC(Message Detection Code四、 哈希函数的用途数字签名哈希函数可以提高签名的速度，减少运算，又可以不泄露签名所对应的消息，还可以将消息的签名与加密变换分开处理。校验可以校验数据是否被篡改。传输消息之前对消息进行哈希变换，接收者也进行相同的哈希变换，若两个哈希值相同，可以认为消息在传输过程中没有被篡改。快速访问散列表的寻址时间复杂度为O(1)，在数据存储中运用较多，这里不作详述。安全访问认证MD5广泛用于操作系统的登陆认证上，如在Unix系统中用户的密码是以MD5（或其它类似的算法）经Hash运算后存储在文件系统中。当用户登录的时候，系统把用户输入的密码进行MD5 Hash运算，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这可以避免用户的密码被具有系统管理员权限的用户知道。伪随机数生成五、 安全哈希算法安全哈希函数的一般结构大部分安全哈希函数都是迭代结构的。图中Mi为被分成L块的原始信息，f为杂凑函数，IV为初始值。填充信息和IV的选择对哈希函数的安全性有很大影响，任何两条消息都不能被填充成相同的消息，填充的末尾应该加上消息的长度；IV的选择定义为该哈希函数描述的一部分。六、 常用安全哈希函数目前使用最多的哈希函数有MD（Message-Digest Algorithm）系列（MD4、MD5、HAVAL、RIPEMD）和SHA系列（SHA-1、SHA-256）MD41990年Ronald L. Rivest设计，通过3圈的操作将任意长度的消息变换成128位的哈希值。MD4算法的前两圈已被Dobbertin等人攻破，证明MD4算法是不安全的，但整个算法并没有被攻破过。具体算法详见MD4算法分析例子：MD4 () = 31d6cfe0d16ae931b73c59d7e0c089c0 MD4 (a) = bde52cb31de33e46245e05fbdbd6fb24 MD4 (abc) = a448017aaf21d8525fc10ae87aa6729d MD4 (message digest) = d9130a8164549fe818874806e1c7014b MD4 (abcdefghijklmnopqrstuvwxyz) = d79e1c308aa5bbcdeea8ed63df412da9 MD4 (ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789) = 043f8582f241db351ce627e153e7f0e4 MD4 (12345678901234567890123456789012345678901234567890123456789012345678901234567890) = e33b4ddc9c38f2199c3e7b164fcc0536MD5MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，经过一系列处理之后，其输出是4个32位字的级联，与 MD4 相同。MD5算法被王小云证明是可攻破的，因此也已经不安全了。MD5与MD4的区别：MD5用了4轮变换，比MD4多一轮；MD4中第一轮没有常量加，MD5中64步每一步用了一个不同的常量Ki；MD5每轮加上前一步的结果，MD4没有。MD5首先对数据进行填充，使其成为512的倍数。上图中的每个HMD5进行4轮运算，每轮包括16次操作，每次操作的流程图如图所示Mi 表示一个32位的输入消息分组（16*32=512），Ki 表示一个32位常数，用来完成每次不同的计算，s表示向左位移s位。图中的F是一个非线性函数，四轮中的F函数各不相同，分别为：F(X,Y,Z) =(X&Y)|(X)&Z)G(X,Y,Z) =(X&Z)|(Y&(Z)H(X,Y,Z) =XYZI(X,Y,Z)=Y(X|(Z)每轮中的16次运算的参数也不相同，详见百度百科。HAVALHAVAL是MD5的改进版本，其轮数可以是3、4或5（每轮16步），输出长度分别为128、160、192或224位。HAVAL用高非线性的7-变量函数取代了MD5的简单非线性函数。SHA1SHA由美国国家标准技术研究所NIST开发，与1993年发表，SHA-1是基于MD4设计的。输入最大长度为264位的数据，输出160位的消息摘要，同样以512位数据块进行处理。具体这里不详述。SHA-256输出由SHA-1的160位扩大到256位，迭代次数由SHA-1的80次增加到128次SHA-384输出扩大到384位，迭代次数增加到192次SHA-512输出扩大到512位，迭代次数增加到256次输入位数输出位数迭代次数分组长度找到碰撞MD4无限128bit48512bit是MD5无限128bit64512bit是SHA-1264-1160bit80512bit理论260SHA-2SHA-256264-1256bit64512bit否SHA-3842128-1384bit801024bit否SHA-5122128-1512bit801024bit否SHA-3224/256/384/51224否七、 评价标准抗冲突性评价一个哈希函数的方法之一是看找到一对碰撞所花费的代价有多高。分布均匀性好的哈希函数有这样的特性，只要输入有少许差异，转换出来的哈希值就会有极大的不同。哈希表大小、填充因子等，主要用于评价哈希表八、 攻击原像攻击：对于给定散列值Y，找到M，使得H(M)=Y第二原像攻击：伪造消息，使其与原始消息的哈希值相同，即对于消息x，找到y，使得h(x)=h(y)。碰撞攻击：即找到任意两