哈希

31 12月
  • MD4,MD5(已淘汰)
  • SHA-1(已淘汰),SHA-2
  • SHA-3
  • (补充一)Keccak算法

1. 单向哈希函数(one-way hash function)(public-key cryptography)

将输入的内容计算出哈希值,以比对是否被篡改

发送者和接收者都会担心消息在发送过程中是否被坏人或者就是对方篡改过?因此需要用哈希值来验证消息的完整性,思路和日常生活中的合同一样,一式两份,然后比对两份合同是否一样。当然计算机数字化不需要保存完整的合同副本,太占用硬盘,只需要一个简单的哈希值就行。

单向哈希函数(one-way hash function),用于将输入的内容计算出哈希值,这个哈希值就是内容的“指纹”。而且还有以下特性:

  • 与内容的类型无关:输入的内容不仅可以是文本,也能是图像或音视频,哈希函数不关心内容的实际含义,全视作比特序列来处理。
  • 与内容的长度无关:无论输入1比特,还是100G,哈希函数都会计算出固定长度的哈希值。例如SHA-256,它计算出的哈希值永远是256比特(32byte)。
  • 单向性:只能用输入的内容计算出哈希值,但无法用哈希值还原出输入的内容。
  • 强抗碰撞性:哪怕输入的内容只被改动了1比特,也要生成出不同的哈希值。(碰撞collision是两个不同的输入产生相同哈希值,例如文件内是“转账1万”,攻击者改成“转账10万”,看看两者生成的哈希值是否相同,如果不同,继续改成“转账 10万”(中间加个空格)或“转账:10万”等,直到碰撞出与原文相同的哈希值)

单向哈希函数在现实中使用的场景很广,例如应用商店下载app,可以判断下载的app是否被镜像站点改动过。一次性口令,口令加密(Password Based Encryption,PBE),消息认证码,数字签名,伪随机数生成器,也用了单向哈希函数。

和公钥密码一样,无论是RSA算法还是单向哈希函数SHA-2/SHA-3,算法本身强度够高,但无法防止中间人攻击(man-in-the-middle attack),即攻击者伪造一份原文和哈希值发送给接收者,接受者能用哈希值判断原文是否被篡改过,但无法判断原文是否是发送者发送的,即原文是否是伪造的。防止中间人攻击需要对公钥使用证书。

1.1 MD4,MD5(已淘汰)

MD4,MD5都被找到了碰撞的方法,已结不够安全了。

(MD取自message digest的缩写)MD4由Rivest于1990年设计,能生成128比特的哈希值(RFC1320),次年又设计了MD5,同样能生成128比特的哈希值(RFC1321)。

1.2 SHA-1(已淘汰),SHA-2

SHA-1已经有碰撞攻击算法,已结不够安全了,不推荐使用。推荐使用:SHA-2(SHA-256,SHA-384,SHA-512)作为单向哈希函数

SHA-1(Secure Hash Algorithm)于1995年由NIST(National Institute of Standards and Technology,美国国家标准技术研究所)设计的单向哈希函数,能产生160比特哈希值。2005年山东大学的王小云教授团队提出了SHA-1的碰撞攻击算法,现在SHA-1已结被列入“可谨慎使用的密码清单”,不建议继续使用,仅作为兼容老系统可被使用。

SHA-256,SHA-384,SHA-512也是NIST设计的单向哈希函数,哈希值分别为256比特,384比特,512比特,它们也被统称为SHA-2,目前尚未收到针对SHA-2的有效碰撞。

1.3 SHA-3

推荐使用SHA-3(Keccak算法)作为单向哈希函数

SHA-3同AES一样,采用全球公开招标竞争的方式。2007年开始NIST对SHA-3公开征集算法,算法经过全球数学家密码学家进行评审,2010年共5个算法进入最终候选名单,2012年Keccak算法最终胜出成了SHA-3。Keccak算法有以下特点:

  • 采用了与SHA-1,SHA-2完全不同的海绵结构(sponge construction)
  • 结构清晰,易于分析
  • 适用于各种设备,包括嵌入式设备
  • 在硬件上表现出很高的性能
  • 比其他候选算法的安全性边际更大。在输入长度上限方面,SHA-1为2^64-1比特,SHA-2为2^128-1比特,SHA-3没有输入长度限制。在输出方面,为了配合SHA-2的哈希值长度,SHA-3规定了SHA-3-224,SHA-3-256,SHA-3-384,SHA-3-512这四个版本。

(补充一)Keccak算法

Keccak海绵结构中,输入的数据经过吸收阶段(absorbing phase)和挤出阶段(squeezing phase)生成输出的哈希值。

吸收阶段:将输入按每 r 个比特为一组进行分组,r 也被称为比特率(bit rate)。将分组与内部状态的 r 个比特进行 xor,结果作为函数f的输入,依次重复。函数f的作用是将输入的数据进行搅拌,输入的长度是 r+c 个比特,这意味着内部状态中有 c 个比特是不受输入分组内容的直接影响的,所以 c 也被称为容量(capacity)

挤出阶段:(吸收和挤出阶段的函数f是相同的)函数f的输出值中的 r 个比特保存为输出分组,并将整个输出值 r+c 个比特再次输入到函数f中,依次重复,直到获得所需长度的输出数据。挤出阶段实际执行的是:以比特率 r 个单位将海绵结构中的内部状态数据挤出来,就像挤出海绵中的水分一样。因此容量 c 的意义在于防止将输入消息中的一些特征泄露出去。

内部状态(state):是一个三维的比特数组,每个小方块代表1比特,共 b = r + c 个比特。为便于描述,将这个三维比特数组的内部状态分为:plane,slice,sheet,row,column,lane

根据Keccak的设计规格,SHA-3的内部状态为 b = 5 * 5 * 64 = 1600 个比特,即由 64 个 5* 5 的 slice 组成。

函数f共5个步骤:θ(theta),ρ(rho),π(pi),χ(chi),ι(iota),共循环 24 轮:

θ(theta):将位置不同的两个column中各自5个比特xor,然后与目标比特xor后覆盖掉目标比特:

ρ(rho):沿z轴lane方向进行比特平移

π(pi):对所有slice执行比特移动

χ(chi):对row进行进行xor操作

ι(iota):对整个state的所有比特进行xor,目的是让state具备非对称性

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注