安全哈希函数简介
安全哈希函数
一、 哈希函数定义
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值进行比较,进而确定输入的密码是否正确。通过这样的步骤,系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这可以避免用户的密码被具有系统管理员权限的用户知道。
伪随机数生成
五、 安全哈希算法
安全哈希函数的一般结构
大部分安全哈希函数都是迭代结构的。图中M i 为被分成L 块的原始信息,f 为杂凑函数,IV 为初始值。
填充信息和IV 的选择对哈希函数的安全性有很大影响,任何两条消息都不能被填充成相同的消息,填充的末尾应该加上消息的长度;IV 的选择定义为该哈希函数描述的一部分。
六、 常用安全哈希函数
目前使用最多的哈希函数有MD (Message-Digest Algorithm)系列(MD4、MD5、HAVAL 、RIPEMD )和SHA 系列(SHA-1、SHA-256) MD4
1990年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
("[***********][***********][***********][***********]34567890") = e33b4ddc9c38f2199c3e7b164fcc0536 MD5
MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组,经过一系列处理之后,其输出是4个32位字的级联,与 MD4 相同。MD5算法被王小云证明是可攻破的,因此也已经不安全了。
MD5与MD4的区别:MD5用了4轮变换,比MD4多一轮;MD4中第一轮没有常量加,MD5中64步每一步用了一个不同的常量K[i];MD5每轮加上前一步的结果,MD4没有。
MD5首先对数据进行填充,使其成为512的倍数。
上图中的每个H MD5进行4轮运算,每轮包括16次操作,每次操作的流程图如图所示
M i 表示一个32位的输入消息分组(16*32=512),K i 表示一个32位常数,用来完成每次不同的计算,
每轮中的16次运算的参数也不相同,详见百度百科。 HAVAL
HAVAL 是MD5的改进版本,其轮数可以是3、4或5(每轮16步),输出长度分别为128、160、192或224位。HAVAL 用高非线性的7-变量函数取代了MD5的简单非线性函数。 SHA1
SHA 由美国国家标准技术研究所NIST 开发,与1993年发表,SHA-1是基于MD4设计的。 输入最大长度为2^64位的数据,输出160位的消息摘要,同样以512位数据块进行处理。具体这里不详述。 SHA-256
输出由SHA-1的160位扩大到256位,迭代次数由SHA-1的80次增加到128次
SHA-384
输出扩大到384位,迭代次数增加到192次 SHA-512
输出扩大到512位,迭代次数增加到256次
MD5 SHA-1
输入位数 无限 264-1
输出位数 128bit 160bit 256bit 384bit 512bit
迭代次数 64 80 64 80 80
分组长度 512bit 512bit 512bit 1024bit 1024bit 找到碰撞
是 理论260 否 否 否
SHA-256 264-1
SHA-2 SHA-384 2128-1
SHA-512 2128-1
七、 评价标准
抗冲突性
评价一个哈希函数的方法之一是看找到一对碰撞所花费的代价有多高。
分布均匀性
好的哈希函数有这样的特性,只要输入有少许差异,转换出来的哈希值就会有极大的不同。
哈希表大小、填充因子等,主要用于评价哈希表
八、 攻击
原像攻击:对于给定散列值Y ,找到M ,使得H(M)=Y
第二原像攻击:伪造消息,使其与原始消息的哈希值相同,即对于消息x ,找到y ,使得h(x)=h(y)。
碰撞攻击:即找到任意两消息M 和M ’,M ≠M ’,使得H(M) = H(M’)
常见的攻击: 生日攻击法
在23个人中,存在两个生日在同一天的人的概率为0.5073,而如果有100个人,则这个概率能达到0.9999997. 利用这个原理,攻击者只需枚举一定量的值,就可以找出一对哈希值相同的输入值。
王小云成功找到MD5的碰撞,且把SHA-1的攻击运算次数从2^80降到2^63。