Friday, October 24, 2014

ECC, See? Si?

With cryptography being based on mathematical manipulation of data, mathematics and strong computers are the potential tools for breaking the encryption. Thousands of scientists and hackers are working diligently to find holes and vulnerabilities in common encryption technology (such as the HeartBleed vulnerability in the HeartBeat extension to TLS), and the computes that are available to them are becoming faster and cheaper.

Keeping ahead of the enemy has been going in two directions. One is making the math “longer” by using longer keys. If you switch from a key that’s 512 bit long to a 1024 bit key, it will take a computer a lot longer to break it (breaking the current 2048 bit keys used in many SSL certificates is considered to be unfeasible with today’s computing power). The other direction is making the math more complex by designing algorithms that will be more effective and harder to break.

Over the years, we’ve seen the industry move from one algorithm to another, and the latest generation in cryptography is ECC – Elliptic Curve Cryptography. ECC is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. Quote from Wikipedia:

Public-key cryptography is based on the intractability of certain mathematical problems. Early public-key systems are secure assuming that it is difficult to factor a large integer composed of two or more large prime factors. For elliptic-curve-based protocols, it is assumed that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is infeasible — this is the "elliptic curve discrete logarithm problem" or ECDLP. The entire security of ECC depends on the ability to compute a point multiplication and the inability to compute the multiplicand given the original and product points. The size of the elliptic curve determines the difficulty of the problem.

Finite Fields? Intractaility? Discrete logarithm? Publicly known base point? If that mambo-jumbo gives you a headache, let’s simplify it a bit….

Encryption is based on encrypting your data using some kind of key, and then decrypting it on the other side. For the other side to do so, it would have to have the key. In classic encryption (for example, a spy working behind enemy lines), the decryptor would have the key beforehand (a.k.a. “Preshared key”), but when two computers are talking over the internet, they can’t do that (assuming you don’t plan on flying out to San Francisco to pre-share a key with eBay or Gmail). Instead, the concept of a public/private key was developed. This is a special piece of math where the sender and recipient use TWO keys. You use one key to encrypt the data, and the other to decrypt it. The math is such that the key used for the encryption cannot be used for the decryption. The first key is designated as the “private” key, and the other the “public” key.

When a cryptographic session starts, the server gives the client its “public” key. The client then generates a unique two-way key that will be used JUST for this session. The client encrypts that two-way key using the server’s public key, and sends it over. Because of the way this math works, only the server can decrypt the key, because only the server has the “private” key. Once it decrypts the encrypted two-way key, both sides have effectively shared a regular key and they can start using it to both encrypt and decrypt subsequent data.

Well…why switch to a two-way key? Why not just use this private/public system for the whole session? The reason is that the math required for this is complex and slow, and if we did that, it would take a long time to transmit the message. Also, if someone was recording the encrypted data, and the private key was ever hacked, every session ever done would be compromised. With the two-way session key, every unique session is protected individually.

So, private/public encryption and decryption are complex and slow, and we keep lengthening the keys to keep up with increasing computer powers…and in comes ECC. Elliptic Curve is based on special math that uses special functions in the family of y2=x3+ax+b. These functions, if plotted, create a curve that’s elliptical. For example:


The math makes it much harder to break, which means an ECC based encryption using a 256 bit key would take as much time to break as a traditional encryption using 2048 bit keys. This means that by using this technology, you are reducing the load on your server significantly, and that means a lot of you are running a website servicing millions of people a day (just think of how much money you can save by using 100 servers instead of 800!). Alternatively, you could stick to the same key length and achieve 8 times the security (as in, it would take 8 times as long to break the key).

I should note that in the real world, things might not be as clearly defined as I stated above. Switching to ECC doesn’t really mean you can ditch 87.5% of your servers, because there are probably other bottle necks. There are other considerations such as compatibility…if your switch to using ECC on your server, your clients need to support it too, and not all clients do (for example, Windows XP doesn’t, and it still comprises a large chunk of the web client market).

Next time I’ll talk more about the practical aspects of using ECC.

No comments: