A Survey of RSA Padding Oracle Attack

本文章主要梳理了一下RSA Padding Oracle相关的攻击，主要是按照时间线从paper角度去整理的，记录了一些看paper和审代码的笔记。

Timeline

The Interval Oracle Attack (RSA parity oracle attack)

Bleichenbachor’s Attack

(1998) Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1
(2003) Klima-Pokorny-Rosa extension of Bleichbacher’s attack on PKCS #1 v1.5 padding
(2012) Bleichenbacher’s Attack Strikes Again- Breaking PKCS#1 v1.5 in XML Encryption
(2014) Revisiting SSL/TLS Implementations: New Bleichenbacher Side Channels and Attacks
(2018) 20 years of Bleichenbacher’s attack
(2018) Return Of Bleichenbacher’s Oracle Threat (ROBOT)
(2019) The 9 Lives of Bleichenbacher’s CAT: New Cache ATtacks on TLS Implementations

Countermeasure agianst Bleichenbachor’s Attack: OAEP => Manger’s Attack

Papers

(1998) Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1

这就是最开始那篇开天辟地的paper (Seminal paper)。

PKCS#1-conforming plaintext

开头2字节是0x00, 0x02
接下来至少8字节不是0x00
直到遇到了一个0x00字节，则把剩余字节作为message/data payload

Chosen-Ciphertext Attacks

RSA向来就很容易受到选择密文攻击，这主要是因为RSA在乘法上具有同态特性。

对于一个密文$c$，攻击者想要对其解密，即得到$m \equiv c^d \pmod{n}$，攻击者可以随机选取一个$s$，并寻求$c’ \equiv s^e c \pmod{n}$的解密结果$m’ \equiv c’^d \equiv (s^ec)^d \equiv s m \pmod{n}$，从而可以很轻松的得到$m \equiv m’s^{-1} \pmod{n}$。

在这篇文章中，假设存在一个oracle，能够解密任何攻击者提供的密文，并告诉攻击者解密结果是否是PKCS#1-conforming plaintext，即是否符合PKCS#1填充方案。攻击者可以利用这个oracle来在没有私钥的情况下实现RSA的解密运算。从而可以(1)解密任意密文(2)伪造合法签名

所有PKCS#1-conforming plaintext都满足 $$ 2B <= m \pmod{n} < 3B, B = 2^{8(k-2)} $$ 攻击者可以发送任意选取$s$，发送$c’ \equiv cs^e \pmod{n}$给服务端，并得到解密结果$ms$是否是PKCS#1-conforming plaintext，从而可以缩小$m$的取值范围。继续这么操作，可以不断地缩小$m$的取值范围，直至最后取值区间大小变为1，得到精确的$m$的值。

具体的操作如下所示，主要是一些数学相关的技巧：

那么这种攻击需要交互多少次才能成功呢？

一个任意选取的$ms$，前2字节为0x00, 0x02的概率为$Pr(A) = \frac{B}{n}$，其具体取值要看模数$n$的大小 $$ 2^{-16} < Pr(A) < 2^{-8} $$ 在开头两字节符合条件的情况下，后续padding string至少有8字节以及一个0x00字节的概率为 $$ Pr(P|A) = (\frac{255}{256})^8 \cdot (1 - (\frac{255}{256})^{k-10}) $$

然后一堆计算，最后算出来想要完成整个攻击，一共需要大约$3/Pr(P) + 16k/Pr(P|A)$次选择密文，在$k=128$时，大概需要$2^{20}$次交互。

SSL3.0中存在对应的攻击场景，具体内容在后续源码分析部分。

(2003) Attacking RSA-based Sessions in SSL/TLS

Overview

场景：SSL/TLS协议握手过程中，在对使用PKCS#1填充方式的RSA解密结果作处理时，会从中提取部分内容作版本号检查，版本号检查的结果能够被作为侧信道来泄露相关信息，攻击者可以利用泄露的信息来通过Bleichenbachor’s Attack解密任意明文或者伪造签名。

危害：

recover the premaster-secret, thus decrypting a captured RSA-based session
sign(forge) a message on behalf of the server

贡献：

introduce the concept of a bad-version oracle
present several methods that speed up the original algorithm
propose and discuss countermeasures

Bad-version Oracle (BVO)

S-PKCS-conforming plaintext

符合[PKCS#1的填充方案](#PKCS#1-conforming plaintext)
第3～k-49字节都不为0x00 （padding string）
第k-48字节为0x00
最后48字节为premaster-secret

k为模数所占的字节数，1024-bit的模数对应k=128

版本号检查

48bytes的premaster secret前2字节会被用来做版本号检查，以防止version rollback attacks 。

问题在于：如果解密后的结果符合PKCS#1填充方案，但是版本号检查出错，服务端就会返回error，这个就被称之为Bad-version Oracle。

具体代码分析在后面源码分析部分。

如何构造BVO？

SSL/TLS协议有一些子协议(sub-protocol)：

Handshake：协商出会话密钥，用于后续加密会话（带星号*的表示可选）
- 客户端先发送ClientHello给服务端，提供支持的密码组件和协议版本号。
- 服务端返回ServerHello给客户端，选择最优的密码组件和协议版本号，并且可选择性地提供证书等信息。
- 客户端在本地生成premaster-secret，用服务端RSA公钥对其加密，并通过ClientKeyExchange将其发送给服务端。随后，客户端可以通过PRF用premaster-secret生成用于会话密钥，并用会话密钥加密发送[ChangeCipherSpec]、Finished，表示结束握手阶段、开始加密会话。
- 服务端收到后，对其解密，并解析出premaster-secret，如果check没问题，则也生成会话密钥，并开始加密会话。
Alert：报告通信过程中出现的错误/警告

攻击者先向服务端发起基于RSA密钥交换的握手(Handshake)请求，随后在ClientKeyExchange期间向服务端发送构造好的密文C，并随机选取一个premaster-secret用于加密Finished消息、完成握手。

服务端检测到bad version number，会通过Alert子协议返回（未加密的）“handshake failuer”或者"decode error"报错，可以根据服务端是否有这个报错来作为BVO。

当然还有其他一些方法也可以用来构造BVO，例如通过Timing side channel（不过利用难度会很大）。

算法优化

更精确地定义了上下界
通过线性组合，快速找到下一个suitable multiplier s，不过优化并不大
对区间个数大于1的$M_i$并行处理
计算了一下概率，并实测了一下BVO的交互次数

防护措施

有更好的填充方案：OAEP。

但是由于兼容性原因并不能立刻转到OAEP填充方案，况且OAEP要是实现的不好也有问题。

提出了3种防护方案，其中比较可行的一种如下所示：

OpenSSL的修复即参考了这个方案。

(2012) Bleichenbacher’s Attack Strikes Again- Breaking PKCS#1 v1.5 in XML Encryption

SOAP(simple object access protocol)是一种用于网络间交换资料的协议，基于XML(eXtensible Markup Language)格式。

XML消息在通信传输的过程中需要保障安全性，SSL/TLS协议只能在传输层面提供安全保护(transport security)，因而有了XML Encryption standards和XML Signature standards标准来在消息层面提供安全保护(message level security)。

XML Encryption standards：提供数据加密

XML Signature standards：提供完整性保护，包括数字签名(digital signatures, public-key signatures)和消息认证码(message authenticaiton codes, secret-key signatures)

这篇paper主要关注XML Encryption standards中存在的安全问题

XML Encryption standards使用hybrid encryption

（非对称加密）发送方生成一个会话密钥k，然后用接收方的公钥加密k，加密算法可选择RSA PKCS#1 v1.5(或v2.0)
（对称加密）发送方再用k来加密数据，加密算法可选AES-CBC, AES-GCM, 3DES-CBC

如上图所示，前半部分是使用非对称加密算法对会话密钥k的加密结果$c_{key}$，后半部分是使用对称加密算法对数据部分的加密$c_{data}$。

其中AES-CBC模式采用如下填充方式：

首先计算需要填充的字节数p，能够使得len(data) + p是块大小的倍数
在末尾填充(p-1)个字节
继续再填充一个字节，值为p

服务端处理流程：当收到这样一个加密的SOAP消息后，服务端首先从前半部分中解密出会话密钥k，若不符合PKCS#1 v1.5填充方式，则会报错security processing failed；拿到k之后，会继续解密数据部分，若不满足填充方式，也会报同样的错security processing failed。

报错的类型是一样的，看起来似乎无法区分到底是前半段出问题，还是后半段出问题，但是这篇paper通过Timming attack可以区分是哪里出了问题。

Attack

goal: 截取到了一段加密传输的消息，想对其解密。

idea A: 依然采用Bleichenbachor’s attack类型的选择密文攻击，不过并不是根据返回的报错来判断是否符合PKCS#1 v1.5填充方式，而是根据时间来判断。注意到，如果$c_{key}$的结果不符合PKCS#1填充方式，那么程序会直接报错返回，不会继续后续AES-CBC的解密以及其他逻辑执行；符合和不符合PKCS#1填充方式，服务端的处理时间是有区别的，可以利用上这一点side channel information来实现攻击。此外，攻击者还可以通过加长后半段的密文长度，来延长AES-CBC的解密时间，从而可以更好地区分时间信息（但也不能很长，不然会影响到发包效率）。

idea B: 前半部分依然选择密文攻击，$c_{key}$符合填充方式后，在后半部分解密的时候，把密文修改成可以被成功解密的形式（iv + c1)，程序可以走到后面的流程，并返回一个不一样error报错信息。

(2012) Eﬀicient Padding Oracle Attacks on Cryptographic Hardware

http://secgroup.dais.unive.it/wp-content/uploads/2012/11/Practical-Padding-Oracle-Attacks-on-RSA.html

算法优化

具体的优化技巧在paper的2.2小节

Trimming M0

在最开始的阶段，先将$M_0$的取值范围进行裁剪。通过给$m$乘上分数$u/t$，然后判断$mu/t$是否在$[2B, 3B-1]$的范围内，从而可以缩小$M_0$的初始取值范围。$t$要能整除$m$，需要试除，并且控制好$u, t$的取值范围。
Skipping Holes

在$i=1$的时候，某些$s$是不可能的，可以直接skip

代码实现： https://gist.github.com/soreatu/38bd088cb6f735777f3a5eb368b55188

(2018) 20 years of Bleichenbacher’s attack

这篇文章是一篇总结性的文章，从Bleichenbacher’s Attack的攻击条件、攻击危害、攻击仍然存在的原因等多个方面进行了探讨，并提出了相应的解决措施。

攻击条件

Padding：RSA加密时，要对明文m填充到与模数n一样长，才能加密
Ciphertext manipulation：RSA在乘法上是同态的，即$Enc(P_1*P_2) = Enc(P_1) * Enc(P_2)$，通常的实现都没有对RSA的密文做完整性校验（MAC），使得攻击者可以通过修改密文来操纵解密后的明文
Information leakage：攻击者可以通过一些侧信道信息来获知解密后的明文是否符合特定的填充格式

攻击危害

解密密文：攻击者可以对含有会话密钥的密文进行解密，从而达到解密整个会话流量的目的。
伪造签名：攻击者可以利用伪造的签名来仿冒成其他的合法用户。

攻击仍然存在的原因

未能及时修复漏洞
同一个密钥被用作多个目的（密钥交换、验证签名）
遗留设备维护不当
部分TLS实现仍在使用RSA算法来交换会话密钥

解决措施

遵从最新的TLS规范
及时打patch补洞
妥善管理密钥，每个密钥都被用作一个目的
理解整个系统架构
采用其他算法来实现TLS握手阶段的密钥交换

