Modern-CryptoⅦ Cryptographic Hash Functions


计算机科学上到处都是哈希函数,得益于哈希函数可以作为一种“压缩”的方式,进行诸如哈希表的构建。密码学上的哈希函数则要满足更多的性质。

Collision resistance

形式化:
对于H:{0,1}m{0,1}n,mn对任何的PPT算法,无法找到一个碰撞,或者说对多项式的寻找方式,xx,H(x)H(x),那么该函数抗碰撞。

m>n,则哈希函数必定会产生碰撞。只是对PPT敌手而言,只有极小概率能够找到碰撞。
可以看到,这里定义的哈希函数是unkeyed的,也因此是确定性的。然而,实际运用中,若要攻破这一哈希函数,便需要去找到一对碰撞,而碰撞的寻找是十分困难的。实际上,这里的unkeyed只是指H(k,x)中的k为公开常量,而非随机选定的意思。随机选定也就是我们之前讨论的PRF之类的了。

在密码学中的证明里,若结果依赖抗碰撞性,形式上我们考虑使用keyed哈希函数,实际上通常使用unkeyed哈希函数,并且同样能够满足抗碰撞。

Definition

Definition: Hash Functions

A hash Function with output length l is a pair of PPT algorithm (Gen,H) satisfying

  1. sGen(1n),|s|n,作为k,并为所有人可知。
  2. For a key s and x{0,1},H(s,x)output a string in {0,1}l(n) if the input x is restricted to |x|=l(n),l(n)l(n),Gen,H)is a fixed-length hash Function.

collision-finding experiment

  1. 生成密钥s。
  2. 敌手被给定密钥s,输出信息xx保证两者长度相同并符合上述定义。
  3. H(x)=H(x),则返回1,否则返回0.

Definition:collision resistant in orcacle

(Gen,H) is a collision resistant if for every PPT A PrsGen(1n)[A(s)(xx)H(s,x)=H(s,x)]negl(n)


weaker notions of security

  1. 第二原象性(Second-preimage or target-collision resistance):对于给定的s和随机的x,找到xx,H(s,x)=H(s,x)是极其困难的,
  2. 单向性(Preimage resistance or one-wayness) 给定s和y,y是H(s,x)的结果,找到x(不一定非要xx),H(s,x)=y

这是在更弱意义上的安全性。有了collision-resistance,这两个性质便都有了。若满足这两个小性质,便可以构造出单向函数。

Domain extension for CRHFs

如同先前一般,这里介绍通过操作模式进行扩展。

The Merkle Damgard transform

Chop input x with length L=|x| into B=Ln,并在最后一块添加0以填充。xB+1=L 有以下形式化: z0=IV,zi=h(zi1,xi) hB+1=H(x)

在这里,由于原消息填充后有被碰撞的可能,例如111||000和1110||00填充后相同,因此最后一块设为L用于防碰撞。
这种构造方式是十分普遍的。在实际的哈希构造方案中基本都用到了该构造方式:MD5,SHA-1,SHA-2。

MD transform collision resistant

if h is collision resistant, so is H.

对上述性质的证明过程,可以通过反证法,若H不满足该性质,则h也不满足抗碰撞。

顺带一提,我国密码学的王小云院士的一大工作便是找到杂凑(hash)函数的碰撞,也因她的工作,采用MD transform的MD5,SHA-1被证明是不安全的。实际运用中,最好采用SHA-2,或者不是MD transform形式的SHA-3算法。

Hash-and-MAC

有了hash函数后,对任意长度的明文m进行认证,可以采用“先对m进行hash,再对hash值进行mac计算”。MAC保证了攻击者无法对任何新的哈希值进行认证,而抗碰撞使攻击者无法找到对应的明文。


构造认证方案:
=(Gen,Mac,Vrfy)
Gen(1n)→<s(GenH(1n)),k(Gen)>
Mac<s,k>(m)=Mack(Hs(m))
Vrfy满足canonical条件。


New Construct

若原是安全的MAC,且H是抗碰撞的,则对任意长度的明文都是安全的MAC方案。

证明过程需要用到归约性证明,证明若敌手要攻破构造的方案,要么攻破MAC要么找到碰撞。

using Hash functions as MACs

在许多场合中,人们会错误的直接把密码学意义上的hash函数用于认证没有基本的密码学常识,这实际上是十分危险的。

Naivey**ng MAC:Mack(m)=H(k||m)

但用hash函数构造MAC是可行的:

Nested MAC(两密钥),若采用的哈希函数是PRF,则NMAC也是PRF,从而就是MAC。

顺带一提,NMAC原论文的h哈希函数默认直接带有PRF属性,所以直接使用了;但一般而言,h只是具有抗碰撞性质的哈希函数。
然而,现代的哈希函数基本都明确要求具有PRF属性,所以歪打正着,NMAC也能够保证安全性。

HMAC则是较为著名的一个方案了。它可以用于任意长度的消息,并用任意的哈希函数构造,较NMAC更加实用。

在HMAC之前,许多人不喜欢用CBC-MAC(太慢)而自己构造MAC,不能不说是一种安全性缺失。HMAC填补了这一漏洞。

Generic attacks on hash Functions

Birthday bound

看上去,对于哈希函数的攻击是十分困难的,最坏情况下要对所有的可能进行蛮力遍历才能得到一对碰撞。然而,生日悖论使攻击可能大大增强:

Birthday bound

若有q个独立均匀随机选取的元素从集合S中选取,|S|=N,则有: q(q1)4NPr[ij,yi=yj]q22N 对于不均匀的选取,第一个不等式成立。

因此,要保证对于q(n)问询的敌手,q(n)2/2<<1,即>2log(q(n))

meaningful collisions

由于有意义的句子里有许多固定格式,理论上而言,可以通过调整较少数量的词来达到缩小搜索空间,从而使攻击更加容易成立。

Small space birthday attacks

相比普通生日攻击,该方法通过两倍的查询来换取存储空间的O(1)复杂度。

Applications

random oracle model(随机预言机)

有几种基于密码学上的哈希函数的构造方案,单凭哈希函数的抗碰撞、单向性是无法完成安全的。
对此,如果想要重新寻找基于底层哈希函数的可证明安全方案,那么找到这类方案前便无法使用;而如果使用现有的密码系统,除了设计者试图攻击未果这一事实外没有任何理由证明其安全性,这是不可接受的。

于是,便有一种看起来“取巧”的方案,在严格的可证明安全和没有任何证明中的一种方法:引入一个理想化的模型来证明密码的安全性,而这就是随机预言机

有证明总比没有好对吧

随机预言机的定义:假设一个随机函数H:{0,1}{0,1}n,其只能够被任何人查询计算,即输入x返回H(x)

用另一种更加玄乎的话来说,在你给定输入前,随机预言机看起来像是完全均匀随机的函数(黑盒啊嗯),原文甚至将随机预言机比作“in the sky”,但你朝天空喊一句x,它就会给你确定的回应H(x),并且H(x)确定下来,无论你后面怎么输入给定的xH(x)都是唯一的回应。

什么b比喻

在构造方案时,证明使用RO(随机预言机),而实际构建方案时,RO用密码学意义上的哈希函数实例化。

可以看到,这是一种启发式的证明,但在实际出乎意料的好用。

另外,随机预言机满足“可编程性”,在归约性证明中可以选定均匀的输出值。

pseudorandom generator

设随机预言机H={0,1}n/2{0,1}n
则有Pry{0,1}n[AH()(y)=1]Prx{0,1}n/2[AH()(H(x))=1]=negl(n)

则H便是PRG。

pseudorandom Function

H={0,1}2n{0,1}n
Fk(x)=H(k||x)

则F便是PRF。

Collision resistant Hash Function

H={0,1}{0,1}n

其本身便可作为抗碰撞的哈希函数实例化。

以上所有的构造都用到了H(x)是uniform的性质,但没有可编程性。

RO

需要注意的是,RO的使用直至现在都存在着争议,有人认为它并不能代表完全的安全,也有人认为我们并没有完全了解RO的性质,可能会有隐藏的问题。

Fingerprinting and deduplication

哈希函数可用于病毒检测,另外,也可以用于云存储等。

Merkle tree

上文提到哈希可以用于云存储。用户只要保存了哈希值,便可以通过哈希值来查询得到对应的云文件,从而对文件进行下载验证等操作。若要高效进行,可以采用Merkle tree这种数据结构。

其构造方法通俗而言,Merkle tree除了叶子节点的tag是对文件的哈希值,其余节点的tag都是对子节点的哈希值。

Merkle tree

若其底层的哈希函数是抗碰撞的,那么具有固定文件数量的Merkle Tree也是抗碰撞的。

客户端存储根节点的哈希值,而服务器维护Merkle Tree以及文件。若客户端需要对应的文件,服务器可以将文件和其Merkle Tree路径外的其他子节点上的所有哈希值(空间复杂度O(log(n))发向客户端,以让客户端验证文件完整性。

MAC and Hash for message authentication

MAC和Hash都可以用于认证,区别为:

MAC要求通信双方在通信前共享密钥,而哈希函数虽然不用密钥的存储,但要求能够安全存储哈希值。

basic password protocol

谁的密码明文存储啊?

原来是CSDN啊

现实中对密码进行哈希操作已经是稀松平常了。具有抗碰撞性的哈希就是好用。

然而,由于许多人采用弱密码,可以用在线字典攻击(攻击者对用户清单统一尝试较少密码),也可以离线字典攻击(暴力查找H(w)=storaged password).
而batch离线字典攻击则假设敌手获取一整个存储密码的文件F,用事先准备的字典集合Dict对其进行离线字典攻击,这种方式更容易攻破其密码,时间复杂度为|Dict|+|F|

于是就有了public salt,也就是我们常说的加盐,即使在密码文件中公开存储盐值,也可以保证其时间复杂度大幅上升,攻击者必须遍历密码文件才能完成一次攻击尝试,于是时间复杂度为O(|Dict|×|F|)


回到对于密码的哈希:如果哈希函数,例如SHA1执行过快,也就是单步执行过快,计算机也能在可接受的时间内完成计算。

于是就有“慢”哈希函数,或者多次应用哈希函数来减慢速度;或者如之前已经叙述过的“加盐”,抑或是服务器辅助的方法(密码学老师似乎就是搞这方向的,还搞了两篇自己的论文放在PPT,乐)。


Author: ZzzRemake
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint policy. If reproduced, please indicate source ZzzRemake !
Comment
来发评论吧~
Powered By Valine
v1.4.18