New Math Breakthroughs in 2014 Weaken Encryption

It is amazing to me that the security of the world relies on a small handful of math concepts that were pioneered in the 1970's. The only way that we can continue to remain secure, is to increase the size of the numbers that protect our data. While there are dozens of valid ciphers out there, there's only a few methods for handing off those keys during the first steps of setting up a secure connection. Those methods are RSA, DH, and ECDH. They are compute intensive and require a lot of time to complete, so generally these connections are set up as a "handshake" where a key for a cipher is handed off securely, and then the encryption switches to those methods for much lighter computational work while maintaining data security.

These methods rely one two principles; The Discrete Logarithm Problem and techniques for factoring large integers.

New advancements in existing techniques have weakened both of these problems and increased the danger of using 1024-bit length keys for RSA and DH, and 128-bit curves for ECDH.

New records were set for attacks against both the discrete logarithm problem and elliptic curves:

A simple 9234-bit finite field was solved, which is a huge step forward in the progress of "proof of concept" solutions for the discrete logarithm problem. These examples often use small primes to make the problem easier to solve and do not represent breaking a "real world" key of this length. The small primes are used to make the problems solve-able in shorter time frames and allow optimizations and tweaks to be applied to their techniques, as well as test new methods.

Type-1 Pairings for elliptic curves, which are used in some live security software (type-3 pairings are overwhelmingly preferred), are now trivial to break. More information on pairings

And a new major discovery was made on finding very large prime numbers:

This discovery brings us much closer to an answer that has been stale for almost 80 years in mathematics.

This new algorithm can make finding very large primes easier to locate and therefore substantially reduce the amount of time spent finding them. When implemented in crypto, this will speed up the process of cracking handshakes in a big way.

The case against the 1024-bit key for Diffie-Hellman and RSA is getting overwhelming. Demand 2048-bit from your security software. Always remember: "Good enough" is not good enough.

VikingVPN uses RSA-2048 for website certificates, DHE-4096 keys that change hourly for our VPN service, and 4096-bit encryption for our PGP email.

< last
next >