(2018) Return Of Bleichenbacher’s Oracle Threat (ROBOT)

大规模扫描知名站点是否存在Bleichenbacher attack

(2019) The 9 Lives of Bleichenbacher’s CAT: New Cache ATtacks on TLS Implementations

还能通过oracle来构造HNP，然后用lattice来求出m，不过效率不高，但思路值得学习

Openssl源码分析

ssl3_get_client_key_exchange函数

在SSL/TLS协议的Handshake环节中，对于客户端发来的ClientKeyExchange消息，服务端会调用ssl3_get_client_key_exchange函数对其进行处理。

ClientKeyExchange消息

ssl3_get_client_key_exchange函数主要会对客户端发送过来的RSA密文进行解密，并从其提取出premaster_secret，用于生成后续加密会话时需要用到的密钥和iv等材料。

0.9.6版本（2000年9月）的OpenSSL中，ssl3_get_client_key_exchange函数的具体实现如下所示：

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73


// https://github.com/openssl/openssl/blob/OpenSSL_0_9_6/ssl/s3_srvr.c#L1246-L1433
static int ssl3_get_client_key_exchange(SSL *s)
	{
	// ...
	n=ssl3_get_message(s,
		SSL3_ST_SR_KEY_EXCH_A,
		SSL3_ST_SR_KEY_EXCH_B,
		SSL3_MT_CLIENT_KEY_EXCHANGE,
		400, /* ???? */
		&ok);

	if (!ok) return((int)n);
	p=(unsigned char *)s->init_buf->data;

	l=s->s3->tmp.new_cipher->algorithms;

#ifndef NO_RSA
	if (l & SSL_kRSA)
		{
		// rsa = ...

		i=RSA_private_decrypt((int)n,p,p,rsa,RSA_PKCS1_PADDING);

		if (i != SSL_MAX_MASTER_KEY_LENGTH)
			{
			al=SSL_AD_DECODE_ERROR;
			SSLerr(SSL_F_SSL3_GET_CLIENT_KEY_EXCHANGE,SSL_R_BAD_RSA_DECRYPT);
			goto f_err;
			}

		if (!((p[0] == (s->client_version>>8)) && (p[1] == (s->client_version & 0xff))))
			{
			/* The premaster secret must contain the same version number as the
			 * ClientHello to detect version rollback attacks (strangely, the
			 * protocol does not offer such protection for DH ciphersuites).
			 * However, buggy clients exist that send the negotiated protocol
			 * version instead if the server does not support the requested
			 * protocol version.
			 * If SSL_OP_TLS_ROLLBACK_BUG is set, tolerate such clients. */
			if (!((s->options & SSL_OP_TLS_ROLLBACK_BUG) &&
				(p[0] == (s->version>>8)) && (p[1] == (s->version & 0xff))))
				{
				al=SSL_AD_DECODE_ERROR;
				SSLerr(SSL_F_SSL3_GET_CLIENT_KEY_EXCHANGE,SSL_R_BAD_PROTOCOL_VERSION_NUMBER);
				goto f_err;
				}
			}

		s->session->master_key_length=
			s->method->ssl3_enc->generate_master_secret(s,
				s->session->master_key,
				p,i);
		memset(p,0,i);
		}
	else
#endif
#ifndef NO_DH
        // ...
#endif
		{
		al=SSL_AD_HANDSHAKE_FAILURE;
		SSLerr(SSL_F_SSL3_GET_CLIENT_KEY_EXCHANGE,SSL_R_UNKNOWN_CIPHER_TYPE);
		goto f_err;
		}

	return(1);
f_err:
	ssl3_send_alert(s,SSL3_AL_FATAL,al);
#if !defined(NO_DH) || !defined(NO_RSA)
err:
#endif
	return(-1);
	}

