2023年7月27日发(作者：)

第11章 消息认证和hash函数

1

第 11 章

消息认证和散列函数

要 点

 消息认证：验证消息的完整性，包括消息和消息源

 对称密码在共享密钥的客户间提供认证，公钥密码用私钥加密也提供认证

 消息认证的常见技术：消息认证码（MAC）和散列（hush）函数

 消息认证码



散列函数

内容

1． 对认证和数字签名的要求；

2． 可能遇到的攻击类型；

3． 基本方法。

11.1 对认证的要求

一、 信息安全的需求

• 保密性（ Confidentiality）

• 完整性（Integrity）

– 数据完整性，未被未授权篡改或者损坏

– 系统完整性，系统未被非授权操纵，按既定的功能运行

• 可用性（Availability）

• 鉴别（Authenticity）

– 实体身份的鉴别，适用于用户、进程、系统、信息等

• 不可否认性（ Non-repudiation）

– 防止源点或终点的抵赖

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

2

• ……

二、 攻击类型

序号

1

2

3

4

5

6

7

8

泄密

消息保密范畴

传输分析：分析双方的通信模式

伪装

篡改

消息认证方面

顺序修改

计时修改：延时和重放

发送方否认

接收方否认

数字签名

数字签名及协议

攻 击 类 型

归纳：

1． 消息认证：

2． 数字签名

11.2 认证函数

一、 功能（两层）

1．下层：产生认证符的函数

2．上层：将函数作为原语验证消息的真实性

二、 函数类型

1． 消息加密：密文作为认证符

2． 消息认证码（MAC）：是消息和密钥的公开函数，产生定长的认证符

3． Hash函数：是消息的公开函数，将任意长的消息映射为定长的Hash值，作为认证符

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

3

11.2.1

消息加密

 消息的自身加密可以作为一个认证的度量

 对称密钥模式和公开密钥模式有所不同

(一) 对称加密

（1） 作用：加密和认证

（2） 前提：明文具有可读性

（3） 困难：如明文为二进制文件或数字化X射线，攻击者可以发假消息

 如何自动确定是否收到的密文可解密为可懂的明文？

 一种解决办法是强制明文有某种结构

（4） 措施：错误检测码（帧校验序列、校验和，FCS）：内部错误控制和外部错误控制

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

4

（5） 特点：A→B：C＝EK(M)

 提供保密性：只有A和B共享K；

 提供认证

 只能发自A；

 传输中未被改变；

 需要某种数据组织形式/冗余；

 不能提供数字签名

 接收方可以伪造消息；

 发送方可以否认消息。

(二) 公钥加密

（1） （公钥）加密： 保密性

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

5

 提供保密性：

 不提供认证，不保证真实性：

（2） （私钥）加密：认证与签名

 提供认证（明文要有某种结构以便区分真实的明文和随机的位串）；

 此时的加密结果即是签名；

 不提供保密性。

（3） 公钥加密：保密、认证与签名

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

6

 用私钥签名，公钥加密

 缺点：一次通信执行4次公钥算法

11.2.2

消息认证码[1:234]

(一) 概述

 消息认证码：使用一个密钥生成一个固定大小的小数据块，并加入到消息中，称为消息认证码（Message

Authentication Code，MAC）或密码校验和（Cryptographic Chechsum）

 接收者可以确信消息M未被改变

 还可以确信消息来自所声称的发送者

 如果消息中包含顺序码（如HDLC，X.25，TCP），则接收者可以保证信息的正常顺序

 特征：利用密钥生成一个固定长的（短）数据

 假定：双方共享密钥K

 类似于加密函数，但不需要可逆性，故从数学角度，比加密算法被攻击的弱点要少

(二) 基本用法（a）：认证

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

7

 提供认证：只有A和B共享K

(三) 基本用法（b）：认证和保密——与明文有关的认证

 提供认证：只有A和B共享K1

 提供保密性：只有A和B共享K2

(四) 基本用法（c）：认证和保密——与密文有关的认证

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

8

 提供认证：使用K1

 提供保密性：使用K2

11.2.3

散列函数

(一) （通过加密得到信息真实性的）问题

 保密性与真实性是两个不同的概念

 本质上，信息加密提供的是保密性而非真实性

 加密代价大(公钥算法代价更大)

 鉴别函数与保密函数的分离能提供功能上的灵活性

 某些信息只需要真实性，不需要保密性

 广播的信息难以使用加密(信息量大)

 网络管理信息等只需要真实性

 政府/权威部门的公告

(二) 概述

 概念：hash码，也称为：哈希函数、hash值、消息摘要、数字指纹（Digitalfinger print）、压缩（Compression）函数、紧缩（Contraction ）函数、数据鉴别码DAC（Data

authentication code）、篡改检验码MDC(Manipulation

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

9

detection code)

 H(M): 输入为任意长度的消息M; 输出为一个固定长度的散列值，称为消息摘要(MessageDigest)。

 与MAC的区别：与密钥无关仅是消息M的函数

 是所有消息位的函数，具有错误检测能力（即改变消息的若干位，都会导致hash码的改变）

(三) 应用

 认证、保密

 认证：hash函数与加密函数的合成即为MAC

 认证与签名：是数字签名技术的本质所在

 保密、认证、签名

 认证：秘密值S为通信双方共享，且不传送，故攻击者无法修改或伪造消息

 认证、保密

(四) 散列函数的基本用法（a）—— 保密和认证

 A→B：EKMHM—— 用共享密钥加密消息及Hash码

 提供保密性—— 只有A和B共享K

 提供认证—— H(M)受密码保护

(五) 散列函数的基本用法（b）—— 认证

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

10

 A→B：MEkHM——用共享密钥加密Hash码

 提供认证—— H(M)受密码保护

(六) 散列函数的基本用法（c）—— 认证和签名

 A→B：MEKRHM—— 用发送方私钥加密Hash码

a

 提供认证和数字签名

 H(M)受密码保护

 只有A能产生EKRHM

a(七) 散列函数的基本用法（d）—— 保密、认证与签名

 A→B：EKMEKRHM—— 用共享密钥加密（c）的结果

 提供认证和数字签名

 提供保密性—— 只有A和B共享K

a

(八) 散列函数的基本用法（e）——认证

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

11

 A→B：MHMS—— 计算消息和秘密值的Hash码

 提供认证—— 只有A和B共享S

 方法e的优点：不含加密处理

– 加密软件很慢

– 加密硬件的开销很大

– 加密硬件是对大长度数据进行优化的

– 加密算法可能受专利保护

– 加密算法可能受出口的限制.

(九) 散列函数的基本用法（f）——认证、保密

 A→B：EKMHMS—— 用共享密钥加密（e）的结果

 提供认证——只有A和B共享S

 提供保密性—— 只有A和B共享K

11.3 消息认证码

11.3.1

对MAC的要求

(一) MAC函数的特性与实现

 MAC函数为多对一映射，包含所有可能的MAC和所有可能的密钥

n-bit MAC： 有2n个可能的MAC；

k-bit 密钥： 有2k个可能的密钥；

N个可能的消息：有N>>2n

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

12

 攻击者如何用强力攻击方法攻击MAC？

假设：用户A和B通信时没有增加保密性实现，攻击者可以看到明文， k>n (k为密钥长度位数，n为MAC长度位数)

给定：M1和MAC1， MAC1= CK1(M1)

密码分析员可以计算MACi = CKi(M1) 对所有可能的Ki，至少有一个Ki保证产生MACi = MAC1

注意：总共会产生2k个MAC结果，但只有2n< 2k个不同的MAC值，因此，有若干个key将产生相同的MAC，而攻击者无法确定哪一个是正确的key。

平均来说， 2k/2n= 2(k-n)个key将产生匹配的MAC，所以，攻击者需要循环多次攻击，以确定K:

第一轮：给定M1和MAC1= CK(M1)，对所有2k个key，计算

MACi = CKi(M1) ，匹配的数量≈2(k-n)

第二轮：给定M2和MAC2= CK(M2)，对所有2(k-n)个key，计算

MACi = CKi(M2) ，匹配的数量≈ 2(k-2×n)

平均来说，如果k=a×n，则需要a轮。

例：k=80， MAC 32-bit，则：

第一轮：248可能的key；

第二轮：216个；

第三轮：1 个；

如果k≤n，则第一轮就可以产生一个唯一对应。仍然可以有多于一个key产生这一配对，这时攻击者只需对一个新的(message， MAC)进行相同的测试。

由此可见，强力攻击企图发现authentication key不小于甚至大于对同样长度的解密key的攻击。

考虑以下的MAC算法

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

13

M = (X1 || X2 || … || Xm) 是一个由64位Xi数据块连接而成，

定义

Δ(M) = X1⊕X2⊕...⊕Xm

CK(M) = EK[Δ(M)]

其中

⊕ 为异或操作；E为ECB工作模式的DES算法。

Key length = 56 bit

MAC length = 64 bit

强力攻击需要至少256次加密来决定K。

但攻击者可以不用找到K就可以实施攻击。

(二) 要求

1．

如果一个攻击者得到M和CK(M)，则他构造一个消息M，使得CK(M)＝CK(M)在计算上不可行的。

2．

CK(M)应均匀分布，即：随机选择消息M和M，CK(M)＝

CK(M)的概率是2n，其中n是MAC的位数。

3．

令M为M的某些变换，即M＝f(M)，（例如：f可以涉及M中一个或多个给定位的反转），在这种情况下，Pr[CK(M)＝

CK(M)] ＝2n。

11.3.2

基于DES的消息认证码

 称为数据认证算法（Data Authentication Algorithm）

– FIPS publication (FIPS PUB 113)

– ANSI standard (X9.17)

 使用CBC(Cipher Block Chaining)方式，初始向量为0。

(一) 最广泛的用法

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

14

将数据按64位分组，D1， D2， … ， DN，必要时最后一个数据块用0向右填充。运用DES算法E，密钥K，数据鉴别码(DAC)的计算如下：

O1 ＝ EK(D1⊕0)

O2 ＝ EK(D2⊕O1)

O3 ＝ EK(D3⊕O2)

…

ON ＝EK(DN⊕ON-1)

M的大小可由通信双方约定。美国联邦电信建议采用24bit[见FTSC-1026]，而美国金融系统采用32bit [ABA，1986]

(二) 工作于CFB模式下DES

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

15

11.4 散列函数[1:241]











h＝H（M）

M —— 变长消息

H（M）—— 定长的hash值

目的：产生文件、消息或其它数据块的“指纹（fingerprint）”

Hash函数与MAC的区别

 MAC需要对全部数据进行加密

 MAC速度慢

 Hash是一种直接产生鉴别码的方法

11.4.1

对散列函数的要求

1、H可以作用于一个任意长度的数据块；

2、H产生一个固定长度的输出；

3、对任意给定的x ，H(x) 计算相对容易，无论是软件还是硬件实现；

4、对任意给定码h，找到x满足H(x)=h具有计算不可行性（单向性）；

5、对任意给定的数据块x，找到满足H(y)=H(x)的y，且y≠x在计算上是不可行的(抗弱碰撞性)；

6、找到任意数据对(x，y)，满足H(x) = H(y)在计算上是不可行的(抗强碰撞性)。

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

16

前三条要求具有实用性，第4条是单向性质，即给定消息可以产生一个散列码，而给定散列码不可能产生对应的消息。第5条性质是保证一个给定的消息的散列码不能找到与之相同的另外的消息。即防止伪造。第6条是对已知的生日攻击方法的防御能力。

11.4.2

简单散列函数

(一) Hash函数的构造

 基于数学难题的构造方法：计算速度慢，不实用

 利用对称密码体制来设计Hash

 直接设计

(二) 直观方法

消息分组M＝（M1,M2,Mm），Mi＝b1i,b2i,bni2，（i＝1～m），则

h＝H（M）＝M1M2Mm＝C1C2Cn2

其中

Ci＝bi1bi2bim

即

分组1

分组2

分组m

位1

b11

b12

b1m

c1

位2

b21

b22

b2m

c2

„

位n

bn1

bn2

bnm

cn









特点：对每一位产生一个简单的奇偶校验（称为经度冗余校验）。

