第6章 消息认证和杂凑算法主要内容l消息认证码l杂凑函数lMD5杂凑算法l安全杂凑算法lHMAC消息认证l消息认证用于抗击主动攻击l验证接收消息的真实性和完整性l验证消息的顺序性和时间性（未重排、重放和延迟）消息认证l网络环境中的攻击(认证的需求) 1.泄漏 2.通信量分析 3.伪装(假报文) 4.内容篡改(插入,删除,调换和修改) 5.序号篡改(报文序号的修改) 6.计时篡改(报文延迟或回放) 7.抵赖(否认收或发某报文)消息认证l消息加密l消息认证码(MAC)lHash函数信源信宿 MEEk(M)DMA方B方kk Dk(Ek(M)常规加密：具有机密性，认证性消息加密提供认证信源信宿 MEEk(M)DMA方B方kk Dk(Ek(M)KUbMEEKUb(M)DMA方B方KRb(1) 公钥加密：机密性MEEKRa(M)DMA方B方KRaKUa(2) 私钥加密：认证性消息加密提供认证MEEkRa(M)EEKUb(EkRa(M)A方KRaKUbDEkRa(M)DMB方KRbKUa(3) 先私钥后公钥加密：机密性，认证性消息加密提供认证消息认证码l消息被一密钥控制的公开函数作用后产生 的、用于认证符的、固定长度的数值，称 为消息认证码，也称为密码校验和。消息认证码的使用方式l通信双方共享密钥KM|CKMCK(M)CK比较消息认证码的使用方式l认证性和保密性-对明文认证M|CK1CMCK1(M)K1比较EK2DK2消息认证码的使用方式l认证性和保密性-对密文认证M|CK1CK1比较EK2DK2产生MAC函数应满足的要求l产生MAC的函数一般为多到一映射。nbit长的 MAC共有2n个可能的取值，可能的消息数远大 于2n。l密钥长度为kbit，可能的密钥数为2k。l敌手有可能不直接攻击密钥，而伪造能够通过 检验的MAC和M。产生MAC函数应满足的要求l假定敌手知道函数C，不知道Kl如果敌手得到M和CK(M)，则构造一满足CK( )= CK(M)的新消息 在计算上不可行lCK(M)在以下意义下是均匀分布的：随机选两个M, ,PrCK( )=CK(M)=2-nl若 是M的某个变换,PrCK(M)=CK( )=2-nCBC-MACl基于CBC模式的DES算法，初始向量取为零。D1DES加密O1K第1次D2DES加密O2K第2次+D2DES加密ONK第N次+ON-1消息认证码与杂凑函数l消息认证码的特点不需要恢复原报文报文的特征要唯一地体现到MAC中密钥是必要的 从报文产生特征的数学方法 杂凑函数HASH函数杂凑函数的定义l杂凑函数H是一个公开函数，将任意长的消息M 映射为较短的、固定长度的一个值H(M)l函数参数l输入：可以任意长度l输出：必须固定长度，一般64、128、160bitslH(M)称为杂凑值、消息摘要，是消息中所有比 特的函数，提供了错误检测的能力。杂凑函数的使用方式l消息与杂凑值连接后用单钥加密，密钥为A,B 共享，保证消息来自A并且不被篡改杂凑函数的使用方式l单钥加密函数仅对杂凑值加密杂凑函数的使用方式l使用发送方私钥加密杂凑值杂凑函数的使用方式l用发送方私钥加密杂凑值，再用单钥加密整个 数据杂凑函数的使用方式l通信双方共享一个秘密值S杂凑函数的使用方式l在上一方式基础上用上加密杂凑函数应满足的条件l已知x,计算H(x)较为容易，已知h，求x使得 H(x)h在计算上不可行，若H满足这一性质， 则称H为单向杂凑函数；l已知H(x)h，求y使得H(y)h在计算上不可 行,若H满足这一性质，则称H为弱单向杂凑函 数；（抗弱碰撞性）l找出任意两个不同的x,y，使得H(x)=H(y)在计 算上不可行，若H满足这一性质，则称H为强单 向杂凑函数（抗强碰撞性）简单的杂凑函数l每个分组按比特异或: Ci = bi1bi2 . bim 其中, Ci是第i个比特的Hash码,1in;m是输入的n比特分组数;bij是第j分组的第i比特;简单的Hash函数的改进方案先将n比特的Hash值设置为0;l按如下方式依次处理数据分组:l将当前的Hash值循环左移一位.l将数据分组与Hash值异或形成新的 Hash值. 这将起到输入数据完全随机化的效果,并且 将输入中的数据格式掩盖掉.生日悖论l在一个会场参加会议的人中，使参会人员中至 少有两人是同日出生的概率超过0.5的参会人 数至少为多少人？k个人都不是同日出生时概率Q(365,k)至少有两人是同日出生的概率P(365,k)P(365,k)1- Q(365,k)生日悖论概率Q(365,k)概率P(365,k)当k23时， P(365,k)0.5。生日悖论推广到一般，假设有N个对象，有r个人， 每个人选择一个对象（可以重复选择）， 那么Prob(重复出现）生日攻击lH有n个可能的输出，H(x)是一个特定的输出， 如果对H随机取k个输入，至少有一个输入y使H(y)=H(x)的概率为0.5时，k有多大？生日攻击l简要分析：H(y)=H(x)的概率为1/n，H(y) H(x)的概率为1-1/n。随机输入的k个值y都使H(y)=H(x)不等的概率为1-1/nk至少有一个y,使得H(y)=H(x)的概率为1 1-1/nk 0.5 解得k=n/2生日攻击lH有 个可能的输出，如果H的k个随机输入中 至少有两个产生相同的输出的概率大于0.5， 则k=l生日攻击具体方式bY0nIV= CV0fbY1nfbYL-1nCVL-1fCV1nnIV = 初始值 CV = 链接值 Yi = 第i 个输入数据块 f = 压缩算法 n = Hash码的长度 b = 输入块的长度迭代型杂凑函数的一般结构CVLCV0=IV= initial n-bit value CVi=f(CVi-1, Yi-1) (1 i L) H(M) = CVLMD5 算法l输入：任意长度的消息l输出：128位消息摘要l处理：以512位输入数据块为单位MD5 (RFC 1321) was developed by Ron Rivest (“R” of the RSA )at MIT in 90s.报文K bitsL512 bits=N 32bits报文长度 (K mod 264)填充 (1 to 512 bits)1000Y0512 bitsY1512 bitsYq512 bitsYL-1512 bitsHMD5 IV128HMD5 CV1128HMD5 CVq128HMD5 CVL-1128512512512512128-bit 摘要MD5产生报文摘要的过程MD5算法描述步骤1：添加填充位(一个1 和若干个0)。在 消息的最后添加适当的填充位使得数据位的 长度满足length 448 mod 512。 步骤2：添加长度。原始消息长度（二进制 位的个数），用64位表示。如果长度超过264 位，则仅取最低64位，即mod 264。MD5算法描述l步骤3：初始化MD缓冲区。一个128位MD 缓冲区用以保存中间和最终Hash函数的结 果。l它可以表示为4个32位的寄存器(A,B,C,D)寄存器初始化为以下的16进制值。 A = 67452301 B = EFCDAB89 C = 98BADCFE D = 10325476MD5算法描述l上述值的存储方式为：Word A: 01 23 45 67 Word B: 89 AB CD EF Word C: FE DC BA 98 Word D: 76 54 32 10MD5算法描述l步骤4：处理消息块（512位 = 16个32位字 ）。压缩函数是本算法的核心(HMD5)。它包 括4轮处理。四轮处理具有相似的结构,但每 次使用不同的基本逻辑函数，记为F,G,H,I 。每一轮以当前的512位数据块(Yq)和128 位缓冲值ABCD作为输入，并修改缓冲值的 内容。每次使用64元素表T164中的四 分之一.T表，由sin 函数构造而成。T的第i个元素表示 为Ti，其值等于 232abs(sin(i),其中i是弧度。 由于abs(sin(i)是一个0到1之间的数，T的每一 个元素是一个可以表示成32位的整数。T表提 供了随机化的32位模板，消除了在输入数据中 的任何规律性的特征。 MD5算法描述T1 = D76AA478 T2 = E8C7B756 T3 = 242070DB T4 = C1BDCEEE T16 = 49b40821T49 = F4292244 T50 = 432AFF97 T51 = AB9423A7 T52 = FC93A039T64 = EB86D391MD5算法描述步骤5：输出结果。所有L个512位数据块处 理完毕后，最后的结果就是128位消息摘要CV0 = IVCVq+1 = SUM32(CVq,RFIYq,RFHYq,RFGYq,RFFYq, CVq)MD = CVLMD5算法描述MD5算法描述lIV = ABCD的初始值（见步骤3）lYq = 消息的第q个512位数据块lL = 消息中数据块数；lCVq = 链接变量，用于第q个数据块的处理lRFx = 使用基本逻辑函数x的一轮功能函数。lMD = 最终消息摘要结果lSUM32=分别按32位字计算的模 加法结果。F,T116,Xi 16 stepsG,T1732,X2i 16 stepsH,T3348,X3i 16 stepsI,T4964,X4i 16 steps+ABCDABCDABCDABCDCVq12832Yq512CVq+1128单个 512-bit 分组的 MD5 处理过程+ is mod 232MD5 压缩函数每一轮包含对缓冲区ABCD的16步操作所组成的一个 序列。 ba + ( b + g(b,c,d) + Xk +Ti)s) 其中， a,b,c,d = 缓冲区的四个字，以一个给定的次序排列; g = 基本逻辑函数F,G,H,I之一； s = 对32位字循环左移s位 Xk = Mq16 + k = 在第q个512位数据块中的第k 个32位字 Ti = 表T中的第i个32位字； + = 模 232的加；逻辑函数的真值表b c d F G H I 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0ABCDABCD+CLSs+gXkTiFunction g g(b,c,d) 1 F(b,c,d) (bc)(bd) 2 G(b,c,d) (bd)(cd) 3 H(b,c,d) bcd 4 I(b,c,d) c(bd)2i = (1+5i) mod 16 3i = (5+3i) mod 16 4i = 7i mod 16SHA-1 算法描述l输入：最大长度为264位的消息；l输出：160位消息摘要；l处理：输入以512位数据块为单位处理；SHA由美国国家标准技术研究所NIST开发，作为联邦 信息处理标准于1993年发表（FIPS PUB 180），1995 年修订，作为SHA-1(FIPS PUB 180-1)，SHA-1基于 MD4设计。SHA-1 算法