第6章-消息认证和杂凑函数.ppt

2020/6/14，1，6.1消息认证码6.2哈希函数6.3MD5哈希算法6.4安全哈希算法6.5HMAC，2020/6/14，2。第一章介绍了信息安全面临的基本攻击类型，包括被动攻击和主动攻击。对抗被动攻击的方法是如前所述的加密，而本章所述的消息认证用于对抗主动攻击。消息认证是一个验证接收消息的真实性(实际上，它是由它声称的实体发送的)和完整性(未被篡改、插入、删除)的过程，也是验证消息的顺序和及时性(未被重新排列、重放、延迟)的过程。此外，在考虑信息安全时，还必须考虑服务的不可否认性，即防止通信方之一拒绝传输的消息。消息不可否认性的实现可以通过数字签名来实现，数字签名也是一种认证技术，也可以用来抵抗主动攻击。2020/6/14，3，消息认证机制和数字签名机制具有生成认证器的基本功能，这也是认证协议的组成部分。验证器是用于验证消息的数值。其生成方法进一步分为消息认证码(message authentication code)哈希函数、2020/6/14、4、6.1消息认证码和6.1.1消息认证码的定义和使用。消息认证码是指一个固定长度的数字值，在由密钥控制的公共函数对消息进行操作后，该值用作认证符，也称为加密校验和。此时，甲、乙双方需要共享一个密钥k。假设甲想发送给乙的消息是M。甲首先计算MAC=CK(M)，其中CK()是密钥控制的公共函数，然后发送给乙。乙收到后，进行与甲相同的计算，得到一个新的MAC，并与收到的MAC进行比较。2020/6/14，5，图6.1媒体访问控制的基本用法，2020/6/14，6。如果只有发送方和接收方知道K，并且由b计算的媒体访问控制与接收到的媒体访问控制一致，则系统实现如下功能：接收方认为发送方发送的消息没有被篡改，因为攻击者不知道密钥，所以篡改消息后媒体访问控制不会相应地被篡改，如果只是篡改消息，则接收方计算的新媒体访问控制将不同于接收到的媒体访问控制。接收者相信发送者不是在假装，因为除了发送者和接收者之外，没有其他人知道密钥，所以其他人不可能为他们发送的消息计算正确的媒体访问控制。2020/6/14，7，MAC函数类似于加密算法，除了MAC函数不必是可逆的，因此它比加密算法更不容易受到攻击。在上述过程中，由于消息本身在发送过程中是明文的，因此该过程仅提供身份验证，而不提供机密性。为了提供保密性，可以在媒体访问控制功能之后或之前执行一次加密，加密密钥也必须由发送方和接收方共享。2020/6/14、8、2020/6/14、9、6.1.2生成媒体访问控制的功能需要满足的要求。当使用加密算法(单密钥算法或公钥算法)加密消息时，其安全性通常取决于密钥的长度。如果加密算法没有弱点，对手只能使用一个不良的搜索攻击来测试所有可能的密钥。如果密钥长度为k位，则较差的搜索攻击将平均执行2k-1测试。特别地，对于仅密文攻击，如果对手知道密文C，他将对所有可能的密钥值Ki执行解密操作Pi=DKi(C)，直到获得有意义的明文。2020/6/14，10，对于媒体访问控制，由于生成媒体访问控制的函数通常是多对一映射，如果生成n位长的媒体访问控制，则函数的取值范围是2n个可能的媒体访问控制，即函数N2n输入的可能消息数，如果函数使用的密钥是k位，则可能的密钥数是2k。如果系统不考虑机密性，即对手可以获得明文消息和相应的媒体访问控制，那么在这种情况下，对手应该考虑使用较差的搜索攻击来获得生成媒体访问控制的功能所使用的密钥。2020/6/14，11，假设kn，并且对手已经获得M1和MAC1，其中MAC1=CK1(M1)，对手获得所有可能的键值Ki的MAC1=CK1(m1)，直到找到某个Ki，使得MACi=MAC1。因为不同密钥的数量是2k，所以将生成2k个媒体访问控制，但是它们中只有2n个是不同的。由于2k2n，许多密钥(平均2k/2n=2k-n)可以生成正确的MAC1，而对手不知道通信的两个用户使用哪个密钥。上述攻击还必须重复如下：2020/6/14，12。M1和MAC1在第一轮中是众所周知的，其中MAC1=CK(M1)。为所有2k个可能的密钥计算MACi=CKi(M1)以获得2k-n个可能的密钥。在第二轮中，M2和MAC2是已知的，其中MAC2=CK(M2)。为在前一轮中获得的2k-n个可能的密钥计算MACi=CKi(M2)以获得2k-2n个可能的密钥。这样，如果k=n，上述攻击模式平均需要轮。例如，如果密钥长度为80位，而媒体访问控制长度为32位，第一轮将生成大约248个可能的密钥，第二轮将生成216个可能的密钥，第三轮将找到正确的密钥。2020/6/14，13。如果密钥的长度小于媒体访问控制的长度，就有可能在第一轮中找到正确的密钥，也有可能找到多个可能的密钥。如果是后者，仍有必要进行第二轮搜索。因此，对消息认证码的不良搜索攻击比使用相同长度密钥的加密算法的不良搜索攻击更昂贵。有些攻击不需要找到用于生成MAC的密钥。例如，2020/6/14，14，假设通过链接64位长分组Xi (I=1，m)，其消息认证码通过以下方法获得：其中它表示异或运算，加密算法是码本模式下的DES。因此，密钥长度为56位，媒体访问控制长度为64位。如果对手获得了CK(M)，那么对手将需要256次加密才能使用差搜索攻击来找到k。然而，对手也可以通过以下方式攻击系统：X1到Xm-1被他们自己选择的Y1到Ym-1替换，并且Ym=y1y2.获得ym-1 (m ),并且Xm被ym代替。因此，对手可以成功地伪造新的消息M=y1.考虑到媒体访问控制中存在的上述攻击类型，我们知道它应该满足以下要求，其中假设对手知道函数c但不知道密钥k:如果对手获得M和CK(M)，则在计算上不可行构造满足CK(M)=CK(M)的新消息M。CK(M)在以下意义上是均匀分布的：两个消息M，M，PrCK(M)=CK(M)=2-n，其中n是媒体访问控制的长度。如果M是M的变换，即M=f(M)，例如f是一个或多个比特的插入，则prCK(M)=CK(M)=2-n，2020/6/14，16。第一个要求是上面例子中的攻击类型。这一要求意味着，在计算上，对手伪造与被截获的媒体访问控制相匹配的新消息而不找到密钥K是不可行的。第二个要求是，如果对手截获了一个媒体访问控制，伪造匹配消息的概率是最小的。最后一个要求是，函数C不能弱于消息的其他部分或某一部分或某一部分的比特，否则对手可能在获得M和MAC后修改M的弱部分，从而伪造与原始MAC匹配的新消息。2020/6/14，17，6.1.3数据认证算法，数据认证算法是最广泛使用的消息认证码之一，已被作为FIPS出版物(FIPS出版物113)和ANSI作为X9.17标准。该算法基于CBC模式的DES算法，其初始矢量为零矢量。要验证的数据(消息、记录、文件或程序)被分成64位长的数据包，D1、D2，DN。如果最后一个包少于64位，可以在右边填入一些零，然后数据认证码计算如下：2020/6/14，18，图6.2数据认证算法，2020/6/14，19，其中e是DES加密算法，k是密钥。数据认证码或者为开，或者为开的最左边的M位，其中16M64。2020/6/14，20，6.2哈希函数，6.2.1哈希函数的定义和用法哈希函数H是一个公共函数，用于将任意长度的消息M映射到较短的固定长度值H(M)，该值称为哈希值、哈希代码或消息摘要作为认证符。哈希码是消息中所有比特的函数，因此提供了错误检测能力，即改变消息中的任何一个或多个比特都会改变哈希码。，2020/6/14，21。哈希函数提供消息认证的基本用法包括6种类型的消息，这些消息在与哈希代码链接后用单密钥加密算法加密。因为所使用的密钥仅由发送方和接收方A和B共享，所以可以保证消息确实来自A并且没有被篡改。同时，由于消息和哈希代码都是加密的，这种方法也提供了隐私。只有散列码用单密钥加密算法加密。当不需要保密性时，这种方法可以减少处理负担。请注意，该方法与图6.1(a)中的媒体访问控制结果完全相同，即EKH(M)被视为一个函数，函数的输入是消息M和密钥k，输出是固定长度的，2020/6/14，22，2020/6/14，23，只有散列码用公钥加密算法和发送者的密钥加密。与(2)中一样，该方法提供身份验证，并且由于只有发送方可以生成加密的哈希代码，因此该方法还为发送方发送的消息提供数字签名。实际上，这种方法是用公钥加密算法和发送方的密钥对数字签名消息的哈希值进行加密，然后与消息进行链接，链接结果用单密钥加密算法进行加密。该方法提供保密性和数字签名，2020/6/14，24，2020/6/14，25，当使用该方法时，通信双方需要共享秘密值S，A计算由消息M和秘密值S链接在一起的散列值，并且在将散列值附加到M之后将散列值发送到B。由于B也具有S，所以可以重新计算散列值以认证消息。由于秘密值S本身还没有被发送，对手不能篡改被拦截的消息或产生虚假消息。此方法仅提供身份验证。该方法在中将消息和哈希值链接后增加了一个单密钥加密操作，从而提供了保密性。因为加密操作缓慢且昂贵，而且许多加密算法也受专利保护，所以方法和方法将优于其他不需要保密的方法。2020/6/14、26、2020/6/14、27、6.2.2哈希函数应满足的条件，哈希函数的目的是为要验证的数据生成“指纹”。为了能够验证数据，散列函数应该满足以下条件：函数的输入可以是任何长度。函数的输出是固定长度的。给定x，找到H(x)相对容易，可以通过硬件或软件实现。给定H，在计算上找x使H(x)=h是不可行的，这个性质称为函数的单向性，H(x)称为单向散列函数。2020/6/14，28，给定x，找到y(yx)使得H(y)=H(x)在计算上不可行。如果单向散列函数满足这个属性，它被称为弱单向散列函数。找到任意两个不同的输入x，y使得H(y)=H(x)在计算上不可行。如果单向散列函数满足这个属性，它被称为强单向散列函数。条件和给出了散列函数无冲突的概念。如果散列函数可以为不同的输入产生相同的输出，那么这个函数就被称为是无冲突的。2020/6/14，29。在上述6个条件中，前3个是用于消息认证的散列函数的基本要求。第四个条件(即单向性)对于使用秘密值的认证技术极其重要(见图6.3(e)。如果散列函数不是单向的，攻击者可以在截取M且C=H(SM)后通过寻找C的逆SM来获得秘密值S。第五个条件使得对手不可能找到另一个与已知消息具有相同散列值的消息。当散列值被加密时(见图6.3(b)和图6.3(c)使用该属性来防止对手的伪造。在这种情况下，对手可以读取传输的明文消息M，因此可以生成消息的散列值H(M)。2020/6/14，30，但是由于对手不知道用于加密散列值的密钥，他不可能伪造消息M和该消息的散列值的加密密文EKH(M)。然而，如果第五个条件不成立，在截取明文消息及其加密散列值之后，对手可以通过以下方式伪造消息：首先，找到被截取消息的散列值，然后生成具有相同散列值的伪造消息，最后将伪造消息和截取的加密散列值发送到的接收者，2020/6/14，31，6.2.3生日攻击，1。相关问题已知一个散列函数H有N个可能的输出，H(x)是一个特定的输出，如果随机取K个输入到H，那么至少一个输入Y使得H(y)=H(x)的概率为0.5，什么是K？为了描述方便，对散列函数H的攻击被称为一类生日攻击。2020/6/14，32，因为H有n个可能的输出，所以由输入Y生成的输出H(y)等于特定输出H(x)的概率是1/n，反之，H(y)等于1-1/n的概率。Y取k个随机值，函数的k个输出都不等于H(x)，其概率等于每个输出不等于H(x)的概率的乘积，并且是1-1/1 因此，y取k个随机值以获得函数的k个输出中至少有一个等于H(x)且为1-1-1/n k的概率。从(1 x)k1 kx，其中|x|365，不可能使任何两个数据不同，因此假设k365。 k个数据项中的任何两个的所有值的数量是2020/6/14，34，即第一个数据项可以是365中的任何一个，第二个数据项可以是其余364中的任何一个，依此类推，最后一个数据项可以是365-k 1个值中的任何一个。如果去掉任何两个项目不同的限制条件，k个数据项中所有值的个数可以是365k.因此，2020/6/14，35，2020/6/14，36，当k=23时，P(365，23)=0.5073，即上述问题只需要23个人。如果k取为100，则P(365，100)=0.9999997，即获得如此大的概率。这个问题之所以被称为悖论，是因为当给定k时，至少两个人同一天生日的概率比预期的要大得多。这是因为考虑了K个个体中的任何两个个体的生日是否相同，并且23个个体中可能的病例数是C223=253。2020/6/14，37，将生日悖论推广到以下问题：给定一个均匀分布在1和n之间的整数随机变量，如果该变量的至少两个k值具有相同值的概率大于0.5，那么最小k值是多少？与上面类似，使P(n，k)0.5可用。如果n=365，那么。生日攻击生日攻击基于以下结论：让哈希函数h有2m个可能的输出(即输出长度m位)。如果h的k个随机输入中至少有两个具有产生大于0.5的相同输出的概率，则。用函数H的相同输出找到两个任意输入的攻击方法称为二类生日攻击。2020/6/14，39，第二类生日攻击可以通过以下方式进行：设置用户以图6.3(c)所示的方式发送消息，即A用自己的密钥对消息的哈希值进行加密，加密后的