HTTPS

安全考虑

Confidentiality

保密性。 防止信息的暴露。

Integrity

完整性。防止信息被篡改。

Authentication

身份认证。 有些攻击者可能修改DNS解析,将URL解析到他们想要的IP地址。 所以,通常需要确保对方拥有它所声称的身份。

Originality

原创性。 第三方可能截获请求信息,之后再去向服务器发请求。 譬如一个下订单的请求,第三方截获后,并不去解密,或是修改,而是将它向服务器反复发送,以达到攻击的目的。 此种攻击行为称为replay attack

Timeliness

时效性。 与replay attack不同,第三方截获后,并不反复发送,而只是延迟请求时间。 譬如一个买入股票的请求,延迟后可能就在一个意想不到的价位入手了。

数字加密

通过加密算法来解决保密性的问题。 这也是解决其它问题的基础。

其基本原理是,发送方通过加密函数,将一段明文(plaintext)转换成密文(ciphertext), 接收方在收到密文后,使用解密函数将密文再转换成明文。 对于不知道解密函数的第三方而言,密文是没有任何意义的。 因此,称这对加密、解密函数为密码(cipher)。 这里将cipher翻译成加密算法(总觉直译为“密码”怪怪的)。

密钥

加密和解密函数通常还需要接收一个密钥(key)做为参数才能正确工作。

传说凯撒曾使用过一种“三字符旋转”(three-character rotation)加密方式, 将消息中的每个字母都用字母表中比它排列靠后三个位置的字母替代。

rot3

这里,加密和解密使用的密钥是3.

由于好的加密算法很有限,不可能大家都使用不同的加密算法。 且一旦暴露,再找替代品也很麻烦。 所以,一般加密算法本身是公开的,只有密钥才是秘密,需要妥善保管。

当然,攻击者可能通过某些手段事先获得了一些信息。 譬如明文的模式,某些明文对应的密文等等。 优秀的加密算法,即使在同时知道明文和密文的条件下,也无法推断出密钥。

这样,攻击者就只剩下穷举法,去遍历密钥的所有可能值。 如果密钥长度是n位,就有2^n种可能,平均需要猜2^n/2次才能猜中。

假设密钥的长度为128位,则一共有约 262,000,000,000,000,000,000,000,000,000,000,000,000 种可能。

对于目前的计算机而言,在合理的时间内是无法完成破解的。

crack-keys

当然,密钥越长,加密和解密耗时就越多。 所以密钥长度和加密性能间存在一个trade-off。

字母旋转这样的加密方式,其密钥数量一共只有25种(密钥为0就不会修改明文),平均尝试13次就能破解掉。 加强版的(monoalphabetic ciphers)可以对字母使用一个双射进行任意替换, 这样的双射一共有26!种(包括不做任何变动),在10^26量级,穷举的话就不太现实了。

对称加密与非对称加密

如果加密函数与解密函数使用使用同样的密钥,则称为对称加密,否则称为非对称加密。

对称加密时,发送方用加密函数和密钥加密,接收方用解密函数和同一个密钥解密。

在非对称加密中,双方均产生了一对密钥:公钥和私钥。 公钥会公布出去,私钥则当作秘密保管。 发送方在发送消息时,用接收方的公钥进行加密,接收方在收到密文后,便可用自己的私钥进行解密。

对称加密算法有DES系列。非对称算法有RSA等。

理论上可以通过大数因式分解来破解RSA,其复杂度比穷举要快。 因此,一般来说非对称加密要求的密钥长度更大(至少1024位)。 密钥长度大,加密解密速度相对对称加密而言就慢一些。

对称加密中,N个人之间通信,需要两两均确定一个密钥,密钥数量为N*(N-1)/2,每个节点需要保管N-1个密钥。 在非对称加密中,N个人一共只产生了2N个密钥,且每个节点只需要保管一个私钥。

软件实现时,对称加密比RSA快至少100倍,硬件实现时可快100到10000倍。 所以非对称加密一般用来进行认证和创建会话密钥。

在发送数据时,发送方选生成一个密钥用于对称加密,称之为会话密钥。 再使用接收方的公钥对会话密钥进行加密,然后将它发送给接收方,确保会话密钥不被窃取。 之后便可以用这个会话密钥开始对数据进行对称加密了。

认证

认证,即能验证某则消息确实来源于某个发送方。

加密本身并不能确保数据的完整性,第三方还是可以篡改消息内容,接收方解密出来后无法判断内容是否被修改过。 当消息可能被篡改时,说消息来源于某个发送方没有什么意义。 所以,确定消息来源于某个发送方,也就意味着需要验证数据的完整性。

加密哈希函数

加密哈希函数(cryptographic hash function),可将任意长度的消息映射成一段固定长度的消息摘要(message digest)。 与校验和类似,将消息摘要置于消息体后,便可用来检验消息是否有被意外修改。

由于加密哈希函数将任意长度的消息映射成固定长度的摘要, 本质是将一个无穷空间映射到一个有限空间, 所以存在将不同消息映射成同样的摘要的可能。 因此,第三方可以截获消息后,利用哈希加密函数得到摘要, 再去寻找一则与原消息拥有同样摘要的消息,将新消息发给接收方, 接收方将无法察觉到这样的变动。 故而为了安全起见,要求使用的加密哈希函数有单向性, 即可以方便算出摘要,但从摘要找到可生成它的消息则不太现实。

比较常见的加密哈希函数有MD5SHA-1等。

消息认证码

但由于加密哈希函数并不是什么秘密,所以第三方截获消息后,可以修改完内容,再生成一份摘要,接收方无法辨别。 所以,单独用加密哈希函数是无法对付恶意篡改者的。

发送方在生成摘要时,输入除消息外还可加上密钥(authentication key),这样第三方就无法生成正确的摘要了。 这个摘要便称为消息认证码(message authentication code),能起到身份认证的作用。

mac-principle

以上就是MAC的工作原理。 并未涉及到加密,所以速度较快。

改进版的HMAC可以结合MD5SHA-1使用。

在认证时需要用到密钥,那如何安全地将这个密钥传给接收方? 可以使用接收方的公钥进行一次加密再进行传输。

数字签名

数字签名的目的便是验证当前收到的消息是否来自某某,是否有被篡改。 它使用公钥加密来实现。

下面看一个使用RSA来进行数字签名的例子。

digital-signature-encrypt

digital-signature-decrypt

之所以要引入哈希,是因为公钥加密速度太慢,使用哈希将内容压缩成很短后,可以较快加密。

公钥认证

有了数字签名机制,数字证书便很容易实现了。

身份证之所以能证明你的身份,是因为大家相信身份证的颁发机构,以及相信身份证难以造假。

数字证书证明的是公钥的正确归属,需要权威机构做担保。 证书分为两部分内容,一部分是信息描述,其中包含公钥。 第二部分是权威机构的签名,即用它的私钥针对第一部分内容生成的一个数字签名

digital certificate

网站需要向CA申请对应域名的数字证书,CA会留下自己的数字签名。 浏览器在与网站通信时,先下载它的证书,检查是哪个CA签发的,再找出对应CA的公钥,如同数字签名中描述的那样进行验证。

digital certificate verifying

HTTPS协议

参考

相关

附录

穷举法平均尝试次数

假设密钥数量为n,当前有明文M和对应的密文c, 则用穷举法将c解密成M需要尝试的次数平均为n/2。 假定密钥生成算法是完全随机的。

证明

将密钥从1到n进行编号,则加密中使用的密钥,其编号为k的概率均为1/n。 故:

期望值为n/2 + 1/2 - 1/n

总结起来:

Polyalphabetic ciper

对于monoalphabetic cipher, 如果攻击者事先知道某些信息,可能就会使破解难度大大降低。