ssl3_get_client_key_exchange函数先通过ssl3_get_message接受客户端发过来的ClientKeyExchange消息，接着调用RSA_private_decrypt函数对密文解密并解填充得到premaster_secret（填充方式默认采用RSA_PKCS1_PADDING），然后对premaster_secret进行长度和版本号的检查，若通过检查则调用generate_master_secret根据premaster_secret来生成master_secret，用作生成后续加密会话密钥和iv的材料。

其中RSA_private_decrypt函数负责最关键的操作——解密、解填充。

核心：RSA_private_decrypt

深入看RSA_private_decrypt函数，会发现实际上是通过调用RSA_eay_private_decrypt函数来实现具体操作的（这边要多绕几下才能找到）。

函数取名为RSA_eay_private_decrypt是因为这些函数的作者的id叫做eay

RSA_eay_private_decrypt的具体代码如下所示：

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73


// https://github.com/openssl/openssl/blob/OpenSSL_0_9_6/crypto/rsa/rsa_eay.c#L245-L336
static int RSA_eay_private_decrypt(int flen, unsigned char *from,
	     unsigned char *to, RSA *rsa, int padding)
	{
	BIGNUM f,ret;
	int j,num=0,r= -1;
	unsigned char *p;
	unsigned char *buf=NULL;
	BN_CTX *ctx=NULL;

	BN_init(&f);
	BN_init(&ret);
	ctx=BN_CTX_new();
	if (ctx == NULL) goto err;

	num=BN_num_bytes(rsa->n);

	if ((buf=(unsigned char *)OPENSSL_malloc(num)) == NULL)
		{
		RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,ERR_R_MALLOC_FAILURE);
		goto err;
		}

	/* This check was for equality but PGP does evil things
	 * and chops off the top '0' bytes */
	if (flen > num)
		{
		RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_DATA_GREATER_THAN_MOD_LEN);
		goto err;
		}

	/* make data into a big number */
	if (BN_bin2bn(from,(int)flen,&f) == NULL) goto err;

	if ((rsa->flags & RSA_FLAG_BLINDING) && (rsa->blinding == NULL))
		RSA_blinding_on(rsa,ctx);
	if (rsa->flags & RSA_FLAG_BLINDING)
		if (!BN_BLINDING_convert(&f,rsa->blinding,ctx)) goto err;

	/* do the decrypt */
	if ( (rsa->flags & RSA_FLAG_EXT_PKEY) ||
		((rsa->p != NULL) &&
		(rsa->q != NULL) &&
		(rsa->dmp1 != NULL) &&
		(rsa->dmq1 != NULL) &&
		(rsa->iqmp != NULL)) )
		{ if (!rsa->meth->rsa_mod_exp(&ret,&f,rsa)) goto err; }
	else
		{
		if (!rsa->meth->bn_mod_exp(&ret,&f,rsa->d,rsa->n,ctx,NULL))
			goto err;
		}

	if (rsa->flags & RSA_FLAG_BLINDING)
		if (!BN_BLINDING_invert(&ret,rsa->blinding,ctx)) goto err;

	p=buf;
	j=BN_bn2bin(&ret,p); /* j is only used with no-padding mode */

	switch (padding)
		{
	case RSA_PKCS1_PADDING:
		r=RSA_padding_check_PKCS1_type_2(to,num,buf,j,num);
		break;
	// ...
		}
	if (r < 0)
		RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_PADDING_CHECK_FAILED);

err:
	// ...
	return(r);
	}

可能第一眼看上去挺乱的，但是仔细看还是可以理出来RSA_eay_private_decrypt实现了两个操作：

对传入的密文from做RSA的解密运算，不过在解密的过程中额外新增了一个blinding的技巧，用于防止timing attacks 。具体过程可以表示为
- 先随机选取一个随机数$A$，做blind运算，计算$c_{blind} \equiv c \cdot A^e \pmod{N}$.
- 然后对其进行解密运算，计算$m_{blind} \equiv (cA^e)^d \equiv m A \pmod{N}$.
- 再做unblind运算，计算$m \equiv m_{blind} \cdot A^{-1} \equiv m_{blind} A \cdot A^{-1} \equiv m \pmod{N}$.
检查并去除PKCS#1填充，将最终结果通过to参数返回。

