1、1Information Security:Principles and Practice,2nd Edition美Mark Stamp著张 戈译第5章 哈希函数及其他25.1 引言本章内容 加密哈希函数 加密哈希函数的标准应用 哈希函数的高级应用 加密相关的副作用问题35.2 什么是加密哈希函数一个加密哈希函数h(x)，必须满足下列所有条件：压缩压缩对于任何长度的输入值x，输出值y=h(x)的长度都比较小。在实际使用中，通常输出值是固定长度的(比如160位长度的二进制值)，而无论输入值的长度是多少。高效高效对于任何的输入值x，必须能够很容易地计算出h(x)。当然，伴随着输入值x的长度增加，计
2、算h(x)所需要的计算量也会随之增加，但是，这不能增长得太快。单向单向给定任意值y，要想找到一个值x，使得h(x)=y，将是计算不可行的。换一种不同的说法，即对于哈希运算，没有行之有效的逆运算。抗弱碰撞性抗弱碰撞性给定x和h(x)，要想找到任意y，满足yx，并且h(y)=h(x)，这是不可能的。抗强碰撞性抗强碰撞性要想找到任意的x和y，使得xy，并且h(x)=h(y)，这是不可能的。也就是说，我们不能够找到任何两个输入，使得它们经过哈希后会产生相同的输出值。4哈希函数在数字签名上的应用以前Alice对一条消息M实施签名，是通过使用她自己的私钥进行“加密”计算得到的，即要计算S=MAlice。如
3、果Alice发送消息M和签名S给Bob，Bob就能够通过执行验证过程M=SAlice来验证该签名的有效性。但是，如果消息M很大，MAlice就是一个成本很高的计算，更不用提发送消息M和签名S的带宽需求了，这两者都会很大。相比之下，在计算一个MAC时，加密的速度会很快，而且在发送时，我们也仅仅需要伴随着消息发送少量附加的校验位(比如MAC)而已。使用哈希函数之后假设Alice有一个加密哈希函数h。那么，h(M)可以被看做文档M的一个“指纹”，也就是说，h(M)比M小得多，但是它能够标识出M。如果M不同于M，那么即使仅仅相差一个单独的二进制位，哈希函数执行的结果也几乎肯定会不同。而且，哈希函数的抗
4、碰撞特性意味着，想要将消息M替换为任何不同的消息M，使得h(M)=h(M)是不可能的 1.一旦哈希值发生相同的情况，该怎么办呢？好的，这说明你已经发现了一个碰撞，也就意味着你已经攻破了这个哈希函数，于是你就成为一个著名的密码破解专家了。所以，这是个双赢的好事。5签名的正确方法假设没有碰撞，那么对h(M)签名和对消息M实施签名的效果一样好。事实上，对哈希值实施签名比起仅仅对消息本身实施签名，实际上会更加安全。现在数字签名的安全性不仅依赖于公钥系统的安全性，而且也依赖于哈希函数本身的安全性如果二者中有任何一个比较弱，签名体制就可能会被破解。65.3 生日问题假如你和其他N个人同在一个房间里。那么，
5、N必须多大，你才有指望找到至少一个人和你有相同的生日呢？或者说：N必须多大，才会使得“有某个人与你生日相同”的概率大于1/2呢？你的生日是在一年中特定的一天。如果一个人和你的生日不同，那么他或她的生日必定是在其他364天中的一天。假设所有的生日都是概率相等的，那么“一个随机选择的人不与你的生日相同”的概率就是364/365。这样，所有的N个人都跟你的生日不同的概率就是(364/365)N，于是，至少有一个人与你的生日相同的概率就是：设置这个表达式等于1/2，并解出N，得到N=253。7N1(364/365)真正的生日问题我们给房间里的N个人分别编上号码1，2，3，N。编号为1的人的生日是一年3
6、65天中的一天。如果所有人的生日各不相同，那么编号为2的人必须与编号为1的人的生日不相同，也就是说，编号为2的人的生日只能是剩余的364天中的任意一天。同样，编号为3的人的生日只能是再剩余的363天中的任意一天，依此类推。假设所有的生日都是概率相等的，考虑上述情况的补集，其最后的概率计算如下式所示设置这个表达式等于1/2，并解出N，我们得到N=2381 365/365 364/365 363/365(365N1)/365生日生日悖论悖论 延伸 对于一个生成N位二进制长度输出的安全哈希函数来说，一个计算开销大约以2N/2为因子的强力破解方式，就能够对其发起有效的攻击。相比较而言，对于一个密钥长度
7、为N位二进制数的安全对称密钥加密方案来说，对其强力破解的计算开销的因子是2N-l。所以，安全哈希函数的输出必须是对称加密密钥二进制位数的大约两倍长，才能够获得与后者基本相当的安全水平。95.4 生日攻击假设哈希函数h生成一个n位二进制长的输出。Trudy原则上能够发起一次生日攻击，具体如下：Trudy选择一条“恶意”消息E，这是她想让Alice签名的消息，但是Alice并不想对其签名。Trudy也创建了一条无害的消息I，她有信心Alice愿意对这条消息签名。然后，Trudy通过对消息实施较小的编辑性修改，生成2n/2条该无害消息I的变体。这些无害的消息，我们分别标识为Ii，其中i=0,1,.,
8、2n/2 1，所有消息都与I的含义相同，但是既然消息本身不同，那么它们的哈希值也不一样。同样，Trudy创建出2n/2个恶意消息E的变体，分别标识为Ei，其中i=0,1,.,2n/2 1。这些消息也都与原始的恶意消息E表达同样的含义，但是它们的哈希值不一样。Trudy对所有的恶意消息Ei以及所有的无害消息Ii实施哈希运算。根据上述生日问题的讨论，她就有希望找到一个碰撞，比方说，h(Ej)=h(Ik)。基于这样的一个碰撞，Trudy将Ik发送给Alice，并请Alice对其进行签名。既然这条消息看起来没有问题，Alice就对其进行签名，并将Ik和h(Ik)Alice返回给Trudy。既然h(Ej
9、)=h(Ik)，那么由此可以得出h(Ej)Alice=h(Ik)Alice，于是，Trudy实际上就已经获得了Alice对恶意消息Ej的签名。10在这个攻击中，Trudy获得了Alice对于一条Trudy自选消息的签名，但是并没有以任何方式攻击潜在的公开密钥加密系统。这个攻击是一个针对哈希函数h的强力攻击，而哈希函数h是用于计算数字签名的。为了防止此类攻击，我们可以选择一个哈希函数，使得该哈希函数的输出值的长度n足够大，以至于Trudy无法完成2n/2个哈希值的计算。115.5 非加密哈希非加密哈希运算的例子（1）其中，每个Xi是一个字节，定义哈希函数h(X)为：这毫无疑问提供了压缩功能，因为
10、任何长度的输入都被压缩为8位二进制的输出。但是，这个哈希很容易被破解，因为生日问题的结论告诉我们，只需对24=16个随机选择的输入执行哈希运算，我们就有望找到一个碰撞。对两个字节进行互换，就总是能够产生一个碰撞，类似如下这种情况：（2）我们将哈希函数h(X)定义为：虽然该函数在交换输入字节顺序的情况下能够输出不同的结果，但是仍然逃不过生日问题带来的麻烦。12012n 1(,.,)XXXXX012n 1(.)mod256hXXXXX012n 2n 1(1)(2).2)mod256hnXnXnXXXX(10101010,00001111)=(00001111,10101010)=10111001h
11、h(00000001,00001111)(00000000,00010001)00010001hh循环冗余校验，或简称为CRC循环冗余校验码的计算本质上是长除法，将余数作为CRC计算的“哈希”值。与常规的长除法不同，CRC在计算中使用XOR运算替代了减法。在一个CRC的计算过程中，除数被指定作为算法的一部分，数据作为被除数。例子假设给定的除数是10011，而有趣的是数据恰好是10101011。那么，我们先对数据附加上4个0(附加的位数要比除数的二进制位数少1)，然后执行如下长除法运算：CRC校验和就是长除法运算的余数在这个例子中，就是1010。135.6 Tiger HashMD5 MD指的是
12、消息摘要(Message Digest)，它的前身是MD4，而MD4本身又继承自MD2。所有的MD系列算法都是由加密领域的大师级人物Ron Rivest所发明。MD5算法生成128位的输出值。SHA-1算法 SHA表示安全哈希算法(Secure Hash Algorithm)，是美国政府的一个标准。SHA-1算法实际上非常类似于MD5算法。两个算法在实践中的主要不同在于SHA-1生成160位二进制长的输出值，比MD5提供了更可观的安全边际。14所谓雪崩效应雪崩效应，是所有加密哈希函数都会追求的一个理想特性。其目标是：在输入值中任何小的变化，都应该级联传递并导致输出结果较大的变化就像雪崩一样。理
13、想情况下，任何输入值的变化引发的输出值变化都是不相关的，这样，攻击者将不得不实施穷举式检索来寻找碰撞。Tiger算法特点 算法的输入先被分成512位二进制长度的分组，如果需要的话，就对输入值进行附加填充位，以补足成512的倍数位的长度。算法输出192位二进制长度的哈希值。算法实现中使用了4个S-box，这4个S-box的每一个都将8位二进制位映射为64位。算法还使用了一个“密钥调度”的算法，不过由于这里没有密钥的概念，该算法实际是施加到了输入分组上。15Tiger算法的过程首先对输入值X进行附加填充位，使其长度满足512位二进制长的倍数，表示为：，其中每一个Xi都是一个512位二进制长的分组。
14、对每一个Xi使用一个外层的轮运算。假设a，b和c都是64位二进制长的值。对于第一轮运算，(a,b,c)的初始值以16进制形式表示如下：1601n-1X=(X,X,.,X)一轮运算之后，输出的(a,b,c)就成为后续下一轮运算的初始三元组。最后一轮运算之后，最终输出的(a,b,c)就是192位二进制长的哈希值。首个外层轮函数F5的输入是(a,b,c)，如果我们标记F5的输出为(a,b,c)，那么F7的输入为(c,a,b)。同样地，如果我们标记F7的输出为(a,b,c)，那么F9的输入为(b,c,a)。上图的每一个函数Fm都包含了8个下图所示的内层轮运算。我们再令W表示内层轮运算的512位二进制的
15、输入值，其可以表示如下17017W=(,.,)w ww对于函数fm,i，当i=0,1,2,.,7时，其各自的输入值分别如下 其中各自对应的函数fm,i-1的输出标记为(a,b,c)。每一个fm,i都依赖于a，b，c，wi和m，其中wi是512位二进制输入值W的第i个64位子分组。c写作：，其中每一个ci都是一个单独的字节。fm,i由下式给定：每一个Si都是一个S-box(即查找表)，将8位二进制映射为64位二进制。18017c(c,c,.,c)密钥调度算法假设令W为密钥调度算法的512位二进制输入值。同上，我们将W写作W=(w0,w1,w7)，其中每一个wi都是一个64位二进制值，我们再令 为
16、wi的二进制补数。密钥调度算法如下，其中最后的计算结果W=(w0,w1,w7)给出了该算法的输出值。19 小结 Tiger哈希算法共包含24轮运算，这24轮运算可以看成是3个外层轮运算，而这每一个外层运算都包含了8个内层轮运算。该算法所有的中间步骤产生的哈希值都是192位二进制值。该算法中S-box的设计使得仅仅经过24轮运算中的3轮计算，每一个输入的二进制位就会影响到a，b和c三者中的每一个。而且，在消息中任何小的变化，都将影响到算法中间步骤产生的哈希值的多个二进制位。在fm,i计算过程中，最后一步的乘法也是该算法设计中的一个关键特性。它的目的是为了确保，对于一轮运算中每个S-box的输入，
17、都将在下一轮的运算中混入到多个S-box中。205.7 HMACHMAC来源怎么才能将密钥混入到所谓的HMAC中呢？将密钥置于消息体之前，即计算h(K,M)假如我们选择计算h(K,M)来得到HMAC。如果消息M=(B1,B2)，其中每个Bi都是512位二进制长，则如果Trudy选择了M，使得M=(M,X)，那么，Trudy有可能利用以上灯饰从h(K,M)找到h(K,M)。因为，对于特定长度的K，M和X，有 将密钥附加于消息体之后，即计算h(M,K)211212()=(,),)=(),)h MF F A BBF h BB()=()=()=()h K,MF h M,K)F h M,K)h M,K假
18、如令B为哈希运算的分组长度，以字节数表示。对于所有流行的哈希算法B=64。ipad=0 x36 重复B次opad=0 x5C 重复B次那么，消息M的HMAC定义为：这个方案将密钥彻底地混入到哈希运算的结果当中。计算一个HMAC值虽然需要执行两遍哈希运算，但是第二次哈希运算仅作用于少量的二进制位并使用了修改的附加填充密钥。所以，总开销比起计算h(M)所需要的开销，仅仅多了少许。HMAC()=(opad,(ipad,)K,MH KH KM更好更好5.8 哈希函数的用途标准应用身份认证消息完整性保护(使用HMAC)消息指纹错误检测高效数字签名等高级应用网上竞价网上竞价垃圾邮件减阻垃圾邮件减阻225.
19、8.1网上竞价假设有一个物品在网上拍卖，而Alice、Bob以及Charlie都想要出价竞拍。每一个竞拍者都有一次机会提交一个秘密的报价，只有当所有的报价都接收到之后，竞拍价格才会公开。依照惯例，报价最高的竞拍者获胜。前提：Alice、Bob以及Charlie，三人之间必然是互相不信任的，另外，他们也绝对都不会信任和接受竞投价格的网上服务。为了努力消除这些担心，网上服务方提出了如下的方案：每一个竞拍者将确定他们各自的竞拍价格，比方说，Alice出价为A，Bob出价为B，Charlie出价为C，各自确保其报价秘密。然后，Alice将提交h(A)，Bob将提交h(B)，Charlie将提交h(C)
20、。一旦所有三个经过哈希运算的报价都已接收到，网上服务方就在线公开发布这些哈希值，以供所有人查阅。优优点点：报价的哈希值将竞拍者与他们的原始报价绑在了一起，而且无需揭示有关报价自身的任何信息。如果率先提交一个报价的哈希值并无什么不利因素，并且一旦提交了报价的哈希值，便再没有任何办法能够改变报价，那么这个方案防止了如前所述的欺骗，缺缺陷陷：它可能会遭受前向检索攻击235.8.2 垃圾邮件减阻假如M为电子邮件消息，T为当前时间。电子邮件消息M包含了发送方和目标接收方的电子邮件地址，但是并不包含任何其他的地址。消息M的发送方必须确定一个值R，使得下式成立：也就是说，发送方必须找到一个值R，使得上面等式
21、中哈希运算的输出结果中前N个二进制位都是0。一旦完成了这一步，发送方就发送三元组(M,R,T)。在接收方Alice接受该邮件之前，她需要验证时间T是否在不久之前，以及验证h(M,R,T)是否以N个0开始。平均而言，发送方就需要执行大约2N次哈希计算。而无论N的长度是多少，接收方只需执行一次哈希计算便能够验证h(M,R,T)是否以N个0开始。为使这个设计行之有效，我们需要选择一个N，使得相应的计算开销处于常规的电子邮件用户能够接受的水平，但其成本又高到了垃圾邮件发送者无法忍受的程度。245.9 其他与加密相关的主题 Shamir的秘密共享机制 有关视觉的加密技术 随机性问题 信息隐藏255.9.
22、1秘密共享问题？假设Alice和Bob想要共享一个秘密信息S，以实现如下的效果：Alice或者Bob(当然也包括其他的任何人)都不能独自确定信息S，除了瞎猜，再无更好的办法。Alice和Bob在一起，就能够轻松地确定该信息S秘密共享机制因为其中有两个参与者，而且双方必须协同合作才能恢复出秘密信息S。26两点决定一条直线两点决定一条直线假设秘密信息S是一个实数。通过点(0,S)在平面上画一条直线L，并给Alice指定直线L上的一点A=(X0,Y0)，给Bob指定直线L上的另一点B=(X1,Y1)。这样，Alice和Bob各自都不掌握关于S的任何信息，因为通过一个独立的点存在无限多的直线。但是，合
23、在一起，两个点A和B唯一确定了直线L，这样就能够确定在Y轴上的截距，于是进而就获得了值S。27“m out of n”型的秘型的秘密共享机制：密共享机制：即对于任何的mn，其中n代表参与者的数量，那么其中任意的m个参与者合作，就能够恢复出共享的秘密。一条直线是一个一次多项式，它可以由两点唯一确定。一条抛物线是一个二次多项式，它可以由三个点唯一确定。一般而言，一个次数为m 1的多项式可以由m个点唯一确定。对于任意的mn，正是上述基本事实使得我们能够构造出一个“m out of n”型的秘密共享机制。285.9.1.1密钥托管如何解决密钥托管机构的信任问题？通过拥有多个托管机构，并允许用户将其密钥
24、在这些托管机构中的n个之间进行分割，使得必须得有n个托管机构中的m个协同合作才能恢复出密钥。Shamir的秘密共享机制可以用于实现这样的一个密钥托管方案。假设N=3 和 m=2，Alice的密钥是S。使用“2 out of 3”方案即可。比如，Alice可能会选择让司法部持有点(X0,Y0)，让商务部持有点(X1,Y1)，再让Fred的密钥托管公司持有点(X2,Y2),。于是，这三个托管机构中必须至少有两个协同合作才能确定Alice的密钥S。295.9.1.2 视觉加密技术视觉秘密共享机制 该机制是绝对安全的。在视觉秘密共享机制(也被称作视觉加密技术)中，解密潜在的图像并不需要执行任何计算。例
25、子：像素分解30如果某个特定像素是白色，我们可以通过抛硬币的方式来决定是使用图中的“a”行还是“b”行。对于一个黑色像素，我们通过抛硬币来在“c”行和“d”行之间选择，然后再使用被选定的行来确定相应的像素部分。如果原始的像素是黑色的，那么其分解的两份重叠之后总是生成一个黑色像素。而如果原始的像素是白色的，那么其分解的两份重叠之后将生成一个半白半黑的像素，这将被视觉感知为灰色。这个结果会损失一定的对比度(黑和灰相对于黑和白)，但是，原始的图像仍然可以清晰地辨别。视觉秘密共享的例子是一个“2 out of 2”型的共享方案315.9.2 随机数在加密技术领域，生成对称密钥、生成RSA密钥对(意即随
26、机选取大素数)以及生成Diffie-Hellman的秘密指数，这些都需要随机数。加密技术中的随机数必须不仅是统计上随机的，而且它们还必须要满足严格得多的条件它们必须是不可预测的。常用的伪随机数生成器就是可预测的，即给定足够大数量的输出值，后续的值将能够被很容易地确定。所以，伪随机数生成器不适用于加密类应用。假设有个服务器专门为用户生成对称密钥，并假设它为一系列用户生成了如下的密钥：KA 给Alice使用KB 给Bob使用KC 给Charlie使用KD 给 Dave使用现在如果Alice、Bob和Charlie都不喜欢Dave，他们就可以将他们的这些信息放在一起，看看是否有助于确定Dave的密钥
27、。即Alice、Bob和Charlie可以利用对于他们自己的密钥KA、KB和KC的理解，来考虑这些信息是否有助于确定出Dave的密钥KD。如果能够根据对于密钥KA、KB和KC的了解来预测KD，那么该系统的安全性是有缺陷的。325.9.2.1德州扑克规则首先给每个玩家发两张牌，正面朝下扣起来作为底牌。然后完成一轮投注。接下来，翻开三张公共牌所有玩家都可以看到公共牌，并可以考虑与他们自己手中的牌结合使用。进行第二轮投注之后，再次翻开一张公共牌，随后再进行一轮投注。最后，翻开最后的一张公共牌，这之后还可以再加投一次注。在所有保持持续跟进到最后的玩家中，谁能够从自己手里的两张底牌和翻开的5张公共牌中组
28、成最好的一手牌，谁就是获胜者。ASF公司开发的扑克牌游戏软件在运用随机数来洗一副牌的时候，随机数的使用方式中有一个严重的缺陷：这个程序无法产生一个真正随机的洗牌结果，于是在游戏中，玩家就有可能实时地确定整副牌的情况。33如何实时地就确定洗牌的结果呢？对于一幅含有52张牌的扑克来说，共有52!2225种不同的洗牌结果。AFS公司的德州扑克程序中使用了一个“随机的”32位二进制整数来确定洗牌的结果。因此，在2225种所有可能的洗牌结果中，这个程序就不可能产生多于其中232种不同的洗牌结果。这是一个不可原谅的设计缺陷！为了生成“随机的”洗牌结果，该程序使用了伪随机数生成器或简称为PRNG。在每次洗牌
29、时，该伪随机数生成器都会基于新的种子值，但种子值基于一个已知的函数，即其值为自午夜0点以来所经历的毫秒数。因为在一天中包含的毫秒数为实际上就会使得最后能够产生的不同洗牌结果的数量小于227。攻击者Trudy将她的时钟与服务器进行同步，她就有可能将需要检测的不同洗牌结果的数量降低为小于218。事实上，当第一轮的公共牌揭晓之后，Trudy就能够唯一确定洗牌结果了，于是她就能够知道其他所有玩家最终整手牌的情况。342724 60 60 100025.9.2.2 随机二进制位的生成真正的随机性不仅非常难以找到，而且非常难以界定。真正的随机性的来源确实存在。例如，放射性衰变就是随机的。但是，基于核放射技
30、术的计算机肯定是不受欢迎的。随机性的另一个来源是臭名昭著的熔岩灯，可以从其混沌行为中获得随机性。因为软件本身是(也希望是)有确定性的，所以真正的随机数必须产生于任何代码之外。355.9.3 信息隐藏隐写术也叫隐藏书写，就是试图隐藏特定信息被传递这一事实。隐写术有很长的历史，特别是在战争中很久之前就已经在使用。现代版本的隐写术涉及在各种媒介中隐藏信息，这些媒介包括诸如图像文件、音频数据，甚至是软件等。数字水印是为了某种不尽相同的目的而实施的信息隐藏。数字水印的分类可以有很多种不同的方式。不可见水印在媒介中是不应该能被感知到的水印。可见水印设计上用于查阅的水印，如在一个文档上打上“TOP SECR
31、ET”的标记。鲁棒水印设计上用于保持其可读性的水印，即使遭受了攻击和破坏。敏感水印设计为易损的水印，发生任何篡改都将导致破坏或损害36不可见数字水印典典型实例型实例：将特定信息以某种方式插入到照片当中，使得当照片被破坏时，仍然有可能从原始照片所剩余的一小块残片中重新构建出整张的图像。例子：将要使用的图像采用24位二进制空域色彩分量表示方式即对于红色向量、绿色向量和蓝色向量分别使用一个字节来表示，各自表示为R，G，B。由于低位的RGB值相对不重要，因为其代表了颜色中不易觉察到的细微变化。所以我们能够将这些低二进制位用于我们选定的其他用途，包括信息隐藏。37未包含任何未包含任何隐藏的信息隐藏的信息
32、整本整本爱丽丝梦游仙爱丽丝梦游仙境境的书的书(以以PDF格式格式)嵌入在了嵌入在了RGB字节的字节的低位中低位中假设一个HTML文件，该文件包含“海象与木匠”这首诗，在HTML中，RGB字体颜色以如下形式的标签所规定.其中，rr是以十六进制形式表示的R的值，gg是以十六进制形式表示的G的值，bb是以十六进制形式表示的B的值。既然R，G和B的低位信息不会影响到对颜色的感知，那么我们可以将信息隐藏在这些位中。读取RGB色彩分量字节的低位就能够生成“隐藏的”信息，即110 010 110 011 000 101。38鲁棒性上述两种方法均完全不具备鲁棒性！因为任何一个了解该设计方案的攻击者能够和目标接收者同样容易地读取其中隐藏的信息。或者攻击者可以换一种方式，通过将该文件替换为另一个文件，除了RGB字节的低位信息被完全随机打乱之外，这个新的文件与原始的文件再没有其他的不同，这样就直接破坏了这些隐藏信息。但仍然面临重重障碍和问题！39对于信息隐藏来说，要想具有鲁棒性，信息必须放在有一定影响力的二进制位上。但是，这就提出了一个严峻的挑战，因为，对于这些确有影响力的二进制位的改变必须要非常地小心谨慎，以便信息隐藏仍然能够保持“不可见性”。5.10 小结 Tiger算法 计算哈希MAC(HMAC)的正确方法 秘密共享机制 视觉加密技术 随机数 信息隐藏技术40