For example, if Trudy the intruder is Bob’s wife and suspects Bob of having an affair with Alice, then she might suspect that the names “bob” and “alice” appear in the text. If Trudy knew for certain that those two names appeared in the ciphertext and had a copy of the example ciphertext message above, then she could immediately determine seven of the 26 letter pairings, requiring 10^9 fewer possibilities to be checked by a brute-force method. Indeed, if Trudy suspected Bob of having an affair, she might well expect to find some other choice words in the message as well.

cipher-text-only attack

攻击者只能拿到密文。

known-plaintext attack

攻击者有部分明文及其对应的密文。

chosen-plaintext attack

攻击者可能选择一段明文,并获得其对应的密文,从而将密钥破解。 譬如前面的字母变换加密方法,攻击都如果能取得以下明文对应的密文,立即就能破解密钥。

The quick brown fox jumps over the lazy dog

针对以上情况,可以使用多个monoalphabetic cipher来进行加密。 譬如有C1, C2两个monoalphabetic,可以考虑使用C1, C2, C2, C1, C2这样的序列来加密。 即第1个字符用C1,第2,3个字符用C2,第4个字符用C1,第5个字符用C2,从第6个字符开始又用C1,进行循环。

这种加密方法(polyaphabetic encryption)可使同样的字母在不同位置时编码会不一样。

对称加密

对称加密可分为两类:

block ciphers

DES即一种block cipher

将原消息拆分为固定大小的块再逐块加密。

假定块大小为3位,则块的可能性共有2^3种。 这个块的集合一共有2^3!种双射映射到自身。 每一种映射即一个密钥,故一共有2^3! = 40320个密钥。

譬如,假设选取以下映射(密钥):

输入 输出 输入 输出
000 110 100 011
001 111 101 010
010 101 110 000
011 100 111 001

可以将010110001111加密成101000111001

如果块大小为64,将会有2^64!种密钥,很难穷举。 但同时,存储密钥时需要至少存储2^64个输入值。 所以,直接存储映射表是不可行的。

为此,可以使用函数来模拟映射表。

block cipher

每个密钥决定了算法内部的这些变换。

Observe that with a key length of n, there are 2n possible keys. NIST [NIST 2001] estimates that a machine that could crack 56-bit DES in one second (that is, try all 256 keys in one second) would take approx- imately 149 trillion years to crack a 128-bit AES key.

stream ciphers

非对称加密

RSA是公钥加密,包括两部分:

生成公钥私钥对

加密与解密

Bob发送消息给Alice的过程如下:

encode

decode

工作原理

给定

encode

需要证明

decode

证明

(ab) mod n = (a mod n)(b mod n) mod n

可得

(c^d) mod n = ((m^e) mod n)^d mod n = (m^(ed)) mod n

所以,需要证明的等式转化成

m = (m^(ed)) mod n

这里需要用到如下结论:

p, q is prime
n = pq
z = (p - 1)(q - 1)

then
(x^y) mod n = (x^(y mod z)) mod n

根据上面的结论,所需要证明的等式被进一步转化成:

m = (m^(ed)) mod n = (m^(ed mod z)) mod n

上述等式之所以成立,是因为我们在生成ed时,保证了ed - 1可被z整除,即(ed) mod z = 1

可见,RSA依赖的基本原理是,可以找到三个大整数e, d, n,对于任意的整数m,下面的等式都成立:

rsa-1

上式左边的运算称为模幂,它有log(ed)级别的解法。 在这里它最有用的特点就是,即使知道了e, n, m,也很难计算出d

上面等式中ed是可交换的,即

rsa-2

这就是解密的工作原理。

破解复杂度

假定攻击者拿到了公钥,即知道了ne,考虑能否解出d

由于(ed) mod z = 1,要得到d,必须知道z,但其值是保密的,只能推断。 由z = (p − 1)(q − 1)可知,如果知道pq,便可得到z。 由于n = pq,可以对n进行因式分解得到pq。 正是因为这个因式分解的难度很大,才使得RSA难以破解。 当n很大时(如1024位),可以认为无解。目前已知能破解的最大长度为768位。