Flaw Found in an Online Encryption Method

Flaw Found in an Online Encryption Method.

Ref: Researchers find flaw in key generation with popular cryptography.

Related article: Crypto shocker: four of every 1,000 public keys provide no security.

-- Tom

 

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?

 

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

 

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

 

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.

 

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'...

 

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.

 

Thank you for clarification

 

Thanks for the info as well

 

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).

 

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.

 

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

 

Primal Fear: Demuddling The Broken Moduli Bug.

-- Tom

 

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.

 

I suspect that improperly accelerated PRNG is causing at least some of this.

 

Experts: RSA weak keys flaw restricted to network devices.

-- Tom