Flaw Found in an Online Encryption Method

Discussion in 'privacy technology' started by lotuseclat79, Feb 14, 2012.

Thread Status:
Not open for further replies.
  1. lotuseclat79

    lotuseclat79 Registered Member

    Joined:
    Jun 16, 2005
    Posts:
    5,096
    Last edited: Feb 15, 2012
  2. x942

    x942 Guest

    This is what I understand on this from reading and watching Security Now.

    The attack is a Birthday Attack (see http://en.wikipedia.org/wiki/Birthday_attack). This means that the likely hood that your one key is exposed is VERY slim. How ever the likely hood that two randomly picked keys are similar is high.

    An example is:

    Is this a huge break through? Yes. Can some one keep generating keys until they get yours? No. Easy fix? Increase bit size to 2048 or higher. Almost all of the collisions found were for 1024 bit keys.

    Can some one explain in more detail? Is this correct or have I missed something?
     
  3. EncryptedBytes

    EncryptedBytes Registered Member

    Joined:
    Feb 20, 2011
    Posts:
    449
    Location:
    N/A
    For those curious about how the "attack" works, I believe the mathematical trick used was Euclidean algorithm?

    If you have two composite moduli N=pq and M=pr that share a prime factor (in this case, p), then gcd(N,M)=p, and thus you instantly factored N and M. Of course gcd is easy to compute as you just run the Euclidean algorithm. So if you have a huge pool of keys N1,N2,...,Nk, you could just take the GCD of them pairwise and you'll get factors for all the ones that have shared prime factors.

    The report stated only .4% of all SSL keys were compromised in their population sample; I don't feel the fault is with the crypto but rather the embedded systems that utilized the crypto, and poor entropy. So I wouldnt go hitting the panic button, I am sure banking sites and other ecommerce are just fine. VPN's, routers or other hardware systems could be at fault depending on the types tested.

    Or I could just be talking out my lower region, though from the information out there so far, it is what I gathered....
     
    Last edited: Feb 16, 2012
  4. Baserk

    Baserk Registered Member

    Joined:
    Apr 14, 2008
    Posts:
    1,317
    Location:
    AmstelodamUM
    From the Ars Technica article;
    'It remains unclear exactly what is causing large clusters of keys to use duplicated factors. Hughes said that when generation is done correctly for a 1024-bit key, it should theoretically require the generation of 2^200 certificates before all possible factors are exhausted. Curiously, the problem of duplicate factors also marred 2048-bit keys, even though they should theoretically provide much more entropy. The researchers searched for similarities among the vulnerable keys for clues about what was causing random number generators to fail during the key generator process, but they were unable to make any determination.

    "Our only conclusion is that there is not just one cause for all of these problems," Hughes said. "This leads to our conclusion that unless you can totally trust your random number generator, RSA is not a good algorithm to choose."
    ' link
     
  5. Hungry Man

    Hungry Man Registered Member

    Joined:
    May 11, 2011
    Posts:
    9,148
    It effects 2048 but not to the same extent at all.

    edit: And yes EB it was Euclidian algorithm where knowing one of the prime factors allows you to know some other stuff. It necessitates being able to guess one of the primes, which is the problem - you can guess right every 1 in 500 times.
     
  6. Baserk

    Baserk Registered Member

    Joined:
    Apr 14, 2008
    Posts:
    1,317
    Location:
    AmstelodamUM
    You're right. I should have know better and should have checked the actual numbers in the PDF. Stupid me for assuming the meaning of 'marred'...:oops:
     
  7. Hungry Man

    Hungry Man Registered Member

    Joined:
    May 11, 2011
    Posts:
    9,148
    It's basically RSA v https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange.

    Basically RSA uses a combination of two large primes. The problem is that you have to randomly generate these primes. For whatever reason this isn't happening.

    Crypto blows my mind so I don't really get it. I had a class that went through it briefly and I've never really understood it due to not having the math background required to understand this stuff.


    http://eprint.iacr.org/2012/064.pdf

    If anyone can understand it - kudos.
     
  8. x942

    x942 Guest

    Thank you for clarification :thumb:
     
  9. x942

    x942 Guest

    Thanks for the info as well :thumb:
     
  10. Baserk

    Baserk Registered Member

    Joined:
    Apr 14, 2008
    Posts:
    1,317
    Location:
    AmstelodamUM
    You're welcome. However, I thought of 'marred' as meaning 'heavily influenced' where the proper meaning is apparantly more like 'slightly tainted'.
    Which is quite a difference...
    Yeah, low entropy and all that, seemingly an issue with (embedded) devices not offering enough factors for properly randomly generating the primes, or something...(tbh, this stuff is above me).
     
  11. x942

    x942 Guest

    :thumb:

    So if I understand that link right (and the rest of the information) generating keys on my own computer should be fine as it can seed the PRNG better than an "embedded" device?

    Either way I am tempted to switch my public keys over to DSA 4096 Bit instead for now.

    And I hear you, I have done classes and research on this stuff and it's still greek to me. Such complicated math, the experts really amaze me.
     
  12. Countermail

    Countermail Registered Member

    Joined:
    Aug 7, 2009
    Posts:
    167
    Location:
    Sweden
    The "low entrophy" problem is not new, it's been known for decades :)

    As long as the keys was generated with a CS-PRNG that is "feed" with decent entrophy, there is no known serious problem with RSA.

    This is not a flaw, it's just that a few percent implemented the cryptography in a bad way, and I'm pretty sure that many of them come from embedded systems.

    We are going to run a script on our database to see if we can find any weak RSA-keys, better be safe than sorry :)
     
  13. lotuseclat79

    lotuseclat79 Registered Member

    Joined:
    Jun 16, 2005
    Posts:
    5,096
    Primal Fear: Demuddling The Broken Moduli Bug.

    -- Tom
     
  14. Hungry Man

    Hungry Man Registered Member

    Joined:
    May 11, 2011
    Posts:
    9,148
    There has always been the question of whether solving the product of primes is as Hard as calculating the factors.

    In this case you're right though, the problem is that it's not being properly seeded and the RNG is popping out the same prime too often.
     
    Last edited: Feb 18, 2012
  15. mirimir

    mirimir Registered Member

    Joined:
    Oct 1, 2011
    Posts:
    6,029
    I suspect that improperly accelerated PRNG is causing at least some of this.
     
  16. lotuseclat79

    lotuseclat79 Registered Member

    Joined:
    Jun 16, 2005
    Posts:
    5,096
    Experts: RSA weak keys flaw restricted to network devices.

    -- Tom
     
Loading...
Thread Status:
Not open for further replies.