消息认证和杂凑算法.ppt

消息认证和杂凑算法
第1页，共97页，编辑于2022年，星期日
第2页，共97页，编辑于2022年，星期日
第1章曾介绍过信息安全所面临的基本攻击类型，包括被动攻击（获取消息的内容、业务流分析）和主动攻击（假冒、重、MAC2，其中MAC2=CK(M2)。对上一轮得到的2k-n个可能的密钥计算MACi=CKi(M2)，得2k-2×n个可能的密钥。
如此下去，如果k=αn，则上述攻击方式平均需要α轮。例如，密钥长为80比特，MAC长为32比特，则第1轮将产生大约248个可能密钥，第2轮将产生216个可能的密钥，第3轮即可找出正确的密钥。
第12页，共97页，编辑于2022年，星期日
如果密钥长度小于MAC的长度，则第1轮就有可能找出正确的密钥，也有可能找出多个可能的密钥，如果是后者，则仍需执行第2轮搜索。
所以对消息认证码的穷搜索攻击比对使用相同长度密钥的加密算法的穷搜索攻击的代价还要大。然而有些攻击法却不需要寻找产生MAC所使用的密钥。
第13页，共97页，编辑于2022年，星期日
例如，设M=(X1‖X2‖…‖Xm)是由64比特长的分组Xi(i=1,…,m)链接得到的，其消息认证码由以下方式得到：
其中表示异或运算，加密算法是电码本模式的DES。因此，密钥长为56比特，MAC长为64比特，如果敌手得到M‖CK(M)，那么敌手使用穷搜索攻击寻找K将需做256次加密。然而敌手还可用以下方式攻击系统： 将X1到Xm-1分别用自己选取的Y1到Ym-1替换，求出Ym=Y1Y2…Ym-1Δ(M)，并用Ym替换Xm。因此敌手可成功伪造一新消息M′=Y1…Ym，且M′的MAC与原消息M的MAC相同。
第14页，共97页，编辑于2022年，星期日
考虑到MAC所存在的以上攻击类型，可知它应满足以下要求，其中假定敌手知道函数C，但不知道密钥K：
① 如果敌手得到M和CK(M)，则构造一满足CK(M′)=CK(M)的新消息M′在计算上是不可行的。
② CK(M)在以下意义下是均匀分布的： 随机选取两个消息M、M′，Pr[CK(M)=CK(M′)]=2-n，其中n为MAC的长。
③ 若M′是M的某个变换，即M′=f(M)，例如f为插入一个或多个比特，那么Pr[CK(M)=CK(M′)]= 2-n。
第15页，共97页，编辑于2022年，星期日
第1个要求是针对上例中的攻击类型的，此要求是说敌手不需要找出密钥K而伪造一个与截获的MAC相匹配的新消息在计算上是不可行的。第2个要求是说敌手如果截获一个MAC，则伪造一个相匹配的消息的概率为最小。最后一个要求是说函数C不应在消息的某个部分或某些比特弱于其他部分或其他比特，否则敌手获得M和MAC后就有可能修改M中弱的部分，从而伪造出一个与原MAC相匹配的新消息。
第16页，共97页，编辑于2022年，星期日
数据认证算法是最为广泛使用的消息认证码中的一个，已作为FIPS Publication（FIPS PUB 113）。
算法基于CBC模式的DES算法，其初始向量取为零向量。需被认证的数据（消息、记录、文件或程序）被分为64比特长的分组D1，D2，…，DN，其中最后一个分组不够64比特的话，可在其右边填充一些0，然后按以下过程计算数据认证码（）：
数据认证算法
第17页，共97页，编辑于2022年，星期日
数据认证算法
第18页，共97页，编辑于2022年，星期日
其中E为DES加密算法，K为密钥。
数据认证码或者取为ON或者取为ON的最左M个比特，其中16≤M≤64。
第19页，共97页，编辑于2022年，星期日
杂凑函数H是一公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值H(M)，作为认证符，称函数值H(M)为杂凑值、杂凑码或消息摘要。杂凑码是消息中所有比特的函数，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个比特都会使杂凑码发生改变。
杂凑函数 杂凑函数的定义及使用方式
第20页，共97页，编辑于2022年，星期日
表示杂凑函数用来提供消息认证的基本使用方式，共有以下6种（）：
① 消息与杂凑码链接后用单钥加密算法加密。由于所用密钥仅为收发双方A、B共享，因此可保证消息的确来自A并且未被篡改。同时还由于消息和杂凑码都被加密，这种方式还提供了保密性，(a)。
② 用单钥加密算法仅对杂凑码加密。这种方式用于不要求保密性的情况下，可减少处理负担。(a)的MAC结果完全一样，即将EK[H(M)]看作一个函数，函数的输入为消息M和密钥K，输出为固定长度，见图6