公钥加密

公开密钥加密(public-key cryptography),也称为非对称加密(asymmetric cryptography)。在这种方法中,需要一对密钥,一个是私钥,另一个是公钥。这两个密钥是数学相关,用某用户密钥加密后所得的信息,只能用该用户的解密密钥才能解密。如果知道了其中一个,并不能计算出另外一个。因此如果公开了一对密钥中的一个,并不会危害到另外一个的秘密性质。称公开的密钥为公钥;不公开的密钥为私钥。

最早公开的公钥加密算法,也同时是至今依然最常用的就是 RSA。

事实上有三类算法和公钥加密相关,一个是前面说到的密钥交换算法,二个就是 RSA 这种加密算法,三个是数字签名算法。

为什么一直使用 RSA 来加密,还一定要使用前面提到的 AES 之类的对称密钥加密?是因为 RSA 比 AES 之类的对称密钥加密,要慢上几百上千倍。

RSA

首先随机选择两个大质数 $p$ 和 $q$,然后把他们相乘,得到 $N$,这个是可以公开的。然后再选择一个加密指数 $e$,这个通常是 3 或者 65537,这个指数是公开的。然后 $(N, e)$ 组合就是公钥。使用公钥将明文 M 加密成密文 C 过程如下:

$$C \equiv M^e \; (\bmod N)$$

对于解密的过程,你需要一个解密指数 $d$。利用 $p$ 和 $q$ 很容易计算出 $d$。这个过程涉及到一定的数学理论。解密过程如下:

$$M \equiv C^d \; (\bmod N)$$

RSA 的安全性建立在 $d$ 很难被逆向计算出来。

对于 RSA 的攻击,从理论上而言,由于尚未发现多项式时间里能够分解质因数的方法,所以还是安全的。但是量子计算机的出现,增加了从量子算法上破解 RSA 的可能。目前常见的破解方式还是实现上。比如 Python 的一个叫 Salt 的库,由于使用加密指数 $e$ 为 1,就导致了 $C = M$ 的情况。

目前通过暴力的方式破解 RSA 达到了 768 位,大大威胁了 1024 bit 密钥的安全性。所以目前推荐密钥至少要有 2048 位。

Diffie-Hellman 密钥交换

在前一篇流加密里面介绍到,加密解密的双方需要有一个 key,需要保证不能泄露这个 key。那么双方要如何在不泄露的情况下都知道这个 key 呢。

Diffie-Hellman 密钥交换算法就是为了解决,通信双方,在一个不安全的通信环境里,在双方互相不认识的情况下,最终能协商出一个只有双方知道的值。

在这里恭喜 Diffie 和 Hellman 两人,前两天刚凭借这个密钥交换算法获得了 2015 年度的图灵奖。

Diffie-Hellman 最核心的思想就是利用某些某个方向计算很容易,但是反反向计算非常难的数学。

数学解释

首先,对于 $y \equiv g^x \quad (\bmod p)$ 这个等式中,知道 g、x、p 是很容易计算出 y 来的。但是知道 y、g、p 的情况下,算出 x 来却十分困难。所以,利用这个等式,我们就可以构建一个密钥协商的过程。

首先,通信的双方 Alice 和 Bob 分别选择一个随机数 $r_A$ 和 $r_B$,然后分别计算他们自己的:

$$ m_A = g^{r_A} \quad (\bmod p)$$

$$ m_B = g^{r_B} \quad (\bmod p)$$

然后 Alice 和 Bob 分别把自己算出来的 $m_A$ 和 $m_B$ 发送给对方。在这个发送的过程中,所有的通信数据都可以被 Eve 看到。所以 Eve 是知道 $m_A$ 和 $m_B$ 的。但是由于反方向计算十分困难,所以 Eve 无法反推出 $r_A$ 和 $r_B$。

Alice 和 Bob 分别接收到对方的 $m_B$ 和 $m_A$ 后。在对方发过来的数据的基础上,带入自己的随机数,例如对于 Bob 会计算:

$$ S = (g^{r_A}) ^ {r_B} \quad (\bmod p) $$

对于 Alice 会计算:

$$ S = (g^{r_B}) ^ {r_A} \quad (\bmod p) $$

尽管计算顺序不一样,但是最后的结果是一样的,$(g^{r_B}) ^ {r_A} \quad (\bmod p) = (g^{r_A}) ^ {r_B} \quad (\bmod p)$。这个 S 就是最后协商的密钥。

椭圆曲线

Diffie-Hellman 还可以利用椭圆曲线(Elliptic curve),就是所说的 ECDH。

椭圆曲线密码学(ECC),基于椭圆曲线数学,作为程序员的我并不能看懂。

ECC 相比较而言的优势在于获得相同的安全性的时候,相对于上面的基于离散对数的方式,所需要的 key 的长度更小,所以计算速度会更快。

中间人攻击

Diffie-Hellman 算法并不能识别交换双方的身份。所以在交换密钥的过程中,可能会被中间人攻击。比如 Mallory 在 Alice 和 Bob 中间,分别和 Alice、Bob 进行密钥交换,那么 Mallory 还是可以分别得到两个人的 key。

为了解决这个问题,需要引入证书体系,将在后面介绍。

流加密

流加密(Stream Cipher)是对称密钥加密算法的一种,用来加密比特流。

流加密算法有两种,一种是利用块加密算法,利用某种工作模式,加密比特流;另一种从设计就是为了比特流考虑的算法。

ECB 模式

利用前一篇里面的块加密算法,很容易构想出一个原始简单的流加密算法。就是把比特流分割成一个个的具有块大小的数据块,然后对每一块分别使用块加密算法进行加密。

这种方式叫做 ECB(Electronic Code Book mode) 模式。这种加密模式最大的问题是相同的原明文块会被转变成相同的加密块。

CBC 模式

CBC 模式,Cipher Block Chining。CBC 模式就是明文数据块在加密之前会和前一个加密过得到的密文块进行异或运算。这个模式的问题是第一个明文块,没有前一个加密块。所以要引入一个 IV(Initialization Vector),初始化向量作为最初的加密块使用。IV 必须随机,不可预测,但没必要加密,重要的是不可预测。

CBC_encryption

CBC_decryption.png

与 CBC 模式很相似的模式还有 CFB 和 OFB 模式。

CBC 模式下基于可预测 IV 的攻击

在 AES 系统中,IV 通常都是可以从密文 C 中读到的。

一种常用的 AESCipher 的 Python 实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import base64
from Crypto.Cipher import AES
from Crypto import Random
class AESCipher:
def __init__( self, key ):
self.key = key
def encrypt( self, raw ):
raw = pad(raw)
iv = Random.new().read( AES.block_size )
cipher = AES.new( self.key, AES.MODE_CBC, iv )
return base64.b64encode( iv + cipher.encrypt( raw ) )
def decrypt( self, enc ):
enc = base64.b64decode(enc)
iv = enc[:16]
cipher = AES.new(self.key, AES.MODE_CBC, iv )
return unpad(cipher.decrypt( enc[16:] ))

其中 IV 都是可以直接知道的。但是 IV 可知并不是什么问题,主要的问题是,IV 要不可被预知。

假设某条加密过的数据 $C_1$ 的 IV 是 $IV_a$ 可知,针对我们即将输入进去的数据的 IV 我们可预知,即 $IV_m$,我们可构造明文数据 $P_m = IV_m \oplus IV_a \oplus G$,其中,G 是我们猜测的 C1 的原文。

然后由

$$
C_m = E(k, IV_m \oplus P_m) \
= E(k, IV_m \oplus(IV_m \oplus IV_a \oplus G)) \
= E(k, IV_a \oplus G)
$$

这里通过比较 $C_m$ 和 $C_1$,可以验证对于 $C_1$ 猜测的原文 G 是否正确。

CBC 模式下把 key 用作 IV 的攻击

把 key 用作 IV 是不安全的。

假设 Alice 的明文 P 包含三个 block,分别为 $P_1 P_2 P_3$,在 CBC 模式下用 key 加密,并且 IV 也是 key。得到的密文 C 为 $C_1 C_2 C_3$ 发送给了 Bob。

在 Bob 接收到密文之前,Mallory 截获了密文。然后把密文篡改成 $C^{‘} = C_1ZC_1$,其中 Z 是全 0 的一个块。当 Bob 接收到被篡改过的密文并解密 $C^{‘}$ 之后,得到三个明文串 $P^{‘}_1$、$P^{‘}_2$ 和 $P^{‘}_3$。

$$P^{‘}_1 = D(k, C_1) \oplus IV = D(k, C_1) \oplus k = P_1 $$

$$P^{‘}_2 = D(k, Z) \oplus C_1 = R$$

$$P^{‘}_3 = D(k, C_1) \oplus Z = D(k, C_1) = P_1 \oplus IV$$

其中 R 是一个无所谓的串。

到此,Mallory 在得知 $P^{‘}_1$、$P^{‘}_2$ 和 $P^{‘}_3$ 的情况下,就可以推算出 IV,由于 key 就是 IV,所以就推算出了 key。

到这里我有个疑惑,Mallory 是怎么得知 $P^{‘}_1$、$P^{‘}_2$ 和 $P^{‘}_3$。然后发现书中这样的一句话 “Under the chosen-ciphertext attack assumption”。这句话的意思是,攻击者可以通过给定某一个特定的密文 C 给解密者并且获得对应解密后的明文结果。通常是利用解密端软件的某些 bug 或者漏洞。所以这里 Mallory 是可以拿到对应的 $P^{‘}_1$、$P^{‘}_2$ 和 $P^{‘}_3$ 的。所以说,这种漏洞的利用还是比较难的。

Padding

Padding 就是填充的意思。

在 CBC 模式下,假设了每个加密块都是块加密算法的 block size 大小。但事实上,真正的数据流的长度是不定的。那么对于最后一块数据,长度不足一个 block 时候,就需要在末尾填充一些其他数据来满足长度要求。这个就是 Padding。

最简单的思维是,填充某个固定的字节,例如 0。问题是,无法区分填充字节和原来的数据。

更好,更常用的方法是 PKCS#5/PKCS#7。基本思想是,对于后面少几个字节,就把几全部填充进去。例如一个 8 个字节的 block,原始数据是 12 34 45,差 5 个字节。那么就填充成 12 34 45 05 05 05 05 05。当某个数据刚好是 block 的整数倍,不需要填充时,则在最后面填充一整个 block。

CBC Padding attack

使用 Padding attack 只需要两点,一段需要解密的密文 $C_i$,和一个可以响应 Padding 是否合法的目标程序。这里假设填充方法是上面说的 PKCS#5/PKCS#7。

首先攻击者构造一个随机串 $R = r_1,r_2,r_3…r_b$。然后,攻击者不停的尝试随机串 $R$ 的最后一个字符 $r_b$,目的是得到一个填充合法的结果。最差的情况是使得最后的明文串 $P_i$ 的最后一位 $P_b$ 是 01。根据上述 PKCS 的填充原理,01 必然是一个合法的填充结果。

CBC_Padding_attack.png

这时我们得到填充合法的结果,我们有此时的随机串 $R$。但是并不知道填充的位数。但是可以知道的是,$P_i$ 的末尾必然是

  • $01$
  • $02\ 02$
  • $03\ 03\ 03$
  • … 这些情况。

当然,从概率上而言,结尾是 $01$ 的可能性最大。

这里,我们假设最后的明文 $P_i = p_0p_1p_2p_3p_4030303$,其中 $p_0p_1p_2p_3p_4$ 是什么并不会影响我们进行填充正确性的检验。

所以我们从 $r_0$ 开始尝试变动,这样会导致最后的 $P_i = p^{‘}_0p_1p_2p_3p_4030303$。但是这样并不会影响我们进行填充正确性的检验。所以我们可以继续变动下一位 $r_1$,这样一直下去,直到填充正确性检验失败,我们就可以知道有多少位的填充 padding。从实际工作角度,我们或许没必要猜测是几位。我们就假定末尾是 01。当填充正确性检验通过的时候,我们不知道最后实际是几位,但是我们只需要变动一下倒数第二位,一旦校验失败,则说明 Padding 一定不是 01,这时我们不管他,继续尝试 $r_0$,直到能说明 Pading 是 01 为止。

接下来,我们假设最后的填充是 $01$,这是最坏的情况。

那么就有 $D(C_i)[b] \oplus r_b = 01$,这样我们可以计算出 $D(C_i)[b]$,即$C_i$被算法 D 解密之后的中间结果的最后一位。要注意这个中间结果,我们做这么多,目的就是这个中间结果,这个中间结果是不会变动的。

接下来我们去尝试倒数第二位。首先,根据上面的等式,我们可以推出 $D(C_i)[b] \oplus r_b \oplus 01 \oplus 02 = 01 \oplus 01 \oplus 02 = 02$,也就是让 $r_b = r_b \oplus 01 \oplus 02$,这时最后的填充位就变成了 02,这样,我们去暴力尝试 R 的倒数第二位,使得最后填充检验通过。这时,我们就可以得到$D(C_i)[b-1]$,也就是这个中间结果的倒数第二位。不断重复这个过程,我们可以得到整个中间结果串 $D(C_i)$。

这时,我们拿出密文 $Ci$ 的前一个密文串 $C{i-1}$,根据 CBC 的工作模式,这里 $C_{i-1} \oplus C_i = P_i$。就这样,我们得到了解密后的结果 $P_i$。然后重复整个过程,我们可以解出所有的明文,除了第一块,因为我们不知道 IV。

RC4

RC4,十分简单,但是已经被攻破。而且很快,13.9 cycles/bit。AES-128 CTR 模式是 12.6 cycles/bit,CBC 模式是 16 cycles/bit。

Salsa20

Salsa20 是一种新的流加密算法。目前有两个版本,Salsa20/12 和 Salsa20/8。其中 12 和 8 表示循环次数,从原始的 20 降下来。与 Salsa20 相似的还有 ChaCha。

Salsa20 和 ChaCha 都非常快。

Salsa20 有个特点就是可以从任意一段进行加密解密。意味着算法可以并行。

CTR 模式

CTR 模式,也叫 counter 模式。

工作流程很简单,一个初始化的随机数 N,然后 N 和一个计数器连起来。和 key 加密后产生 key stream 再和明文 P 异或产生密文 C。每加密一块后计数器就加一。循环往复。

CTR_encryption.png

CTR_decryption.png

和 Salsa20 一样,可以从任意一段开始,也就是可以并行。

Crypto101 是作为非数学专业,入门现代密码学不错的学习资料。本阅读笔记系列主要以一个程序员的视角来看待现代密码学。Crypto101 原文可以从官网下载到 www.crypto101.io

异或

异或$\oplus$操作是密码学中非常重要的一个运算。

基本运算规则如下:

1
2
3
4
00=0
10=1
01=1
11=0

通过以上可以推出一些常用的其他规律:

  1. 异或运算可以任何顺序 $a \oplus b = b \oplus a$,即交换律
  2. 自己异或自己都是 0
  3. 任何比特异或 0 的结果都还是自己

通过上述规律,可以推导出 $a \oplus b \oplus a = b$。通过这个原则,可以认为 a 异或 b 是加密过程,再异或 a 就是解密过程。

完美的加密模式是,明文的每个比特都和一个真随机的比特 key 进行异或。但是这样缺点也很明显,key 会和明文一样长。

块加密

块加密(Block Cipher)即分组加密算法,允许对固定长度的块进行加密。

它使用加密函数 E,通过密钥 k 可以使得明文 P 变成密文 C:

$$ C = E(k, P) $$

明文和密文都是字节序列,这两者通常都拥有相同的长度,并且是被块加密算法规定好的一个长度,叫做块大小(block size)。所有可能的 key 被称为 keyspace,即键空间。

解密的过程相反,使用解密函数 D,通过和上面加密时一样的密钥 k 和密文 C,可以获得明文 P:

$$ P = D(k, C) $$

目前最常用的块加密算法是 AES。

