前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >写给开发人员的实用密码学 - Hash算法

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

作者头像
云水木石
发布2020-12-29 15:56:12
2.1K0
发布2020-12-29 15:56:12
举报
文章被收录于专栏:大龄程序员的人工智能之路

说到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算法哈希值:

代码语言:javascript
复制
$ echo -n "hello" | openssl sha256
(stdin)= 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

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

代码语言:javascript
复制
$ 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。

代码语言:javascript
复制
MD5(M)=Hash

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

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

代码语言:javascript
复制
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 碰撞。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-12-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 云水木石 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 密码学Hash算法示例
  • 密码学Hash算法的特点
  • 密码学Hash算法的用途
  • Hash算法一览
  • 小知识:王小云院士真的破解了 MD5 吗?
相关产品与服务
命令行工具
腾讯云命令行工具 TCCLI 是管理腾讯云资源的统一工具。使用腾讯云命令行工具,您可以快速调用腾讯云 API 来管理您的腾讯云资源。此外,您还可以基于腾讯云的命令行工具来做自动化和脚本处理,以更多样的方式进行组合和重用。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档