密码学学习 - 密码杂凑函数

发布于 2024-10-16 17:50:53 字数 14093 浏览 13 评论 0

一开学专业课就是密码学，意料之中，但是在课程进行中发现和本科时候学的密码学还是有所区别的，而且自己也已经很多不记得了，趁有空，把一些密码学的东西总结下，也算是对之前内容的复习和对现在正上着的课程的预习了。因为密码学是一门大学科，也没打算将所有的东西都弄懂，能够把一些常用的东西理清楚其实就很不错了，而这一篇主要是对密码杂凑函数的一些总结和概述。

简介

先引用维基上对于杂凑函数的介绍：“密码散列函数（英语：Cryptographic hash function），又译为加密散列函数、密码散列函数、加密散列函数，是散列函数的一种。它被认为是一种单向函数，也就是说极其难以由散列函数输出的结果，回推输入的数据是什么。这样的单向函数被称为“现代密码学的驮马”。这种散列函数的输入数据，通常被称为消息（message），而它的输出结果，经常被称为消息摘要（message digest）或摘要（digest）。”

简单来说，杂凑函数就是一种单向函数，由输入计算得出结果容易，但是理论上由输出结果计算输入是困难的，另外，杂凑函数也叫 hash 函数、散列函数等。另外，杂凑函数需符合以下性质：

抗原像攻击（单向性），对任意给定的 hash h，找到满足 H(y)=h 的 y 在计算上不可行
抗第二原像攻击（抗弱碰撞性），对任何给定的分块 x，找到满足 y≠x 且 H(x)=H(y) 的 y 在计算上是不可行的
抗碰撞（抗强碰撞性），找到任何满足 H(x)=H(y) 的偶对(x,y) 在计算上是不可行的

其中，满足上述条件的为弱 Hash 函数，如果函数的输出满足伪随机性测试标准，则成为强 Hash 函数。
此外，对于杂凑函数的计算，应该满足以下条件：

哈希函数应该在 CPU/软件和 AS IC/硬件上都有效地实现。
哈希函数的计算速度应该和磁盘 IO 相当
短消息或长消息优化设计

杂凑函数输入输出

函数输入：

输入长度以 bit 计算
允许 0 长度输入
通常一个给定的哈希函数会规定最大输入长度

函数输出：

固定长度输出
一般输出长度为 128/160/256/512 位（不同函数)
同一类哈希函数的算法相似，输出长度和参数不同（比如 salt）

杂凑函数结构

对于杂凑函数，目前最常见的为两种，分别为 Merkle Damgard 结构和海绵结构，其核心思想都在于尽可能将数据原文中的信息扩散到 hash 值中。

Merkle Damgard 结构

算法流程：

把消息划分为 n 个消息块
对最后一个消息块做长度填充
每个消息块和一个输入向量做一个运算，把这个计算结果当成下个消息块的输入向量
IV 为初始向量，已知且固定不变

Merkle Damgard 结构是使用地较多的一种杂凑函数结构，其中常见的 MD5、SHA1 等都是使用这一结构，但是这一结构也有其弊端，攻击者可以利用哈希长度扩展攻击进行破解，当然，在破解该种杂凑函数时需要满足以下条件：

知道密文 secret 的长度
知道一个密文 secret 的 hash 值

海绵（sponge）结构

海绵结构能够进行数据转换，将任意长的输入转换成任意长的输出。在使用海绵结构前，需要进行预处理，预处理会将数据进行分块，分成大小相同的块，在预处理后，海绵结构主要分为以下两部分：

吸入阶段（absorbing phase）：将块 x_i 传入算法并处理。
挤出阶段（squeezing phase）：产生一个固定长度的输出

假设输入为 x，核心处理函数为 f,则其流程分为以下几步：

对输入串 x 做 padding，使其长度能被 r 整除，将 padding 后分割成长度为 r 的块，即 x=x_0||x_1||x_2||…||x_t-1。
初始化一个长度为 r+c bit 的全零向量。
输入块 x_i，将 x_i 和向量的前 r 个 bit 亦或，然后输入到 f 函数中处理。
重复上一步，直至处理完 x 中的每个块。
输出长为 r 的块作为 y_0，并将向量输入到 f 函数中处理，输出 y_1，以此类推。得到的 Hash 序列即为 y=y_0||y_1||y_2||…||y_u。对于对应不同输出长度的杂凑函数，只需要在 y_0 中取出对应长度的前缀即可。

对于海绵结构，一些较新的杂凑函数，如 SHA-3 算法等，使用的就是这一结构。

MD5 杂凑函数

MD5 是使用最为广泛的杂凑函数之一，其由 Ron Rivest 设计，在此之前有 MD2 MD4，而 MD5 则是在 RFC1321 中被提出，使用 Merkle Damgard 结构，后续成为使用最广泛的哈希算法，其哈希长度为 128bits，主要攻击方法为爆破和密码分析。

将输入信息 text 的位数按照特定的方法填充至 512 的整数倍，然后每 512 位为一个分组 M[i]进行处理。每个分组又将分为 16 个 32 位的子分组，经过一系列循环后将产 4 个 32 位的散列值 a, b, c, d，作为下一个分组的输入。最终，将 a, b, c, d 组合起来即可得到 text 的 MD5 值。

其算法流程如下：

信息填充
对明文信息进行填充 0，使其长度 mod512=448，因此信息的位长度被扩展为(Nx512+448)。然后再在这个结果后面附加一个以 64 为二进制表示的填充前信息长度，即此时长度变为 (N+1)*512。
结构初始化
定义一个结果，包含每次需要处理的明文块（512bits）和计算出来的散列值 128bits。在散列的整个过程，各个明文块计算的散列值都由其进行传播。
分组
将填充好的明文信息进行分组，每组 512 位，共 N+1 组
处理分组
设置链接变量初值，共四个，每个 32 位，四组共 128 位，即密文长度为 128 位：
a = 0x01234567，b = 0x89abcdef， c = 0xfedcba98，d =0x76543210
再设 A = a,B = b,C = c,D = d
进入 hash 循环运算，循环次数为明文信息的分组数 N+1
每次循环运算分为 4 轮，每轮使用不同的函数计算，设其实的 512 位分组为 M，则将其划分为 16*32，即 16 个小分组，在 4 轮循环中，需要进行对应这 16 个小分组的 16 次运算，4 轮结束后，将循环后的 a,b,c,d 值加到 A,B,C,D 上即得新一轮的链接变量，当所有 512 位分组都循环结束后，此时的 A,B,C,D 值即为哈希值。其涉及 4 个计算公式如下：
F(X,Y,Z) =(X&Y)|((~X)&Z)
G(X,Y,Z) =(X&Z)|(Y&(~Z))
H(X,Y,Z) =X^Y^Z
I(X,Y,Z)=Y^(X|(~Z))
（&是与，|是或，~是非，^是异或）

函数说明：
如果 X、Y 和 Z 的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。
假设 M[j]表示消息的第 j 个子分组（从 0 到 15），常数 ti 是 4294967296*abs(sin(i)) 的整数部分，i 取值从 1 到 64。

F(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + F(b, c, d) + Mj + ti) <<< s)
GG(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + G(b, c, d) + Mj + ti) <<< s)
HH(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + H(b, c, d) + Mj + ti) <<< s)
II(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + I(b, c, d) + Mj + ti) <<< s)

在每次循环中，其循环分为 4 轮，可用下列公式表示：

a = A; b = B; c = C; d = D;
//对 M[j]的第一轮循环
FF(a,b,c,d,M[0],7,0xd76aa478);
FF(d,a,b,c,M[1],12,0xe8c7b756);
FF(c,d,a,b,M[2],17,0x242070db);
FF(b,c,d,a,M[3],22,0xc1bdceee);
FF(a,b,c,d,M[4],7,0xf57c0faf);
FF(d,a,b,c,M[5],12,0x4787c62a);
FF(c,d,a,b,M[6],17,0xa8304613);
FF(b,c,d,a,M[7],22,0xfd469501) ;
FF(a,b,c,d,M[8],7,0x698098d8) ;
FF(d,a,b,c,M[9],12,0x8b44f7af) ;
FF(c,d,a,b,M[10],17,0xffff5bb1) ;
FF(b,c,d,a,M[11],22,0x895cd7be) ;
FF(a,b,c,d,M[12],7,0x6b901122) ;
FF(d,a,b,c,M[13],12,0xfd987193) ;
FF(c,d,a,b,M[14],17,0xa679438e) ;
FF(b,c,d,a,M[15],22,0x49b40821);
 
