哈希函数具有单向性和抗碰撞性,被广泛应用于区块链、口令保护及软件保护。

原文标题:《【图学院】这里有哈希函数「家族」的秘密 ......》
撰文:PlatON

哈希函数是现代密码体系中的一个重要组成部分,被普遍应用在社会生产生活当中。平时大家比较感兴趣的数字货币,就使用了哈希函数。

五分钟了解哈希函数的特性、分类与应用

从理论角度来看,哈希函数是以任意长度的数据为输入,输出相应固定长度的值(比如,32byte)。这个值为哈希值,又称摘要、散列、杂凑、指纹。这可能看起来很难理解,其实就是一种数学函数,输入的长度可以是任意的,但输出的长度是固定的。

五分钟了解哈希函数的特性、分类与应用

密码学的很多概念是从现实世界的概念迁徙而来,比如哈希是模拟人类的指纹。因为人类的指纹始终不变,不可能跟随人的胖瘦而更改,也不可能同时代表两个人。

在网络安全协议中,哈希函数可以用来处理电子签名,将冗长的签名文件压缩为一段独特的数字信息,像指纹鉴别身份一样保证原来数字签名文件的合法性和安全性。

哈希函数的特性

哈希函数具有两大基本属性(敲黑板,这是重点):单向性和抗碰撞性。单向性决定了哈希函数的正向计算效率高,反向计算难度非常大,几乎不可能;而抗碰撞性决定了无法找到两个不同的输入,使得其输出(即哈希值)是一致的。

接下来,让我们依次进行阐述。

单向性

哈希函数的单向性意味着,给定一个哈希值,我们无法(很难)逆向计算出其原像输入。即给定一个哈希值 y,我们无法计算出 x,使得 y=H (x)。简单来说,是无法逆向推理。

五分钟了解哈希函数的特性、分类与应用

对于无法逆向推理,你可能会产生疑问:难道就不能通过不断试错的方法,碰碰运气,得到最终的 x 值吗?也就是说,尝试不同的 x 值,总有一个经过哈希后能得到正确的 y 值吧?这只能说,实践出真知。

以哈希函数 SHAI (输出为 160-bit)为例,假设计算机具备的算力为 73TH/s (即每秒可执行 73×1012 次哈希),Bitman 算力最高矿机 AntminerS17+),那么其一年可执行的哈希运算为 2×1022 次,要搜索出每一个原像大概需要 282 年,超过 100 万亿亿年。

以下是计算过程:

73TH/s=73×1012/s≈2×1022/year≈278/year

2160÷278=282year>1024year

所以,反向计算出哈希函数原像的难度太大,几乎不可能。

抗碰撞性

碰撞指的是在输入区间 D 中的任意两个不同输入 x、y,两者的哈希值是相同的。那么哈希函数的抗碰撞性意味着,找出任意两个不同的输入值 x、y,使得 H (x)= H (y)是困难的。(这里称为「困难」的原因,是消息空间是无穷的,而哈希值空间是有限的,因此一定会存在碰撞,只是对寻找碰撞的算力需要有难度上的约束)。

五分钟了解哈希函数的特性、分类与应用

以哈希函数 SHAI (输出为 160-bit)为例:其输出空间为(0,2160),假设有一万亿个哈希值,发生碰撞的概率仅为 3×10-25。被碰撞的概率太低,几乎不可能。

因此,哈希函数的碰撞虽很难,但产生碰撞的几率并不为零。比如,我们将十只鸽子放到五个箱子里面,一定会有两只鸽子是在同一个箱子里面。

再比如下图的生日攻击问题,考虑所有人的生日都是独立均匀随机分布在 365 天内,因为第二个人不能跟第一个人有相同的生日 (概率是 364/365),第三个人不能跟前两个人生日相同 (概率为 363/365),依此类推,用阶乘方法计算。最终得知,当 n=23 时,概率趋于 50%,而人的出生率并不是均匀随机的,因此 23 人实际概率应该大于 50%。

五分钟了解哈希函数的特性、分类与应用

因此,哈希函数的抗碰撞性依据其内部构造而定,不同的哈希函数被攻击的几率不同。

哈希函数算法「家族」

从哈希(Hash)函数这一概念诞生至今,已经提出了几十种哈希算法,每类算法对应不同的参数又会形成不同的算法实现。众多的哈希函数如同一个江湖,其中 MD 家族和 SHA 家族是「哈希江湖」中最具声望的两大家族。

国际: MD4、MD5、SHA-1、SHA-256、SHA-3。(MD 系列、SHA-1 已被破解)

国内:国产自主研发的商用密码哈希算法,即 SM3

MD5 由美国密码学家罗纳德·李维斯特(Ronald Linn Rivest)设计,经 MD2、MD3 和 MD4 发展而来,输出的是 128 位固定长度的字符串。主要用于增强算法复杂度和不可逆性,因其普遍、稳定、快速的特点,仍广泛应用于普通数据的加密保护领域。

SHA-1 由美国国家安全局(NSA)提出,输出的是 160 位固定长度的字符串,在 MD5 的基础上提高输出的长度,单向操作的数量以及单向操作的复杂性,但未做任何根本改进来使其能够抵御更强大的机器。

SHA-3 是由美国国家标准与技术研究所(NIST)发布的,采用了不同于 MD 算法 (如 MD5) 结构的海绵结构,是目前较为安全的哈希函数。

国内的哈希算法有国产自主研发的商用密码算法 SM3,由国家密码管理局于 2010 年发布,主要用于数字签名及验证、消息认证码生成及验证、随机数生成等,其算法是公开的。据国家密码管理局表示,其安全性及效率与 SHA-256 相当。

每个算法都是有生命周期,不可能永远被使用。比如曾在商业市场广泛运用的 MD5 算法,被中国科学院院士、清华大学王小云教授攻破,造成密码学界的轰动。

王小云教授给出了首个在 MD5 算法上的碰撞例子,并且该碰撞案例是通过 IBM P690 计算机约 1 小时左右即可寻找到,从而证实了 MD5 算法无法防止碰撞,不适用于安全性认证。

王小云教授对 MD5 防碰撞性的攻击表现在:

能够在较短时间内计算找到消息 M1 和 M2,使得 M2 产生的哈希值与 M1 产生的哈希值相同。如此,MD5 的抗碰撞性就已不满足,使得 MD5 不再是安全的哈希算法。

因此,某个单一的哈希算法可能在十年甚至三十年内保证是安全的,能被大家放心地使用。一旦被攻破,大家只能开始换用另一种算法。当然,这个过程是非常漫长的。

哈希函数的应用

哈希函数具有单向性和抗碰撞性,即使仅仅改变输入信息的一个字符也会产生一个完全不同的哈希值,该特性帮助我们防止数据被篡改。

我们可以将原始数据和经过哈希算法得到的数据一块发送给对方,对方收到数据之后,对数据使用相同的哈希算法进行计算,如果得到的哈希值和对方发过来的相同,那么就说明数据没有经过篡改。

哈希函数的应用非常广泛,例如以下几种:

  1. 口令保护:在现代 web 应用中,账户系统的口令通过哈希函数处理后,再存储于服务器上,使得口令只对用户自己可知;
  2. 软件保护:对外发布软件时,同时使用哈希函数计算出软件的哈希值,与软件一起发布,防止用户下载假冒软件;
  3. 区块链:在区块链中,账户与交易都涉及哈希函数的使用。

在区块链中,哈希函数的主要价值是防篡改。每一个区块都存有前一个区块的哈希值,前一个区块叫做当前区块的父区块。当修改当前区块的任意值,都会对父区块产生影响。

前面我们提到,每个算法都是有生命周期,不可能永远被使用。如果 SHA-256 算法被攻破,是不是意味着区块链就挂了?是的,除非全网升级新的哈希算法。SHA-256 算法可能被使用 30 多年或者更长时间,这都很难被确定。

值得一提的是,比特币使用 SHA-256 来转换数据的方式非常有趣,它将算法在协议中连续执行了两次。注意,这并不是为了抵御生日攻击。显然如果 Hash(x) = Hash(y),那么也有 Hash(Hash(x)) = Hash(Hash(y)),为了缓解长度扩展攻击。

从本质上说,这种攻击需要恶意攻击者知道哈希输入值的长度,在这个已知的长度上再加上一个秘密的字符串,就可以发动哈希函数内部的一部分,从而扰乱哈希函数。由于 SHA-256 是 SHA-2 算法家族的成员,它有这一类的短板,而比特币通过将哈希函数连续运行两次来缓解这个缺陷。

总的来说,哈希函数在生活当中无处不在,包括我们平常在网络上输入的口令,背后都是哈希函数在起作用。不仅如此,它在区块链中的应用和价值也是显而易见的,通过提高其内部操作的复杂性或输出长度,使得被运用的哈希函数在一定时间内足够安全。

如同哈希函数的发展史,当有旧的算法被攻破,就有新的算法被发明。我们一直在尽全力探寻一个计算更高效的未来,不断挑选最好的工具,经得起时间的考验!

来源链接:mp.weixin.qq.com