密码技术之单向散列函数

单向散列函数（one-way hash function）,也称为消息摘要函数（message digest function）、哈希函数、杂凑函数，是指输入消息（message）输出散列值（hash value）,用于消息的完整性（一致性）检查。

它有啥特点：

1，根据任意长度的消息计算出固定长度的散列值。

2，能够快速计算出散列值。

3，输入消息不同，散列值也不同。

4，单向性。通过散列值无法还原出消息。

它有啥应用：

比如：

基于口令的加密（Password Based Encryption,PBE）,通过口令和salt计算散列值，用于加密的密钥，防止针对口令的字典攻击。

消息认证码可以检测篡改和伪装。

数字签名用于是指计算出消息的散列值，然后对其签名。

一次性口令，常用于服务器对客户端的合法性认证，通过使用散列函数保证口令在通信链路上只传输一次，即使泄露了口令，也无法使用。

有那些单向散列函数呢？

1，MD4被外国人、MD5已经被我国王小云院士碰撞攻击算法攻破了，不安全了。

2，SHA-1、SHA-2(SHA-256、SHA-384、SHA-512)，当然SHA-1也是在2005年被王院士攻破了，虽然SHA-2还没被攻破。

3，SHA-3，在05年SHA-1被强碰撞性被攻破的情况下，NIST(美国国家标准技术研究所)开始制定了下一代SHA-3的标准工作，2012年keccak算法成为SHA-3。

由于之前的单向散列函数都是通过循环执行压缩函数的方法来生成散列值，keccak是一种海绵结构因此传统攻击方法无效。

keccak的设计者之一Gilles Van Assche大神，在Github上的主页：https://github.com/gvanas

看一看keccak的设计思路吧：

先看一看Hash(n, M, N, H)参数

散列位大小 (n)是指SHA3的散列值长度有224、256、384、512四种。

消息文本M：输入消息。

N：消息摘要的长度bit大小。

哈希变量H：输出。

keccak是一种海绵结构。对输入数据填充经过absorbing phase吸收和squeezing phase挤出两个阶段，最终输出散列值。还有一种变体双工结构。

1，将填充后的输入消息，按照r个bit为一组进行分割成若干个输入分组。现在要每个分组的r的比特，吸收进海绵中，然后挤出，如何进行？

将输入分组1，与初始值为0的内部状态的r个比特进行异或运算，其结果作为函数f的输入值。

将函数f的输出值r个比特再与输入分组2进行异或。反复执行，直到最后一个输入分组，结束吸收阶段，进入挤出阶段。

函数f的输入输出长度都是b=r+c，这里面的c是不受输入分组直接影响，但会到函数f的间接影响。r被称为比特率，c被称为容量，主要是用于防止消息内部特征泄露。

2，函数keccak内部状态是一个三维比特数组，5*5*b个比特组成的数组，这个参数就是b,也就是内部状态的比特长度。

SHA3采用的b=1600,1600是25的整数倍(2的6次方64倍)。keccak-f[b]的每一轮包含5个步骤。实质上就是对各个比特位进行运算，详细情况可以Google。

攻击途径：

1，暴力破解，利用文件冗余性生成具有同一散列值的另一个文件，暴力破解需要尝试的次数根据散列值长度技术出来，比如SHA3-512，需要尝试2的512次方，现实中是不可能完成了。找出具有指定散列值的消息攻击分为2种，pre-image attack是指给定一个散列值，找出具有该值的任意消息。second pre-image attack是指给定消息1，找到和消息1散列值相同的消息2。

2，生日攻击（birthday attack），暴力破解是指找到特定生成散列值的消息，生日攻击是找到散列值相同的两条消息，散列值可以是任意值。举例来说暴力破解是已有文本的散列值，找到相同散列值的文本进行替换。生日攻击是事先准备好两份散列值相同的消息，将消息进行替换。也可以这样理解，两个人的生日都是某个特点日期可能性确实不高，但是找到“只要有2个人生日日期相同，不管哪一天都可以”的话，可能性却很高。

最后，单向散列函数虽然能辨别出“篡改”但无法解决消息的发送者伪装问题，还需要进行认证。

本文为安智客之前的一篇读书笔记！