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.

by