//对 M[j]的第二轮循环
GG(a,b,c,d,M[1],5,0xf61e2562);
GG(d,a,b,c,M[6],9,0xc040b340);
GG(c,d,a,b,M[11],14,0x265e5a51);
GG(b,c,d,a,M[0],20,0xe9b6c7aa) ;
GG(a,b,c,d,M[5],5,0xd62f105d) ;
GG(d,a,b,c,M[10],9,0x02441453) ;
GG(c,d,a,b,M[15],14,0xd8a1e681);
GG(b,c,d,a,M[4],20,0xe7d3fbc8) ;
GG(a,b,c,d,M[9],5,0x21e1cde6) ;
GG(d,a,b,c,M[14],9,0xc33707d6) ;
GG(c,d,a,b,M[3],14,0xf4d50d87) ;
GG(b,c,d,a,M[8],20,0x455a14ed);
GG(a,b,c,d,M[13],5,0xa9e3e905);
GG(d,a,b,c,M[2],9,0xfcefa3f8) ;
GG(c,d,a,b,M[7],14,0x676f02d9) ;
GG(b,c,d,a,M[12],20,0x8d2a4c8a);
 
//对 M[j]的第三轮循环
HH(a,b,c,d,M[5],4,0xfffa3942);
HH(d,a,b,c,M[8],11,0x8771f681);
HH(c,d,a,b,M[11],16,0x6d9d6122);
HH(b,c,d,a,M[14],23,0xfde5380c) ;
HH(a,b,c,d,M[1],4,0xa4beea44) ;
HH(d,a,b,c,M[4],11,0x4bdecfa9) ;
HH(c,d,a,b,M[7],16,0xf6bb4b60) ;
HH(b,c,d,a,M[10],23,0xbebfbc70);
HH(a,b,c,d,M[13],4,0x289b7ec6);
HH(d,a,b,c,M[0],11,0xeaa127fa);
HH(c,d,a,b,M[3],16,0xd4ef3085);
HH(b,c,d,a,M[6],23,0x04881d05);
HH(a,b,c,d,M[9],4,0xd9d4d039);
HH(d,a,b,c,M[12],11,0xe6db99e5);
HH(c,d,a,b,M[15],16,0x1fa27cf8) ;
HH(b,c,d,a,M[2],23,0xc4ac5665);
   
//对 M[j]的第四轮循环
II(a,b,c,d,M[0],6,0xf4292244) ;
II(d,a,b,c,M[7],10,0x432aff97) ;
II(c,d,a,b,M[14],15,0xab9423a7);
II(b,c,d,a,M[5],21,0xfc93a039) ;
II(a,b,c,d,M[12],6,0x655b59c3) ;
II(d,a,b,c,M[3],10,0x8f0ccc92) ;
II(c,d,a,b,M[10],15,0xffeff47d);
II(b,c,d,a,M[1],21,0x85845dd1) ;
II(a,b,c,d,M[8],6,0x6fa87e4f) ;
II(d,a,b,c,M[15],10,0xfe2ce6e0);
II(c,d,a,b,M[6],15,0xa3014314) ;
II(b,c,d,a,M[13],21,0x4e0811a1);
II(a,b,c,d,M[4],6,0xf7537e82) ;
II(d,a,b,c,M[11],10,0xbd3af235);
II(c,d,a,b,M[2],15,0x2ad7d2bb);
II(b,c,d,a,M[9],21,0xeb86d391);
 
A += a;
B += b;
C += c;
D += d;

处理完所有的 512 位的分组后，得到一组新的 A,B,C,D 的值，将这些值按 ABCD 的顺序级联，然后输出。这里还要注意，输出的 MD5 是按内存中数值的排列顺序，所以我们要分别对 A,B,C,D 的值做一个小端规则的转换。举个例子：A 有 32 位，分成 4 个字节 A1A2A3A4。输出 A 的时候，要这样输出：A4A3 A2A1。这样就能输出正确的 MD5 了。

SHA-1 杂凑函数

SHA-1（Secure Hash Algorithm 1，安全散列算法 1）是一种密码杂凑函数，由美国国家安全局设计，并由（NIST）发布为 FIPS。SHA-1 的数据杂凑值为 160 位（20 字节），杂凑值通常的呈现形式为 40 个十六进制数。该杂凑函数使用的是和 MD5 一样的 Merkle Damgard 结构。

SHA1 对任意长度明文的预处理和 MD5 的过程是一样的，即预处理完后的明文长度是 512 位的整数倍，但是有一点不同，那就是 SHA1 的原始报文长度不能超过 2 的 64 次方，然后 SHA1 生成 160 位的报文摘要。SHA1 算法简单而且紧凑，容易在计算机上实现。SHA-1 和 MD5 相比，其差别大致可概括如下：

差异处	MD5	SHA1
摘要长度	128 位	160 位
运算步骤数	64	80
基本逻辑函数数目	4	4