继续深入看RSA_padding_check_PKCS1_type_2是如何进行PKCS#1填充check的。

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


// https://github.com/openssl/openssl/blob/OpenSSL_0_9_6/crypto/rsa/rsa_pk1.c#L181-L223
int RSA_padding_check_PKCS1_type_2(unsigned char *to, int tlen,
	     unsigned char *from, int flen, int num)
	{
	int i,j;
	unsigned char *p;

	p=from;
	if ((num != (flen+1)) || (*(p++) != 02))
		{
		RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2,RSA_R_BLOCK_TYPE_IS_NOT_02);
		return(-1);
		}
#ifdef PKCS1_CHECK
	return(num-11);
#endif

	/* scan over padding data */
	j=flen-1; /* one for type. */
	for (i=0; i<j; i++)
		if (*(p++) == 0) break;

	if (i == j)
		{
		RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2,RSA_R_NULL_BEFORE_BLOCK_MISSING);
		return(-1);
		}

	if (i < 8)
		{
		RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2,RSA_R_BAD_PAD_BYTE_COUNT);
		return(-1);
		}
	i++; /* Skip over the '\0' */
	j-=i;
	if (j > tlen)
		{
		RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2,RSA_R_DATA_TOO_LARGE);
		return(-1);
		}
	memcpy(to,p,(unsigned int)j);

	return(j);
	}

传入的from参数为解密结果，flen参数表示(unsigned char *) from字节数组的长度，num参数表示模数$N$的字节数（1024bit的模数占128字节）。最前面的两个to和tlen参数用于存放解填充格式后data payload的缓冲区及其可写的最大长度。

PKCS#1填充格式如下图所示：

PKCS#1填充格式

from是由BN_bn2bin函数将$m \equiv c^d \pmod{N}$大整数转换为字节数组后的结果，类似于Python里的long_to_bytes操作，不会补上开头的0x00字节，从而导致flen只有num-1的长度。

第8行的if语句中的判断条件(num != (flen+1)) || (*(p++) != 02)，即为判断from的开头两字节是否为0x00, 0x02。

开头两字节的判断

随后，会逐字节往后扫描padding string字段，直至扫描到一个0x00字节。

（若到结尾都没有扫描到，则会报错并返回）

padding string扫描

接着，会根据这个0x00字节的位置来判断padding string的长度是否大于8，要是padding string的长度不符合要求，也会报错返回。

剩下的部分即为data payload部分，也就是SSL/TLS中的premaster_secret，调用memcpy函数将其写入to中。

to会一直返回到i=RSA_private_decrypt((int)n,p,p,rsa,RSA_PKCS1_PADDING);中的p指针所指向的缓冲区中。RSA_private_decrypt函数的返回值i即为to数组的长度，也就是提取出来的premaster_secret的长度。

如果RSA_private_decrypt函数在执行的过程中出现了问题，则会设置返回值i为-1。

回到最上层ssl3_get_client_key_exchange函数中，接下来会对premaster_secret做长度检查，判断其长度是否为48。

长度检查

若长度不正确或者出现错误(i == -1)，则会goto调转到f_err处。

Alert报错

会调用ssl3_send_alert通过Alert子协议向客户端发送尚未加密的报错信息，并中止握手过程。

98年的Bleichenbachor’s Attack正是利用了这样的一个侧信道信息，构建了一个Padding Oracle，用于选择密文攻击。

若通过了长度检查，则会进行下一步的版本号检查。

版本号检查

版本号检查会判断48字节的premaster_secret的前2个字节是否为对应的版本号。若版本号不正确，也会通过Alert子协议返回报错。其中s->version为此次握手过程中最开始ClientHello消息中客户端指定的版本号。SSL3的版本号为0x0300；TLS1.0的版本号为0x0301。

能执行到这里说明已经符合PKCS#1填充方案了，但因为版本号检查没通过而中止。版本号检查没通过也会Aler报错，这是另外一个侧信道信息，为后续03年的攻击埋下了种子。

通过这两个检测后，说明获取到的premaster_secret没有问题，就可以来到最后一步生成master_secret了。

生成master_secret

调用generate_master_secret函数，通过SHA1和MD5哈希函数从premaster_secret中扩展出48字节的master_secret。具体操作可以由下图来表示：

master_secret具体生成过程

总结一下，ssl3_get_client_key_exchange函数的处理流程为：

获取密文 => (Blinded)解密运算 => 解填充 => 长度检查 => 版本号检查 => 生成master_secret

其中，如果解密或解填充操作出现问题，会向客户端报告错误；如果长度和版本号检查不通过，也会向客户端报告错误。

要是一切都没有问题，则会使用生成的master_secret开启后续的加密会话。

98年patch

0.9.5版本的openssl已经对Bleichanbachor’s Attack做了防护，但是在一次修复中意外删掉了防护代码，好在后来01年的时候又重新加了回来。

01年的修复代码在这里：

01年修复的前半段

01年修复的后半段

此次修复的方法是，当RSA_private_decrypt执行出现问题(返回值i被设置为-1)或者提取出的data payload字段长度不为48时(长度检查未通过)，程序不会跳转到f_err去发Alert报错，而是随机生成一段48字节的premaster_secret，假装没问题继续后续握手过程。

但是这种修复方案只能保证以下两种情况的防护：

解密结果开头不为0x00, 0x02
解密结果开头为0x00, 0x02，但是提取出的data payload字段长度不为48字节，即扫描到第一个0x00的位置不是右数第49位。

仍然会存在漏网之鱼：解密结果开头为0x00, 0x02，后续扫描到第一个0x00的位置恰好为右数第49位，导致data payload字段长度正好为48字节，可以通过长度检测进入到下一步版本号检测；而版本号检测时，又正好不符合规定的版本号（前2字节不为0x0301），这时会执行goto f_err跳转，发Alert报错。此即为03年paper所描述的攻击方法。

在符合PKCS#1填充方案的条件下，这种情况的触发概率为 $$ P(BVO|A) = (\frac{255}{256})^{k-51}\cdot \frac{1}{256}\cdot(1- (\frac{1}{256})^2) $$ 1024-bit的RSA对应的k为128，上述概率为0.002889814542354661

此外，还有其他侧信道攻击的可能，例如Timing Attack。

解密结果是否符合PKCS#1填充方案，后续会执行两种不同的代码流程，这其中存在time difference，攻击者对这个time difference进行测量，也能达到攻击的目的，不过利用难度会大幅上升，攻击的可行性也会大打折扣。

03年patch

03年paper发出来之后，openssl又在98年patch之上又再加了一层防护措施，代码如下所示：

03年修复

即使通过了长度检查，但是版本号检查出问题，也不会goto f_err，而是生成一段随机的premaster_secret，假装没问题继续后续操作。

至此，基本上就封堵住这种攻击，没有其他方法能泄露出很明显的有关解密结果是否符合PKCS#1填充的侧信道信息。

TODO: 最新的patch

SSL/TLS Implementations

OpenSSL
BoringSSL
BearSSL
GNUSSL
…

downgrade attack

POODLE
FREAK
Logjam

后续研究方向

深入研究

算法优化：问题规约为，在$\mathbb{Z}_n$中，对于随机变换$ms \pmod{n}$，如何更高概率地落在$E <= ms <= F$这个区间中。
找其他的side channel information

Timing Attack是一个很好的思路，但是利用难度很大。理论上可以，但实际上不一定可行。
根据这个漏洞pattern去挖现实软件的洞
- 手动
- 自动

拓展延伸

看OpenSSL里面握手其他部分的源码实现
其他SSL/TLS库的实现？
TLS1.3里面都不用RSA了，不如转去学习一手ECC？