现代密码学理论与实践 第11章 消息认证和散列函数 Fourth Edition by William Stallings Slides by 杨寿保 syang@ustc.edu.cn http://staff.ustc.edu.cn/~syang 2012年11月 2019/5/8 现代密码学理论与实践-11

本章要点 消息认证是用来验证消息完整性的一种机制或服务。消息认证确保收到的数据确实和发送时的一样(即没有修改、插入、删除或重放)，且发送方声称的身份是真实有效的。 对称密码在那些相互共享密钥的用户间提供认证。用消息发送方的私钥加密消息也可提供一种形式的认证。 用于消息认证的最常见的密码技术是消息认证码和安全散列(hash)函数。 MAC是一种需要使用秘密密钥的算法，以可变长的消息和秘密密钥作为输入，产生一个认证码。拥有秘密密钥的接收方产生一个认证码来验证消息的完整性。 散列函数将可变长度的消息映射为固定长度的散列值，或叫消息摘要。对于消息认证码，安全散列函数必须以某种方式和秘密密钥捆绑起来。 2019/5/8 现代密码学理论与实践-11

消息认证 Message Authentication 消息认证(报文认证)关心的问题是 保护消息的完整性 验证发起方身份 消息源的不可否认(解决分歧) 消息认证要考虑安全需求 三种消息认证的方法 消息加密 消息认证码(MAC) 哈希函数 2019/5/8 现代密码学理论与实践-11

11.1 对认证的要求 网络通信环境中可能的攻击 泄密Disclosure，将消息透露给没有合法身份的第三方 传输分析Traffic analysis，分析双方通信模式 伪装Masquerade，欺诈源向网络中插入一条消息 内容篡改Content modification，对消息内容的修改 顺序篡改Sequence modification，对消息顺序的修改 计时篡改Timing modification，对消息的延时和重放 信源抵赖Source repudiation,发送方否认发送过某消息 信宿抵赖Destination repudiation，接收方否认接收过某消息 消息认证就是验证所收到的消息确实来自真正的发送方且未被修改的消息，也可以验证消息的顺序和时效 2019/5/8 现代密码学理论与实践-11

11.2 认证函数 11.2.1 消息加密 消息加密本身提供了一种认证手段 对称加密 接收方可以确信消息是由发送方产生的，因为除了接收方以外只有发送方拥有加密密钥，产生出用此密钥可以解密的密文 如果消息可以是任意的位模式，接收方无法确定收到的消息是合法明文的密文。因此，通常不管密文的值是什么，如果解密后得到的明文有合法明文的位模式，接收方都会作为真实的密文接收。 2019/5/8 现代密码学理论与实践-11

2019/5/8 现代密码学理论与实践-11

解决解密所得消息是否具有可读性的问题 要求明文具有某种易于识别的结构，如在加密前对每个消息附加一个帧校验序列FCS 2019/5/8 现代密码学理论与实践-11

公钥加密作为认证手段 若要提供认证，发送方用自己的私钥对消息加密，接收方用发送方的公钥解密(验证)，就提供了认证功能。 如果发送方用私钥加密消息，再用接收方的公钥加密，就实现了既保密又认证的通信。 这也需要注意区分伪造的不合理的消息。 既保密又认证的通信的代价是需要执行四次复杂的公钥算法而不是两次。 2019/5/8 现代密码学理论与实践-11

2019/5/8 现代密码学理论与实践-11

11.2.2 消息认证码MAC 使用密钥产生短小的定长数据分组，即所谓的密码检验MAC，将它附加在报文中。通信双方A和B共享密钥K，报文从A发往B，A计算MAC=CK(M), 附在报文后发给B。B对接收到的报文重新计算MAC，并与接收到的MAC比较。如果只有收发双方知道密钥且两个MAC匹配，则： 接收方可以确信报文未被更改； 接收方可以确信报文来自声称的发送者； 接收方可以确信报文序号正确，如果有的话。 报文认证不提供保密 MAC函数类似加密，但非数字签名，也无需可逆 将MAC直接与明文并置，然后加密传输比较常用 2019/5/8 现代密码学理论与实践-11

MAC：消息认证码的特点 MAC加密所得的消息校验和 MAC是一种多对一的函数 MAC = CK(M) 定义域由任意长的消息组成，值域由所有可能的MAC和密钥组成。若使用n位长的MAC, 则有2n个可能的MAC, 有N条可能的消息, N>>2n. 若密钥长度为k, 则有2k种可能的密钥。 如N为2100, n为10, 共有2100不同的消息, 210种不同的MAC, 平均而言同一MAC可由2100/ 210=290条不同的消息产生。若密钥长度为5，则从消息集合到MAC值的集合有25=32不同映射。 可以证明，由于认证函数的数学性质，与加密相比，认证函数更不易被攻破 2019/5/8 现代密码学理论与实践-11

2019/5/8 现代密码学理论与实践-11

2019/5/8 现代密码学理论与实践-11

11.2.3 散列函数 Hash Function 一个散列函数以变长的消息M作为输入，产生定长的散列码H(M)，作为输出，亦称作报文摘要Message Digest. 散列码是消息所有比特的函数值，具有差错检测能力，消息任意一比特的改变都将引起散列码的改变 不同的散列码使用方式 对附加了散列码的消息进行加密 使用常规加密方法仅对散列码加密 使用公开密钥方法仅对散列码加密，提供数字签名 同时提供保密和签名，可以分别使用常规方法加密消息及使用公开密钥方法加密散列码 其他 不希望使用加密函数的理由 加密过程很慢，硬件开销大，初始化的开销，专利问题，出口限制 2019/5/8 现代密码学理论与实践-11

2019/5/8 现代密码学理论与实践-11

2019/5/8 现代密码学理论与实践-11

2019/5/8 现代密码学理论与实践-11

11.3 消息认证码MAC 对MAC的要求 基于DES的消息认证码 FIPS PUB 113 若攻击者已知M和C(K,M), 则构造满足C(K,M’)=C(K,M)的消息M’在计算上是不可行的 C(K,M)应该是均匀分布的, 即对任何随机选择的消息M和M’，C(K,M’)=C(K,M)的概率是2-n, 其中n是MAC的位数 设M’是M的某个已知的变换，即M’=f(M), 如f可能表示逆转M的一位或多位, 那么Pr[C(K,M)=C(K,M’)]的概率是2-n. （直观理解：只要两消息不相同，其MAC值相同的概率都只是2-n ） 基于DES的消息认证码 FIPS PUB 113 该算法定义为以密码分组链接(CBC)为操作方式的用0作为初始化向量的DES 2019/5/8 现代密码学理论与实践-11

2019/5/8 现代密码学理论与实践-11

使用消息认证码的几种情形 MAC不提供数字签名，因为双方共享密钥。 接收方无法对所有收到的消息进行解密工作，则可以进行有选择地鉴别，对消息作随机检查 对明文计算机程序进行鉴别，检查完整性 某些应用不关注消息的保密而更重视鉴别消息的真实性，如SNMPv3，将保密与鉴别分开 保密函数与鉴别函数的分离能提供结构上的灵活性，如在应用层完成鉴别而在较低层加密 在超过接收时间后继续延长保护期限，同时允许处理消息内容 MAC不提供数字签名，因为双方共享密钥。 2019/5/8 现代密码学理论与实践-11

11.4 散列函数 散列函数 一个散列函数以变长的报文M作为输入，产生定长的散列码H(M)作为输出，即报文摘要Message Digest. 散列码是报文所有比特的函数值，具有差错检测能力，报文任意一比特的改变都将引起散列码的改变。 h=H(M) 报文摘要的基本原理 对任意长度的明文m，经由哈希函数(杂凑函数)h产生固定长度的哈希值h(m)，用来对明文作认证(authentication)或数字签名(digital signature)。哈希函数值是对明文的一种“指纹”(finger print)或是摘要(digest)。对哈希函数值的数字签名，就是对此明文的数字签名，可以用来提高数字签名的效率。 2019/5/8 现代密码学理论与实践-11

2019/5/8 现代密码学理论与实践-11

对散列函数的要求 h=H(M) 1. H可以应用于任意大小的数据块 2. H产生固定长度的输出 3. 对任意给定的明文x，计算H(x)容易，可由硬件或软件实现 4. 对任意给定的散列码h，找到满足H(x)=h的x，在计算上不可行，单向性 5. 对任何给定的分组x，找到满足y≠x且H(x)=H(y)的y，在计算上不可行，抗弱碰撞性 6. 找到任何满足H(x)=H(y)的偶对(x, y)，在计算上不可行，抗强碰撞性 2019/5/8 现代密码学理论与实践-11

