Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement