信息安全课程教学课件消息认证.ppt

其它hash算法 MD4 MD4使用三轮运算，每轮16步； MD5使用四轮运算，每轮16步。 MD4的第一轮没有使用加法常量，第二轮运算中每步迭代使用的加法常量相同，第三轮运算中每步迭代使用的加法常量相同，但不同于第二轮使用的加法常量；MD5的64部使用的加法常量T[i]均不同。 MD4使用三个基本逻辑函数，MD5使用四个。 MD5中每步迭代的结果都与前一步的结果相加，MD4则没有。 MD5比MD4更复杂，所以其执行速度也更慢，Rivest认为增加复杂性可以增加安全性。 RIPEMD-160 欧共体RIPE项目组研制。 输入可以是任意长的报文，输出160位摘要。 对输入按512位分组。以分组为单位处理。 算法的核心是具有十轮运算的模块，十轮运算分成两组，每组五轮，每轮16步迭代。 对Hash函数的攻击 对一个hash算法的攻击可分三个级别： 预映射攻击（Preimage Attack）：给定Hash值h，找到其所对应的明文M，使得Hash(M)=h，这种攻击是最彻底的，如果一个hash算法被人找出预映射，那这种算法是不能使用的。 次预映射攻击（Second Preimage Attack）：给定明文M1，找到另一明文M2（M1≠M2），使得hash(M1)=hash(M2)，这种攻击其实就是要寻找一个弱碰撞； 碰撞攻击 (Collision Attack)：找到M1和M2，使得hash(M1)=hash(M2) ，这种攻击其实就是要寻找一个强碰撞。 生日攻击 给定一个散列函数H和某hash值H(x)，假定H有n个可能的输出。如果H有k个随机输入, k必须为多大才能使至少存在一个输入y,使得H(y)=H(x)的概率大于0.5？ K=n/2 结论 如果hash码为m位，则有2m个可能的hash码。 如果给定h=H(X)，要想找到一个y，使H(y) =h的概率为0.5，则要进行多次的尝试，尝试的次数k=2m/2=2m-1 所以，对于一个使用64位的hash码，攻击者要想找到满足H(M’)=H(M)的M’来替代M，平均来讲，他要找到这样的消息大约要进行263次尝试。 但是，存在一种攻击，称为“生日攻击”，却可以大大减小尝试的次数，对于64位的hash码，所需的代价仅为232次。 生日悖论 一个教室中，最少应有多少学生，才使至少有两人具有相同生日的概率不小于1/2？ 概率结果与人的直觉是相违背的. 实际上只需23人,即任找23人，从中总能选出两人具有相同生日的概率至少为1/2。 一个不等式：(1-x)≤e-x (x≥0) 当x很小，趋近于0时， (1-x)≈ e-x 两个集合中元素的重复 给定两个集合X和Y，每个集合有k个元素： X:{x1,x2,…,xk}, Y:{y1,y2,…,yk}, 其中，各元素的取值是1~n之间的均匀分布的随机值(kn) 那么，这两个集合中至少有一个元素相同(重复)的概率R(n,k)是多少呢？ 给定x1，那么y1=x1的概率为1/n，所以y1≠x1的概率为1-1/n。那么Y中的k个值都不等于x1的概率为(1-1/n)k 同理，给定x2，那么Y中的k个值都不等于x2的概率为(1-1/n)k 同理，给定xk，那么Y中的k个值都不等于xk的概率为(1-1/n)k 所以，Y中没有元素与X中元素相同的概率为： 那么， Y中至少有一个元素与X中元素相同的概率为： 根据不等式：(1-x)≤e-x (x≥0)可知： 实施生日攻击 前面提到过，对于一个使用64位的hash码，攻击者要想找到满足H(M’)=H(M)的M’来替代M，平均来讲，他要找到这样的消息大约要进行263次尝试。这太困难了！ 设M和hash算法生成64位的hash值。 攻击者可以根据M，产生232个表达相同含义的变式(例如在词与词之间多加一个空格)。 同时准备好伪造的消息M’，产生232个表达相同含义的变式。 在这两个集合中，找出产生相同hash码的一对消息M1和M1’。根据生日悖论，找到这样一对消息的概率大于0.5。 最后，攻击者将拿M1给发送者签名，但发送时，把M1’和经加密的hash码一起发送。 Birthday Attacks: example A准备两份合同M和M′ ，一份B会同意，一份会取走他的财产而被拒绝 A对M和M′各做32处微小变化(保持原意),分别产生232个64位hash值 根据前面的结论,超过0.5的概率能找到一个M和一个M′,它们的hash值相同 A提交M,经B审阅后产生64位hash值并对该值签名,返回给A A用M′替换M Hash与MAC的区别 MAC需要对全部数据进行加密 MAC速度慢 Hash是一种直接产生鉴别码的方法 Hash可用于数字签名 常用Hash算法 迭代型