计算机科学上到处都是哈希函数，得益于哈希函数可以作为一种“压缩”的方式，进行诸如哈希表的构建。密码学上的哈希函数则要满足更多的性质。
Collision resistance
形式化：
对于$H:\{0,1\}^m\rightarrow \{0,1\}^n,m\geq n$对任何的PPT算法，无法找到一个碰撞，或者说对多项式的寻找方式，$x\neq x’,H(x)\neq 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
- $s\leftarrow Gen(1^n),|s|\geq n$,作为k,并为所有人可知。
- For a key s and $x\in\{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)\geq l(n)$，Gen，H)is a fixed-length hash Function.
collision-finding experiment
- 生成密钥s。
- 敌手被给定密钥$s$，输出信息$x$，$x’$保证两者长度相同并符合上述定义。
- 若$H(x)=H(x’)$，则返回1，否则返回0.
Definition:collision resistant in orcacle
(Gen,H) is a collision resistant if for every PPT $\mathcal{A}$ $$Pr_{s\leftarrow Gen(1^n)}[\mathcal{A}(s)\rightarrow(x\neq x')\land H(s,x)=H(s,x')]\leq negl(n)$$
weaker notions of security
- 第二原象性(Second-preimage or target-collision resistance)：对于给定的s和随机的x，找到$x’\neq x,H(s,x)=H(s,x’)$是极其困难的，
- 单向性(Preimage resistance or one-wayness) 给定s和y，y是$H(s,x)$的结果，找到$x’$（不一定非要$x\neq x’$），$H(s,x’)=y$
这是在更弱意义上的安全性。有了collision-resistance，这两个性质便都有了。若满足这两个小性质，便可以构造出单向函数。
Domain extension for CRHFs
如同先前一般，这里介绍通过操作模式进行扩展。
The Merkle Damgard transform
Chop input x with length $L=|x|$ into $B=\lceil \frac{L}{n}\rceil$,并在最后一块添加0以填充。$x_{B+1}=L$ 有以下形式化： $z_0=IV,z_i=h(z_{i-1},x_i)$ $h_{B+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保证了攻击者无法对任何新的哈希值进行认证，而抗碰撞使攻击者无法找到对应的明文。
构造认证方案：
$\prod’=(Gen’,Mac’,Vrfy’)$
$Gen’(1^n)\rightarrow <s(Gen_H(1^n)),k(Gen)>$
$Mac_{<s,k>}'(m)=Mac_k(H^s(m))$
$Vrfy$满足canonical条件。
New Construct
若原$\prod$是安全的MAC，且$H$是抗碰撞的，则$\prod'$对任意长度的明文都是安全的MAC方案。
证明过程需要用到归约性证明，证明若敌手要攻破构造的方案，要么攻破MAC要么找到碰撞。
using Hash functions as MACs
在许多场合中，人们会错误的直接把密码学意义上的hash函数用于认证没有基本的密码学常识,这实际上是十分危险的。
$Naive$y**ng MAC：$Mac_k(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$，则有： $$\frac{q(q-1)}{4N}\leq Pr[\exists i\neq j,y_i=y_j]\leq\frac{q^2}{2N}$$ 对于不均匀的选取，第一个不等式成立。
因此，要保证对于q(n)问询的敌手，$q(n)^2/2^\ell<<1$，即$\ell>2log(q(n))$
meaningful collisions
由于有意义的句子里有许多固定格式，理论上而言，可以通过调整较少数量的词来达到缩小搜索空间，从而使攻击更加容易成立。
Small space birthday attacks
相比普通生日攻击，该方法通过两倍的查询来换取存储空间的$O(1)$复杂度。
Applications
random oracle model(随机预言机)
有几种基于密码学上的哈希函数的构造方案，单凭哈希函数的抗碰撞、单向性是无法完成安全的。
对此，如果想要重新寻找基于底层哈希函数的可证明安全方案，那么找到这类方案前便无法使用；而如果使用现有的密码系统，除了设计者试图攻击未果这一事实外没有任何理由证明其安全性，这是不可接受的。
于是，便有一种看起来“取巧”的方案，在严格的可证明安全和没有任何证明中的一种方法：引入一个理想化的模型来证明密码的安全性，而这就是随机预言机。
有证明总比没有好对吧
随机预言机的定义：假设一个随机函数$H:\{0,1\}^*\rightarrow\{0,1\}^n$，其只能够被任何人查询计算，即输入$x$返回$H(x)$。
用另一种更加玄乎的话来说，在你给定输入前，随机预言机看起来像是完全均匀随机的函数(黑盒啊嗯)，原文甚至将随机预言机比作“in the sky”,但你朝天空喊一句$x$，它就会给你确定的回应$H(x)$,并且$H(x)$确定下来，无论你后面怎么输入给定的$x$，$H(x)$都是唯一的回应。
什么b比喻
在构造方案时，证明使用RO(随机预言机),而实际构建方案时，RO用密码学意义上的哈希函数实例化。
可以看到，这是一种启发式的证明，但在实际出乎意料的好用。
另外，随机预言机满足“可编程性”，在归约性证明中可以选定均匀的输出值。
pseudorandom generator
设随机预言机$H=\{0,1\}^{n/2}\rightarrow \{0,1\}^n$
则有$Pr_{y\leftarrow \{0,1\}^n}[\mathcal{A}^{H(\cdot)}(y)=1]-Pr_{x\leftarrow \{0,1\}^{n/2} }[\mathcal{A}^{H(\cdot) }(H(x))=1]=negl(n)$
则H便是PRG。
pseudorandom Function
$H=\{0,1\}^{2n}\rightarrow\{0,1\}^n$
$F_k(x)=H(k||x)$
则F便是PRF。
Collision resistant Hash Function
$H=\{0,1\}^*\rightarrow\{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|\times|F|)$
回到对于密码的哈希：如果哈希函数，例如SHA1执行过快，也就是单步执行过快，计算机也能在可接受的时间内完成计算。
于是就有“慢”哈希函数，或者多次应用哈希函数来减慢速度；或者如之前已经叙述过的“加盐”，抑或是服务器辅助的方法（密码学老师似乎就是搞这方向的，还搞了两篇自己的论文放在PPT，乐）。
