【信息保护论】Ch7.加密加固：单向散列函数

单向哈希函数

Hash（散列值）函数又称哈希函数。

针对CIA系统中的完整性，确保这个文件是真的这个文件是否被篡改。前面说过的再传送攻击以及中间人攻击等，本质都是伪造数据并令接收人认为是正确数据，从而达到一些企图。

当我们编辑完一个文件然后关机睡觉起床，再打开这个文件，请问这个文件真的是昨天的文件吗，还是其他人伪造的这个文件？如何判别？
最简单的方法是：当我们编辑完这个文件，我将其复制一份到我的硬盘上并拔下硬盘，然后第二天我比较硬盘中的数据与计算机中的数据是否一致。这里硬盘就是安全的场所。想要验证完整性，最好的方法就是将想要确保安全性的物品保存到一个安全的场所，然后在需要检验时，从安全的场所中取出来进行比对，因为我认为这个场所是安全的，所以我默认其是真的，与之不同则认定是为假的。也就是说，本质上这种方法只能验证出数据是否发生过改变，但是断言说真与假就过于片面。

说到真伪的判断，不得不得提指纹了。假设有一个犯罪嫌疑人，与其相当相近的身材外貌出现在监控上，当我们想要调查他时，由于监控不清楚，我们比着监控看人和比对现场的指纹和他的指纹，肯定是后者更容易。后者具备指纹编写，验证方便，且不可否认（你说你没有，但是凶器上有你的指纹，这就是证据，想要推翻这个证据需要新的证据，如果无法提供则将认定其供词为假）。那么作为数据文件，能否有文件的[指纹]来方便我们进行操作呢？

哈希函数：可以成为文件的指纹来提供验证完整性。我们将昨天的文件通过哈希函数转化为哈希值后，与今天的文件通过同一个哈希函数转换成的哈希值进行数据比较，如果二者相同则认定昨天的文件就是今天的文件，至少他们数据没有被改变，但是持有者是可能不同的。哈希函数可以当做文件的指纹，你当然持有你的指纹，但并不意味着除你以外的人就不持有你的指纹，是哈希函数的风险所在。

简单的哈希函数例子：我们将一个输入除以23，并将其小数位第7~10位作为哈希函数值。则345689的哈希值是7391，因为他们的商是15029.95652173913043…

单方向哈希函数one-way hash function：单方向哈希函数是指通过哈希函数将输入变为输出后，利用输出反向推理出输入非常困难的函数。单方向哈希函数是后文要讲解的几项认证技术与密码技术的基础。
特点：

1. 输入与输出的长度无关联，任意长度的输入 可以输出任意长度的输出。标准是不同的哈希函数。
2. 哈希函数的输出往往是固定的，同一个哈希函数（SHA-1为例），不论输入是多少bit，输出固定为160bit。
3. 哈希值运算过程是高速的。给定输入计算出输出虽然高速，但是输入位数越多，运算时间自然会变长。
4. 信息不同，哈希值不同，具有单方向性，只要输入变动，输出一定会变动，但变动频率等特点不会反映到彼此上。即便输入只变更了1bit数据，输出也极大可能截然不同。

抗碰撞特性Collision Resistance

碰撞（Collision):不同的输入，经过哈希函数后得到了相同的输出。
抗碰撞特性（Collision Resistance）：发现碰撞的概率非常小的性质。即H(x)=H(y),已知H（x）的情况下找到一个y非常难的性质。

• Preimage Resistance: 想要找到关于y=H（M）的M从算术上不可能
• 2nd Preimage Resistance: 想要找到满足H（x）=H（y）且x≠y的y非常困难
• Collision Resistance:想要找到满足H（x）=H（y）且x≠y的y从算术上不可能。换言之具有强单方向性。
• 单方向性：从输入计算输出非常简单，但是从输出计算输入却非常困难，无法通过哈希值逆算原信息的性质。

哈希函数中的一些用语：

应用的例子：

1. 自己入手的软件是否被篡改的验证。 单位中的应用软件通过哈希函数生成哈希值并保存到移动硬盘上，下班上班后，要确认自己企业电脑中的应用程序是否被修改过数据，此时可以使用将当前状态下的应用程序用哈希函数输出一个哈希值与自己移动硬盘中的比较，对比结果即可知道数据是否被修改过。
2. Password Based Encryption（PBE）：以密码为基础的加密。在PBE中将password和salt混合后通过哈希输出哈希值，并把这个哈希值当做加密的密钥。可以防止密码字典攻击。
3. 信息认证代码MAC：目前在SSL和TLS中使用。通信过程中可以检测出伪造，将明文和密钥混合后输出哈希值来使用。
4. 数字签名：为了简化签名过程，将明文用哈希值来替代，然后将这个哈希值进行数字签名来验证。
5. 伪随机数生成器：需要通过满足之前的随机数列不能在现实意义上被用来推测出未来的随机数列的性质，为了保证这个性质的实现，需要使用单方向哈希函数。
6. One time password:一次性密码。企业中用来验证是否是真正的客户，即便该密码泄露也无法被恶意使用。
   Ps)23456项是问本文后面的重点，因此在这里不过长的叙述。

哈希函数发展史

哈希函数面临的攻击

1. 暴力解码：哈希函数不是加密算法，因此这个暴力解码与加密算法中的不同。来看下面一个例子：

由于买卖，A想要给B转账十万元并写下了电子合同。该信息被黑客截获，黑客现在中断了A与B的通信，想要修改金额，将十万元给修改成一亿元。此时，黑客会通过机械来生产大量同义句，如
A给B的支付金额是一亿元
A给B的支付金额是一亿圆
A给B的支付金额是壹亿元
A给B的支付金额是壹亿圆
A给B的支付金额是￥100000000
A给B的支付金额是￥100,000,000
…
这些句子都是一个意思，然后用这些句子生产的哈希值与原转账十万元比较，直到输出一个与原文相同的哈希值，将二者替换，就能够达成目的了。这也是暴力解码的一种方式。这种方式并不是通过输出去反向算出输入，并没有本质上破解哈希函数，而是破坏了合同本身，其实目的不在于置换的内容如何，只要我用一个随机内容生成了对应相同的哈希值，我就可以破坏AB二人之间的正常交易。

2. 生日攻击：利用生日问题引申出的攻击手段。先来看生日问题。

除去2.29，N人中有两个人生气相同的个概率是多少?为了让任意两人生日相同的概率大于50%，应该至少有多少人？

N=23时，这个式子的值为0.507297。因此，只要23个人就可以，是不是比想象中要少得多。

所以生日攻击也是运用这道理。黑客生成N个十万元合同和N个亿元合同，比较这两个合同的哈希值，找到两边有相同的时，将亿元合同代替对应的十万元合同并伪造成A发给B的。这个过程就是生日攻击。N越大则生日攻击越难成功,N越小则生日攻击越容易成功。假定A的单方向哈希函数的位数是M，Mbit的所有二进制数组空间是2^M个，N≈$\sqrt{2^M}=2^{\frac{M}{2}}$,也就说当N=$2^{\frac{M}{2}}$时，黑客就有50%以上的概率能够成功生日攻击。也就说对于SHA-1，只需要计算机有能力实行$2^{80}$次生日攻击，就有50%以上的概率找对对应哈希值，虽然现在计算机力已经能够达到，但在20世纪初期这一度被认为是天文数字。

哈希函数无法解决的问题：虽然哈希函数可以鉴出数据是否被变更，但是无法鉴定该数据本身是否来源不正当，也就说无法鉴别真伪。因此就需要导入认证技术，其中最典型的两项技术是数字签名和MAC。