信息安全导论（以问题为导向） 课件 05 报文鉴别与哈希函数

1报文鉴别与哈希函数教学视频、国家级一流在线课程链接：/course/FUDAN-1206357811内容提要安全服务与安全需求报文鉴别的安全需求对报文加密来实现报文鉴别报文鉴别码哈希函数生日攻击2内容提要1、安全服务与安全需求34复习：安全服务/安全需求我们的故事从哪里开始？

通信保密

：较早期的安全需求公开密钥密码对称密钥密码提炼：安全服务/安全需求“通信保密”可以概括所有的安全需求吗？

答：不能。信息安全需求有许多种，通信保密只是一种安全需求，我们对现实世界的安全需求提炼和归类，用以下抽象名词来概括典型的安全需求保密性（Confidentiality）完整性（Integrity）可用性（Availability）可认证（Authentication）抗抵赖/抗否认（Non-repudiation）5内容提要2、报文鉴别的安全需求6安全需求分析的例子泄密流量分析修改内容破坏数据包收到的先后顺序不承认发送过某个报文冒名顶替浏览器访问网银Web服务器应用的安全需求78报文鉴别的安全需求报文鉴别的三重含义（安全需求）:1）保护报文的完整性2）验证发送者的身份3）抗抵赖：防止报文发送者抵赖

（解决争议）将尝试以下三种方案实现报文鉴别:报文加密报文鉴别码(MAC)HASH（哈希）函数9报文鉴别的含义注意：不是所有的方案都能够完整实现上述报文鉴别所包括的三个安全需求：1）需要仔细甄别2）训练密码学思维；3）分析过程比结论重要：将尝试以下三种方案实现报文鉴别:报文加密报文鉴别码(MAC)HASH（哈希）函数10一些名词的含意

报文vs.

明文

我们有时候不考虑保密性.报文鉴别（Message

Authentication）vs.身份认证（Authentication）内容提要3、对报文加密来实现报文鉴别3.1用对称密钥1112报文加密-对称密钥报文加密在提供保密性的同时，本身也能提供了某些报文鉴别的安全服务如果发送者使用对称密钥加密报文:接收者知道发送者创建了它（前提：接收者自己没有创建过）因为现在只有发送者和接收者知道这个对称密钥知道报文内容在通信过程中没有被篡改发送者（Source）A接收者（Destination）B13报文加密-对称密钥接收到的密文可以解密为明文，但可能难以自动确定报文是否被篡改报文应具有合适的结构，冗余信息或校验和来检测报文是否被更改发送者（Source）A接收者（Destination）B14报文加密-对称密钥AB:

E(K,M)，或记作EK(M)保密性——只有A和B知道K一定程度的报文鉴别——只能来自于A——传输过程中没被篡改 —需要有特定的格式/冗余不提供抗抵赖——接受者不能伪造报文——发送者不能否认报文发送者（Source）A接收者（Destination）B内容提要3、对报文加密来实现报文鉴别3.2用公开密钥密码1516报文加密-公钥加密如果使用公钥加密:无法实现报文鉴别所包括的任何一项安全服务因为任何人都知道公钥仅能提供“保密性”发送者（Source）A接收者（Destination）B17报文加密-私钥加密(签名)如果使用私钥加密:如果发送者使用私钥加密，则不具有保密性因为任何人都知道公钥然而可以实现报文鉴别所有的安全需求仍然需要冗余信息确认报文是否被篡改发送者（Source）A接收者（Destination）B18报文加密-先私钥后公钥发送者用私钥对报文签名，然后使用接收者的公钥加密同时提供保密性和报文鉴别的所有三种安全服务代价是需要使用两个公钥发送者（Source）A接收者（Destination）B19报文加密－公开密钥总结

公钥加密：仅提供保密性20报文加密－公开密钥总结

私钥加密：报文鉴别所有的三种安全服务21报文加密-私钥加密(签名)

发送者（Source）A接收者（Destination）B22报文加密－公开密钥总结

先私钥后公钥加密：保密性、报文鉴别的所有三种服务内容提要4、报文鉴别码4.1报文鉴别码的定义2324用加密实现报文鉴别的缺点Q:报文加密的缺点?开销

加密整个报文，相当于用整个报文作文报文鉴别码较难实现自动的25报文鉴别码(MAC)报文鉴别码：固定长度的比特串（例如128个bit,等）由报文鉴别码算法生成算法的输入包括：报文和密钥算法设计类似于对称密钥算法，但不可逆附加到报文上用于报文鉴别接收者对报文执行相同方向的计算并检查它是否与收到的MAC匹配确保报文来自声称的发送者且传输过程中没被篡改26报文鉴别码如图所示MAC提供报文鉴别的完整性、发送者身份验证两种安全服务27报文鉴别码为什么用MAC?有时候只需要报文鉴别有时需要长时间保存数据的完整性(例如：档案)注意MAC不是数字签名内容提要4、报文鉴别码4.2报文鉴别码的用法2829报文鉴别码的用法

(a)报文鉴别的1，2两项安全服务发送者（Source）A接收者（Destination）B30报文鉴别码的用法发送者（Source）A接收者（Destination）B

(b)保密性和报文鉴别的第1和2项服务明文加报文鉴别码31报文鉴别码的用法发送者（Source）A接收者（Destination）B

(b)保密性和报文鉴别的第1和2项服务密文加报文鉴别码内容提要4、报文鉴别码4.3报文鉴别码的性质3233MAC的性质MAC是密码性质校验和

MAC=CK(M)压缩可变长度的报文M使用秘钥K输出固定长度的报文鉴别码是一个多对一的函数可能许多报文有相同的MAC但是找到这些MAC值相同的报文是非常困难的34MAC的要求攻击：能够找到M’≠M,但CK(M’)＝CK(M)需要MAC满足以下要求:不能通过一个报文和它的MAC，找到另一条有相同MAC的报文MAC应该是均匀分布的MAC应该取决于报文的每一位35可以使用分组密码的CBC（CipherBlockChaining）模式将最后一个密文块作为MACDataAuthenticationAlgorithm(DAA)

报文鉴别码算法就是基于DES-CBC，是一个早期的MAC生成算法令IV=0并用比特0填充最后一个明文块在CBC模式下使用DES加密报文将最后一个密文块作为MAC值或者最后一个块的最左边的M位(16≤M≤64)这个算法最终得到的MAC太短，不够安全简单的构造MAC算法的方法36DAA算法内容提要5、哈希函数5.1哈希函数的定义与性质3738哈希函数（Hash）将任意长度的报文压缩到固定长度的二进制串：

h=H(M)

通常假设哈希函数是公开的没有密钥注意MAC使用对称密钥用于检测报文是否被更改

保护完整性能够通过多种不同的方式应用于报文经常用于创建数字签名39哈希函数和数字签名40哈希函数性质实质上是生成输入文件/报文/数据的指纹

h=H(M)压缩可变长度的报文M生成固定长度的指纹找到碰撞构成对哈希的攻击：找到M’≠M,但H(M’)＝H(M)41对哈希函数的要求可应用于任意大小的报文

M生成固定长度的输出h很容易计算报文M的哈希值：h=H(M)

已知h，不能计算得到x

使得

H(x)=h单向性给定

x，找到

y，使得H(y)=H(x)是计算上不可行的弱抗碰撞性找到任意的

x,y；

使得H(y)=H(x)是计算上不可行的强抗碰撞性内容提要5、哈希函数5.2哈希函数的用法4243哈希函数的应用44哈希函数的应用(a)加密报文和哈希值(d)加密(c)的输出–用对称密钥(b)仅加密哈希值–用对称密钥(c)加密哈希值–发送者的私钥(e)计算报文和随机数的哈希值(f)加密(e)的输出内容提要5、哈希函数5.3哈希函数的算法实现4647简单的哈希函数现将报文分组，报文分组异或运算的结果作为哈希值可以防止随机的报文比特错，但不够安全

需要有密码性质的安全性更高的函数48用分组密码构造哈希函数可以使用分组密码构造哈希函数令H0=0并用零填充最后一个分组计算:Hi=EMi[Hi-1]将最后一个分组看做哈希值类似于CBC

方法，但不使用密钥哈希值相对较短(限制为密文分组大小)49哈希算法的一般结构

50经典的哈希算法MD5SHA-1RIPEMD-16051MD5由RonaldRivest设计（RSA设计者之一）一系列Hash算法MD2,MD4…

生成128-bit的哈希值曾经是广泛使用的哈希算法成为Internet标准－RFC1321200x年起，穷举攻击和密码分析都受到广泛关注MD5算法分析工作，中国学者做出了重大贡献。王小云等提出模差比特跟踪法快速寻找哈希碰撞。在CRYPTO2004会议的快报中，王小云和同事演示了如何快速找到MD5和其他相关哈希函数中的碰撞。他们的工作获得了极大的国际影响和关注。52SecureHashAlgorithm(SHA)SHA最初由NIST和NSA于1993年设计于1995年修订为SHA-1与DSA签名方案一起使用作为美国标准标准号FIPS180-11995,也是因特网标准RFC3174基于MD4设计生成160-bit的哈希值2005年起，针对SHA-1安全性的最新碰撞分析研究结果，引起了一定程度担忧53修订版SHA2002年，NIST发布了修订版FIPS180-2给出了3种新的SHA版本

SHA-256,SHA-384,SHA-512为兼容AES密码提供的更高的安全性而设计结构和相关细节与SHA-1类似。因此，相关密码分析是类似的，安全级别更高54SHA-512概览55RIPEMD-160RIPEMD-160是在欧洲开发的参与攻击MD4/5的研究人员设计某些方面与MD5/SHA类似

生成160-bit哈希值

比SHA慢，但更安全56哈希函数的安全性讨论像分组密码一样，穷举攻击是最好的选择前提是算法没有漏洞暴力破解穷举攻击的平均尝试次数是2m/2

其中m是输出的哈希值的bit数量目前，128-bit哈希安全性较弱,160-bit甚至哈希值更长更好注意：分组密码穷举攻击的平均尝试次数是1/2*2m，其中m是密钥长度内容提要6、生日攻击5758生日攻击（BirthdayAttacks）生日悖论在一组23名随机选择的人中，至少有两人同一天生日的概率约为50％。如果有30人，则概率约为70％。

找到具有相同生日的两个人与找到哈希碰撞是一回事。59生日攻击23个人生日各不相同的概率是

因此至少两个人生日相同的概率为1-0.493=0.507上述公式不易求解，需要找到近似函数：

推广到n个人的情形60n

个人生日各不相同的概率约为至少两个人生日相同的概率约为更一般地说，假设我们有N个对象，N很大。有

r个人，每个人选择一个对象61生日攻击选择

r2/2N=ln2,我们发现如果r≈1.177,那么至少两个人选择同一个对象的概率为50%。如果有N种可能性(N种哈希值)，并且我们有一个长度为

的列表（个报文），那么匹配的可能性在50％左右。如果我们想增大匹配的可能性，我们可以列出一个长度为的常数倍的列表。62生日攻击(例子)我们有40个车牌，设每个车牌都以