信息安全原理与实践-第二版05-哈希函数及其他-PPT

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,大家好,*,1,信息安全原理与实践,Information Security:Principles and Practice,2nd Edition,美,Mark Stamp,著,张 戈译,大家好,2,第,5,章 哈希函数及其他,大家好,3,5.1,引言,本章内容,加密哈希函数,加密哈希函数的标准应用,哈希函数的高级应用,加密相关的副作用问题,大家好,4,5.2,什么是加密哈希函数,一个加密哈希函数,h,(,x,),，必须满足下列所有条件：,压缩,对于任何长度的输入值,x,，输出值,y,=,h,(,x,),的长度都比较小。在实际使用中，通常输出值是固定长度的,(,比如,160,位长度的二进制值,),，而无论输入值的长度是多少。,高效,对于任何的输入值,x,，必须能够很容易地计算出,h,(,x,),。当然，伴随着输入值,x,的长度增加，计算,h,(,x,),所需要的计算量也会随之增加，但是，这不能增长得太快。,单向,给定任意值,y,，要想找到一个值,x,，使得,h,(,x,)=,y,，将是计算不可行的。换一种不同的说法，即对于哈希运算，没有行之有效的逆运算。,抗弱碰撞性,给定,x,和,h,(,x,),，要想找到任意,y,，满足,y,x,，并且,h,(,y,)=,h,(,x,),，这是不可能的。,抗强碰撞性,要想找到任意的,x,和,y,，使得,x,y,，并且,h,(,x,)=,h,(,y,),，这是不可能的。也就是说，我们不能够找到任何两个输入，使得它们经过哈希后会产生相同的输出值。,大家好,5,哈希函数在数字签名上的应用,以前,Alice,对一条消息,M,实施签名，是通过使用她自己的私钥进行“加密”计算得到的，即要计算,S,=,M,Alice,。如果,Alice,发送消息,M,和签名,S,给,Bob,，,Bob,就能够通过执行验证过程,M,=,S,Alice,来验证该签名的有效性。但是，如果消息,M,很大，,M,Alice,就是一个成本很高的计算，更不用提发送消息,M,和签名,S,的带宽需求了，这两者都会很大。相比之下，在计算一个,MAC,时，加密的速度会很快，而且在发送时，我们也仅仅需要伴随着消息发送少量附加的校验位,(,比如,MAC),而已。,使用哈希函数之后,假设,Alice,有一个加密哈希函数,h,。那么，,h(,M,),可以被看做文档,M,的一个“指纹”，也就是说，,h,(,M,),比,M,小得多，但是它能够标识出,M,。如果,M,不同于,M,，那么即使仅仅相差一个单独的二进制位，哈希函数执行的结果也几乎肯定会不同。而且，哈希函数的抗碰撞特性意味着，想要将消息,M,替换为任何不同的消息,M,，使得,h,(,M,)=,h,(,M,),是不可能的,1.,一旦哈希值发生相同的情况，该怎么办呢？好的，这说明你已经发现了一个碰撞，也就意味着你已经攻破了这个哈希函数，于是你就成为一个著名的密码破解专家了。所以，这是个双赢的好事。,大家好,6,签名的正确方法,假设没有碰撞，那么对,h,(,M,),签名和对消息,M,实施签名的效果一样好。事实上，对哈希值实施签名比起仅仅对消息本身实施签名，实际上会更加安全。,现在数字签名的安全性不仅依赖于公钥系统的安全性，而且也依赖于哈希函数本身的安全性,如果二者中有任何一个比较弱，签名体制就可能会被破解。,大家好,7,5.3,生日问题,假如你和其他,N,个人同在一个房间里。那么，,N,必须多大，你才有指望找到至少一个人和你有相同的生日呢？或者说：,N,必须多大，才会使得“有某个人与你生日相同”的概率大于,1/2,呢？,你的生日是在一年中特定的一天。如果一个人和你的生日不同，那么他或她的生日必定是在其他,364,天中的一天。假设所有的生日都是概率相等的，那么“一个随机选择的人不与你的生日相同”的概率就是,364/365,。这样，所有的,N,个人都跟你的生日不同的概率就是,(364/365),N,，于是，至少有一个人与你的生日相同的概率就是：,设置这个表达式等于,1/2,，并解出,N,，得到,N,=253,。,大家好,8,真正的生日问题,我们给房间里的,N,个人分别编上号码,1,，,2,，,3,，,，,N,。编号为,1,的人的生日是一年,365,天中的一天。如果所有人的生日各不相同，那么编号为,2,的人必须与编号为,1,的人的生日不相同，也就是说，编号为,2,的人的生日只能是剩余的,364,天中的任意一天。同样，编号为,3,的人的生日只能是再剩余的,363,天中的任意一天，依此类推。假设所有的生日都是概率相等的，考虑上述情况的补集，其最后的概率计算如下式所示,设置这个表达式等于,1/2,，并解出,N,，我们得到,N,=23,大家好,9,延伸,对于一个生成,N,位二进制长度输出的安全哈希函数来说，一个计算开销大约以,2,N,/2,为因子的强力破解方式，就能够对其发起有效的攻击。,相比较而言，对于一个密钥长度为,N,位二进制数的安全对称密钥加密方案来说，对其强力破解的计算开销的因子是,2,N,-l,。,所以，安全哈希函数的输出必须是对称加密密钥二进制位数的大约两倍长，才能够获得与后者基本相当的安全水平。,大家好,10,5.4,生日攻击,假设哈希函数,h,生成一个,n,位二进制长的输出。,Trudy,原则上能够发起一次生日攻击，具体如下：,Trudy,选择一条“恶意”消息,E,，这是她想让,Alice,签名的消息，但是,Alice,并不想对其签名。,Trudy,也创建了一条无害的消息,I,，她有信心,Alice,愿意对这条消息签名。,然后，,Trudy,通过对消息实施较小的编辑性修改，生成,2,n,/2,条该无害消息,I,的变体。这些无害的消息，我们分别标识为,I,i,，其中,i=0,1,.,2,n,/2,1,，所有消息都与,I,的含义相同，但是既然消息本身不同，那么它们的哈希值也不一样。,同样，,Trudy,创建出,2,n,/2,个恶意消息,E,的变体，分别标识为,E,i,，其中,i,=0,1,.,2,n,/2,1,。这些消息也都与原始的恶意消息,E,表达同样的含义，但是它们的哈希值不一样。,Trudy,对所有的恶意消息,E,i,以及所有的无害消息,I,i,实施哈希运算。根据上述生日问题的讨论，她就有希望找到一个碰撞，比方说，,h,(,E,j,)=,h,(,I,k,),。基于这样的一个碰撞，,Trudy,将,I,k,发送给,Alice,，并请,Alice,对其进行签名。既然这条消息看起来没有问题，,Alice,就对其进行签名，并将,I,k,和,h,(,I,k,),Alice,返回给,Trudy,。既然,h,(,E,j,)=,h,(,I,k,),，那么由此可以得出,h,(,E,j,),Alice,=,h,(,I,k,),Alice,，于是，,Trudy,实际上就已经获得了,Alice,对恶意消息,E,j,的签名。,大家好,11,在这个攻击中，,Trudy,获得了,Alice,对于一条,Trudy,自选消息的签名，但是并没有以任何方式攻击潜在的公开密钥加密系统。,这个攻击是一个针对哈希函数,h,的强力攻击，而哈希函数,h,是用于计算数字签名的。,为了防止此类攻击，我们可以选择一个哈希函数，使得该哈希函数的输出值的长度,n,足够大，以至于,Trudy,无法完成,2,n,/2,个哈希值的计算。,大家好,12,5.5,非加密哈希,非加密哈希运算的例子,（,1,）其中，每个,X,i,是一个字节，定义哈希函数,h,(,X,),为：,这毫无疑问提供了压缩功能，因为任何长度的输入都被压缩为,8,位二进制的输出。但是，这个哈希很容易被破解，因为生日问题的结论告诉我们，只需对,2,4,=16,个随机选择的输入执行哈希运算，我们就有望找到一个碰撞。,对两个字节进行互换，就总是能够产生一个碰撞，类似如下这种情况：,（,2,）我们将哈希函数,h,(,X,),定义为：,虽然该函数在交换输入字节顺序的情况下能够输出不同的结果，但是仍然逃不过生日问题带来的麻烦。,大家好,13,循环冗余校验，或简称为,CRC,循环冗余校验码的计算本质上是长除法，将余数作为,CRC,计算的“哈希”值。与常规的长除法不同，,CRC,在计算中使用,XOR,运算替代了减法。,在一个,CRC,的计算过程中，除数被指定作为算法的一部分，数据作为被除数。,例子,假设给定的除数是,10011,，而有趣的是数据恰好是。那么，我们先对数据附加上,4,个,0(,附加的位数要比除数的二进制位数少,1),，然后执行如下长除法运算：,CRC,校验和就是长除法运算的余数,在这个例子中，就是,1010,。,大家好,14,5.6,Tiger Hash,MD5,MD,指的是消息摘要,(Message Digest),，它的前身是,MD4,，而,MD4,本身又继承自,MD2,。,所有的,MD,系列算法都是由加密领域的大师级人物,Ron Rivest,所发明。,MD5,算法生成,128,位的输出值。,SHA-1,算法,SHA,表示安全哈希算法,(Secure Hash Algorithm),，是美国政府的一个标准。,SHA-1,算法实际上非常类似于,MD5,算法。两个算法在实践中的主要不同在于,SHA-1,生成,160,位二进制长的输出值，比,MD5,提供了更可观的安全边际。,所谓,雪崩效应,，是所有加密哈希函数都会追求的一个理想特性。其目标是：在输入值中任何小的变化，都应该级联传递并导致输出结果较大的变化,就像雪崩一样。理想情况下，任何输入值的变化引发的输出值变化都是不相关的，这样，攻击者将不得不实施穷举式检索来寻找碰撞。,大家好,15,Tiger,算法特点,算法的输入先被分成,512,位二进制长度的分组，如果需要的话，就对输入值进行附加填充位，以补足成,512,的倍数位的长度。,算法输出,192,位二进制长度的哈希值。,算法实现中使用了,4,个,S-box,，这,4,个,S-box,的每一个都将,8,位二进制位映射为,64,位。,算法还使用了一个“密钥调度”的算法，不过由于这里没有密钥的概念，该算法实际是施加到了输入分组上。,大家好,16,Tiger,算法的过程,首先对输入值,X,进行附加填充位，使其长度满足,512,位二进制长的倍数，表示为：，其中每一个,X,i,都是一个,512,位二进制长的分组。,对每一个,X,i,使用一个外层的轮运算。假设,a,，,b,和,c,都是,64,位二进制长的值。对于第一轮运算，,(,a,b,c,),的初始值以,16,进制形式表示如下：,大家好,17,一轮运算之后，输出的,(,a,b,c,),就成为后续下一轮运算的初始三元组。最后一轮运算之后，最终输出的,(,a,b,c,),就是,192,位二进制长的哈希值。,首个外层轮函数,F,5,的输入是,(,a,b,c,),，如果我们标记,F,5,的输出为,(,a,b,c,),，那么,F,7,的输入为,(,c,a,b,),。同样地，如果我们标记,F,7,的输出为,(,a,b,c,),，那么,F,9,的输入为,(,b,c,a,),。,上图的每一个函数,F,m,都包含了,8,个下图所示的内层轮运算。我们再令,W,表示内层轮运算的,512,位二进制的输入值，其可以表示如下,大家好,18,对于函数,f,m,i,，当,i,=0,1,2,.,7,时，其各自的输入值分别如下,其中各自对应的函数,f,m,i,-1,的输出标记为,(,a,b,c,),。每一个,f,m,i,都依赖于,a,，,b,，,c,，,w,i,和,m,，其中,w,i,是,512,位二进制输入值,W,的第,i,个,64,位子分组。,c,写作：,，,其中每一个,c,i,都是一个单独的字节。,f,m,i,由下式给定：,每一个,S,i,都是一个,S-box(,即查找表,),，将,8,位二进制映射为,64,位二进制。,大家好,19,密钥调度算法,假设令,W,为密钥调度算法的,512