Flaw Found in an Online Encryption Method

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

Not open for further replies.
1. lotuseclat79Registered Member

Joined:
Jun 16, 2005
Posts:
5,390
Last edited: Feb 15, 2012
2. x942Guest

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. EncryptedBytesRegistered 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. BaserkRegistered Member

Joined:
Apr 14, 2008
Posts:
1,321
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."

5. Hungry ManRegistered Member

Joined:
May 11, 2011
Posts:
9,146
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. BaserkRegistered Member

Joined:
Apr 14, 2008
Posts:
1,321
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'...

7. Hungry ManRegistered Member

Joined:
May 11, 2011
Posts:
9,146
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. x942Guest

Thank you for clarification

9. x942Guest

Thanks for the info as well

10. BaserkRegistered Member

Joined:
Apr 14, 2008
Posts:
1,321
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. x942Guest

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. CountermailRegistered Member

Joined:
Aug 7, 2009
Posts:
169
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. lotuseclat79Registered Member

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

-- Tom

14. Hungry ManRegistered Member

Joined:
May 11, 2011
Posts:
9,146
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. mirimirRegistered Member

Joined:
Oct 1, 2011
Posts:
9,252
I suspect that improperly accelerated PRNG is causing at least some of this.

16. lotuseclat79Registered Member

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

-- Tom