适合：将随机数用于数据完整性检查。

有效性：与数据格式的随机性有关

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

17

(三) 改进

思路：每处理完一个分组后，将hash值循环向左移位一次。

例 ：h＝（00„0）（n位）

for

i＝1 to m do { 将h循环左移一次；h＝hMi }

11.4.3

生日攻击

 假定使用64位的散列码，是否安全?

 如果采用传输加密的散列码和不加密的报文M，对手需要找到M，使得H(M)=H(M)，以便使用替代报文来欺骗接收者.

 一种基于生日悖论的攻击可能做到这一点.

(一) 穷举攻击

对64位hash码，改M为M，并使H(M)＝H(M)，平均约需263次尝试

(二) 生日悖论

 生日问题：一个教室中，最少应有多少学生，才使至少有两人具有相同生日的概率不小于1/2？

 概率结果与人的直觉是相违背的。

 实际上只需23人，即任找23人，从中总能选出两人具有相同生日的概率至少为1/2。即P(365，23)=0.507 3。

 任选P(365，100)=0.999 999 7。

(三) 生日攻击

 相关问题

 给定一个散列函数，有n个可能的输出，输出值为H(x)，如果H有k个随机输入， k必须为多大才能使至少存在一个输入y，使得H(y)=H(x)的概率大于0.5.

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

18

 对单个y， H(y)=H(x)的概率为1/n，反过来H(y)≠H(x)的概率为1-(1/n).

 如果产生k个随机值y，他们之间两两不等的概率等于每个个体不匹配概率的乘积，即[1-(1/n)]k，这样，至少有一个匹配的概率为1-[1-(1/n)]k≈1-[1-(k/n)]=k/n.要概率等于0.5，只需k=n/2.

 对长度为m位的散列码，共有2m个可能的散列码，若要使任意的x、y 有H(x)=H(y)的概率为0.5，只需k=2m/2

 实例

 A准备两份合同M和M，一份B会同意，一份会取走他的财产而被拒绝

 A对M和M各做32处微小变化(保持原意)，分别产生232个64位hash值

 根据前面的结论，超过0.5的概率能找到一个M和一个M，它们的hash值相同

 A提交M，经B审阅后产生64位hash值并对该值签名，返回给A

 A用M替换M

—

Hash必须足够长(64128160)

11.4.4

分组链接（Block Chaining）技术

(一) 思路

 用对称加密算法构造hash函数

 M=(M1，M2，…，MN)， H0=Initial value，Hi=f(Mi，Hi-1)，

例如Rabin方法：M＝（M1,M2,MN），使用对称加密体制，即

H0＝IV，Hi＝EMiHi1 （i＝1～N）

Hash码: G＝H(M)＝HN

 速度慢，且许多这样的hash函数被证明不安全(与E的安全密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

19

性无关)

 现在很少使用

(二) 中间相遇攻击（另一种生日攻击）

截获一条消息及其签名，签名是加密后的hash码，hash码有m位。

(三) 改进

Hi＝EMiHi1⊕Hi1

Hi=EHi-1(Mi)⊕Mi

Hi=EHi-1(Mi)⊕Mi⊕Hi-1

Hi=EHi-1(Mi⊕Hi-1)⊕Mi

Hi=EHi-1(Mi⊕Hi-1)⊕Mi⊕Hi-1

11.5 散列函数和MAC的安全性

攻击类型：穷举攻击和密码分析

11.5.1

穷举攻击

(一) hash函数

(二) 消息认证码

11.5.2

密码分析

密码编码学与网络安全——原理与实践 第11章 消息认证和hash函数

20

(一) hash函数

（1） 安全hash码的一般结构

•由Merkle于1989年提出

•Ron Rivest于1990年提出MD4

•几乎被所有hash函数使用

•具体做法:

–把原始消息M分成一些固定长度的块Yi

–最后一块被填充并使其包含消息M长度

–设定初始值CV0

–压缩函数f， CVi=f(CVi-1，Yi-1)

–最后一个CVi为hash值

（2） 图形表示

(二) 消息认证码

密码编码学与网络安全——原理与实践