安全性：SHA1 所产生的摘要比 MD5 长 32 位。若两种散列函数在结构上没有任何问题的话，SHA1 比 MD5 更安全。
速度：两种方法都是主要考虑以 32 位处理器为基础的系统结构。但 SHA1 的运算步骤比 MD5 多了 16 步，而且 SHA1 记录单元的长度比 MD5 多了 32 位。因此若是以硬件来实现 SHA1，其速度大约比 MD5 慢了 25％。
简易性：两种方法都是相当的简单，在实现上不需要很复杂的程序或是大量存储空间。然而总体上来讲，SHA1 对每一步骤的操作描述比 MD5 简单。

其算法流程如下：

SHA-1 算法中，填充时第一位填 1，其他填 0，再将长度附到后面，此时明文长度为 512 的倍数，按照 512 划分分组，分别表示为 Yi，然后对于每个分组进行处理。其预处理和 MD5 类似，区别主要在于后续的分组处理，在此也只对预处理后的步骤进行介绍：

每个 512 位分组划分为 16 个小分组 Mi，将 16 个小分组扩充为 80 份小分组，记为 Wi，扩充方法为：

Wt = Mt , 当 0≤t≤15
Wt = (Wt-3⊕Wt-8⊕Wt-14⊕Wt-16)<<<1, 当 16≤t≤79

SHA1 有 4 轮运算，每一轮包括 20 个步骤（一共 80 步），最后产生 160 位摘要，这 160 位摘要存放在 5 个 32 位的链接变量中，分别标记为 A、B、C、D、E。这 5 个链接变量的初始值以 16 进制位表示如下。

A=0x67452301
B=0xEFCDAB89
C=0x98BADCFE
D=0x10325476
E=0xC3D2E1F0

SHA1 有 4 轮运算，每一轮包括 20 个步骤，一共 80 步，当第 1 轮运算中的第 1 步骤开始处理时，A、B、C、D、E 五个链接变量中的值先赋值到另外 5 个记录单元 A′，B′，C′，D′，E′中。这 5 个值将保留，用于在第 4 轮的最后一个步骤完成之后与链接变量 A，B，C，D，E 进行求和操作。
在 SHA-1 每轮步骤中，使用的函数步骤是一样的：

A,B,C,D,E←[(A<<<5)+ ft(B,C,D)+E+Wt+Kt],A,(B<<<30),C,D

其中 ft(B,C,D) 为逻辑函数，Wt 为子明文分组 W[t]，Kt 为固定常数。这个操作程序的意义为：

将[(A<<<5)+ ft(B,C,D)+E+Wt+Kt]的结果赋值给链接变量 A；
将链接变量 A 初始值赋值给链接变量 B；
将链接变量 B 初始值循环左移 30 位赋值给链接变量 C；
将链接变量 C 初始值赋值给链接变量 D；
将链接变量 D 初始值赋值给链接变量 E。

举一个例子来说明 SHA1 哈希算法中的每一步是怎样进行的，比起 MD5 算法，SHA1 相对简单，假设 W[1]=0x12345678，此时链接变量的值分别为 A=0x67452301、B=0xEFCDAB89、C=0x98BADCFE、D=0x10325476、E=0xC3D2E1F0，那么第 1 轮第 1 步的运算过程如下:

将链接变量 A 循环左移 5 位，得到的结果为：0xE8A4602C。
将 B，C，D 经过相应的逻辑函数：
(B&C)|(~B&D)=(0xEFCDAB89&0x98BADCFE)|(~0xEFCDAB89&0x10325476)=0x98BADCFE
将第（1）步，第（2）步的结果与 E，W[1]，和 K[1]相加得：
0xE8A4602C+0x98BADCFE+0xC3D2E1F0+0x12345678+0x5A827999=0xB1E8EF2B
将 B 循环左移 30 位得：(B<<<30)=0x7BF36AE2。
将第 3 步结果赋值给 A，A（这里是指 A 的原始值）赋值给 B，步骤 4 的结果赋值给 C，C 的原始值赋值给 D，D 的原始值赋值给 E。
最后得到第 1 轮第 1 步的结果：

A = 0xB1E8EF2B
B = 0x67452301
C = 0x7BF36AE2
D = 0x98BADCFE
E = 0x10325476

按照这种方法，将 80 个步骤进行完毕。第四轮最后一个步骤的 A，B，C，D，E 输出，将分别与记录单元 A′，B′，C′，D′，E′中的数值求和运算。其结果将作为输入成为下一个 512 位明文分组的链接变量 A，B，C，D，E，当最后一个明文分组计算完成以后，A，B，C，D，E 中的数据就是最后散列函数值。

