哈希函数学习笔记

2023-10-27

一、哈希函数的定义

哈希函数(Hash Function)是一公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值H(M)，又称为散列函数、杂凑函数.我们称函数值H(M)为哈希值、杂凑值、杂凑码、或消息摘要。

杂凑值是消息中所有比特的函数，因此提供错误检测能力。消息中任何一个比特或者几个比特的改变都会造成杂凑值的改变。

二、哈希函数的性质

可作用于任意长度的数据块（实际上是不是任意，比如SHA-1要求不超过2的64次方）
产生一个固定长度的输出（e.g., SHA-1的输出为160比特，SHA-256的输出是256比特）
给定任意x，H(x)的计算比较容易
单向性（也成为抗原像性，one-wayness/Preimage Resistance）。：给定哈希值不可能产生对应的消息。对于任意给定的消息，计算其哈希值容易.但是，对于给定的哈希值h，要找到M使得H(M)＝h在计算上是不可行的。e.g., C=<M, H(M||K)>
弱抗碰撞（抗二次原像，weakly collision-free）:给定的消息的哈希值不能找到与之相同的另外的消息（完整性，防止伪造）。给定消息x，y，使得H(x)=H(y)在计算上是不可行的。
强抗碰撞（strongly collision-free）:对于任意消息x，y，H(x)=H(y)在计算上是不可行的。也就是对于已知的生日攻击方法（一种针对哈希函数的攻击手段，通过利用生日悖论来增加找到碰撞的概率）的防御能力。强抗碰撞包含弱抗碰撞。

总结：密码学上安全的哈希函数H应该包含的性质：①对于任意的消息x，计算H(x)是容易的。②H是单向的③H是强抗碰撞的

三、哈希函数的常见攻击方法

1. 穷举攻击

原像攻击（preimage attack）和第二原像攻击(second preimage attack)

对于给定的哈希值h，试图找到满足H(x)=h的x。对于m位的哈希值，穷举的规模大约是2^m.

原像攻击的目标是从已知的哈希值中找到对应的输入。在原像攻击中，攻击者已经获得了特定的哈希值，然后尝试找到产生该哈希值的输入。这种攻击可以看作是一种逆向工程，攻击者试图通过逆向计算来还原哈希函数的输入。原像攻击是对哈希函数的强抗原像性（Preimage Resistance）的挑战。（对应于单向性）

第二原像攻击的目标是在已知输入的情况下，找到另一个具有相同哈希值的不同输入。与原像攻击不同的是，第二原像攻击假设攻击者已经获得了一个特定的输入，并且试图生成另一个具有相同哈希值的不同输入。这种攻击是对哈希函数的强抗第二原像性（Second Preimage Resistance）的挑战。（对应于弱抗碰撞）

哈希函数的强抗原像性要求从哈希值推导出原始输入是计算上不可行的，而强抗第二原像性要求在已知输入的情况下找到具有相同哈希值的不同输入同样是计算上不可行的。

碰撞攻击（collision reresistance）

找到两个消息x ≠ y,满足 H(x) = H(y)；对于m位的哈希值，预计在2^{m/2}次尝试之后就将找到具有相同哈希值的数据。

总结：对于m位的哈希值，抗穷举攻击的强度为2^{m/2}（目前128比特已经不够, 需要160比特甚至更多.）

2. 生日攻击

3. 其他攻击

利用算法的性质进行攻击、哈希函数使用迭代结构（将消息分组之后再处理）、密码分析的攻击集中于压缩函数f的碰撞。

四、哈希函数的构造方法

1. 基于数学难题的构造方法

如MASH-1, MASH-2, 涉及模乘/平方运算，计算速度慢，不实用。

2. 基于对称密码体制的构造方法

分组密码的工作模式是：根据不同的数据格式和安全性要求，以一个具体的分组密码算法为基础构造一个分组密码系统的方法.基于分组的对称密码算法比如DES/AES算法只是描述如何根据秘钥对一段固定长度(分组块)的数据进行加密，对于比较长的数据，分组密码工作模式描述了如何重复应用某种算法安全地转换大于块的数据量.

