Quickly posting this here? Legit? Translated from:
http://www.cristianamicelli.com.ar/blog/rsahack/ RSAhack
Posted by Cristian on 05/09/201411/09/2014 Amicelli
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.
RSA algorithm
The algorithm consists basically of three steps:
Key Generation
Based on two distinct prime numbers, to which they are known as "p and q", which are chosen randomly.
Taking primes n is calculated, which is basically the product of "pq" which makes "n" (semiprime) in the module.
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.
A number that is called "d" using modular arithmetic, where "d" must be the inverse modular multiplier "e" is then determined.
Then we have that:
The public key is made up of "n" and "e" and the private key is composed of "n", "d", "p", "q" and these modules.
encryption
Using the public key (nye) A message "c" is created (Encryption)
c ≡ m (clear message) ^ e (mod n)
decryption
Using the private key (n, d, p, q) is obtained from c m
m ≡ c (encrypted message) ^ d (mod n)
attacks
As we saw above seems complicated operation, although there are many complicated known attacks that can be performed partially.
Cyclic Encryption:
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.
Dual EC DRBG:
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.
Birthday Paradox
Most interesting of all is that for the attack only need to have the public key values of the victim
factoring:
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.
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.
Where are RSA
As previously mentioned this algorithm is well known and is not implemented in a number of places.
OpenSSL
GnuPG
PGP
OpenVPN
ETC
RSAhack
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.
When OpenSSL generates an RSA key uses rsa_builtin_keygen function located within /crypto/rsa/rsa_gen.c
static int rsa_builtin_keygen (RSA * rsa, int bits, bignum * E_value, BN_GENCB * cb)
{
Bignum * r0 = NULL, * r1 = NULL, * r2 = NULL, * r3 = NULL, * tmp;
Bignum local_r0, local_d, local_p;
Pr0 bignum *, * d, * p;
int bitsp, bitsq, k = 1, n = 0;
BN_CTX * ctx = NULL;
BN_CTX_new ctx = ();
if (ctx == NULL) goto err;
BN_CTX_start (ctx);
r0 = BN_CTX_get (ctx);
r1 = BN_CTX_get (ctx);
r2 = BN_CTX_get (ctx);
r3 = BN_CTX_get (ctx);
if (r3 == NULL) goto err;
bitsp = (bits + 1) / 2;
bitsq = bits-bitsp;
/ * We need the RSA components non-NULL * /
if (! RSA-> n && ((RSA-> n = BN_new ()) == NULL)) goto err;
if (! RSA-> d && ((RSA-> d = BN_new ()) == NULL)) goto err;
if (! RSA-> e && ((RSA-> e = BN_new ()) == NULL)) goto err;
if (! RSA-> p && ((RSA-> p = BN_new ()) == NULL)) goto err;
if (RSA-> q && ((RSA-> q = BN_new ()) == NULL)!) goto err;
if (RSA-> DMP1 && ((RSA-> BN_new DMP1 = ()) == NULL)!) goto err;
if (RSA-> dmq1 && ((RSA-> BN_new dmq1 = ()) == NULL)!) goto err;
if (RSA-> iqmp && ((RSA-> BN_new iqmp = ()) == NULL)!) goto err;
BN_copy (RSA-> e, E_value);
***********
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.
What this means it helps ?, partly because the attack is that for a 1024-bit key numbers are 512 bits.
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.
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.
I pass an example:
genrsa -out key 1024 openssl
This command generates an RSA key with OpenSSL 1024.
openssl rsa key -in -text -out key2
This further allows us to pass the RSA key text which we get the following.
Private-Key: (1024 bit)
modulus:
00: c7: 76: 50: d1: 5f: d3: e1: fc: 31: 3f: 7d: e6: e0: 49:
28: 75: b6: 7e: 29: c3: 3a: 1d: ce: 46: 27: 1f: e5: 60: 9b:
2d: 26: 37: 75: 80: 94: 07: 7a: 05: 87: 45: 5d: d4: ad: 6f:
ce: df: 26: 23: a1: 3d: 0f: 26: 92: 0a: from: 9b: 95: 07: 55:
e8: 36: 4c: 92: bf: 99: 59: 22: 7a: a2: 22: 21: 82: 4b: 90:
06: 72: 4b: 46: c3: 3f: 32: b6: c8: 3a: b6: 3c: 2f: 7e: 3f:
a2: 98: fc: 60: d7: 3b: aa: 35: 14: 13: 50: 68: 0a: 4c: 84:
71: 39: e4: 47: dd: dd: 7b: 86: 85: d3: f5: 0a: 86: 34: db:
47: b1: 00: 9d: 28: from: e2: 4d: ad
publicExponent: 65537 (0x10001)
privateExponent:
53: 69: 08: d6: e5: a9: e7: 60: dc: ff: 5e: 19: 04: 45: d3:
a3: 96: 13: 20: 47: c1: af: e1: 28: b9: 07: bf: 96: 2c: 8e:
2e: e3: 16: 42: 14: a5: 23: c3: d8: 13: 8b: ef: 7a: 2f: bd:
64: d7: c0: 22: 97: 34: 14: bf: 11: c8: 91: 6b: 3a: cc: 13:
f5: 51: 04: 34: 5a: 19: 8d: 3c: 3f: bd: a9: 5c: 98: 0d: bc:
56: f8: ea: 68: da: 1c: a9: a1: d0: 05: 83: 97: e9: 29: 41:
09: 5a: 8a: 9d: 03: be: 39: 5c: 11: 44: 9e: 7f: ac: 48: d3:
a1: 64: 40: b1: 5d: 8a: f9: c3: 7e: c5: e6: the 9th: 80: 8a: 00:
86: 52: 0d: 27: 73: 98: 51: 01
prime1:
00: ee: 80: 9d: af: ee: 43: e1: 41: f9: 23: 53: 39: 54: 89:
13: 43: 3d: ef: c2: db: d2: 87: the 9th: 3c: 2c: a1: d9: d4: 88:
12: 03: c6: 96: db: 2e: 3b: 52: b0: a7: 9e: 44: 0a: dc: 9c:
06: 57: e1: 50: 7b: 1d: 1d: b7: d1: 68: 00: 36: 09: 51: 7c:
a3: 53: 3c: fd: a1
Prime2:
00: d6: 18: 79: 3a: bf: 95: 28: 13: 06: 03: 11: 72: b7: 8b:
9f: 2a: 5d: ec: 1e: 7b: 89: 0b: 88: dd: 67: 8e: 55: 0b: ac:
af: 56: 9c: 09: 6f: 8d: 79: d1: b3: 24: 79: 5f: 82: d6: b4:
70: 6e: a3: 93: c8: af: d7: 4a: a1: c0: a6: d2: f4: 7f: cf:
72: 3d: 6d 1c: 8d
exponent1:
4b: 99: cd: 62: 45: 1e: 93: 3a: bc: 64: 6c: 2f: 12: 12: d9:
5e: 49: 35: c5: 08: b5: 35: 72: b8: 7c: 55: 59: 9d: 3a: fc:
aa: e1: ba: 54: 03: d5: 9e: 22: 8d: 1f: 67: e6: 21: 83: fb:
a6: c3: af: 25: 37: 57: 82: 3b: 08: c2: 78: 5e: 7f: cc: 08:
61: 8c: 45: c1
exponent2:
7e: ad: 22: 65: d1: 5f: b6: c3: 72: c6: 33: f7: b5: 84: 66:
5b: d2: 10: d8: 84: 6d: b5: 26: 79: 22: 41: c4: 2e: 51: 31:
b9: c4: 3f: 8d: 02: 9f: b6: a5: 11: 8a: c3: 29: 8e: 52: 5b:
48: 0b: 7f: 70: ba: 22: 5f: a5: 4f: 71: 25: d6: c7: 1c: fe:
52: 3c: 12: 2d
coefficient:
00: d6: fa: 86: 0c: ff: 5f: 8c: 3d: db: 74: b2: bd: ac: 84:
1b: 86: 16: b6: 24: 98: 0b: 5b: e8: 89: 90: 38: e2: 7c: 96:
ee: 3b: c1: 0e: bc: eb: 66: 64: 16: ca: e7: 6c: 85: 0a: 7b:
f2: ee: e7: 4a: 39: 9c: 66: 77: fd: 34: 77: 66: b7: d1: 51:
a8: 55: ca: 5f: f3
----- BEGIN RSA PRIVATE KEY -----
MIICXAIBAAKBgQDHdlDRX9Ph / DE / febgSSh1tn4pwzodzkYnH + Vgmy0mN3WAlAd6
BYdFXdStb87fJiOhPQ8mkgrem5UHVeg2TJK / mVkieqIiIYJLkAZyS0bDPzK2yDq2
PC9 P6KY + / GDXO6o1FBNQaApMhHE55Efd3XuGhdP1CoY020exAJ0o3uJNrQIDAQAB
AoGAU2kI1uWp52Dc / 14ZBEXTo5YTIEfBr + EouQe / liyOLuMWQhSlI8PYE4vvei + 9
ZNfAIpc0FL8RyJFrOswT9VEENFoZjTw / valcmA28VvjqaNocqaHQBYOX6SlBCVqK
OVwRRJ5 NQO + / + cN + rEjToWRAsV2K xeaagIoAhlINJ3OYUQECQQDugJ2v7kPhQfkj
UzlUiRNDPe / C29KHmjwsodnUiBIDxpbbLjtSsKeeRArcnAZX4VB7HR230WgANglR
fKNTPP2hAkEA1hh5Or + VKBMGAxFyt4ufKl3sHnuJC4jdZ45VC6yvVpwJb4150bMk
C1rRwbqOTyK eV + / XSqHAptL0f89yPW0cjQJAS5nNYkUekzq8ZGwvEhLZXkk1xQi1
NXK4fFVZnTr8quG6VAPVniKNH2fmIYP7psOvJTdXgjsIwnhef8wIYYxFwQJAfq0i
ZdFftsNyxjP3tYRmW9IQ2IRttSZ5IkHELlExucQ / jQKftqURisMpjlJbSAt / cloi
UjwSLQJBANb6hgz X6VPcSXWxxz + / X4w923SyvayEG4YWtiSYC1voiZA44nyW7jvB
DrzrZmQWyudshQp78u7nSjmcZnf9NHdmt9FRqFXKX / M =
----- END RSA PRIVATE KEY -----
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.
After getting a good deal (many) primes we can start making Fuerza Bruta on a public key, and then to generate the private key.
advice for driving large primes recommend using GMP
Here's a video where you can see running RSAhak, in an attack on a public key of 1024 bits.
video Demonstration
I leave a simple module written in Python so that after the primes to generate RSA private key. You can download it from github.
Later I'll post the full project RSAhack
Cristian Amicelli
Tagged as: Cryptography, Superpower, Python, RSA
Categorized as: Cryptography
4 thoughts on "RSAhack"
jorge kamlofsky says:
09/08/2014 at 13:29
Hello, Cristian. I am a mathematician: Discrete Mathematics teacher IAU. Hence I know Juan Manuel, who passed me your presentations.
Excellent job! Congratulations! I will try to reproduce the attack in order to understand it better. Thanks and regards.
JK
Reply
Cristian Amicelli says:
09/08/2014 at 17:45
Thank you Jorge, you have any questions, ideas or advice do not hesitate to perform them
Reply
NU11 says:
09/09/2014 at 18:24
SEAS primes not the same length == primes SEAN not the same length?
Reply
Cristian Amicelli says:
09/14/2014 at 19:21
Post navigation
Pharming ← PHP and cURL
View: Mobile | Classic
Google Translate for Business:Translator ToolkitWebsite TranslatorGlobal Market Finder
