原创文章,转载请注明:转载自Keegan小钢 并标明原文链接:http://keeganlee.me/post/reading/20160705 微信订阅号:keeganlee_me 写于2016-07-05
前一篇文章总结了密码部分的内容,包括一次性密码本、对称密码、公钥密码、混合密码系统等。这些密码在一定程度上能够保证消息的机密性,即可以防止被窃听导致秘密泄露。但却无法防御信息被篡改,也无法确定消息的来源是否就是真实的发送者而不是来自伪装者,也防止不了发送者事后否认自己先前做过的行为。关于这些问题,在本文总结的密码技术中就可以找到解决方案。
本文是关于《图解密码技术》第二部分的内容总结,包括单向散列函数、消息认证码、数字签名、证书。
使用单向散列函数可以获取消息的“指纹”,通过对比“指纹”,就能够知道两条消息是否一致。这种一致性,也称为完整性,可以识别出消息是否被篡改。
单向散列函数(one-way hash function)有一个输入和一个输出,其中输入称为消息(message),输出称为散列值(hash value)。散列值也称为消息摘要(message digest)或者指纹(fingerprint)。单向散列函数可以根据消息的内容计算出散列值,而散列值就可以用来检查消息的完整性。
单向散列函数的性质
单向散列函数的例子
单向散列函数有很多种,MD4、MD5、SHA-1、SHA-256、SHA-384、SHA-512、SHA-3等等。
MD4是由Rivest于1990年设计的,MD是消息摘要(message digest)的缩写,两者都能够产生128比特的散列值。不过,第二年,即1991年,就已经有人提出了MD4的漏洞,很容易就寻找到了MD4散列碰撞的方法。因此,Rivest又设计了更为成熟的MD5。MD5到现在依然有着广泛的应用,例如很多网站和应用的登录密码都使用了MD5。但MD5的强抗碰撞性已经被攻破,也就是说,现在已经能够产生具备相同散列值的两条不同的消息。所以,其实MD5已经不安全了。
SHA是NSA(美国国家安全局)设计,NIST(美国国家标准与技术研究院)发布的一系列单向散列函数。SHA是以MD4和MD5类似的原理为基础来设计的。SHA-1能够产生160比特的散列值,不过消息长度是有上限的,上限为2^64比特(准备地说是2^64-1)。当然这个数已经非常巨大,所以在实际应用中没有问题。不过,SHA-1的强抗碰撞性已于2005年被攻破。所以,SHA-1也和MD5一样没那么安全了。不过,貌似SHA-1依然是目前使用最广泛的单向散列函数。
SHA-256、SHA-384和SHA-512的散列值长度分别为256比特、384比特和512比特。它们的消息长度也存在上限,SHA-256的上限和SHA-1一样,而SHA-384和SHA-512的消息上限则为2^128比特(确切值为2^128-1)。这些单向散列函数合起来称为SHA-2。目前,SHA-2还没有被攻破。
在2005年SHA-1被攻破的背景下,促进了SHA-3的产生。SHA-3与AES一样采用了公开竞赛的方式进行标准化,最后胜出的是Keccak算法。
单向散列函数SHA-1
SHA-1作为一个具有代表性的单向散列函数,让我们看看它的算法流程是怎样的。整体流程如下图:
可以分为四个步骤:
首先,将输入分组的512比特分成16组,每组32比特。然后,剩下的 W16 ~ W79 使用如下的公式进行计算:
将5个缓冲区的值与输入分组的信息进行混合,然后再执行80个步骤的处理。从结果来看,这80个步骤所完成的操作,就是将输入分组的512比特的数据,也SHA-1所保持的160比特的内部状态(5个缓冲区)进行混合。通过80个步骤的反复执行,SHA-1就能够将已经过填充的消息全部混入这160比特的内部状态中,而SHA-1所输出的散列值,就是所有处理结束之后最终的内部状态(160比特)。
在一个步骤完成之后,缓冲区A、B、C、D的内容会被分别复制到B、C、D、E中(其中B要循环左移30比特之后再复制),而缓冲区 E 的内容则会与其他缓冲区的内容以及Wt、Kt相加之后再被复制到缓冲区A中。 由于上述处理要循环80个步骤,因此输入分组中 1 比特的变化,就会影响到散列值中几乎所有的比特,通过这样的方式,就能够实现单向散列函数所应具备的性质。
对单向散列函数的攻击
对单向散列函数的攻击主要就是对单向散列函数的”抗碰撞性“的攻击。
对“弱抗碰撞性”的攻击主要是利用消息的冗余性生成具有相同散列值的另一个消息,这种攻击也是暴力破解,每次都稍微改变一下消息的值,然后对这些消息求散列值。在这种情况下,暴力破解需要尝试的次数可以根据散列值的长度计算出来。以SHA-1为例,由于它的散列值长度为160比特,因此最多只要尝试2^160次就能够找到目标消息。由于尝试次数纯粹是由散列值长度决定的,因此散列值长度越长的单向散列函数,其抵御暴力破解的能力也就越强。
对“强抗碰撞性”的攻击一般称为生日攻击。生日攻击不是寻找生成特定散列值的消息,而是要找到相同散列值的两条消息,而散列值则可以是任何值。生日攻击的原理来自生日悖论,也就是利用了“任意散列值一致的概率比想象中高”这样的特性。相对于暴力破解,生日攻击所需尝试的次数要少得多,一般只需要是暴力破解的一般。
单向散列函数无法解决的问题
单向散列函数可以实现完整性的检查,但却识别不了“伪装”,即无法解决认证问题。认证问题需要使用消息认证码和数字签名来解决。
单向散列函数在实际应用中很少单独使用,而是和其他密码技术结合使用。后面要讲的消息认证码和数字签名都使用了单向散列函数,而下一篇要讲的密钥、伪随机数和应用技术也都使用了单向散列函数。
消息认证码(message authentication code)是一种确认完整性并进行认证的技术,简称为 MAC。消息认证码的输入包括任意长度的消息和一个发送者与接受者之间共享的密钥,它可以输出固定长度的数据,这个数据称为 MAC 值。
消息认证码与单向散列函数很类似,都是根据任意长度的消息输出固定长度的数据,不同的是,消息认证码比单向散列函数多了一个共享密钥。没有共享密钥的人就无法计算出 MAC 值,消息认证码正是利用这一性质来完成认证的。此外,和单向散列函数一样,哪怕消息中发生 1 比特的变化,MAC 值也会发生变化,消息认证码正是利用这一性质来确认完整性的。
消息认证码的使用步骤
消息认证码的使用步骤如下图:
发送者与接收者需要事先共享密钥,然后发送者使用共享密钥对消息计算 MAC 值,接着将消息和 MAC值一起发送给接收者。接收者收到消息和 MAC 值后,使用同一个共享密钥对消息计算 MAC 值,当计算出来的 MAC 值和接收到的 MAC 值一致的,就证明认证成功了。
而既然是使用共享密钥,那就和对称密码一样,存在密钥配送问题。要解决密钥配送问题,同样可以使用事先共享密钥、密钥配送中心、Diffie-Hellman密钥交换、公钥密码等方法。具体请看前一篇文章的密钥配送问题部分。
消息认证码的实现
消息认证码有很多种实现方法。可以使用SHA-1、MD5之类的单向散列函数来实现,其中有一种实现方法叫 HMAC,后面我们再讲它实现的具体步骤。
也可以使用DES、AES之类的分组密码来实现消息认证码,将分组密码的密钥作为消息认证码的共享密钥来使用,并用 CBC 模式将消息全部加密。由于消息认证码不需要解密,因此,可以只保留最后一个分组的密文作为 MAC 值,而其他密文则全部丢弃。由于 CBC 模式的最后一个分组会收到整个消息以及密钥的双重影响,因此可以将它用作消息认证码。
此外,使用流密码和公钥密码等也可以实现消息认证码。
HMAC
HMAC 是一种使用单向散列函数来构造消息认证码的方法,其中,HMAC 中的 H 就是 Hash 的意思。HMAC 中所使用的单向散列函数并不仅限于一种,任何高强度的单向散列函数都可以被用于 HMAC,也就是说,HMAC 所使用的单向散列函数是可以被替换的。
HMAC 是按照下列步骤来计算 MAC 值的:
对消息认证码的攻击
对消息认证码可以发起重放攻击,即攻击者可以通过将事先拦截保存的正确 MAC 值不断重放来发动攻击。有几种方法可以防御重放攻击:
另外,除了重放攻击,对消息认证码也可以进行暴力破解和生日攻击,这和对单向散列函数的攻击一样。对消息认证码来说,应保证不能根据 MAC 值推测出通信双方所使用的密钥。例如 HMAC 就是利用单向散列函数的单向性和抗碰撞性来保证无法根据 MAC 值推测出密钥的。
消息认证码无法解决的问题
使用消息认证码可以对消息进行认证并确认完整性,即能够识别出消息的篡改和伪装。但却解决不了“对第三方证明”和“防止否认”。
假如接收者在收到发送者的消息之后,想要向第三方证明这条消息的确是发送者发送的,但是用消息认证码无法进行这样的证明,为什么呢?首先,第三方要校验 MAC 值,就需要知道发送者与接收者之间共享的密钥。但知道密钥后,也校验出 MAC 值是正确的,依然无法证明消息就是发送者发的,因为也有可能是接收者发的。
既然第三方无法做出证明,那么,如果发送者事后否认自己发送过消息,而谎称是接收者自己发送给自己的消息,对于这种情况也是无法证明,即无法防止否认。
后面要讲的数字签名就可以解决这两个问题。
消息认证码之所以无法对第三方证明和防止否认,就是因为发送者和接收者使用了同一个共享密钥。那么,如果发送者和接收者不使用共享密钥,而各自使用不同密钥呢?假如发送者使用的密钥是一个只有自己知道的私钥,在这里可称为“签名密钥”,当发送者发送消息时,用她的签名密钥生成一个“签名”。相对地,接收者使用另一个密钥,称为“验证密钥”,可对签名进行验证。但是,使用验证密钥是无法生成签名的。也就是说,只有签名密钥可以生成签名,而用相应的验证密码可以对该签名进行验证。这种技术就是数字签名(digital signature),也称为电子签名,或简称为签名。另外,签名密钥只能由签名的人持有,而验证密钥则是任何需要验证签名的人都可以持有。
上面讲的内容,和公钥密码很像吧?其实,数字签名就是通过将公钥密码反过来用而实现的。
公钥密码与数字签名
下图是使用公钥加密(即公钥密码)的简单流程图:
而下图则是使用私钥加密(即数字签名)的简单流程图:
那么,为什么用私钥加密就相当于生成签名,而用公钥解密就相当于验证签名呢?这是因为组成密钥对的两个密钥之间存在严密的数学关系,使用公钥加密的密文,只能用与该公钥配对的私钥才能解密;同样地,使用私钥加密的密文,也只能用与该私钥配对的公钥才能解密。也就是说,如果用某个公钥成功解密了密文,那么就能够证明这段密文是用与该公钥配对的私钥进行加密所得到的。用私钥进行加密这一行为只能由持有私钥的人完成,正式基于这一事实,才可以将用私钥加密的密文作为签名来对待。而由于公钥是对外公开的,因此任何人都可以用公钥进行解密,即任何人都能够对签名进行验证。
数字签名的方法
有两种生成和验证数字签名的方法:
我们知道,公钥密码算法本来就非常慢。用这种方法需要对整个消息进行加密,就会非常耗时。因此,在实际应用中,基本不会使用直接对消息签名的方法。
因为散列值比较短,因此对其进行加密签名就会快很多。
数字签名的实现
数字签名的实现也有很多种,基本也是使用单向散列函数和公钥密码技术相结合。而公钥密码部分常用的就是使用RSA,另外也有使用EIGamal、Rabin。还有一种数字签名算法叫DSA(Digital Signature Algorithm)。而使用最广泛的应该就是使用RSA的数字签名了。
使用RSA实现数字签名很简单。而为了更加简单起见,这里不使用单向散列函数,而是直接对消息进行签名。首先,需要将文本的消息先编码为数字,因为在RSA中,被签名的消息、密钥以及最终生成的签名都是以数字形式表示的。接着,使用下列公式生成签名:
D 和 N 就是签名者的私钥。生成签名后,发送者就可以将消息和签名一起发送给接收者了。
而验证签名时则使用下列公式:
E 和 N 就是签名者的公钥。接收者计算出“由签名求得的消息”后,与发送者直接发送过来的“消息”内容进行对比(如果使用了单向散列函数那就是对比消息的散列值)。如果两者一致则签名验证成功,否则签名验证失败。
对数字签名的攻击
因为数字签名结合了单向散列函数和公钥密码,因此,对单向散列函数和公钥密码的攻击也同样对数字签名有效。比如,针对公钥密码的中间人攻击对数字签名来说就颇具威胁。要防止中间人攻击,就需要确认自己所得到的公钥是否真的属于自己的通信对象。而解决此问题的方案也和公钥密码一样,一般可以使用公钥证书。
对单向散列函数的攻击也是对“抗碰撞性”的攻击,使用高强度的单向散列函数就可以增大被破解的难度。
另外,还可以利用数字签名攻击公钥密码。因为对消息签名,从另一方面来说,也是对消息解密。利用这一点,攻击者就可以发动一种巧妙的攻击,即利用数字签名来破译密文。
假设攻击者拦截到发送者发给接收者的密文后将其保存了下来,并给接收者写了一封邮件,谎称自己是密码学研究者,正在进行关于数字签名的实验,请求接收者对附件中的数据进行签名并回复,说附件中的数据只是随机数据,不会造成任何问题。而实际上,附件的数据就是刚才保存下来的密文。如果接收者中计而对附近进行了签名并回复给了攻击者,那攻击者不费吹灰之力就可以破译密文了。
对于这种攻击,应该采取怎样的对策呢?首先,不要直接对消息进行签名,对散列值进行签名比较安全;其次,公钥密码和数字签名最好分别使用不同的密钥对。然而,最重要的就是绝对不要对意思不清楚的消息进行签名,尤其是不要对看起来只是随机数据的消息进行签名。
数字签名无法解决的问题
用数字签名既可以识别出篡改和伪装,还可以防止否认。即是说,数字签名同时实现了确认消息的完整性、进行认证以及否认防止。
然而,数字签名存在和公钥密码一样的问题,那就是公钥问题。公钥必须属于真正的发送者,要确认公钥是否合法,就需要使用证书。这就是后面要讲到的内容了。
无论是公钥密码还是数字签名,都存在需要验证公钥是否合法的问题。而证书,就是用来对公钥合法性提供证明的技术。
公钥证书(Public-Key Certificate,PKC)和驾照类似,一般会记有姓名、组织、邮箱地址等个人信息,以及属于本人的公钥,并由认证机构(Certification Authority、Certifying Authority,CA)施加数字签名。
认证机构就是能够认定“公钥确实属于此人”并能够生成数字签名的个人或组织。认证机构中有国际性组织和政府所设立的组织,也有通过提供认证服务来盈利的一般企业,此外个人也可以成立认证机构哦。世界上最有名的认证机构当属VeriSign公司。
证书的应用场景
通过认证机构使用证书的过程如下图所示:
公钥基础设施(PKI)
公钥基础设施(Public-Key Infrastructure)是为了能够更有效地运用公钥而制定的一系列规范和规格的总称。公钥基础设施一般根据其英语缩写而简称为PKI。PKI只是一个总称,而并非指某一个单独的规范或规格。比如,使用最广泛的 X.509 规范也是PKI的一种。
PKI的组成要素主要有3个:
这三者的关系如下图:
另外,认证机构会有层级的关系,处于最顶层的认证机构一般就称为根CA(Root CA)。上层认证机构可以验证下层认证机构的证书,即是说,下层认证机构的证书是经过上层认证机构签名的。而根CA则会对自己的证书进行签名,这叫自签名。认证机构的层级关系如下图:
当发送者需要对最底层的Bob的数字签名进行验证时,首先从最顶层的根CA开始,然后获得下层的公钥证书,这个证书上面会带有上层的数字签名,因此需要用上层的公钥对数字签名进行验证。这样逐层向下验证,一直验证到最底层的Bob。
对证书的攻击
由于证书使用的就是数字签名技术,因此针对数字签名的所有攻击方法对证书都有效。
另外,在公钥注册之前也可以进行攻击。用户准备在认证机构注册自己的公钥时,攻击者可以把消息拦截,然后将公钥替换成自己的。这样一来,认证机构就会对“接收者的个人信息”和“攻击者的公钥”这个组合进行数字签名。要防止这种攻击,接收者可以在将自己的公钥发送给认证机构进行注册时,使用认证机构的公钥对自己的公钥进行加密。此外,认证机构在确认接收者的身份时,也可以将公钥的指纹(即散列值)一并发送给接收者请他进行确认。
攻击者还可以利用注册相似人名进行攻击。证书是认证机构对公钥及其持有者的信息加上数字签名的产物,对于一些相似的身份信息,计算机可以进行区别,但人类往往很容易认错,而这就可以被用来进行攻击。比如,假设用户信息中名字的部分是:
而攻击者用另一个类似的用户信息注册了另一个不同的公钥:
随后,攻击者伪装成Bob,将 Name = BOB 的公钥发送给通信对象Alice,Alice看到证书中的用户信息,很可能会将BOB误认为是自己要发送消息的对象Bob。
要防止这种攻击,认证机构必须确认证书中所包含的信息是否真的是其持有者的个人信息,当本人身份确认失败时则不向其颁发证书。
攻击者也可以窃取认证机构的私钥,不过认证机构对私钥的保护是非常严密的,所以一般比较难窃取。如果认证机构的私钥泄露了,认证机构就需要将私钥泄露一事通过 CRL 通知用户。CRL(Certificate Revocation List)为证书作废清单,是认证机构宣布作废的证书一览表,具体来说,是一张已作废的证书序列号的清单,并由认证机构加上了数字签名。
利用钻上面提到的 CRL 的空子也可以进行攻击。因为从公钥失效到发送者收到 CRL 需要经过一段时间,攻击者就可以利用这段时间差来发动攻击。
关于证书的 Q&A
其实,如果能够取得可信的公钥,比如通信双方在同一个办公室,很容易取得可信的公钥,这种情况下则不需要认证机构。否则,认证机构和证书的存在就有意义了。当持有可信的认证机构公钥,并相信认证机构所进行的身份确认的情况下,则可以信任该认证机构颁发的证书以及通过该途径取得的公钥。
其实这是错误的。自己开发保密的方法是犯了典型的隐蔽式安全(security by obscurity)错误。私下开发安全相关的技术其实是危险的,仅靠一家公司的力量无法开发出足以抵御攻击的安全技术。这也是为什么 AES 和 RSA 算法要采用公开竞赛的方式,让全世界的安全专家一起来验证这些技术的安全性。
其实,这个问题关系到“信任是如何产生的”这一本质性问题。为什么我们要把钱存进银行呢?认证机构是否让人感到可信,和银行是一样的。
也有不依赖于认证机构的,PGP 软件就是。PGP 是通过信任网的方法来建立每个人之间的信任关系的。下一篇文章再具体讲 PGP。
本篇文章总结了四部分内容:单向散列函数、消息认证码、数字签名和证书。数字签名的安全性最高,既能确保完整性,也能进行认证和防止否认。另外,数字签名也是将单向散列函数和公钥密码技术相结合在了一起。前一篇文章所讲的混合密码系统也是结合了多种技术。其实,实用性的安全产品,都是多种密码技术组合在一起实用的。例如,PGP、SSL\TLS等。下一篇就会讲如何将多种密码技术组合在一起。