《现代密码学》散列函数与消息鉴别.ppt

现代密码学 散列函数与消息鉴别,主要内容,散列函数 MD5算法 安全散列算法SHA-1 消息鉴别 基于加密技术的消息鉴别 基于散列函数的消息鉴别 HMAC算法,散列函数的概念,散列函数（hash函数）可以表示为： hH(m) 其中，m为任意长度的输入消息（message），h为固定长度的消息摘要（ message digest，MD ），也称为散列码，函数H即为散列函数。 散列函数H有以下基本特性： (1)H(m)能用于任意长度的的数据并产生定长输出。 (2)对于给定的m,H(m)易于计算，使得软件和硬件实现成为实际可行。 (3)H(m)算法公开，不需要密钥。,H还必须具有以下安全特性： (1)单向性：对任何给定的码h，寻找m使得H(m) = h在计算上是不可行的 (2)具有弱抗碰撞性（week collision resistance） ：对于任何给定的消息m，寻找一个与m不同的消息m使得H(m)=H(m)在计算上不可行。 (3)具有强抗碰撞性（ strong collision resistance ）：寻找任意两个不同的消息m和m使得使得H(m)=H(m)在计算上不可行。,对散列函数必须具有的性质的理解： 系统可能存在的伪造方式 伪造方式一：若攻击者截获某一消息摘要h,如果H的逆函数H-1是易求的，可算出H-1(h)=m, 满足h=H(m)。为防止这一点，必须要求散列函数H为单向的，即计算H的逆函数H-1在计算上是不可行的。 伪造方式二：从一个有效签名(m,y)开始，此处y= sigk(H(m)。首先计算h=H(m)，并企图找到一个m=m满足H(m)=H(m)。若做到这一点，则(m,y)也将为有效签名。为防止这一点，要求函数h具有弱抗冲突特性，即，对给定消息m，在计算上几乎找不到不同于m的m X使H(m)=H(m)。,3.伪造方式三：首先找到两个不同的消息m和m,满足H(m)=H(m),然后把m 给他人且使他人对m的摘要H(m)签名，从而得到y,那么(m,y)是一个对于（m,y）有效的伪造。为防止这一点，要求函数h具有强抗冲突特性，即，在计算上几乎不可能找到相异的m，m使得H(m)=H(m). 注：强抗冲突自然含弱抗冲突！,散列函数的应用,保证数据的完整性 1.数据存储中的完整性： 假定m是要存储的信息，h=H(m)是消息m的散列值，并将h安全的保存，之后使用数据m时，用户都可以先用散列函数计算其散列值并与h比较，若相等，则说明数据m是完整的，否则说明m被篡改。 2.通信过程中的数据完整性： 假定m是要发送的信息， h=H(m)是消息m的散列值，将（m,h)发送给接受者，接收者验证h是否等于H(m)。（存在很大的安全问题！）,问题：Hash函数H是公开的，攻击者如果将m改成m,消息摘要也会变成h=H(m),接收者无法发现消息的改变。 一个解决方法：带密钥的hash函数h=H(k,m)攻击者无法计算h=H(k,m),因为没有密钥k。 散列函数实现数据传输中的完整性保护模型： 假定A要给B发送一条信息m，且他们共享一个密钥k，则A进行以下计算： h=H(m,k),并把m|h(|表示两个消息序列的连接)发送给B，B很容易计算H(m,k),验证m的完整性。,散列函数的应用,数字签名 将散列函数应用于数字签名，一般方法是不直接对消息m签名，而对m对应的散列码h进行签名，这样可以提高签名的速度(|h|m|),且不泄露签名所对应的信息，因此散列函数在数字签名中应用广泛。,散列函数的一般结构,目前使用的大多数散列函数，其结构都是迭代型的。将输入的消息m分成t个分组( m1 ，,m2，mt)，每组固定长度为b位。如果最后一个分组的长度不够，需要对其进行填充。通常的填充方法是保证最后一个分组的最后64位为m的总长度，然后在中间填充。,对散列函数的攻击,穷举攻击： 第一种是最明显的：给定消息M的散列值H(M)，破译者逐个生成其他消息M，以使H(M)= H(M)假定其输出为m比特，那么寻找一个消息，使其散列值与给定散列值相同则需要计算2m次。 第二种攻击方法设计更巧妙：攻击者寻找两个随机的消息：M和M，并使H(M)=H(M)(这称为碰撞)，这就是所谓的生日攻击，它比第一种方法来得容易。,生日悖论 在k个人中，要至少有两个人生日相同的概率大于 0.5，问k的最小值是多少？ 使k个值不重复的取值方式数目N为： 而k个数任意取两个值的方式总数为：365k 因此存在不重复的概率为： 而出现重复的概率为： 。,计算可得，当k = 23时，至少有一个重复的几率 为0.5073，当k = 100时，至少有一个重复的概率 为0.9999997、 生日悖论 原因 虽然组中某个特定的人与组中其他人生日相 同的概率很小，但组中任意两人生日相同的 概率却很大。 推论 给定一个取整数的随机变量，它服从1到n间 的均匀分布，另有一个包含k个（kn）这样 随机变量的选集，至少有一个重复的概率P(n, k)为：,对较大的k，上式可简化为： 假定散列函数H的输出长度为m位，则H有2m个可 能输出，那么对某个输入x，y，有H(x)=H(y)的 概率存在时： 这种寻找散列函数H具有相同输出的两个任意输入的攻击方式就称为生日攻击.,对散列函数的生日攻击方法 源点A准备通过附加m-bit的散列码以及用A的私有密钥对散列码加密来对报文进行“签名”。 攻击者对该报文产生2m/2个报文变种，所有这些变种在本质上均表达同样的意思。攻击者还准备了相同数量的报文，均是用于替代真报文的假报文的变种。 比较两个报文集以发现能够产生相同散列值的报文对。根据生日悖论，成功的概率大于0.5。如果没有发现任何匹配，将产生其他有效的报文和假报文，直到出现一个匹配。 攻击者提供一个对A签名有效的变种。该签名被附加在这个带有欺诈性报文上发往原来的接收者。因为这两个报文变种具有相同的散列码，故它们能产生相同的签名；即使不知道加密密钥，攻击者也肯定获得成功,对散列函数的生日攻击,假定其输出为m比特，那么寻找一个消息，使其散列值与给定散列值相同则需要计算2m次；而寻找两个消息具有相同的散列值仅需要试验2m/2个随机的消息。 每秒能运算一百万次单向散列函数的计算机得花600,000年才能找到一个消息与给定的64比特散列值相匹配。同样的机器可以在大约一个小时里找到一对有相同散列值的消息。,生日攻击举例,Alice准备一份合同的两种版本X和Y，X对Bob有利，而Y将使他破产。 Alice对这两种版本的每一份都做一些细微的改变（如利用空格、回车等），分别产生232份不同的文件，并计算所有文件的散列值。,X1,H(X1),X2,H(X2),X3,H(X3),Y1,H(Y1),Y2,H(Y2),Y3,H(Y3),232份,232份,Alice比较两种不同版本的文件的散列值集合，找到散列值相同的一组。根据生日悖论，成功的可能性大于0.5。 Alice挑选出这一组，将其中的X传给Bob。 Bob在对他有利的那份合同版本签名。 在以后的某个时候，Alice用Bob未签名的合同代替他签过名的合同。现在他能使公证人员确信Bob签署过另一份合同。,X1,H(X1),X2,H(X2),X3,H(X3),Y1,H(Y1),Y2,H(Y2),Y3,H(Y3),232份,232份,MD5算法,Message Digest Algorithm MD5（消息摘要算法第五版）为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。 MD表示消息摘要(Message Digest) MD5是MD4的改进版，该算法对输入的任意长度消息产生128位散列值(或消息摘要),输入被划分成为512位的数据块,MD5算法,数据的分拆与填充 1.设输入信息为任意长度的m,将m按照512比特块进行分拆，对最后一个一个比特块填充成一个448比特的消息块： m= ( m1，m2，mt ） 填充规则为从m最低位开始，先添加一个1，再添加若干个0，使最后一个比特块填充成448比特的块。 2.将原始消息m的长度l用64位的二进制数表示，（若不足64位，则添加若干0补足；当原消息长度大于264时，用消息长度mod 264填充） 3.将l的64位二进制表示添加到的mt 后面记为mt. 4.将每个消息块分拆成16个字，令M0 1N1为填充后消息的各个字(每字为32位)，N是16的倍数,MD5算法的逻辑程序 1.初始化MD5缓冲区 初始化用于计算消息摘要的128位缓冲区。这个缓冲区由四个32位寄存器A、B、C、D表示。寄存器的初始化值为(按低位字节在前的顺序存放)： A: 01 23 45 67 B: 89 ab cd ef C: fe dc ba 98 D: 76 54 32 10,2.按512位的分组处理输入消息 这一步为MD5的主循环，包括四轮。每个循环都以当前的正在处理的512比特分组Yq和128比特缓冲值ABCD为输入，然后更新缓冲内容。 3.MD5的输出 由A、B、C、D四个寄存器的输出按低位字节在前的顺序(即以A的低字节开始、D的高字节结束)得到128位的消息摘要。,单个512比特分组的MD5主循环处理：,四轮的操作类似，每一轮进行16次操作。各轮的操作过程如图所示。,四轮操作的不同之处在于每轮使用的非线性函数不同.这四个非线性函数分别为(其输入/输出均为32位字)： F(X,Y,Z) = (X Y) (X) Z) G(X,Y,Z) = (X Z) (Y (Z) H(X,Y,Z) = X Y Z I(X,Y,Z) = Y (X (Z) 其中， 表示按位与； 表示按位或；表示按位反； 表示按位异或。,这一步中还用到了一个有64个元素的表T164，Ti=232abs(sin(i)，i的单位为弧度。 将这一步骤的处理过程归纳如下： for i = 0 to N/161 do /* 每次循环处理16个字，即512位的消息分组*/ /*把A存为AA，B存为BB，C存为CC，D存为DD*/ AA = A BB = B CC = C DD = D,MD5的安全性,山东大学的王小云教授在2004年美洲密码年会上做了攻击MD5等四个算法的报告，并给出了一个具体的MD5的碰撞的例子。这清楚表明了MD5不是强抗碰撞的，MD5的安全性受到了严重的威胁。,安全散列算法SHA-1,SHA（secure hash aigorithm）是美国NIST 在1993年发布的。 SHA-1则是1995年发布的修订版本，它也是基于散列算法D4。 SHA-1是数字签名标准DSS(Digital Signature Standard)中使用的散列算法。它能够处理最大长度为264位的输入数据，输出为160位的散列码，它的输出正好作为数字签名算法DSA的输入。,SHA1产生消息摘要的过程类似MD5，如图所示,SHA-1的具体过程,1.填充消息 将消息填充为512位的整数倍，填充方法和MD5完全相同：先填充一个1，然后填充一定数量的0，使其长度比512的倍数少64位 用原消息长度的64位表示填充。这样，消息长度就成为512的整数倍 以M0、M1、Mn表示填充后消息的各个字块(每字块为16个32位字),2. 初始化缓冲区 SHA要用到两个缓冲区，两个缓冲区均有五个32位的寄存器。 第一个缓冲区标记为A、B、C、D、E 第二个缓冲区标记为H0、H1、H2、H3、H4 此外，运算过程中还用到一个标记为W0、W1、W79 的80个32位字序列和一个单字的缓冲区TEMP。 在运算之前，初始化Hj： H0 = 0x67452301 H1 = 0xEFCDAB89 H2 = 0x98BADCFE H3 = 0x10325476 H4 = 0xC3D2E1F0,3.按512位的分组处理输入消息 SHA运算主循环包括四轮，每轮20次操作。SHA用到一个逻辑函数序列f0、f1、f79。每个逻辑函数的输入为三个32位字，输出为一个32位字。定义如下(B、C、D均为32位字)： ft(B,C,D)=(BC)(BD) (0t19) ft(B,C,D)=BCD (20t39) ft(B,C,D)=(BC)(BD)(C D) (40t59) ft(B,C,D)= B C D (60t79) SHA运算中还用到了常数字序列K0、K1、K79，其值为 Kt = 0x5A827999 (0t19) Kt = 0x6ED9EBA1 (20t39) Kt = 0x8F1BBCDC (40t59) Kt = 0xCA62C1D6 (60t79),SHA算法按如下步骤处理每个字块Mi (1)把Mi分为16个字W0、W1、W15，其中，W0为最左 边的字。 (2) for t =16 to 79 do let Wt =(Wt3 Wt8 Wt14 Wt16)1 (3) Let A =H0，B =H1，C =H2，D =H3，E =H4 (4) for t =0 to 79 do TEMP = (A5)+ft (B, C, D)+E +Wt +Kt ; E =D; D =C; C =(B30); B = A; A = TEMP; (5) Let H0 =H0 +A, H1 =H1 +B, H2 =H2 +C, H3 =H3 +D, H4 =H4 +E 4. 输出 在处理完Mn后，160位的消息摘要为H0、H1、H2、H3、H4级联的结果。,SHA-1算法与MD5的比较,消息鉴别,消息鉴别是用以验证接收消息的真实性（确实是由他所声称的实体发来的）和完整性（未被篡改、插入、删除），同时还用于验证消息的顺序性和时间性（未被重排、重放、延迟等）。 除此之外，在考虑信息安全问题时还要考虑业务的抗抵赖性，即防止通信双方中的某一方对所传输消息的否认或抵赖。实现消息的抗抵赖性可采用数字签名机制。 大体来说，实现消息鉴别的手段可分为两类：基于加密技术的消息鉴别和基于散列函数的消息鉴别。,基于加密技术的消息鉴别,基于对称加密体制的消息鉴别 (a)常规加密： 实现：发送方A和接收方B共享密钥k,A用k将M加密后通过公共信道传给B，B接收到信息后，通过是否能用k将其恢复成合法信 息，来判断消息是否来自A及消息的完整性。 特点：只能提供机密性（只有A和B知道密钥k）和提供鉴别（只能发自A，且未被篡改）给定解密函数D和密钥K，终点将接受任何输入X并产生输出Y =DK(X)。如果X是对应的加密函数产生的合法报文M的密文，那么Y是报文M的明文，否则，Y将是毫无意义的二进制比特序列。在B方需要某些自动化的手段以确定Y是否是合法的明文，以此确定来自A。,假定报文M能是任何任意的比特组合。在这 种情况下，在终点没有自动的方法来确定收到 的报文是否是合法的报文的密文。此结论无可 辩驳：如果M能是任何比特组合，则与X的值无 关，而Y = DK(X)是一些比特组合，因此必须 作为真的明文被接受下来。 一般来说，仅需要从所有可能的比特模式 中的一个小子集中来考虑合法的明文。在这种 情况下，任何可疑的密文不可能产生合法的明 文。例如，假定在106里仅仅有一种组合是合 法的明文。那么从中随机选中一个比特组合看 作密文来能产生合法明文报文的概率仅仅是 10-6。,基于公钥密码体制的消息鉴别 (b)只提供机密性 实现：发送方A用接收方B的公钥对信息M加密后传输给B，B用自己的私钥将密文恢复出明文M。 特点：只能实现机密性(只有B才可以解密出信息)。不能提供鉴别(因为B不能确定消息来源，任何人都可以用B的公钥来加密信息)；不能提供数字签名(A可以抵赖发送信息),基于加密技术的消息鉴别,基于公钥密码体制的消息鉴别 (c)提供消息鉴别和数字签名 实现：发送方A用自己的私钥对消息进行加密，通过公共信道传输给B，B用A的公钥对信息解密并完成鉴别。 特点：可提供数字签名（只有A拥有自己的私钥，故只有A才能产生出用A的公钥才可解密的密文，所以消息一定来自于A），可提供鉴别（传输中未被篡改，否则B无法解密信息）。 不能提供机密性保护，为什么？ 因为任何具有发送方A的公钥的人都可以解密密文，因此这种方法并不能保证信息的机密性。,基于公钥密码体制的消息鉴别 (d)实现机密性、鉴别、数字签名 实现：在发送方A用自己的私钥进行进行加密运算之后（实现数字签名）之后，再用B的公钥进行加密（实现机密性）。 这种方法是(b)和(c)两种方法的结合，它可以实现保密、鉴别和数字签名。缺点是一次完整的通信需要执行公钥算法的加密、解密各两次。,基于散列函数的消息鉴别,1.消息鉴别码MAC (Message Authentication Code) 消息鉴别码MAC，是使用一个特定的密钥将消息通过某种鉴别算法计算得出的一串代码,是用于提供数据原发鉴别和数据完整性的密码校验值。由如下形式的函数h生成: MAChK(M) 其中M是变长的报文，K是仅由收发双方共享的密钥，hK(M)是定长的鉴别符。 MAC函数类似于加密。一个区别是MAC函数无 需是可逆的，而对解密则必须是可逆的。结果由 于鉴别函数的这个数学性质使得它比加密函数更 不易被破解。,hK具有如下特性： (1)给定一个值k和一个输入M，hK(M)是容易计算的； (2)压缩：能将任意长度的输入映射成一个固定长度的输出； (3)强抗碰撞性：要找到两个不同的消息x和y，使得它们的输出相等在计算上是不可行的 因为hK具有压缩，强抗碰撞性等特性，使它更类似于散列函数。因此在应用中往往使用带密钥的散列函数作为hK函数来实现MAC。,基于DES的报文鉴别码 是联邦信息处理标准（FIPS PUB 113）和ANSI标准（X9.17）。 该算法定义为以密码分组链接（CBC）为操作方式的用0作为初始化向量的DES。被鉴别的数据（例如报文、记录文件或者程序）被分为连续的64 bit分组：D1，D2，DN。如果必要，用0填充最后分组的右边形成满64 bit的分组。 使用DES算法E、秘密密钥K，数据鉴别代码 （DAC）可计算如下： O1 = EK(D1) O2 = EK(D2O1) ON = EK(DNON-1),利用MAC进行消息鉴别的基本方法： 假定通信双方，A和B，共享一个共有的密钥K。当A有要发往B的报文M时，它将计算MAC，MAC作为报文和密钥K的一个函数值：MAC = hK(M)，然后将加上MAC报文发往预定的接收者。使用相同的密钥，接收者对收到的报文执行相同的计算并得出MAC。将收到的MAC与MAC进行比较。如果二者相等，假定只有收方和发方知道密钥，那么可以判断：,(1)接收者确信报文未被篡改。如果一个攻击 者更改报文而未更改MAC，那么接收者计算出 的MAC将不同于接收到的MAC。因为假定攻击者 不知道该密钥，因此攻击者不可能更改MAC来 对应更改后的报文。 (2)接收者确信报文来自所谓的发送者。因为 没有其他人知道该密钥，因此没有人能够为一 个报文准备合适的MAC。,图a中的方法只能提供消息鉴别，而不能提供机密性(因为消息M是以明文的形式传输的)。 如果在生成M之后(如图b)或者之前(如图c)使用加密机制，则可以保证消息的机密性。,2.基于散列函数的消息鉴别,这是单向散列函数报文鉴别码的一个变种。就像消息鉴别码，一个散列函数以一个变长的报文M作为输入，并产生一个定长的散列码H(M)，作为输出。散列码是报文所有比特的函数值，并有差错检测能力：散列函数只是输入消息的函数，输入消息中任意一比特或若干比特发生改变都将导致散列码发生改变。 但必须注意的是，散列函数没有密钥，在散列函数公开的情况下，任何人都可以根据输入计算散列值。在安全通信中，常需要一个密钥与散列函数结合起来产生MAC,（a）AB：EKM|H(M) ：用对称密码体制加密消息及其散列值 提供保密仅A和B共享K 提供鉴别通过对H(M)的比较鉴别，可确定信息来 源于A且未被篡改,（b）AB：M|EKH(M):用对称密码体制只对消息的散列值加密 不能提供机密性消息M以明文形式传递 提供鉴别,（c）AB：M|EKRaH(M):用公钥密码体制只对散列值加密 提供鉴别 提供数字签名只有A能生成EKRaH(M),（d）AB：EKM|EKRaH(M):用发送方的私钥对散列值进行数字签名，用对称密码体制加密消息并得到数字签名 提供鉴别，数字签名，机密性,（e）AB：M|H(M|S):只是用散列算法，其 中S是仅收发双方共享的一个秘密信息，且S不 参与传递 提供鉴别仅A和B共享S,（f）AB：EKM|H(M)|S：在方法e的基础上，用对称密码体制加密消息和散列值 提供鉴别和数字鉴别仅A和B共享S 提供保密仅A和B共享K,当不需保密时，方法(b)和(c)在降低计算量上要优于那 些需对整个报文加密的方法。然而，目前对避免加密 的方法 (e)越来越重视。对这种重视，其原因为： 加密软件很慢。即使每个报文中需加密的数据量很小，也可能有稳定的报文流进和流出一个系统。 加密硬件的开销是不可忽略的。尽管已有费用低廉的实现DES算法的芯片，但如果网络中的所有结点都必须拥有这种加密能力，累加的