An idea to solve the CloudFlare Heartbleed challenge
tl;dr: list of values that if any of them is leaked one can recover the RSA private key: \(p\), \(q\), \(d \mod{(p-1)}\), \(d \mod{(q-1)}\), \(c^d \mod q\), and \(c^d \mod p\), where \(c\ = m^e\) and \(m\) is the premaster secret sent by the client.
I plan to take a look at the challenge this weekend, but it seems that someone has solved it in just a few hours. Very nice work. Anyway here's how I think this challenge could be solved:
I plan to take a look at the challenge this weekend, but it seems that someone has solved it in just a few hours. Very nice work. Anyway here's how I think this challenge could be solved:
1. Exploit the fact that if you know any intermediate values in the Chinese Remainder algorithm, you can recover the private key.
2. Search for these intermediate values in the leaked memory.
The private key will be used in two cases:
a) To decrypt the proposed premaster secret from the client.
b) To sign an ephemeral (EC)DH public key.
a) To decrypt the proposed premaster secret from the client.
b) To sign an ephemeral (EC)DH public key.
In both cases you know the value \(c\) and \(m\) in the equation \(c^d = m \pmod N\), where \(d\) is the private key, and \(N\) is the modulus. To make it faster \(c^d \pmod N\) is carried out using Chinese Remainder algorithm in which there are two intermediate values \(x_1\) and \(x_2\) that are calculated as follows:
\(c^d = c^{d\mod{q-1}} = x_1 \pmod q\)
\(c^d = c^{d\mod{p-1}} = x_2 \pmod p\)
\(c^d = c^{d\mod{q-1}} = x_1 \pmod q\)
\(c^d = c^{d\mod{p-1}} = x_2 \pmod p\)
Note that \((m - x_1)\) is a multiple of \(q\). So you can use \(\gcd(m - x_1, N)\) to obtain \(q\), if you happen to know \(x_1\). Searching for \(x_1\) looks feasible because it's a bignum half the size of the modulus.
Warning: I haven't verified that this actually works. I just come up with the idea while taking a shower.
Update: I've taken a look at the code, and I think this idea should work. OpenSSL indeed uses Chinese Remainder.
static int RSA_eay_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
{
BIGNUM *r1,*m1,*vrfy;
BIGNUM local_dmp1,local_dmq1,local_c,local_r1;
BIGNUM *dmp1,*dmq1,*c,*pr1;
int ret=0;
BN_CTX_start(ctx);
r1 = BN_CTX_get(ctx);
m1 = BN_CTX_get(ctx);
vrfy = BN_CTX_get(ctx);
r1 and m1 are the intermediate values, and they seem to be allocated for every invocation of this function. Their bignum_st structures are re-used from a pool, but the actual values are freshly allocated from the heap, unless I miss something. This is important, because we want these values sitting near the Heartbeat request. Note that if you read this function you may get the impression that p and q are also freshly allocated, but in fact they aren't.
Update: someone pointed out that r1 and m1 will be scrubbed before Heartbeat requests are processed. Too bad :(.
Update: a simple exploit that simply searches for \(p\) in the leaked memory: https://gist.github.com/epixoip/10570627.
Update: you need to protect pre-calculated CRT parameters stored in the private key as well. See http://lekkertech.net/akamai.txt.
Besides \(d\), \(p\), and \(q\) inside the encoded private key there are also two pre-calcuted CRT parameters: \(d_p = d \pmod{p - 1}\) and \(d_q = d \pmod{q - 1}\). If you know \(d_p\) you can recover the private key as follows:
\[
\begin{aligned}
d_p & = d \pmod{p - 1} \\
\rightarrow ed_p & = ed \pmod{p-1} \\
\rightarrow ed_p & = 1 \pmod{p-1}\\
\end{aligned}
\]
That means \(p - 1\) is a divisor of \(ed_p - 1\).
Update: I've taken a look at the code, and I think this idea should work. OpenSSL indeed uses Chinese Remainder.
static int RSA_eay_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
{
BIGNUM *r1,*m1,*vrfy;
BIGNUM local_dmp1,local_dmq1,local_c,local_r1;
BIGNUM *dmp1,*dmq1,*c,*pr1;
int ret=0;
BN_CTX_start(ctx);
r1 = BN_CTX_get(ctx);
m1 = BN_CTX_get(ctx);
vrfy = BN_CTX_get(ctx);
r1 and m1 are the intermediate values, and they seem to be allocated for every invocation of this function. Their bignum_st structures are re-used from a pool, but the actual values are freshly allocated from the heap, unless I miss something. This is important, because we want these values sitting near the Heartbeat request. Note that if you read this function you may get the impression that p and q are also freshly allocated, but in fact they aren't.
Update: someone pointed out that r1 and m1 will be scrubbed before Heartbeat requests are processed. Too bad :(.
Update: a simple exploit that simply searches for \(p\) in the leaked memory: https://gist.github.com/epixoip/10570627.
Update: you need to protect pre-calculated CRT parameters stored in the private key as well. See http://lekkertech.net/akamai.txt.
Besides \(d\), \(p\), and \(q\) inside the encoded private key there are also two pre-calcuted CRT parameters: \(d_p = d \pmod{p - 1}\) and \(d_q = d \pmod{q - 1}\). If you know \(d_p\) you can recover the private key as follows:
\[
\begin{aligned}
d_p & = d \pmod{p - 1} \\
\rightarrow ed_p & = ed \pmod{p-1} \\
\rightarrow ed_p & = 1 \pmod{p-1}\\
\end{aligned}
\]
That means \(p - 1\) is a divisor of \(ed_p - 1\).
Comments