编程知识 cdmana.com

写给开发人员的实用密码学 - Hash算法

说到Hash(哈希),开发人员应该不陌生,比如Hash表是一种非常常用的数据结构,通过Hash表能够根据键值快速找到数据。哈希函数将文本(或其他数据)映射为整数,从而能够提高检索效率。

密码学中的Hash算法和普通的Hash算法不是同一个概念,从安全的角度考虑,密码学中的Hash算法除了有普通Hash算法的特性之外,还有其他的一些特性。

密码学Hash算法也通常称作摘要算法,是密码学中的基础算法,是现代密码学中的核心组成部分。2004年山东大学王小云教授发表论文,指出了MD5和SHA-1两种Hash算法的漏洞,引起了业界的恐慌,足以说明Hash算法的重要性。密码学中有很多密码学Hash算法,比如MD5、SHA-1、SHA128、SHA256、SHA512等,国家商用密码中也有一个Hash算法SM3。我们不用理解Hash算法的内部实现原理,更应该关注其特性、用途以及使用中需要注意的点。

在密码学中,Hash函数将任意大小(例如文本消息)的输入数据转换为固定大小(例如256位)的结果,这称为哈希值(或哈希码、消息摘要)。比如SHA-256和SHA3-256,可将任意输入转换为256位输出。

哈希算法

密码学Hash算法示例

我们可以借助 OpenSSL 附带的命令行工具计算字符串"hello"的SHA256算法哈希值:

$ echo -n "hello" | openssl sha256
(stdin)= 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

也可以借助开源国密算法库 GmSSL 的命令行工具,计算 SM3 算法的哈希值:

$ echo -n "hello" | gmssl dgst -sm3
(stdin)= becbbfaae6548b8bf0cfcad5a27183cd1be6093b1cceccc303d9c61d0a645268

密码学Hash算法的特点

设计一个Hash算法并不难,但要设计一个能用于密码学上的Hash算法非常难,需要有非常深厚的数学和密码学功底。一个设计良好的密码学Hash算法需要具有如下特点:

  1. 确定性:相同的消息总是能得到同样的摘要值,特定的Hash算法,不管消息长度是多少,最终的摘要值长度是相同的。

  2. 快速:计算任何给定消息的哈希值应该很快。

  3. 难以分析:对输入消息的微小修改将完全改变输出哈希值。

  4. 不可逆:通过摘要值很难逆向计算出原始消息,Hash算法具备单向性,摘要值是不可逆的,这也是非常重要的特性。为了逆向计算出原始消息,唯一的方法就是采用暴力攻击、字典攻击、彩虹表

  5. 没有碰撞:找到两个具有相同哈希值的不同消息非常困难(或几乎不可能)。

注意第5点,没有冲突是一种理想情况,考虑到最后生成的摘要值只有固定的有限位,必然存在不同消息具有相同哈希值的情况,但这里强调的是找到它们非常困难。后面谈到 MD5 的破解将会谈到。

密码学Hash算法的用途

密码学哈希算法用途很广,下面看看最常见的几个用途:

  • 文档/消息完整性

验证文件/文档/消息的完整性。比如我们在网站下载文件时,网站通常会给出文件的 MD5 值或 SHA256 值。

OpenSSL源码Hash值

通过对比哈希值,我们可以确保自己下载的文件和服务器上是一致的。

  • 存储密码

这个开发人员应该很熟悉,当然也有菜鸟程序员直接往数据库中存储明文密码(从曝光的拖库攻击事件中,发现这么做的公司还不少)。开发人员通常不将纯文本密码保存在数据库中,而保存密码散列值或从密码派生的更复杂的值(例如,Scrypt派生的值)。

/etc/shadow文件

上面的示例来自现代 Linux 系统中的 /etc/shadow 文件,里面的密码存储为带盐的多轮SHA-512哈希值。

采用这种解决方案,即使数据库或数据文件泄露,攻击者也无法通过口令的摘要值计算出原始口令,攻击者很难伪造用户进行攻击。

系统具体如何校验用户密码呢?大概的步骤如下:

  • 用户输入用户名和口令登录。

  • 系统使用Hash算法计算出口令的摘要值。

  • 系统使用用户名和摘要值在数据库表中进行检索,一旦匹配到就说明该用户输入的口令是正确的。

  • 生成唯一ID

生成特定文档/消息的(几乎)唯一ID。密码散列函数几乎根据文档的内容唯一地标识文档。当然从理论上讲,任何哈希函数都可能发生碰撞,但是这种碰撞不太可能发生,因此大多数系统(如Git)都假定它们使用的哈希函数不存在碰撞。

这样的示例有 git 版本管理系统,其每一个提交通过一个哈希值标记。

git通过哈希值标记一个提交

这个特性还可以用来比较大文件,通过计算两个文件的Hash值,比较Hash值就可以判断两个文件是否相同。

  • 伪随机数生成

