Friday, December 4, 2015

Breaking Diffie Hellman security with massive computing

Following blogpost and paper talk one possible method NSA would have used to read IPsec and SSL encrypted data.

https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/

And detailed paper here:  https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf

Both IPSec and SSL/TLS use DH algorithm to get hold of shared secret without sharing the actual secret.  Please see my previous post on this :  http://netsecinfo.blogspot.com/2015/12/diffie-hellman-so-well-explained-here.htmlo note is that prime number 

I don't understand all mathematical details presented in the paper.  But important thing to note is that in IPSec and SSL,  DH prime number and  base numbers are not secret.  They are sent in clear between the parties.  Prime numbers are even advertised. For example,  IPSec RFC 3256 defines the prime numbers for various DH Groups.

According to the paper:

"The current best technique for attacking Diffie-Hellman relies on compromising one of the private exponents (a, b) by computing the discrete log of the corresponding public value (g a mod p, g b mod p).
"

Once the private exponents are known via the massive compute power,  getting hold of shared key is not a problem as it is well known technique used to compute the shared secret.

My initial reading was that the large amount of computation power is required to get hold of private exponents for every DH operation.  Apparently,  that is not true.  Once a particular shared secret is retrieved, any further DH exchanges can be broken with smaller compute power.  That is, some part of intermediate computational results can be reused.  That way,  any attacker need to invest only one time on massive computational power.  Then rest of DH exchanges can be broken with little compute power as long as same prime is used in new DH exchanges.

Now that this news is out,  this may be done by malicious entities. That is actually more concerning.

What are alternative solutions?

- Use EC version of DH.
- Create new primes for each tunnel and exchange the prime number.

Any other solutions?

Thanks
Srini

No comments: