Hash函数(消息认证)

1哈希函数——消息认证认证（authentication）是防止网络系统遭受主动攻击的重要技术认证的主要目的有两个第一，验证消息的发送者是真的，而不是冒充的，称为实体认证，包括信源、信宿等的认证和识别。第二，验证信息的完整性，即验证数据在传送或存储过程中未被篡改、重放或延迟，称为消息认证。21消息认证码带密钥的Hash函数称为消息认证码(MAC：messageauthenticationcode).消息认证码是实现消息认证的重要工具.MAC有两个不同的输入，一个是消息x，另一个是密钥K.MAC产生定长的输出.实例:某一个大公司A想给它的客户发布一个新产品的广告,A希望不对广告内容加密,但又希望其它公司不能修改广告内容或冒充公司A发布同样的广告,或者当广告内容被修改后能够发现.如果使用不带密钥的Hash函数,由于其它公司可能在修改广告内容后产生新的散列值,从而使A无法确认原广告是否被修改.设计MAC算法的要求在不知道密钥的情况下，难以找到两个不同的消息具有相同的输出。31消息认证码基于分组密码CBC工作模式构造MAC基于分组密码CBC工作模式构造MAC算法已经成为ISO/IEC9797标准，它使用密文链接和双密钥三重加密技术。设EK表示以K为密钥的加密算法，设K’是一个与K不同的密钥，消息分组长度为n。首先把消息x分成L个n位块x=x1x2…xL，计算：hK是一个n位MAC.记为CBC-MAC.)).(()(),2()(),(1111,LKKKiiKiKHEExhLixHEHxEH41消息认证码基于Hash函数构造MAC设h是一个（不带密钥）Hash函数，K是密钥，x是消息，则定义消息认证码hK如下：).||()(xKhxhK基于MD5算法直接构造消息认证码MD5-MACMD5-MAC算法使用96字节的常数).20(||||||||||3.c7bd75bdc27d29da94b87bc421b21d918,be3643a0aab5f5c7e728e962ce177b801134,c551b1e457cd43f290ac45ef972121210iTTTTTTUTTTiiiiiii其中下标加法运算是模3相加.如果密钥K的长度小于128位，则通过多次自行链接，最后截取左边128位作为以下算法中使用的密钥K。51消息认证码将密钥K扩展成3个16字节的子密钥K0，K1，K2，其中把K0，K1分成4个32位的子串Kj[i]（j=0,1,i=0,1,2,3）.5MD).20()||||(5MDMD5iKUKKii表示不进行填充的其中对MD5进行修改：用K0代替MD5的4个32位寄存器ABCD.把K1[i]与MD5第i+1遍中每个常数232sin(j)进行模232加法.将512位的分组链接到消息x右边，再按MD5的要求进行填充.2212022||||||TKTKTKK将上一步的结果输入到修改后的MD5中，取其输出的前一半（64位）作为消息x的消息认证码MD5-MAC(x).MD5-MAC软件实现比较容易，其运算速度与MD5大体相近.62HMAC算法消息认证码HMAC（keyed-hashingformessageauthenticationcode）是Bellare等人于1996年提出，1997年作为RFC2104发表，成为事实上的Internet标准，包括IPSec协议在内的一些安全协议都使用了HMAC算法。HMAC算法利用已有的Hash函数，关键问题是如何使用密钥。使用不同的Hash函数，就可以得到不同的HMAC。选用MD5时的HMAC记为HMAC-MD5，选用SHA-1时的HMAC记为HMAC-SHA1。72HMAC算法HMAC算法描述设HMAC使用的Hash函数为h，每次处理的输入分组长度为b比特（使用MD5与SHA-1时，b=512），最后的输出长度为l比特（使用MD5时，l=128；使用SHA-1时，l=160）。如果HMAC的输入消息为x，则x=x1x2…xL，其中每一个分组xi（1≤i≤L）的长度为b比特。令HMAC使用的密钥为K，密钥K可以是任意的、长度不超过b比特的比特串（HMAC算法推荐密钥最小长度为l比特）。当密钥K的长度超过b比特时，使用Hash函数h对K进行压缩，把K作为h的输入，并将输出的l比特作为密钥K。82HMAC算法HMAC算法的流程图x2x1SixL…KipadSoh(Si||x)KopadHMAC(x)Hash函数hHash函数h92HMAC算法HMAC算法具体执行步骤(1)如果密钥K的长度小于b比特，则在其右边填充一些“0”，使其成为长度为b比特的比特串，仍记为K。(2)计算Si=Kipad，其中ipad是HMAC算法中规定的一个长度为b比特的比特模式串，它等于将00110110重复b/8次后得到的比特串。(3)把HMAC的输入消息x=x1x2…xL附加在Si的右端，得到Si||x=Si||x1x2…xL，将该比特串作为Hash函数h的输入，得到l比特的输出h(Si||x)。(4)计算So=Kopad，其中opad是HMAC算法中规定的另一个长度为b比特的比特模式串，它等于将01011010重复b/8次后得到的比特串。(5)将第(3)步得到的h(Si||x)附加在So的右端，并以该比特串作为Hash函数h的输入，得到l比特的输出。(6)将第(5)步的输出作为HMAC算法的最终输出结果，即消息x的消息认证码HMAC(x)。102HMAC算法HMAC的安全性建立在嵌入Hash函数基础上的所有MAC，其安全性在某种程度上都依赖于该Hash函数的强度。对于HMAC，可以给出HMAC的强度与所嵌入Hash函数强度之间的关系。根据伪造者在给定时间内伪造成功和用相同密钥产生给定数量的消息-MAC对的概率，可以用于描述MAC的安全性。Bellare等人（1996年）已经证明，如果攻击者已知若干（时间、消息-MAC）对，则成功攻击HMAC的概率等价于对所嵌入Hash函数的下列攻击之一：(1)即使对于攻击者而言，IV是随机的、秘密的和未知的，攻击者也能计算压缩函数的输出。(2)即使IV是随机的和秘密的，攻击者也能找到Hash函数的碰撞。在目前的计算水平下，使用MD5和SHA-1等作为HMAC算法所嵌入的Hash函数，HMAC的安全性是可以保证的。113应用数据完整性数据完整性是指数据在生成、传送或存储过程中没有被非法篡改.使用Hash函数可以保证数据的完整性使用MAC设用户A将消息x发送给接收者B，A与B共享秘密的MAC密钥K，hK是MAC。用户A计算x的MAChK(x)，将数据C=x||hK(x)发送给B。B通过其它方法确定用户A的身份，分开接收到的数据x’，使用共享密钥K计算hK(x’)，并与接收到的hK(x)相比较。如果hK(x’)=hK(x)，则B确定消息x’是来自于具有密钥K的用户A，在传输过程中未被篡改。C发送方A接收方B比较x1xx1hK||xhK123应用使用Hash函数和加密设A与B共享分组密码的密钥K,EK是加密算法,h是公开的Hash函数.用户A计算C=EK(x||h(x)),并将数据C发送给B.B利用密钥K进行解密,得到x’和h(x)，然后计算h(x’),并与接收到的h(x)相比较.如果h(x’)=h(x),则B确定消息x’是真实的.由于这里对h(x)进行了加密,所以对Hash函数h的要求可以适当降低.C发送方A接收方B比较x1xx1hEK||DKxh133应用加密使用MAC和加密设A与B共享分组密码的密钥K和MAC的密钥K’,EK是加密算法,hK’是MAC。用户A计算C=EK(x||hK’(x)),并将数据C发送给B.B利用密钥K进行解密,得到x’和hK’(x),然后计算hK’(x’),并与接收到的hK’(x)相比较.如果hK’(x’)=hK’(x),则B确定消息x’是真实的.该技术的优点是即使加密算法被攻破,MAC仍然能提供完整性保护作用.其缺点是需要管理K和K’两个密钥.C发送方A接收方B比较x1xx1hK’EK||DKxhK’143应用实现数据源认证数据源认证也称为消息认证,它是要求证实一个实体在过去某个时刻建立的数据源.数据源认证也包括数据完整性.提供数据源认证的方法有:(1)使用消息认证码MAC;(2)对附加上散列值的消息进行加密.设用户A将消息x发送给接收者B,A与B共享密钥K,则用户A向B发送以下数据可实现数据源的认证.(1)EK(x||h(x)):提供保密(仅双方共享K)和认证(加密保护散列值);(2)x||EK(h(x)):提供认证（加密保护散列值）;(3)x||h(x||S)：提供认证（仅双方共享随机数S）；(4)EK(x||h(x||S))：提供保密和认证（仅双方共享K、S）。153应用由于加密软件慢、硬件费用高、加密算法专利保护和出口限制等因素,人们倾向于不使用带有加密的认证方法,愿意使用方法(3)。数据源认证方案不能提供数据源的不可拒绝性，因为任何一方都可以使用共享密钥创建一个消息及其认证。如果需要解决这种潜在的争执，可以使用可信第三方或公钥技术。使用MAC能够确定数据是在过去某个时间由特定一方生成的，但是不能提供唯一性和时间上的保证，也不能发现消息是否重用或重发。为了解决这些问题，必须使用随时间变化的参数，例如时间戳、序列号和随机数等。