简单的说就是，DES/AES算法描述怎么加密一个数据块，分组密码工作模式模式了如果 重复加密比较长的多个数据块. 常见的分组密码工作模式有五种：电码本( Electronic Code Book， ECB)模式、密文分组链接(Cipher Block Chaining，CBC)模式、密文反馈(Cipher Feed Back ， CFB)模式、输出反馈(Output Feed Back ，OFB)模式和计数器(Counter, CTR)模式.

(1) ECB:

加密：输入是当前明文分组。 $C_n=E_K[P_n]$

解密：每一个密文分组分别解密。 $P_n=D_k[C_n]$

(2) CBC:

加密：输入是当前明文分组和前一次密文分组的异或. $C_n=E_K[C_{n-1} \oplus P_n]$

解密：每一个密文分组被解密后，再与前一个密文分组异或得明文. $P_n=D_k[C_n] \oplus C_{n-1}$

在CBC模式中，每个明文数据块与前一个加密后的数据块进行异或运算，然后再进行加密。这种运算方式将前一个密文块的影响传递到当前块，增加了密码算法的非线性性，提高了安全性。

下面是CBC模式的基本工作流程：

将明文数据划分为固定长度的数据块（通常为64位或128位）。
选择一个初始向量（Initialization Vector, IV），它是一个随机的、与明文数据块长度相同的值。
对第一个数据块进行异或运算：将初始向量与第一个明文数据块进行异或操作。
将异或运算的结果作为输入，使用加密算法（如AES、DES等）对数据块进行加密，生成第一个密文数据块。
对后续的数据块进行同样的操作：将前一个密文数据块与当前明文数据块进行异或运算，然后再进行加密。
重复步骤5，直到所有数据块都被加密。
最后一个加密后的数据块即为CBC模式的输出密文。

解密时，需要使用相同的密钥和初始向量进行解密操作。解密的过程与加密过程相似，只是解密后的结果需要与前一个密文数据块进行异或运算来恢复原始明文数据块。

CBC模式的主要特点是每个数据块的加密都依赖于前一个数据块的密文，因此在传输和存储数据时，需要保持初始向量的机密性和完整性，以防止攻击者破坏密文的完整性。

总的来说，CBC模式通过使用初始向量和异或运算增加了密码算法的非线性性，提高了加密的安全性。它广泛应用于各种加密协议和应用中，如TLS/SSL、IPSec等。

(3) CFB

加密算法的输入是64比特移位寄存器，初值为某个初始向量IV。
加密算法输出的最左(最高有效位)j比特与明文的第一个单元P1进行异或，产生出密文的第1个单元C1，并传送该单元。
然后将移位寄存器的内容左移j位并将C1送入移位寄存器最右边(最低有效位)j位.  这一过程继续到明文的所有单元都被加密为止

(4) OFB

与CFB类似，不同点：①OFB模式是将加密算法的输出反馈到移位寄存器 ② CFB模式中是将密文单元反馈到移位寄存器

(5) CTR

加密：输入是当前明文分组和计数器密文分组的异或. $C_i=E_K[\mathsf{VI}||CTR_i] \oplus P_i$

解密：每一个密文分组被解密后，再与计数器密文分组异或得明文 $P_i=E_K[\mathsf{VI}||CTR_i] \oplus C_i$

与CBC的比较：

CTR加了一个随机数nonce，分组密文是将nonce和计数器i连接之后的字符串进行加密，再和明文分组取抑或。

分组密码工作模式的比较

ECB模式，简单、高速，但最弱、易受重发攻击，一般不推荐.
CBC模式适用于文件加密，比ECB模式慢.安全性加强. 当有少量错误时，不会造成同步错误
OFB模式和CFB模式较CBC模式慢许多. 每次迭代只有少数比特完成加密. 若可以容忍少量错误扩展，则可换来恢复同步能力，此时用CFB或OFB模式. 在字符为单元的流密码中多选 CFB模式.
CTR模式用于高速同步系统，不容忍差错传播

五、常用哈希函数简介

1. SHA-256

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)