本周末花了点时间阅读了一下 shadowsocks 2.8.1 版和 shadowsocks-go 1.1.4 版的源码。

原本工作原理是知道的,这里通过阅读源码,增加了对 eventloop 的网络模型和 Go 语言的 goroutine 模型的认知。两者比较起来,Python 版代码不记测试共计 4000 余行,Go 版本包括测试一共才 2000 多行代码。当然,主要原因是 Go 版本功能要少一点,比如 UDP 的支持,和 TCP Fast Open 特性支持。从理解上而言,Go 版本要远远好于 Python 版本。

基本原理

shadowsocks 的基本工作原理并不复杂。shadowsocks 包括 local 和 server 两个程序。local 运行在用户自己的机器上,server 运行在墙外的服务器上。正常工作模式下,local 通常会监听本地 1080 端口,提供 socks v5 协议接口。在用户本机进程和 local 的 1080 端口建立 TCP 连接之后,首先会发送一个 hello 包,或者叫 handshake 握手包。local 程序接收到这个包之后,进行简单的包数据检查之后就返回一个确认包。本机进程收到确认的包之后,会再发送一个请求包,包的主要内容就是目标服务的地址和端口号。local 程序接收到请求包之后,会和 server 程序建立一个 TCP 连接,连接建立之后会把上面的目标服务的地址和端口号传给 server。这个连接是穿墙的关键,连接里面传输的数据都是经过加密的,最常用的就是 aes-256-cfb。local 程序会对请求包返回一个确认的包。然后本机进程就开始向 local 传输实际的数据,local 接收到之后加密继续传给 server。server 接收到之后把数据解密出来,然后和目标服务建立 TCP 连接,并把解密后的数据发送出去。然后接收数据就是上述的反过来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
great firewall
+
|
|
+----------+ | +-----------+
| | | | |
socks5 | local | encryption | server | raw data
<------------> 1080 | | <-----------+----------> | | <----------->
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
+----------+ | +-----------+
|
|
|
+

为了理解以上内容,强烈建议阅读一下 socks v5 协议的 RFC 1928。不长,一共才 9 页,定义的包格式也很少。

shadowsocks

shadowsocks Python 版本主要包括 Eventloop、TCPRelay、UDPRelay 和 DNSResolver 这几个模块。我们主要介绍 TCP 的模式,UDP 不做过多介绍。

shadowsocks 主要的工作流程就是先进行配置处理,然后针对每个需要监听的端口建立一个 TCPRelay 和 UDPRelay,并添加到 eventloop 里。然后启动 eventloop 的循环。当 eventloop 接收到事件时,将事件分发,调用对应的 handle_event 进行处理。对于每个建立的客户端发起的 TCP 连接,都会新建一个 TCPRelayHandler 进行处理。

在这里,local 和 server 使用的是同一个 TCPRelay 类,他们的处理流程都统一了起来。但是就是因为如此,代码的理解上反而显的不是那么清晰。

Eventloop

shadowsocks 最早期的版本是基于线程的模型处理并发连接的。由于种种原因,线程模型在频繁建立连接、高并发的情况下效率并不高。现在的版本是基于 eventloop 的处理模型。shadowsocks 里使用的 eventloop 是基于 epoll 模型的封装,把 select 和 kqueue 都封装成了 epoll 模型的接口。

eventloop 最重要的方法 run 里的逻辑,就是典型的 epoll 处理方式。这里强烈建议去理解一下 epoll 的工作模型。这里很简单,接收到 event 之后,调用对应的 handle_event 方法进行处理。

TCPRelay

TCPRelay 里有个概念就是 _server_socket,表示的是监听端口的 socket。然后看 TCPRelay 的 handle_event 逻辑就分为了两块,如果是 _server_socket,那么就只有客户端请求建立连接的事件,_server_socket 负责 accept 之后创建新的 TCPRelayHandler;如果不是,那么说明是客户端连接的读写事件,直接分发到对应的 TCPRelayHandler 调用 handle_event 进行处理。

tcprelay.py 这个文件最上方,有一段注释是描述的客户端连接建立的全部过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# as sslocal:
# stage 0 SOCKS hello received from local, send hello to local
# stage 1 addr received from local, query DNS for remote
# stage 2 UDP assoc
# stage 3 DNS resolved, connect to remote
# stage 4 still connecting, more data from local received
# stage 5 remote connected, piping local and remote
# as ssserver:
# stage 0 just jump to stage 1
# stage 1 addr received from local, query DNS for remote
# stage 3 DNS resolved, connect to remote
# stage 4 still connecting, more data from local received
# stage 5 remote connected, piping local and remote

在 TCPRelayHandler 里,就是按照如下定义的 stage 的流程运行的。

1
2
3
4
5
6
7
STAGE_INIT = 0
STAGE_ADDR = 1
STAGE_UDP_ASSOC = 2
STAGE_DNS = 3
STAGE_CONNECTING = 4
STAGE_STREAM = 5
STAGE_DESTROYED = -1

先看 handle_event,里面的逻辑分成了 remote_sock 和 local_sock 两部分。先从 local_sock 开始。从客户端建立 TCP 连接之后,TCPRelayHandler 创建的时候,local_sock 就存在了,由于是客户端主动建立的连接,数据也都是客户端先发起的,所以先从 local_sock 的可读事件开始。记住,我们目前处于 STAGE_INIT 状态。在进入_on_local_read之后,紧守着is_local_stage两个变量,就可以按照上面基本原理里面说的工作流程,将状态机运行起来了。

eventloop 模型比较让人讨厌的就是要不停的循环,然后进入各自的 handle_event 里去思考流程,比较麻烦。

shadowsocks-go

我们再来看看 Go 语言版本基于 goroutine 协程模型。

Go 语言版本的 local 和 server 也是十分相似的。

以 local 程序开始介绍。从 main 开始,处理各种配置的问题;然后到 run 运行起来,建立服务端的 socket,监听端口,循环接收来自客户端的连接请求;然后调用 handleConnection,并建立 goroutine,处理该连接的所有逻辑;在 handleConnection 里,所有逻辑就十分的简单了,全部是同步的方式,从上到下,一步一步的,最后建立上行和下行的两个 PipeThenClose。

main 就没什么好说的了,就是初始化配置,各种参数检查,然后跳到 run 开始运行。run 里面最主要的就是一个 for 的无限循环,不停的 accept 连接,然后 go handleConnection(conn) 开启新的 goroutine 协程并发的执行。

handleConnection 的逻辑分为 4 块。第一块就是到 handShake,无非就是按照 socks v5 协议要求接收一个包,返回一个包。第二块是到 getRequest,这里也是按照 socks v5 协议要求,接收一个包,这个包里主要的内容就是目标服务的地址和端口号。第三块是到 createServerConn,这里返回的 remote 是一个和远端的 server 建立的连接,是一个 ss.Conn 的类型,这个 Conn 类型是在标准库 net.Conn interface 的基础上进行的封装,实现了 Read 和 Write 接口。自己实现的 Read 接口会从 src 读数据之后并解密后返回,Write 接口会把数据加密后写入到 socket 中。最后第四块就是两个 PipeThenClose,自己这个 goroutine 和新开启的 goroutine 并发的从本地到远端、远端到本地的上下行的数据传输。

server 的执行流程和上述也是一样的,main 里面处理配置之后到 run 开始执行。run 里面无限循环接收请求,建立连接,然后go handleConnection(ss.NewConn(conn, cipher.Copy())) 开启新的 goroutine。需要注意的是这里传入的是 ss.Conn 类型的客户端连接,他的 Read 和 Write 接口是有解密和加密的逻辑的。handleConnection 方法的逻辑也十分相似了,除了没有第一步的握手阶段。

总结

总得看来,shadowsocks 并不复杂。Python 版本的 eventloop 和 Go 版本的 goroutine,两种模型相比较,个人觉得 goroutine 明显更加容易理解。

在理解上述内容之前,需要读者对于 socket 编程、epoll 模型、socks v5 的协议内容和 Go 语言要有一定的了解。