How to Leak a Key

I’m sure everyone has been following the great Heartbleed crisis over the last week. The “Heartbleed Challenge” set up by Cloudflare established that you could get the server private key, specifically, the primes used to generate the key would show up in the Heartbleed data occasionally. Doing a memory dump of a simple OpenSSL server application (https://github.com/matthewarcus/ssl-demo) showed that after reading the keys at startup, it later copies the prime data to higher locations in the heap where they become more likely to be included in a Heartbeat response.

An extract from a hex dump of the heap after making a single request shows:

000273f0  00 00 00 00 01 00 00 00  51 00 00 00 00 00 00 00  # Prime1
00027400  85 52 42 a0 71 54 76 bd  98 49 4f 25 fc d3 e1 89
...
00027460  00 00 00 00 01 00 00 00  51 00 00 00 00 00 00 00  # Prime2
00027470  3b c8 8b 7d 52 74 db e0  af 9e 13 d7 a2 0a fc ea
...
0002d020  60 55 00 00 00 00 00 00  50 45 00 00 00 00 00 00  # Input buffer
0002d030  16 03 01 16 03 03 00 28  e8 d6 b3 68 87 08 d4 7f
...
00031570  00 00 00 00 00 00 00 00  c1 44 00 00 00 00 00 00  # Output buffer
00031580  00 00 00 16 03 03 00 28  82 c9 a8 9a 87 b5 cf e7
...
00038990  90 00 00 00 00 00 00 00  50 00 00 00 00 00 00 00  # Prime 2 again
000389a0  3b c8 8b 7d 52 74 db e0  af 9e 13 d7 a2 0a fc ea
...
00038b50  30 00 00 00 00 00 00 00  50 00 00 00 00 00 00 00  # Prime 1 again
00038b60  85 52 42 a0 71 54 76 bd  98 49 4f 25 fc d3 e1 89  

The first line in each section is the malloc header, the second line is part of the data; also, all of these malloced blocks are in use (otherwise some of the data would be overwritten with free list data).

The first two primes are from the initial processing of the private key, the next two items are the input and output buffers for the connection, then we have two more copies of the primes, which only appear after a connection has been made.

So where are these persistent copies of the primes coming from? Some investigation shows that the first time OpenSSL actually uses an RSA key for a private operation, it calculates various auxiliary values for use in Montgomery arithmetic and stores them away in the key structure. Unfortunately, one of the values that gets stored away is the modulus used, which in this case is one of the primes:

rsa_eay.c:

static int RSA_eay_mod_exp(BIGNUM *r0,
                           const BIGNUM *I,
                           RSA *rsa,
                           BN_CTX *ctx)
{
  ...
  if (rsa->flags & RSA_FLAG_CACHE_PRIVATE)
  {
    if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_p,
                                CRYPTO_LOCK_RSA,
                                p, ctx))
      goto err;
    if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_q,
                                CRYPTO_LOCK_RSA,
                                q, ctx))
      goto err;
    ...
   }
}

bn_mont.c:

BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont,
                                    int lock,
                                    const BIGNUM *mod,
                                    BN_CTX *ctx)
{
  ...
  if (!*pmont) {
    ret = BN_MONT_CTX_new();
    if (ret && !BN_MONT_CTX_set(ret, mod, ctx))
    ...
  }
}
...
int BN_MONT_CTX_set(BN_MONT_CTX *mont,
                    const BIGNUM *mod,
                    BN_CTX *ctx)
{
  int ret = 0;
  BIGNUM *Ri,*R;
  BN_CTX_start(ctx);
  if((Ri = BN_CTX_get(ctx)) == NULL) goto err;
  R= &(mont->RR); /* grab RR as a temp */
  if (!BN_copy(&(mont->N),mod)) goto err; /* Set N */
  ...
}

That BN_copy in the last line is the culprit. Once allocated, these values stay in memory until the RSA key is deleted. So even if the original key data is stored in protected or hard to get at memory, a Heartbleed attack may still be able to get to the primes.

This also explains why, as far as I know, no one has managed to capture the CRT parameters or the private exponent itself – they stay safely tucked away in the low part of the heap. Also, depending on the application startup behaviour, it might be that the primes end up below the input buffers (by default, OpenSSL caches up to 32 previously allocated buffers of each type) in which case they won’t be visible to Heartbleed – this might explain why in the Cloudflare challenge, only one of the primes seemed to be turning up.

Update 20/04/14: actually, it’s worse than this – bignum resizing can also leak private data onto the heap in unpredictable ways, see John Graham-Cumming’s post at https://blog.cloudflare.com/searching-for-the-prime-suspect-how-heartbleed-leaked-private-keys/

---