单向散列函数

单向散列函数能够根据任意长度的消息计算出固定长度的散列值，通过对比散列值可以判断两条消息是否一致，这种技术可用来辨别篡改。

SHA-3的具体实现方法。

针对单向散列函数的工具：暴力破解和生日攻击。

使用单向散列函数可以辨别篡改，但无法分辨伪装。要解决这个问题，需要使用消息认证码和数字签名。

介绍

单向散列函数（one-way hash function）有一个输入和一个输出，输入为消息（message），输出为散列值*（hash value）。

单向散列函数可以根据消息内容计算出散列值，散列值可用来检查消息的完整性。

如下图所示，用来检验文件完整性。

消息可以是图像文件或音频文件，也可以是无法识别的二进制数据，单向散列函数会将其作为单纯比特序列来处理，无需知道消息的实际含义。

散列值的长度和消息长度无关。无论1bit、1Mb或者1Gb的数据，单向散列函数都会计算出固定长度的散列值。

SHA-256单向散列函数始终生成32字节的散列值。

性质

散列值长度固定

单向散列函数的输入消息可以是任意长，但生成的散列值最好是短而且固定的。

快速计算

计算散列值所花费的时间必须短。

抗碰撞性

密码技术中所使用的单向散列函数都需要具备抗碰撞性。

单向性

无法通过散列值反算出消息的性质。

术语

单向散列函数也称为消息摘要函数（message digest function）、哈希函数或杂凑函数。

单向散列函数输入的消息也成为原像（pre-image）。

单向散列函数输出的散列值也成为消息摘要（message digest）或者指纹（fingerprint）。

完整性也称为一致性。

常见算法

SHA-3

Keccak

Keccak是一种被选定为SHA-3标准的单向散列算法。

Keccak可以生成任意长度的散列值.

SHA-3没有输入长度限制。

海绵结构

Keccak采用了与SHA-1、SHA-2完全不同的海绵结构（sponge construction）。

Keccak的海绵结构中，输入的数据先要进行填充，之后要经过吸收阶段（absorbing phase）和挤出阶段（squeezing phase），最终生成输出的散列值。

吸收阶段

1. 将经过填充的输入消息以 $r$ 个比特为一组，分割为若干个输入分组。
2. 将“内部状态的 $r$ 个比特”与“输入分组 $1$ ”进行 $\bigoplus$，其结果作为“函数 $f$ 的输入值”。
3. 将“函数f的输出值 $r$ 个比特”与“输入分组 $2$ ”进行 $\bigoplus$，其结果再次作为“函数 $f$ 的输入值”。
4. 反复执行上述步骤，直到到达最后一个输入分组。
5. 所有输入分组处理完成后，进入挤出阶段。

函数 $f$ 的作用是将输入的数据进行复杂的搅拌操作并输出结果，其操作对象是长度为 $b = r + c$ 个比特的内部状态，内部状态的初始值为 $0$ 。

比特率（bit rate）：每次被吸入的输入分组长度为 $r$ 个比特，因此 $r$ 被称为比特率。

容量（capacity）：函数 $f$ 的输入长度不是 $r$ 个比特，而是 $r + c$ 个比特，这其中 $c$ 个比特是通过函数 $f$ 来影响输出结果的。 这里的 $c$ 被称为容量，其意义在于防止将输入消息的一些特征泄露出去。

挤出阶段

1. 将“函数 $f$ 的输出值中的 $r$ 个比特”保存为“输出分组 $1$”，并将整个输出值（$r + c$ 个比特）再次输入到函数 $f$ 中。
2. 将“函数 $f$ 的输出值中的 $r$ 个比特”保存为“输出分组 $2$”，并将整个输出值（$r + c$ 个比特）再次输入到函数 $f$ 中。
3. 反复执行上述步骤，直到获得所需长度的输出数据。

内部状态

Keccak中 $b= r + c$ 个比特的内部状态是通过函数 $f$ 进行变化的。

Keccak的内部状态是一个3维比特数组，如下图所示。 图中的每个小方块代表 $1$ 个比特，$b$ 个小方块按照 $5 \times 5 \times z$ 的方式组合起来，就称为一个沿 $z$ 轴延伸的立方体。

因此可以将state看作是由 $5 \times 5 = 25$ 条lane构成的，也可以看作是由与lane的长度相同数量的slice堆叠而成。

Keccak的本质就是实现一个能够将上述结构的state进行有效搅拌的函数 $f$，这与分组密码的搅拌过程非常相似。

函数Keccak-f[b]

该函数时用来对内部状态进行搅拌的，其携带的参数 $b$ 就是内部状态的比特长度。这里称为宽度。

根据Keccak的设计规格，宽度 $b$ 的取值有 $25,50,100,200,400,800,1600$ 共$7$种值，这$7$个数字都是$25$整数倍，分别是$1,2,4,8,16,32,64$倍。

slice的大小为 $5 \times 5 =25$ 个比特，因此 $\frac{b}{25}$ 即为slice的片数，或者lane的长度。

SHA-3 采用的是其中的最大宽度，即 $b=5 \times 5 \times 64=1600$。

在Keccak中，可以通过改变宽度$b$就可以改变内部状态的比特长度。 但无论如何改变，slice的大小依然是$5 \times 5$，改变的只有lane的长度而已，因此Keccak宽度的变化并不会影响其基本结构。

Keccak-f[b]中的每一轮包含了5个步骤：$\theta, \rho, \pi, \chi, \iota$，总共循环$12+2\tau$轮。Keccak的设计规格中规定: $$ 2^{\tau} = \frac{b}{25} $$ 因此SHA-3中所使用的Keccak-f[1600]函数，其循环轮数为$24$轮。

步骤 $\theta$

将位置不同的两个column中各自$5$个比特通过XOR运算加起来，然后再与置换目标比特求XOR，最后覆盖目标比特。

步骤 $\rho$

沿 $z$ 轴（lane方向）进行比特平移。

步骤 $\pi$

对整条lane上的所有slice执行相同的比特移动操作。

步骤 $\chi$

对row应用如下操作，其中分别为NOT、AND以及XOR操作。

步骤 $\iota$

用固定的轮常熟对整个state的所有比特进行XOR运算，目的是让内部状态具备非对称性。

攻击

MD结构：通过循环执行压缩函数的方式来生成散列值，应用于Keccak之前的单向散列函数，例如MD4、MD5、RIPEMD、RIPEMD-160、SHA-1以及SHA-2。

为了规避SHA-1的风险，SHA-2应运而生，但是SHA-2是基于和SHA-1相同的MD结构，问题没有得到根本性的解决。

Keccak采用了和MD结构完全不同的海绵结构，因此针对SHA-1的攻击方法对Keccak是无效的。

用途

检测软件是否被篡改

很多软件都会把通过单向散列函数计算出的散列值公布在自己的官网上，用户在下载软件之后，可以自行计算散列值，然后与官方网站上公布的散列值进行对比。

通过散列值，用户可以确认自己所下载到的文件与软件作者所提供的文件是否一致。

基于口令的加密

单向散列函数也被用于基于口令的加密（Password Based Encryption, PBE）。

PBE的原理是将口令和盐（salt，通过伪随机数生成器产生的随机值）混合后计算其散列值，然后将这个散列值用作加密的密钥。

PBE可以防御针对口令的字典攻击。

消息认证码

使用单向散列函数可以构造消息认证码。

消息认证码是将“发送者和接收者之间的共享密钥”和“消息”进行混合后计算出的散列值。

使用消息认证码可以检测并防止通信过程中的错误、篡改以及伪装。

数字签名

数字签名的处理过程非常耗时，因此一般不会对整个消息内容直接施加数字签名，而是先通过单向散列函数计算出消息的散列值，然后再对这个散列值施加数字签名。

伪随机数生成器

一次性口令

攻击

暴力破解

根据已有消息的散列值，来寻找具备相同散列值的另一条不同的消息。相当于破解单向散列函数的“弱抗碰撞性”的攻击。

生日攻击

攻击者生成散列值相同的两条消息，第一条消息用于发送者计算散列值，第二条消息用于替换。这是破解单向散列函数的“强康碰撞新”的攻击。

生日问题

在 $N$ 个人中，只要有两个人生日一样的概率大于二分之一，那么 $N$ 至少最小是多少？

$N$ 个人生日全都不一样的概率为 $$ \frac {365 \times 364 \times … \times (365-N+1)}{365^N} $$

因此概率为 $$ 1 - \frac {365 \times 364 \times … \times (365-N+1)}{365^N} = 1 - \frac{365!}{365^N(365-N)!} $$ 当 $N=23$ 时，该值约为 $0.507297$ 。

这种现象称为生日悖论。

任意 $N$ 个人中两个人生日相同的概率和 $N$ 个人中和指定一人生日相同的概率不是同一个问题。

问题

单向散列函数能够辨别出“篡改”，无法辨别出“伪装”。

如果第三方攻击者，伪装成发送者，将消息和哈希值发送给接收者，接收者通过单向散列函数验证也没有问题。因此，不仅需要确认文件的完整性，还需要对发送者进行认证。

认证的技术包括消息认证码和数字签名。