伪随机数生成和密钥派生。生成随机序列的一种简单方法是这样的:从随机种子开始(例如键盘单击或鼠标移动)。附加“1”并计算散列以获得第一个随机数,然后附加“2”并计算散列获得第二个随机数,以此类推。

  • 工作量证明算法

主要用在比特币,也就是俗称的挖矿。大多数工作量证明算法计算的哈希值大于特定值(称为挖掘难度)。为了找到此哈希值,矿工计算了数十亿个不同的哈希,并采用其中的最大哈希值,因为哈希数是不可预测的。例如,工作证明问题的定义如下:找到一个数字p,以使hash(x + p)的开头保留10个零位。

Hash算法一览

在过去,软件开发人员设计了许多密码哈希算法。其中有些已证明不安全(例如 MD5 和 SHA1 ),有些仍被认为是安全的(例如 SHA-2 、SHA-3 和 BLAKE2 )。下面让我们了解一下目前广泛使用的加密哈希算法。

  • MD5

MD5是一种比较常用的Hash算法,摘要值长度固定是 128 比特, MD5 算法目前被证明已经不安全了,不建议使用。

  • SHA-1

SHA-1算法类似于MD5算法,输出的长度固定是160比特。SHA-1算法在严谨的加密学中已经被证明是不安全的,但在实际中仍然有使用,因为在现实世界中要构造出碰撞还是非常困难的,需要经过大量的运算。当然在新的应用中要避免使用。

  • SHA-2

SHA-2是一系列强大的密码哈希函数:SHA-256(256位哈希)、SHA-384(384位哈希)、SHA-512(512位哈希)等。SHA-2算法是目前建议使用的Hash算法,在美国作为官方加密标准发布。

从设计上讲,哈希输出的位数越多,一般而言具有更高的安全性和更高的抗冲突性。通常,128位哈希函数要比256位哈希函数要弱,而256位哈希函数要比512位哈希函数弱。因此,SHA-512比SHA-256更强大。

  • SHA-3

SHA-3算法并不是为了取代SHA-2算法,而是一种在设计上和SHA-2完全不同的算法,主要有四种算法,分别是SHA3-256、SHA3-512、SHA3-224、SHA3-384,输出的长度分别是256比特、512比特、224比特、384比特。

在相同的哈希长度下,SHA-3比SHA-2更安全。例如,SHA3-256比SHA-256提供更多的加密强度。

SHA-3被认为是高度安全的,在美国作为官方推荐的加密标准发布。

  • SM3

SM3是国密密码杂凑算法标准,由国家密码管理局于2010年12月公布。SM3的输出杂凑值长度为256比特(32字节),与国际标准SHA-256等长。SM3设计安全性为128比特,安全性与256比特椭圆曲线/SM2、SM4/SMS4、AES-128等同。

小知识:王小云院士真的破解了 MD5 吗?

2004年8月,在美国加州圣巴巴拉召开的国际密码大会上,王小云宣读了自己和研究团队对于MD4、MD5、HAVAL-128和RIPEMD四个国际著名密码算法的破译结果。

这被认为是2004年密码学界最具突破性的结果,堪称学术界的一场强烈地震。当年国际密码大会总结报告上写道:我们该怎么办?MD5被重创了,它即将从应用中淘汰。

2005年,美国《新科学家》杂志在一篇文章中,用了颇具震撼力的标题——《崩溃!密码学的危机》,报道了王小云团队花10年时间取得的学术成果。

所谓的“破解”其实误导了很多人,并不是说扔给王小云一个 MD5 散列值,然后她马上就能算出一个原文来。从密文推算出明文理论上是不可能的,所以王小云的研究成果并不能通过 MD5 的散列值逆向推算出明文。即给定 Hash 值,王小云不能逆向计算出 M。

MD5(M)=Hash

其中 M 指密码的明文,Hash 表示密码散列后的密文。

实际上,王小云的研究成果如下:

MD5(M1)=MD5(M2)

即给定消息 M1,能够计算获取 M2,使得 M2 产生的散列值与 M1 产生的散列值相同。如此,MD5 的抗碰撞性就已经不满足了,使得 MD5 不再是安全的散列算法。这样一来,MD5 用于数字签名将存在严重问题,因为可以篡改原始消息,而生成相同的 Hash 值。

这里,简单地用王教授的碰撞法给大家举个简单的例子。假如用户 A 给 B 写了个 Email 内容为 Hello,然后通过王教授的碰撞法,可能得到 Fuck 这个字符串的摘要信息和 Hello 这个字符串产生的摘要信息是一样的。如果 B 收到的 Email 内容为 Fuck,经过 MD5 计算后的,B 也将认为 Email 并没有被修改!但事实并非如此。

王小云院士的研究报告表明,MD4,MD5,HAVAL-128,RIPEMD 和 SHA-1 均已被证实存在上面的漏洞,即给定消息 M1,能够找到不同消息 M2 产生相同的散列值,即产生 Hash 碰撞。

版权声明
本文为[osc_pl358sty]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4300166/blog/4816193

Scroll to Top