第11章-hash函数

第11章Hash函数网络通信的攻击威胁泄露：把消息内容发布给任何人或没有合法密钥的进程流量分析：发现通信双方之间信息流的结构模式，可以用来确定连接的频率、持续时间长度；还可以发现报文数量和长度等伪装：从一个假冒信息源向网络中插入消息内容篡改：消息内容被插入、删除、变换、修改顺序修改：插入、删除或重组消息序列时间修改：消息延迟或重放否认：接受者否认收到消息；发送者否认发送过消息信息安全的需求保密性（Confidentiality）完整性（Integrity）数据完整性，未被未授权篡改或者损坏系统完整性，系统未被非授权操纵，按既定的功能运行可用性（Availability）鉴别（Authenticity）实体身份的鉴别，适用于用户、进程、系统、信息等不可否认性（Non-repudiation）防止源点或终点的抵赖（1）消息鉴别与散列函数定义消息鉴别（MessageAuthentication)：是一个证实收到的消息来自可信的源点且未被篡改的过程。散列函数（HashFunctions)：一个散列函数以一个变长的报文作为输入，并产生一个定长的散列码，有时也称报文摘要，作为输出。数字签名（DigitalSignature）是一种防止源点或终点抵赖的鉴别技术。鉴别和认证鉴别：authentication真伪性(1)用来验证发送的数据,特别是一个信息的完整性的过程(2)在用户开始使用系统时对其身份进行的确认认证：Certification资格审查计算安全学用语,指为了鉴定一个计算机系统或网络的设计和它提供的手段在多大程度上能满足预定的安全要求而进行的技术评估鉴别的结构任何消息认证或数字签名机制可以看到两个层次：底层必须有某种函数产生一个认证标识：一个用于认证一个报文的值高层认证协议以底层函数为原语，使接收者完成报文的鉴别鉴别的目的信源识别：验证信息的发送者是真正的，而不是冒充的验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等鉴别模型鉴别系统的组成鉴别编码器和鉴别译码器可抽象为鉴别函数一个安全的鉴别系统，需满足（1）指定的接收者能够检验和证实消息的合法性、真实性和完整性（2）消息的发送者和接收者不能抵赖（3）除了合法的消息发送者，其它人不能伪造合法的消息鉴别函数分类消息加密：整个消息的密文作为认证标识消息鉴别码(MAC)：公开函数+密钥产生一个固定长度的值作为认证标识散列函数：一个公开函数将任意长度的消息映射到一个固定长度的哈希值，作为认证标识对称加密AB:():()kkABkAEMBBDMM与共享密钥，查看是否为有意义的明文2020/3/813哈希函数的应用消息认证数字签名口令保护、文件完整性等hash函数应用(1)消息认证kAB:E[MH(M)]提供鉴别－加密保护H(M)提供保密－仅A和B共享密钥kkAB:ME[H(M)]提供鉴别－加密保护H(M)AB:MH(MS)]]提供鉴别－仅A和B共享消息SkAB:E[MH(MS)]]提供鉴别－仅A和B共享S提供保密－仅A和B共享密钥kaKR提供鉴别和数字签名－加密保护H(M)－仅A能生成E[H(M)]hash函数应用(2)数字签名akKRAB:E[ME[H(M)]]提供鉴别和数字签名提供保密－仅A和B共享密钥k产生单向口令文件:如操作系统存储口令的Hash值而不是口令本身。入侵检测和病毒检测：将每个文件的Hash值H(F)存储在安全系统中，随后就能够通过重新计算H(F)来判断文件是否被修改过。构建随机函数（PRF）或用做伪随机发生器。其他应用（2）hash定义散列函数H(M):输入为任意长度的消息M;输出为一个固定长度的散列值，称为消息摘要(MessageDigest）H(M)是消息M的所有位的函数并提供错误检测能力：消息中的任何一位或多位的变化都将导致该散列值的变化H(M)又称为：哈希函数、数字指纹（Digitalfingerprint)、压缩（Compression)函数、数据鉴别码（Dataauthenticationcode）等散列函数的定义散列函数：M:变长报文H(M):定长的散列值主要用于为文件、报文或其它分组数据产生指纹()hHM2020/3/825Hash函数浓缩任意长的消息M到一个固定长度的取值h=H(M)通常假设hash函数是公开的且不使用密钥（MAC使用密钥）Hash函数用户检测对消息的改变多种方式工作方式常用于产生数字签名散列函数应满足的条件：散列函数的目的是为需认证的数据产生一个“指纹”。为了能够实现对数据的认证，散列函数应满足以下条件：1）函数的输入可以是任意长。2）压缩性：函数的输出是固定长，如MD5输出128bit，SHA-1输出160bit。具有压缩性。3）已知X，求H(x)较为容易，可用硬件或软件实现。4）抗原像攻击（单向性）：已知h，求使得H(x)=h的x在计算上是不可行的，这一性质称为函数的单向性，称H(x)为单向散列函数。5)抗弱碰撞性：已知x，找出y(y≠x)使得H(y)=H(x)在计算上是不可行的。如果单向散列函数满足这一性质，则称其是抗弱碰撞的。6)抗强碰撞性：找出任意两个不同的输入x、y，使得H(x)=H(y)在计算上是不可行的。如果单向散列函数满足这一性质，则称其是抗强碰撞的。7)伪随机性：H的输出满足伪随机性测试标准抗强碰撞攻击抗弱碰撞攻击抗原像攻击Hash函数安全特性之间的联系HASH安全性：安全威胁一(a)伪造方式一：Oscar以一个有效签名(x,y)开始，此处y=sigk(h(x))。首先他计算Z=h(x)，并企图找到一个x'满足h(x')=h(x)。若他做到这一点，则(x',y)也将为有效签名。为防止这一点，要求函数h具有无碰撞特性。定义1(弱无碰撞)，散列函数h称为是弱无碰撞的，是指对给定消息x∈X，在计算上几乎找不到异与x的x'∈X使h(x)=h(x')。安全威胁二(b)伪造方式二：Oscar首先找到两个消息x=x',满足h(x)=h(x'),然后Oscar把x给Bob且使他对x的摘要h(x)签名，从而得到y,那么(x',y)是一个有效的伪造。定义2(强无碰撞)散列函数h被称为是强无碰撞的,是指使得h(x)=h(x‘)的偶对(x,x‘)在计算上不可行。注：强无碰撞自然含弱无碰撞！安全威胁三(c)伪造方式三：在散列函数的用法(e)中,秘密值S本身并不发送,如果散列函数不是单向的,攻击者截获到M和H(M||S).然后通过某种逆变换获得M||S,因而攻击者就可以得到S.定义3(单向的)称散列函数h为单向的，是指计算h的逆函数h-1在计算上不可行。安全威胁四：生日攻击攻击者的主要攻击目标是找到一对或更多对碰撞消息。攻击Hash算法和计算碰撞消息的方法。（1）一般的方法，攻击任何类型的Hash算法，比如“生日攻击”；（2）特殊的方法，只能用于攻击某些特殊的Hash算法。题目描述密码学中有种很有意思的攻击方式叫做生日攻击。其原理是基于这样一个神奇的结论：如果一个房间里有23个人，那么其中两个人生日相同的概率超过50%，当人数上升到40人时，这一概率提高到了89%以上。注意生日相同指的是两个人的出生月份和日期相同，不考虑年份。这个结论听上去很神奇，因为一年有365天，但是，事实上你可以通过概率知识验证这个结论。计算机率的方法是，首先找出表示n个人中，每个人的生日日期都不同的概率。上式等于p(n)表示n个人中2人生日相同的概率当n=23发生的概率大约是0.507()pn生日攻击假定使用64位的散列码,是否安全?如果采用传输加密的散列码和不加密的报文M,对手需要找到M,使得H(M)=H(M),以便使用替代报文来欺骗接收者。一种基于生日悖论的攻击可能做到这一点。相关问题给定一个散列函数,有n个可能的输出,输出值为H(x),如果H有k个随机输入,k必须为多大才能使至少存在一个输入y,使得H(y)=H(x)的概率大于0.5.对单个y,H(y)=H(x)的概率为1/n,反过来H(y)H(x)的概率为1-(1/n).如果产生k个随机值y,他们之间两两不等的概率等于每个个体不匹配概率的乘积,即[1-(1/n)]k,这样,至少有一个匹配的概率为1-[1-(1/n)]k.要概率等于0.5,只需k=n1/2对长度为m位的散列码，共有2m个可能的散列码，若要使任意的x,y有H(x)=H(y)的概率为0.5,只需k=2m/2m越长攻击上计算越接近不可行性；Hash必须足够长(64128160)Hash函数的分类根据安全水平：定义1(弱无碰撞)，散列函数h称为是弱无碰撞的，是指对给定消息x∈X，在计算上几乎找不到异于x的x'∈X使h(x)=h(x')。定义2(强无碰撞)，散列函数h被称为是强无碰撞的,是指在计算上几乎不可能找到相异的x，x'使得h(x)=h(x')。注：强无碰撞自然含弱无碰撞！Hash函数的分类根据是否使用密钥带秘密密钥的Hash函数:消息的散列值由只有通信双方知道的秘密密钥K来控制。此时，散列值称作MAC。不带秘密密钥的Hash函数：消息的散列值的产生无需使用密钥。此时，散列值称作MDC。（3）典型hash函数hash函数通用结构•由Merkle于1989年提出•RonRivest于1990年提出MD4•几乎被所有hash函数使用•attacksfocusoncollisionsinfunctionf•具体做法:–把原始消息M分成一些固定长度的块Yi–最后一块padding并使其包含消息M长度–设定初始值CV0–压缩函数f,CVi=f(CVi-1,Yi-1)–最后一个CVi为hash值bY0nIV=CV0fbY1nfbYL-1nCVL-1fCV1nnIV=initialvalue初始值CV=chainingvalue链接值Yi=ithinputblock(第i个输入数据块)f=compressionalgorithm(压缩算法）n=lengthofhashcode(散列码的长度)b=lengthofinputblock(输入块的长度)GeneralStructureofSecureHashCodeCVLCV0=IV=initialn-bitvalueCVi=f(CVi-1,Yi-1)(1iL)H(M)=CVL2020/3/843MD5消息摘要算法由RonaldRivest设计作为互联网的RFC1321标准MD5即Message-DigestAlgorithm5，用于确保信息传输完整一致。是计算机广泛使用的散列算法之一（又译摘要算法、哈希算法），主流编程语言普遍已有MD5实现。将数据（如汉字）运算为另一固定长度值，是散列算法的基础原理，MD5的前身有MD2、MD3和MD4。产生128-bit的hash值直到现在仍是被广泛使用的hash算法最近已受到穷举攻击和密码分析攻击MD5算法应用其典型应用是对一段Message（字节串）产生Fingerprint（指纹），以防止被篡改。比如，在UNIX下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构为：MD5(httpd-2.2.0.tar.bz2)=402b90a2e47205f94b3b1d91e1a8c459，这就是httpd-2.2.0.tar.bz2文件的数字签名。如果在以后传播这个文件的过程中，无论文件的内容发生了任何形式的改变（包括人为修改，如Repack进木马病毒，或者下载过程中线路不稳定引起的传输错误等），只要你对这个文件重新计算MD5时就会发现信息摘要不相同，由此可以确定你得到的只是一个不正确的文件。MD5还广泛用于加密和解密技术上。例如在UNIX系统中用户的密码就是以MD5（或其它类似算法）经加密后存储在文件系统中。MD5的算法框图输入消息可任意长，压缩后输出为128bits。算法步骤(1)－分组