java和go中的密码学(11)-哈希算法介绍

标签:密码学
发布时间:2018年10月22日 价值:20000.00 / 共识:29

背景

试想下平日生活中的些场景:

1)平时我们下载大文件,如电影、jdk这种几百M或几G,我们如何确定眼前下载到本地的文件是和服务器的文件是完全相同的?如何确定下载过程中没有被篡改过?

2)有天暴发户老板发送两份pdf合同文件给你,打开文件你发现各自有几百页约定条文。老板说后面那个合同文件来自生意伙伴,你帮我们快速对比下合同内容是不是完全相同的,今晚给答复他。这个时候你准备怎么对比?要知道,几百页合同条文,一个下午时间,你不可能逐字对比完的。

上面的场景,细心的你很快发现都是“确认两个文件是不是完全相同”,你第一时间会这样想:如果文件完全相同的话,那他们的字节(数量、序列)必定相同!于是你准备设计程序将两个文件一个一个字节对比……的确,这样是行。只是这样会非常耗费时间、空间资源。假如哪天来两个几十G的文件对比呢?几百G呢??

你会发现上面的方法很快行不通。而哈希值,就可以完美解决你的烦恼。

小联想

在正式介绍哈希值前,我们来做个小思考:我们这么大个人身上什么是独一无二的、什么是别人身上一定只能是会不一样的?你很快会想到:指纹、眼睛虹膜、DNA序列。没错,世界上那么多人,却不存在任何两个人在这三方面会完全相同(就像世界上没有相同的两片叶子般)!也就是说,一个人,必定唯一对应一个指纹(或眼睛虹膜、DNA序列),反之,亦然!(于是,我们的指纹、眼睛虹膜被老板们应用在平日上下班打卡机防作弊了……)

Ok,既然那么大个人,会有唯一对应着的一个“那么小”的指纹(或眼睛虹膜、DNA序列)。那么在计算机领域,对于一个很大的文件,会不会也有唯一对应着的一个“那么小”的数据片段呢?

如果有的话,两个文件的对比,就可以直接对比他们各自的那个所谓的“一个‘那么小’的数据片段”,这样就会非常快得到对比结果了。
所谓的“一个‘那么小’的数据片段”,是存在的,被称为:哈希值。Well, 哈希值,就是一个文件的「指纹」、「眼睛虹膜」或「DNA序列」, 彼此唯一对应着、不离不弃!
而获取一个文件的哈希值的方式就是:哈希算法!

定义

哈希算法(Hash Algorithm),又称散列算法,杂凑算法,是一种从任意文件中创造小的数字「指纹」的方法。与指纹一样,散列算法就是一种以较短的信息来保证文件唯一性的标志,这种标志与文件的每一个字节都相关,而且难以找到逆向规律。因此,当原有文件发生改变时,其标志值也会发生改变,从而告诉文件使用者当前的文件已经不是你所需求的文件。
其实由上面的场景和定义,我们可以快速归纳出,哈希函数理应具备以下性质:

  1. 1. 压缩:对于任意大小的输入x,哈希值的长度很小,并且是固定的长度
  2. 2. 确定性:哈希函数的算法是确定性算法,算法执行过程不引入任何随机量。这意味着相同消息的哈希结果一定相同。
  3. 3. 易计算性:必须很快就可以计算出来
  4. 4. 单向性:通过给定的哈希值得到原文是不可行的,求解哈希函数的逆很困难
  5. 5. 抗碰撞性:理想的哈希函数是无碰撞的,但是实际的算法设计中很难做到,有两种抗碰撞性
  6. i.弱抗碰撞性:对于给定的一个消息,要发现另一个消息使其碰撞在计算上不可行
  7. ii.强抗碰撞性:对于任意的一对不同的消息,使其碰撞在计算上不可行
  8. 6. 高灵敏度:当一个输入位发生变化时,会有一半以上的输出位发生变化

哈希函数家族

常见哈希算法有很多,每个文件在不同的哈希算法计算后会得到不同的哈希值,犹如一个人有多个国家的国籍时会在这些国家分别会有唯一的身份证号码一样。

哈希算法,目前主流分为两个系列,如下:
1.MD系列:

  1. (1) MDMessage Digest的缩写,数据摘要。
  2. (2) 常见成员有MD4MD5,计算得到的哈希值是128bit长度。目前都已经被证明容易碰撞、不安全了,不推荐使用。

2.SHA系列

  1. (1) SHASecurity Hash Algorithm的缩写,安全哈希算法
  2. (2) SHA-1160bit2017223日已被google实现碰撞。不安全了,不推荐使用。
  3. (3) SHA-2家族,包括SHA-224SHA-256SHA-384SHA-512四个哈希算法。
  4. (4) SHA-3,之前名为Keccak算法。
  5. SHA-3并不是要取代SHA-2,因为SHA-2目前并没有出现明显的弱点。由于对MD5出现成功的破解,以及对SHA-0SHA-1出现理论上破解的方法,NIST感觉需要一个与之前算法不同的,可替换的加密杂凑算法,也就是现在的SHA-3

3.小众系列

  1. 1RipeMD算法:针对MD4MD5算法缺陷分析提出的算法。这些算法主要是针对摘要值的长度进行了区分。
  2. RIPEMD160160bit,比特币地址的生成环节使用到。
  3. RipeMD算法和MAC算法系列相结合,有产生了HmacRipeMD128HmacRipeMD160两种算法。
  4. 2Tiger算法:号称最快的Hash算法,专门针对64为机器做优化了。其消息长度为192
  5. 3Whirlpool:被列入iso标准。与AES加密标准使用了相同的转化技术,极大提高了安全性,被称为最安全的摘要算法,长度为512
  6. 4Gost3411:信息摘要长度为256

这些算法的实现java6都没提供。这里BouncyCastle进行了支持。

4.Mac系列
全称 Message Authentication Code,也称为消息认证码(带密钥的Hash函数),通信实体双方使用的一种验证机制,保证消息数据完整性的一种工具。

  1. 常见如下:
  2. (1) HMACMD2
  3. HMACMD5
  4. (2) HMACSHA1
  5. HMACSHA256
  6. HMACSHA512
  7. (3) HMACRIPEMD160

抗碰撞性

看到这里的朋友很容易就为“文件在每个哈希算法计算后的哈希值唯一”这个论断表示质疑。的确,这种质疑是对的。因为这个“唯一”是一个大概率的唯一,而非绝对唯一。而这“大概率的唯一”就是哈希算法的“抗碰撞性”保证的。“大概率的唯一”是指在当前或者可预见未来的技术条件都极难以实现碰撞。拿MD5做例子。

MD5,常见的是128bit,即由128个0,1组成,这意味着只有(2的128次方)个01组合,或者说,MD5的值域中最多只能有(2的128次方)个文件不唯一,再多出一个文件都是会出现相同哈希值的另一个文件。显然,如果我们样本文件足够多,理论上完全可以超出(2的128次方)个文件的。但是如果你要找出一个文件的MD5值是和另一个相同,单从概率上来说,你的几率是1/(2的128次方)。这个概率有多小呢?你要知道地球的沙子颗粒数也才约(2的84次方)个而已啊!这意味着你要找出一个文件MD5哈希值和另一个文件相同的难度,远远比在地球上找出相同的两粒沙子难。这样类比,你应该就体会到要找出另一个文件的难度有多大了。类比MD5,你就可以容易理解SHA256\SHA512这些哈希算法的抗碰撞性有多强!

然而,再渺茫(低概率)的事件都有触发的可能,现在觉得不可能,是因为现在还没有找到对应的方法。

犹如MD5刚出来一段时间,大家都觉得极难触发碰撞事件,所以大家都很放心地使用。但是直到2005年,山东大学的王小云教授团队已经破解MD5!

再如SHA-1, 哈希值长达160bit,比MD5更抗碰撞,可是在2017年2月23日Google就全球宣告实现碰撞(传送门)!令人惊讶的是,google找出的碰撞文件居然是两个有意义的PDF文件!!震惊世界!致使当年密码学界顶级学术会议CRYPTO为之延期19小时,就是为了等待google的论文写完提交!!

应用

哈希函数,常常用于以下场景:

  1. 1.数据完整性验证:文章开头介绍的场景,就是个经典体现了。
  2. 2.数字签名:因为非对称加密算法速度较慢,所以在消息摘要上进行数字签名,在统计上可以认为与对文件本身进行数字签名是等效的
  3. 3.口令的安全性:仅将口令的哈希值进行保存,进行口令校检的时候仅需比对哈希值即可,即使攻击者获取了口令的哈希值,也无法计算出口令。

详细:我们进行web系统(BS,假设非https)开发时,用户模块中的登录尤为重要。通常做法是:用户填写登录表单提交,先通过浏览器的js脚本对密码明文进行一次哈希后传回到server。Server将接收到的密码哈希值再进行一次哈希后跟数据库中的预存密码对比,如果相同则登录成功。

Tips:
上述场景中,我们之所以对密码哈希后保存是不希望系统DB中直接存储用户密码明文,否则系统管理者或者是黑客攻破DB后就可以直接拿到密码明文了。

不过大家要注意,我们是需要进行两次哈希计算的,一次在客户端、一次在服务器端。很多朋友容易忽略服务器端的哈希计算、想当然地仅仅存了客户端哈希计算的结果入库。试想,如果一天黑客攻破了账户db拿到所有用户的密码哈希值,那么以后黑客就可以用此密码哈希值随意登录了。可是,如果多一个“服务器端的哈希计算”的话,即使黑客拿到db中的密码哈希值也没用,因为黑客传过来的哈希值会在服务器端再哈希计算一次,这样就跟DB里面的对应密码存储值完全不同了。于是黑客还是无法登录!

攻击方法

由前面,我们知道哈希函数结果只能保证“大概率唯一”。当样本足够多,理论上我们一定可以实现碰撞的。

于是就出现了以下的攻击方法:

字典法和暴力攻击:提前准备好科学的、足够的明文样本,一一计算(暴力穷举)各明文的哈希值后跟目标哈希值匹配,如果相同则攻破。这种方法最简单直接、可是得消耗极大的资源(注意,如果将来量子计算机投产,那么穷举破解只也是瞬间的事情)。
查表法:提前准备好科学的、足够的明文样本的哈希值样本,拿目标哈希值跟哈希样本匹配,如果相同则攻破。想尝试下? 传送门
反向查表法:首先攻击者构造一个基于密码-用户名的一对多的表,当然数据需要从某个已经被入侵的数据库获得,然后猜测一系列哈希值并且从表中查找拥有此密码的用户。通常许多用户可能有着相同的密码,因此这种攻击方式也显得尤为有效。
彩虹表一种在时间和空间的消耗上找寻平衡的破解技术。它和查表法很类似,但是为了使查询表占用的空间更小而牺牲了破解速度。因为它更小,于是我们可以在一定的空间内存储更多的哈希值,从而使攻击更加有效。能够破解任何8位及以下长度MD5值的彩虹表已经出现了(传送门)。(之所以起这个名字,是因为样本链表平行拼在一起,样子像彩虹)

加盐

如果你实践过上述传输门的话,你会发现通过查表法、彩虹表法破解哈希值其实不是难事。那么基于前文的“口令的安全性”场景,我们如何加固系统的账户密码模块呢?加盐哈希

查表法和彩虹表只有在所有密码都以相同方式进行哈希加密时才有效。如果两个用户密码相同,那么他们密码的哈希值也是相同的。我们可以通过“随机化”哈希来阻止这类攻击,于是当相同的密码被哈希两次之后,得到的值就不相同了。比如可以在密码中混入一段“随机”的字符串再进行哈希加密,这个被字符串被称作盐值。如同上面例子所展示的,这使得同一个密码每次都被加密为完全不同的字符串。为了校验密码是否正确,我们需要储存盐值。通常和密码哈希值一起存放在账户数据库中,或者直接存为哈希字符串的一部分。

  1. SHA-256做例:
  2. hash("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
  3. hash("hello" + "A*JKIO)()_") = 8ac5d763a76186008de6e2a3f23d16e7c405c0a9fd57a2bfb703da55e73e9214
  4. hash("hello" + "4ru890fdsklj+_") = e184172cb836660086ebeae7ce5e73f7d232ede6889121b707d217eb424bb5a4
  5. hash("hello" + "890=-kl32jk-") = e0b7d336eb0f3676d4b6b93d9fd66e8a631110de1edad76afad8b1f9d6e75c2a

显然,盐值的自身特点会直接影响哈希值破解的难度。盐值的产生,我们通常要保证“足够随机”的同时,也要保证“别用短盐值”。如果盐值太短,攻击者可以相对容易构造一个查询表包含所有可能的盐值。

其实,严格意义来说,盐值应该使用基于加密的伪随机数生成器(Cryptographically Secure Pseudo-Random Number Generator – CSPRNG)来生成。CSPRNG和普通的随机数生成器有很大不同,如C语言中的rand()函数。物如其名,CSPRNG专门被设计成用于加密,它能提供高度随机和无法预测的随机数。我们显然不希望自己的盐值被猜测到,所以一定要使用CSPRNG。常见编程语言中都会具备CSPRNG方法的,java中就是java.security.SecureRandom

意识误区

1)上文中的账户密码存储缺少“服务器端哈希计算”是个常见误区。

2)工程中,设计哈希、加密的环节,千万不要自己设计自己的随机、哈希、加密算法,更别以为“只要不让别人知道我的系统中使用的算法就行了”!!一定要用常见的、工业级、久经历史考验的算法! 记得柯克霍夫原则:数据的安全基于密钥而不是算法的保密。

  • 分享 收藏
2 条评论
  • bingo 联合创始人兼CTO 虫洞社区

    介绍的很齐全,各类hash算法都cover到了

    2018-10-26 15:34
  • 寒星 区块链应用开发 ppmoney

    @bingo
    谢谢评论,哈哈,简单写写而已。

    2018-10-25 09:52