Tag Archives: Diffie Hellman

The Future Of Cryptography

Sorry, this post may be a little geeky.

I have said that the world of SSL is terminally broken.  Now I have some agreement.  And the guys saying it are not “some guys in a diner”.   They won the best paper award at the 22nd ACM Conference on Computer and Communications Security.  And they are saying that what is broken is much more than SSL.

Diffie Hellman Key Exchange (DHKE), the basis of a lot of SSL, VPN and SSH traffic, they say, is broken.  Diffie Hellman is based on prime numbers.  Very large prime numbers.  Unfortunately, as these prime numbers get large, it is very difficult to find the next week.  There is a program called GIMPS that uses massively distributed computing and has only found 15 new primes since 1996.  Of course, those numbers have 22 million digits each.

Anyway, given that these primes are known, you can do precomputing to compromise DHKE, at least in some cases, right now.  Many people think that the NSA is doing just that.  While complaining that the Internet is going dark.

The NSA’s plan was to replace the traditional DHKE with elliptic curve, but then, suddenly, they did a 180 about face (more about that in a future post) and told everyone they were  just kidding.  NSA’s Suite B, which is used to encrypt data up to the top secret level was all about elliptic curve.  Until the standard was unceremoniously yanked and replaced with a new standard that doesn’t use the words elliptic curve.

Why?  They mumbled something about Quantum computing, but what is much more likely is that they have figured out a way to compromise the fundamental math in elliptic curve.

What is clear here is that we have a problem and we don’t have a solution.  What is worse is that there are some people who like it that way, some people who don’t understand the problem and a few people would would like to fix it.

But, give the current standards process, even if we invented a solution tomorrow, which is not likely, it would not be approved as a standard for years and would take more years to roll out.

Which means, for the foreseeable future, we are kind of in trouble.


How The NSA Broke Trillions Of Encrypted Connections

Encryption can be very secure.  Or Not.  It depends on how it is implemented.  Apparently, at least according to some sources, most of the Internet has gotten it wrong.  That’s not very comforting.

The rules of who people are protecting themselves from has changed from just a few years ago.  Now we are talking about nation states and extremely well funded hackers.

Here is the flaw.  The most common form of encryption is what is behind HTTPS,  VPNs and SSH.  Part of that protocol is to exchange keys between the sender and the recipient and is called Diffie Hellman or DH.   Those keys secure the communications used in eCommerce (such as Amazon) or your bank (such as Chase or Citi).

Apparently, most common DH implementations use one of two 1,024 bit prime numbers as part of the process.

Cracking one of these numbers would allow the NSA to decrypt two thirds of the VPN connections and one quarter of the SSH sessions around the world.

Cracking the second of these numbers would give the NSA access to 20% of the top 1 million web site.

According to the article, it would likely have taken the NSA a year and a few hundred million dollars.  Given the payback, this is a no brainer.

Obviously, the NSA is not confirming this, but this is what researchers think.

The solution is either to increase the size of the numbers that the web site is using (from 1,024 bits to either 2,048 bits or 4,096 bits), which makes the computation required to crack the keys out of reach of the NSA or at least change the software to not use one of these standard primes.

Some web sites (I just checked Google and Facebook) have already upgraded to more secure solutions.  Hopefully, they are not using “standard” numbers, but that leaves tens of millions of web sites and VPNs still susceptible.  Hopefully, many of these are in the Mideast!

VPN and SSH administrators can control their key size, making the encryption much more difficult to crack – but they must do that;  the users usually cannot do that themselves.  For users of web sites, the web site has to make the change.  All the user can do is complain and hope they fix it.

Which is why security IMPLEMENTERs have to be so careful.

Information for this post came from Reddit and The Hacker News.