Bitcoin Forum
December 14, 2017, 07:14:03 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: OpenSSL RSA Hack?  (Read 1611 times)
srmojuze
Member
**
Offline Offline

Activity: 87


View Profile WWW
October 05, 2014, 06:35:24 AM
 #1

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

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1513278843
Hero Member
*
Offline Offline

Posts: 1513278843

View Profile Personal Message (Offline)

Ignore
1513278843
Reply with quote  #2

1513278843
Report to moderator
1513278843
Hero Member
*
Offline Offline

Posts: 1513278843

View Profile Personal Message (Offline)

Ignore
1513278843
Reply with quote  #2

1513278843
Report to moderator
micax1
Hero Member
*****
Offline Offline

Activity: 602


View Profile
October 31, 2014, 06:28:26 PM
 #2

any mirror? site seems to be down
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!