第六章-消息认证和杂凑算法-2015-6.

《第六章-消息认证和杂凑算法-2015-6.》由会员分享，可在线阅读，更多相关《第六章-消息认证和杂凑算法-2015-6.（85页珍藏版）》请在金锄头文库上搜索。

1、信息安全理论与应用,第六章消息认证和杂凑算法,主讲教师：梁向前 研究方向：密码学与信息安全 Email ：liangxq87,本章提要,6.1 消息认证码 6.2 杂凑函数 6.3 MD5杂凑算法 6.4 安全杂凑算法SHA SHA-3(Keccak算法)简介 6.5 HMAC,1,6.1 消息认证码,6.1.1 消息认证码的定义及使用方式 信息安全所面临的基本攻击类型，包括： 被动攻击（获取消息的内容、业务流分析） 抗击被动攻击的方法是加密，伪装 主动攻击（假冒、重放、消息的篡改、业务拒绝(中断)） 消息认证则是用来抗击主动攻击的方式之一,2,消息认证的作用和含义： 消息认证用以验证接收消息

2、的如下属性： 真实性（的确是由它所声称的实体发来的：消息源认证） 完整性（未被篡改、插入、删除） 消息的顺序性和时间性（未重排、重放、延迟） 业务的不可否认性（即防止通信双方中的某一方对所传输消息的否认） 实现消息的不可否认性可通过数字签字，数字签字也是一种认证技术，它也可用于抗击主动攻击,3,消息认证机制和数字签字机制需要有产生认证符的基本功能 这一基本功能又作为认证协议的一个组成部分 认证符是用于认证消息的数值，经过压缩函数计算而得 认证符的产生有两大类 消息认证码：MAC(Message Authentication Code) 杂凑函数(也称散列函数，hash function) 消息

3、认证码MAC指消息被一密钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值，也称为密码校验和 此时需要通信双方A和B共享一密钥k,4,设A欲发送给B的消息是M，A首先计算MAC=CK(M)，其中CK()是密钥控制的公开函数，然后向B发送MMAC， B收到后做与A相同的计算，求得一新MAC，并与收到的MAC做比较，如图1(a)所示,消息的完整性和消息源认证,图(b)的方式最常用,5,如果仅收发双方知道K，且B计算得到的MAC与接收到的MAC一致，则该系统就实现了以下功能： 消息完整性：接收方相信发送方发来的消息未被篡改，因为攻击者不知道密钥，所以不能够在篡改消息后相应地篡改MAC，而如果

4、仅篡改消息，则接收方计算的新MAC将与收到的MAC不同 消息源认证：接收方相信发送方不是冒充的，这是因为除收发双方外再无其他人知道密钥，因此其他人不可能对自己发送的消息计算出正确的MAC MAC函数与加密算法的不同之处为MAC函数不必是可逆的，因此与加密算法相比更不易被攻破,MAC与加密算法不同,6,图1(a)中，由于消息本身在发送过程中是明文形式，所以这一过程只提供认证性而未提供保密性 为提供保密性可在MAC函数以后(如图1(b)或以前(如图1(c)进行一次加密，而且加密密钥也需被收发双方共享 在图1(b)中，M与MAC链接后再被整体加密 在图1(c)中，M先被加密再与MAC链接后发送 通常

5、希望直接对明文进行认证，因此图1(b)所示的使用方式更为常用,7,注意:加密密钥和认证密钥必须不同（如果有两处需要密钥的话） 加密密钥与认证密钥不同则对保密性的破译不会给认证性的破译带来效益，有效密钥长度为二者之和 如果二者相同，则对保密性的破译，同时也对认证性的破译也有一定效益，这时有效密钥长度至多为一个密钥的长度。也可以把认证和保密算法看成是单一密钥控制下的一个算法 因此加密密钥与认证密钥相同则实际上降低了总的安全性。 比如 认证后使用同一个密钥加密，则如果攻击者通过对密文的破译而找到加密密钥，则认证秘钥也同时被破译了，从而也失去了认证性 对加密密钥的破译比对消息认证码的破译要容易的多,8

6、,6.1.2 产生MAC的函数应满足的要求,使用加密算法(单钥或公钥算法)加密消息时，其安全性一般取决于密钥的长度 如果加密算法没有弱点，则敌手只能使用穷搜索攻击，直到得到有意义的明文 对于消息认证码MAC，其产生函数一般都为多到一映射 如果产生n比特长的MAC，则函数的取值范围即为2n个可能的MAC 函数输入可能的消息个数N2n，而且如果函数所用的密钥为k比特，则可能的密钥个数为2k。 如果系统不考虑保密性，即敌手能获取明文消息和相应的MAC，那么在这种情况下要考虑敌手使用穷搜索攻击来获取产生MAC的函数所使用的密钥,9,一种穷搜索攻击 假定kn，且敌手已得到M1和MAC1，其中MAC1=C

7、K1(M1)，敌手对所有可能密钥值Ki求MACi=CKi(M1)，直到找到Ki使得MACi=MAC1 由于kn，2k个密钥仅能产生2n个不同的MAC，所以有很多密钥（平均有2k/2n=2k-n个）都可产生出正确的MAC1，而敌手无法知道进行通信的两个用户用的是哪一个密钥，还必须按以下方式重复上述攻击： 第1轮 已知M1、MAC1，其中MAC1=CK(M1)。对所有2k个可能的密钥计算MACi=CKi(M1)，得2k-n个可能的密钥 第2轮 已知M2、MAC2，其中MAC2=CK(M2)。对上一轮得到的2k-n个可能的密钥计算MACi= CKi(M2)，得2k-2n个可能的密钥 如此下去，如果k

8、=n，则上述攻击方式平均需要轮。例如，密钥长为80比特，MAC长为32比特，则第1轮将产生大约248个可能密钥，第2轮将产生216个可能的密钥，第3轮即可找出正确的密钥 如果密钥长度小于MAC的长度， kn，则第1轮就有可能找出正确的密钥，也有可能找出多个可能的密钥，如果是后者，则仍需执行第2轮搜索,10,所以对消息认证码的穷搜索攻击比对使用相同长度密钥的加密算法的穷搜索攻击的代价还要大(所以加密和认证密钥不能同) 然而有些攻击方法不需要寻找产生MAC的密钥 例如，设M=(X1X2Xm)是由64比特长的分组Xi(i=1,m)链接得到的，其消息认证码由以下方式得到： (M)=X1X2 Xm CK

9、(M)=EK(M) 其中表示异或运算，加密算法是电码本模式的DES。 密钥长为56比特，MAC长为64比特， 如果敌手得到MCK(M)，那么敌手使用穷搜索攻击寻找K将需做256次加密 然而敌手还可用以下方式攻击系统：将X1到Xm-1分别用自己选取的Y1到Ym-1替换，求出Ym= Y1Y2 Ym-1 (M)，并用Ym替换Xm。因此敌手可成功伪造一新消息M= Y1Y2 Ym，且M的MAC与原消息M的MAC相同,11,考虑到MAC所存在的以上攻击类型，可知它应满足以下要求，其中假定敌手知道函数C，但不知道密钥K： 如果敌手得到M和CK(M)，则构造一满足CK(M)=CK(M)的新消息M 在计算上是不

10、可行的 第1个要求是针对上例中的攻击类型的，此要求是说敌手不需找出密钥K, 而伪造一个与截获的MAC相匹配的新消息在计算上是不可行的 CK(M)在以下意义下是均匀分布的：随机选取两个消息M、M，PrCK(M)=CK(M)=2-n，其中n为MAC的长 第2个要求是说敌手如果截获一个MAC，则伪造一个相匹配的消息的概率为最小 若M是M的某个变换，即M=f(M)，例如f为插入一个或多个比特，那么PrCK(M)=CK(M)=2-n 最后一个要求是说函数C不应在消息的某个部分或某些比特弱于其他部分或其他比特，否则敌手获得M和MAC后就有可能修改M中弱的部分，从而伪造出一个与原MAC相匹配的新消息,12,

11、6.1.3 数据认证算法,数据认证算法是最为广泛使用的消息认证码中的一个，已作为FIPS Publication（FIPS PUB 113）并被ANSI作为X9.17标准 算法基于CBC模式的DES算法，其初始向量为零向量 需被认证的数据(消息、记录、文件或程序)被分为64比特长的分组D1，D2，DN， 其中最后一个分组不够64比特的话，可在其右边填充一些0，然后按下图所示过程计算数据认证码,13,O1=EK(D1) O2=EK(D2O1) O3=EK(D3O2) ON=EK(DNON-1) 其中E为DES加密算法，K为密钥 数据认证码或者取为ON或者取为ON的最左M个比特，其中16M64。,

12、14,6.2 杂凑函数,6.2.1杂凑函数的定义及使用方式 杂凑函数H是一公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值H(M)，作为认证符，称函数值H(M)为杂凑值、杂凑码或消息摘要 杂凑函数又称散列函数、哈希函数、hash函数 杂凑码是消息中所有比特的函数，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个比特都会使杂凑码发生改变 杂凑函数用来提供消息认证的基本使用方式，共有6种,15,第一类：先hash、再对称加密 消息与杂凑码链接后用单钥加密算法加密：见图3(a) 提供消息的保密性、认证性、完整性 用单钥加密算法仅对杂凑码加密：见图3(b) 提供消息的认证性、完整

13、性 用于不要求保密性的情况，可减少处理负担。将EKH(M)看作一个函数，函数的输入为消息M和密钥K，输出为固定长度,16,第二类：先hash，再签名 用公钥加密算法和发方秘密钥仅加密杂凑码：见图3(c) 提供消息的认证性、完整性、不可否认性 事实上这种方式就是数字签字 由于加密运算的速度较慢，代价较高，而且很多加密算法还受到专利保护，因此在不要求保密性的情况下，方式和将比其他方式更具优势 消息的杂凑值用公钥加密算法和发方秘密钥加密后与消息链接，再对链接后的结果用单钥加密:见图3(d) 提供了消息的保密性和数字签字(认证性、完整性、不可否认性),17,第三类：带密钥的hash(共享秘密值),实际

14、上是一种MAC 发方计算消息M和秘密值S链接在一起的杂凑值，作为M的认证码：见图3(e) 要求通信双方共享一个秘密值S 提供消息的认证性、完整性 对中的消息认证码再增加单钥加密运算：见图3(f) 提供消息的保密性、认证性、完整性,18,6.2.2杂凑函数应满足的条件,杂凑函数的目的是为需认证的数据产生一个“指纹”。为了能够实现对数据的认证，杂凑函数应满足以下条件： 函数的输入可以是任意长 函数的输出是固定长 已知x，求H(x)较为容易，可用硬件或软件实现 前3个是杂凑函数能用于消息认证的基本要求 已知h，求使得H(x)=h的x在计算上是不可行的，这一性质称为函数的单向性，称H(x)为单向散列函

15、数 单向性对使用秘密值的认证技术(见图3(e)极为重要。假如不具有单向性，则攻击者截获M和C=H(SM)后，求C的逆SM，就可求出秘密值S,19, 已知x，找出y(yx)使得H(y)=H(x)在计算上是不可行的 满足这一性质的单向散列函数称为弱单向散列函数 第5个条件使得敌手无法在已知某个消息时，找到与该消息具有相同杂凑值的另一消息 这一性质用于杂凑值被加密情况时(见图3(b)和图3(c)防止敌手的伪造，由于在这种情况下，敌手可读取传送的明文消息M，因此能产生该消息的杂凑值H(M)。进而产生一个具有相同杂凑值的伪造消息，再将伪造的消息和截获的加密的杂凑值发往通信的接收方 但由于敌手不知道用于加

16、密杂凑值的密钥，他就不可能既伪造一个消息M，又伪造这个消息的杂凑值加密后的密文EKH(M),20, 找出任意两个不同的输入x、y，使得H(y)=H(x)在计算上是不可行的 如果单向散列函数满足这一性质，则称其为强单向散列函数 第6个条件用于抵抗生日攻击 第和第个条件给出了杂凑函数无碰撞性的概念，如果杂凑函数对不同的输入可产生相同的输出，则称该函数具有碰撞性,21,6.2.3生日攻击,1. 第I类生日攻击 已知一散列函数H有n个可能输出，H(x)是一特定输出，若对H随机取k个输入，则至少有一个输入y使得H(y)=H(x)的概率为0.5时，k有多大？ 称对散列函数H寻找上述 y 的攻击为第I类生日攻击 第I类生日攻击的概率计算 因为H有n个可能的输出，所以输入y产生的输出H(y)等于特定输出H(x)的概率是1/n y取k个随机值而函数的k个输出中没有一个等于H(x)的概率等于1-1