强哈希函数 条件1, 2, 3，4是所谓单向性问题(One-way) 条件5、6是对使用的哈希值的数字签名方法所做的安全保障，否则攻击者可由已知的明文及相关的数字签名任意伪造对其他明文的签名 条件6主要用于防范所谓的生日攻击法 能满足条件1-5的，称为弱哈希函数(Weak Hash Function) 能同时满足条件6的，称为强哈希函数(Strong Hash Function) 应用在数字签名上的哈希函数必须是强哈希函数 2019/5/8 现代密码学理论与实践-11

简单哈希函数 1978年，Rabin利用DES, 使用密文块链方式(CBC, Cipher Block Chaining)提出一种简单快速Hash函数： 2019/5/8 现代密码学理论与实践-11

简单哈希函数 将明文M分成固定长度64位的明文块(block)m1, m2, …, mn，使用DES的CBC操作方法，对每一明文块陆续加密 令h0 = 初始值，hi = Emi[hi-1]以及G = hn。 这种方法不使用密钥, G就是64位的哈希函数值, 不安全。 2019/5/8 现代密码学理论与实践-11

对哈希函数的攻击法 命题 若试图伪造明文M的签名，让签字人签名M’, 得到与M一样的签名, 即要找到满足H(M’)=H(M)的M’, 到底需要找多少明文才能找到这个对应的M’？ Rabin的方法 若一个函数可能有n个函数值，且已知一个函数值h(x)，任选k个任意数作为函数输入值，问：k必须多大才能保证至少找到一个输入值y，且 h(x) = h(y)的概率大于1/2？ 结论：当k>n/2时，这个概率将超过1/2 2019/5/8 现代密码学理论与实践-11

Rabin的对哈希函数的攻击法 对于任意y，满足h(x) = h(y)的概率是1/n，不满足的概率是1-1/n。k个任意输入没有一个满足h(x) = h(y)的概率是(1-1/n)k，至少有一个满足的概率是1-(1-1/n)k。根据二项式定理， (1-a)k = 1-ka +(k(k-1)/2!)a2 – (k(k-1)(k-2)/3!)a3 … 当a→0时，(1-a)k →1-ka. 所以，至少有一个y满足h(x) = h(y)的概率几乎等于 1-(1-ka) = ka, 这里, a即为1/n, 至少有一个y满足h(x) = h(y)的概率几乎等于k/n。当k>n/2时，这个概率将超过1/2。 因此，看来64位的Hash函数，有264种组合，攻击者只要尝试k >n/2，即264/2 = 263个明文，就有可能获得超过1/2的成功机会。 2019/5/8 现代密码学理论与实践-11

Yuval对哈希函数的生日悖论攻击法 但是，Yuval提出用生日悖论(Birthday Paradox)对Robin的方法进行攻击，证明只需要232次的运算就有可能获得超过1/2的成功机会。 生日攻击的数学背景 到底k要多大，才能在k个人中，至少找到两个人有同一天生日的概率大于1/2？ k个人的生日总排列数是365k，k个人有不同生日的总排列数为： N = Pk365 = 365!/(365-k)! 即第一个人可能有365种生日选择，第二个人必须不同于第一个人，所以有364种选择，依此类推。 2019/5/8 现代密码学理论与实践-11

对哈希函数的生日悖论攻击法 k个人有不同生日的概率 Q(365, k) = (365!/(365-k)!)/365k = 365!/(365k(365-k)!) k个人中至少有两个人有相同生日的概率是 P(365, k) = 1- Q(365, k) k要多大，才能保证在k个人中，至少有两个人同一天生日的概率大于1/2？ 计算得P(365, 23) = 0.5073，即k = 23。 当 k = 100时，P(365, 100) = 0.999997。 可以这样解释，在23个人当中，考虑某一个人的特定生日，在剩下的22个人中能找到相同特定生日的概率是很小的, 即使剩余每个人都有不同的生日，也只有22/365概率；但是只考虑同一天生，只有 = 253种不同的组合。所以只要23个人，找到两人同一天生的概率大于1/2: 253/365 2019/5/8 现代密码学理论与实践-11

生日悖论 2019/5/8 现代密码学理论与实践-11

散列函数和MAC的安全性 穷举攻击 密码分析 散列函数 消息认证码 2n/2将决定散列码抗击强行攻击的强度 安全散列函数 2019/5/8 现代密码学理论与实践-11

安全散列码的一般结构 2019/5/8 现代密码学理论与实践-11

习题与思考题 第11章： 2019/5/8 现代密码学理论与实践-11