# OpenSSL RSA Hack: www.cristianamicelli.com.ar/blog/rsahack

a guest
Oct 4th, 2014
9,048
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. Translated from:
2. http://www.cristianamicelli.com.ar/blog/rsahack/
3.
4. RSAhack
5.
6. Posted by Cristian on 05/09/201411/09/2014 Amicelli
7. As we all know, is one of the RSA asymmetric algorithms (Public and Private Key) used and best known in recent decades. It was created by Rivest, Shamir and Adleman in 1977, The safety of this algorithm lies in the problem of factoring integers.
8.
9. RSA algorithm
10. The algorithm consists basically of three steps:
11.
12. Key Generation
13.
14. Based on two distinct prime numbers, to which they are known as "p and q", which are chosen randomly.
15.
16. Taking primes n is calculated, which is basically the product of "pq" which makes "n" (semiprime) in the module.
17.
18. Now once the module having the Euler function φ (n) = (p-1) (q-1) is used, and having this calculation proceeds to choose a public exponent which is known as "e" this has two particular be less than φ (n) and is also coprime of this, usually 65 537 is used.
19.
20. A number that is called "d" using modular arithmetic, where "d" must be the inverse modular multiplier "e" is then determined.
21.
22. Then we have that:
23.
24. The public key is made up of "n" and "e" and the private key is composed of "n", "d", "p", "q" and these modules.
25.
26. encryption
27.
28. Using the public key (nye) A message "c" is created (Encryption)
29.
30. c ≡ m (clear message) ^ e (mod n)
31.
32. decryption
33.
34. Using the private key (n, d, p, q) is obtained from c m
35.
36. m ≡ c (encrypted message) ^ d (mod n)
37.
38. attacks
39. As we saw above seems complicated operation, although there are many complicated known attacks that can be performed partially.
40.
41. Cyclic Encryption:
42.
43. Be decrypted using the same key figure is the public key, by an attack that uses only data from the victim that are public. The problem is that we present ourselves then anyone who knows the keys used in the process of figure or key exchange, could theoretically recover the secret.
44.
45. Dual EC DRBG:
46.
47. It is a generator cryptographically secure pseudo-random numbers, which was developed by the National Security Agency (NSA) and later adopted by RSA Security in your kit Bsafe which adopted double elliptic curve. However, this Backdoor was discovered in 2007, and was detailed by security expert Bruce Schneier.
48.
50.
51. Most interesting of all is that for the attack only need to have the public key values ​​of the victim
52.
53. factoring:
54.
55. In number theory, integer factorization or prime factorization is to decompose a composite number (not prime) in non-trivial divisors, which when multiplied give the original number.
56.
57. In this type of attack is try to factor n into p and q, and (p-1) (q-1) calculated by allowing you to determine d and e.
58.
59. Where are RSA
60. As previously mentioned this algorithm is well known and is not implemented in a number of places.
61.
62. OpenSSL
63. GnuPG
64. PGP
65. OpenVPN
66. ETC
67. RSAhack
68. In what is developing this tool basically abusing a flaw in the implementation of RSA in OpenSSL found in all versions, the attack is done by Brute Force is made.
69.
70. When OpenSSL generates an RSA key uses rsa_builtin_keygen function located within /crypto/rsa/rsa_gen.c
71.
72. static int rsa_builtin_keygen (RSA * rsa, int bits, bignum * E_value, BN_GENCB * cb)
73. {
74. Bignum * r0 = NULL, * r1 = NULL, * r2 = NULL, * r3 = NULL, * tmp;
75. Bignum local_r0, local_d, local_p;
76. Pr0 bignum *, * d, * p;
77. int bitsp, bitsq, k = 1, n = 0;
78. BN_CTX * ctx = NULL;
79.
80. BN_CTX_new ctx = ();
81. if (ctx == NULL) goto err;
82. BN_CTX_start (ctx);
83. r0 = BN_CTX_get (ctx);
84. r1 = BN_CTX_get (ctx);
85. r2 = BN_CTX_get (ctx);
86. r3 = BN_CTX_get (ctx);
87. if (r3 == NULL) goto err;
88.
89. bitsp = (bits + 1) / 2;
90. bitsq = bits-bitsp;
91.
92. / * We need the RSA components non-NULL * /
93. if (! RSA-> n && ((RSA-> n = BN_new ()) == NULL)) goto err;
94. if (! RSA-> d && ((RSA-> d = BN_new ()) == NULL)) goto err;
95. if (! RSA-> e && ((RSA-> e = BN_new ()) == NULL)) goto err;
96. if (! RSA-> p && ((RSA-> p = BN_new ()) == NULL)) goto err;
97. if (RSA-> q && ((RSA-> q = BN_new ()) == NULL)!) goto err;
98. if (RSA-> DMP1 && ((RSA-> BN_new DMP1 = ()) == NULL)!) goto err;
99. if (RSA-> dmq1 && ((RSA-> BN_new dmq1 = ()) == NULL)!) goto err;
100. if (RSA-> iqmp && ((RSA-> BN_new iqmp = ()) == NULL)!) goto err;
101.
102. BN_copy (RSA-> e, E_value);
103.
104. ***********
105. In the portion of the code, we see that it has a bit and then divides by 2 the length of the key, this is done to determine the length of p and q, that is, for a 1024-bit key p and q will be prime numbers 512, 5 bits and 511.5 bits.
106.
107. What this means it helps ?, partly because the attack is that for a 1024-bit key numbers are 512 bits.
108.
109. Looking at other implementations in applications such as GnuPG have realized this and corrected the lines, so that the prime numbers are not the same length, which adds another layer of complexity.
110.
111. But however it is not all primes to perform Superpower we lack, if this becomes quite complicated but we have several options depending on the hardware you have, the better the quality of the task simpler calculation. But to start, we can use it and extract OpenSSL primes.
112.
113. I pass an example:
114.
115. genrsa -out key 1024 openssl
116. This command generates an RSA key with OpenSSL 1024.
117.
118. openssl rsa key -in -text -out key2
119. This further allows us to pass the RSA key text which we get the following.
120.
121. Private-Key: (1024 bit)
122. modulus:
123. 00: c7: 76: 50: d1: 5f: d3: e1: fc: 31: 3f: 7d: e6: e0: 49:
124. 28: 75: b6: 7e: 29: c3: 3a: 1d: ce: 46: 27: 1f: e5: 60: 9b:
125. 2d: 26: 37: 75: 80: 94: 07: 7a: 05: 87: 45: 5d: d4: ad: 6f:
126. ce: df: 26: 23: a1: 3d: 0f: 26: 92: 0a: from: 9b: 95: 07: 55:
127. e8: 36: 4c: 92: bf: 99: 59: 22: 7a: a2: 22: 21: 82: 4b: 90:
128. 06: 72: 4b: 46: c3: 3f: 32: b6: c8: 3a: b6: 3c: 2f: 7e: 3f:
129. a2: 98: fc: 60: d7: 3b: aa: 35: 14: 13: 50: 68: 0a: 4c: 84:
130. 71: 39: e4: 47: dd: dd: 7b: 86: 85: d3: f5: 0a: 86: 34: db:
131. 47: b1: 00: 9d: 28: from: e2: 4d: ad
132. publicExponent: 65537 (0x10001)
133. privateExponent:
134. 53: 69: 08: d6: e5: a9: e7: 60: dc: ff: 5e: 19: 04: 45: d3:
135. a3: 96: 13: 20: 47: c1: af: e1: 28: b9: 07: bf: 96: 2c: 8e:
136. 2e: e3: 16: 42: 14: a5: 23: c3: d8: 13: 8b: ef: 7a: 2f: bd:
137. 64: d7: c0: 22: 97: 34: 14: bf: 11: c8: 91: 6b: 3a: cc: 13:
138. f5: 51: 04: 34: 5a: 19: 8d: 3c: 3f: bd: a9: 5c: 98: 0d: bc:
139. 56: f8: ea: 68: da: 1c: a9: a1: d0: 05: 83: 97: e9: 29: 41:
140. 09: 5a: 8a: 9d: 03: be: 39: 5c: 11: 44: 9e: 7f: ac: 48: d3:
141. a1: 64: 40: b1: 5d: 8a: f9: c3: 7e: c5: e6: the 9th: 80: 8a: 00:
142. 86: 52: 0d: 27: 73: 98: 51: 01
143. prime1:
144. 00: ee: 80: 9d: af: ee: 43: e1: 41: f9: 23: 53: 39: 54: 89:
145. 13: 43: 3d: ef: c2: db: d2: 87: the 9th: 3c: 2c: a1: d9: d4: 88:
146. 12: 03: c6: 96: db: 2e: 3b: 52: b0: a7: 9e: 44: 0a: dc: 9c:
147. 06: 57: e1: 50: 7b: 1d: 1d: b7: d1: 68: 00: 36: 09: 51: 7c:
148. a3: 53: 3c: fd: a1
149. Prime2:
150. 00: d6: 18: 79: 3a: bf: 95: 28: 13: 06: 03: 11: 72: b7: 8b:
151. 9f: 2a: 5d: ec: 1e: 7b: 89: 0b: 88: dd: 67: 8e: 55: 0b: ac:
152. af: 56: 9c: 09: 6f: 8d: 79: d1: b3: 24: 79: 5f: 82: d6: b4:
153. 70: 6e: a3: 93: c8: af: d7: 4a: a1: c0: a6: d2: f4: 7f: cf:
154. 72: 3d: 6d 1c: 8d
155. exponent1:
156. 4b: 99: cd: 62: 45: 1e: 93: 3a: bc: 64: 6c: 2f: 12: 12: d9:
157. 5e: 49: 35: c5: 08: b5: 35: 72: b8: 7c: 55: 59: 9d: 3a: fc:
158. aa: e1: ba: 54: 03: d5: 9e: 22: 8d: 1f: 67: e6: 21: 83: fb:
159. a6: c3: af: 25: 37: 57: 82: 3b: 08: c2: 78: 5e: 7f: cc: 08:
160. 61: 8c: 45: c1
161. exponent2:
162. 7e: ad: 22: 65: d1: 5f: b6: c3: 72: c6: 33: f7: b5: 84: 66:
163. 5b: d2: 10: d8: 84: 6d: b5: 26: 79: 22: 41: c4: 2e: 51: 31:
164. b9: c4: 3f: 8d: 02: 9f: b6: a5: 11: 8a: c3: 29: 8e: 52: 5b:
165. 48: 0b: 7f: 70: ba: 22: 5f: a5: 4f: 71: 25: d6: c7: 1c: fe:
166. 52: 3c: 12: 2d
167. coefficient:
168. 00: d6: fa: 86: 0c: ff: 5f: 8c: 3d: db: 74: b2: bd: ac: 84:
169. 1b: 86: 16: b6: 24: 98: 0b: 5b: e8: 89: 90: 38: e2: 7c: 96:
170. ee: 3b: c1: 0e: bc: eb: 66: 64: 16: ca: e7: 6c: 85: 0a: 7b:
171. f2: ee: e7: 4a: 39: 9c: 66: 77: fd: 34: 77: 66: b7: d1: 51:
172. a8: 55: ca: 5f: f3
173. ----- BEGIN RSA PRIVATE KEY -----
174. MIICXAIBAAKBgQDHdlDRX9Ph / DE / febgSSh1tn4pwzodzkYnH + Vgmy0mN3WAlAd6
175. BYdFXdStb87fJiOhPQ8mkgrem5UHVeg2TJK / mVkieqIiIYJLkAZyS0bDPzK2yDq2
176. PC9 P6KY + / GDXO6o1FBNQaApMhHE55Efd3XuGhdP1CoY020exAJ0o3uJNrQIDAQAB
177. AoGAU2kI1uWp52Dc / 14ZBEXTo5YTIEfBr + EouQe / liyOLuMWQhSlI8PYE4vvei + 9
178. ZNfAIpc0FL8RyJFrOswT9VEENFoZjTw / valcmA28VvjqaNocqaHQBYOX6SlBCVqK
179. OVwRRJ5 NQO + / + cN + rEjToWRAsV2K xeaagIoAhlINJ3OYUQECQQDugJ2v7kPhQfkj
180. UzlUiRNDPe / C29KHmjwsodnUiBIDxpbbLjtSsKeeRArcnAZX4VB7HR230WgANglR
181. fKNTPP2hAkEA1hh5Or + VKBMGAxFyt4ufKl3sHnuJC4jdZ45VC6yvVpwJb4150bMk
182. C1rRwbqOTyK eV + / XSqHAptL0f89yPW0cjQJAS5nNYkUekzq8ZGwvEhLZXkk1xQi1
183. NXK4fFVZnTr8quG6VAPVniKNH2fmIYP7psOvJTdXgjsIwnhef8wIYYxFwQJAfq0i
184. ZdFftsNyxjP3tYRmW9IQ2IRttSZ5IkHELlExucQ / jQKftqURisMpjlJbSAt / cloi
185. UjwSLQJBANb6hgz X6VPcSXWxxz + / X4w923SyvayEG4YWtiSYC1voiZA44nyW7jvB
186. DrzrZmQWyudshQp78u7nSjmcZnf9NHdmt9FRqFXKX / M =
187. ----- END RSA PRIVATE KEY -----
188. All we need is to extract the prime numbers that look and keep them in the same format as we see what is hexadecimal, this task can be automated so you can start playing with numbers Cousins ​​Big Eye is not the only way, but if used for testing.
189.
190. After getting a good deal (many) primes we can start making Fuerza Bruta on a public key, and then to generate the private key.
191.
192. advice for driving large primes recommend using GMP
193.
194. Here's a video where you can see running RSAhak, in an attack on a public key of 1024 bits.
195.
196. video Demonstration
197.
198.
199. I leave a simple module written in Python so that after the primes to generate RSA private key. You can download it from github.
200.
201. Later I'll post the full project RSAhack
202.
203. Cristian Amicelli
204.
205.
206. Tagged as: Cryptography, Superpower, Python, RSA
207. Categorized as: Cryptography
208.
209. 4 thoughts on "RSAhack"
210.
211. jorge kamlofsky says:
212. 09/08/2014 at 13:29
213. Hello, Cristian. I am a mathematician: Discrete Mathematics teacher IAU. Hence I know Juan Manuel, who passed me your presentations.
214. Excellent job! Congratulations! I will try to reproduce the attack in order to understand it better. Thanks and regards.
215. JK
216.
218. Cristian Amicelli says:
219. 09/08/2014 at 17:45
220. Thank you Jorge, you have any questions, ideas or advice do not hesitate to perform them
221.
223. NU11 says:
224. 09/09/2014 at 18:24
225. SEAS primes not the same length == primes SEAN not the same length?
226.
228. Cristian Amicelli says:
229. 09/14/2014 at 19:21
230.
231.
232.
233.