常见杂凑函数对比

目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2。

MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。其输出为 128 位。MD4 已证明不够安全。
MD5（RFC 1321）是 Rivest 于 1991 年对 MD4 的改进版本。它对输入仍以 512 位分组，其输出是 128 位。MD5 比 MD4 复杂，并且计算速度要慢一点，更安全一些。MD5 已被证明不具备"强抗碰撞性"。
SHA （Secure Hash Algorithm）是一个 Hash 函数族，由 NIST（National Institute of Standards and Technology）于 1993 年发布第一个算法。目前知名的 SHA-1 在 1995 年面世，它的输出为长度 160 位的 hash 值，因此抗穷举性更好。SHA-1 设计时基于和 MD4 相同原理，并且模仿了该算法。SHA-1 已被证明不具"强抗碰撞性"。
为了提高安全性，NIST 还设计出了 SHA-224、SHA-256、SHA-384，和 SHA-512 算法（统称为 SHA-2），跟 SHA-1 算法原理类似。SHA-3 相关算法也已被提出。

可以看出，上面这几种流行的算法，它们最重要的一点区别就是"强抗碰撞性"。另外，在维基中对于一些主流的杂凑函数有进行对比，其总结如下：

算法和变体	输出杂凑值长度(bits)	数据块长度(bits)	最大输入消息长度(bits)	循环次数
MD5	128	512	无限	64
SHA-0	160	512	2^64-1	80
SHA-1	160	512	2^64-1	80
SHA-256	256	512	2^64-1	64
SHA-512	512	1024	2^128-1	80
SHA3-224	224	1152	无限	24
SHA3-256	256	1088	无限	24
SHA3-512	512	576	无限	24

杂凑函数安全性

如果不存在设计缺陷，根据杂凑函数的三大性质，函数的安全性取决于输出哈希值的位长度。假设给定一个长度为 m 的杂凑函数，攻击者至少需要爆破 2^(m/2) 次，这是利用生日攻击进行推导得出，具体推导过程这里不详细阐述，提供一个参考

由生日攻击可得，假设哈希空间大小为 N，则只要计算（π/2*N）^1/2 ，就有 50%的可能性产生碰撞，假设 N 为 365，按照公式计算出为 23.9，其概率如下图：

由生日攻击可得，哈希碰撞所需耗费的计算次数，和取值空间的平方根是一个数量级。假设 d 为哈希空间大小，n 为当前碰撞次数，则当前碰撞成功的概率计算公式为：

由公式可得，假设哈希值为 m 位，则攻击者准备 2^m/2 次方信息 X 生成 hash，2^m/2 次方信息 Y 生成 hash，则找到 hash(X)=hash(Y) 的概率为 50%。

杂凑函数应用

在密码系统中的应用

密钥导出
消息认证码
数字签名中的消息摘要
将公钥密码机制转为 CCA 安全机制
构造伪随机数生成器

其它应用

文件校验：使用杂凑函数计算文件哈希值作为文件完整性的校验值，检查文件是否被更改。
内容标识符：使用杂凑函数作为数据指纹，判断数据是否可信
分布式哈希表
哈希表，将 key 和 value 以（hash(key) ，value）的形式存储，即为哈希表，哈希表将所有数据存储在同一台设备上，而分布式哈希表则将说句分为若干个部分分别存储在不同的机器上，从而降低数据被全部损坏的风险。
分布式哈希表是一种分布式的存储方法，不需要中心节点服务器，直接由每个客户端负责一个小范围的路由，并负责存储一小部分数据，从而实现整个 DHT 网络的寻址和存储。其次，DHT 网络还在和关键字最接近的节点上复制备份冗余信息，从而避免单一节点失效的问题。
DHT 寻址和存储过程：
通过 DHT 数据结构它把 KEY 和 VALUE 用某种方式对应起来。使用 hash() 函数把一个 KEY 值映射到一个 index 上：hash(KEY) = index。这样就可以把一个 KEY 值同某个 index 对应起来。然后把与这个 KEY 值对应的 VALUE 存储到 index 所标记的存储空间中。这样，每次想要查找 KEY 所对应的 VALUE 值时，只需要做一次 hash() 运算就可以找到了。以上就是寻址过程。
这里的 hash 函数为一个一致性哈希函数，假设存储空间地址可以以 0-2^32-1 表示，则该一致性函数即将 key 值 hash 成一个 index 值，index 值即为空间地址，以此就可以按照 index value 进行存储和寻址。