ECC beauty and legacy beast

Picture yourself in an Abelian group on a two-dimensional finite field with identity point at the infinity and group generator…

Sometimes technology resembles psychedelic pictures of the 60’s – in a good way. Elliptic curve cryptography primitives are an example of such technology. When – as a programmer – you dive into them, you find yourself in a spectacularly simple yet effective machine. I am still talking about the ECC! While working on a project which uses ECC primitives I started wondering: why only a handful of protocols use these? Why is such beautiful tool as ECDSA left alone in the corner and everyone dances with bigger and bigger hammers like RSA?

It is worth noting that understanding the mathematics behind ECC is not exactly simple – but it is also not hard at all. You just need to familiarize yourself with group and group operations, look at the hard problems of elliptic curve (reversing point addition for a start) and then play with examples on really small finite fields with simple elliptic curves.

This experience is not necessary to implement anything using ECC, but if you do it you will find yourself in much better position for designing anything new involving ECC.

The benefits from programmer’s point of view are obvious:

• small footprint,
• efficient computation and
• higher security parameter

Small footprint does not mean only small key sizes compared to discrete-logarithm-based cryptography schemes. It also means the implementation is less memory intensive which is especially important on embedded systems. The same applies to the efficient computation benefit – either you lack resources and need to perform cryptography without crippling other functionality or you have CPU resources but you want to scale. Second scenario being common in the data center. Of course if you posses enough power CPU-wise and do not care about efficiency, this is not much of a benefit to you then.

For security freaks the important benefit is an easy way to use high security parameter. Reaching the so-called 128-bit security you just need 256 bits for a private ECDSA key which is much less than you need with DSA or RSA. There even if you do not care about efficiency, the security parameter could be the key benefit for you.

But the real question is how to leverage ECC in your programs? For connection-oriented encryption you usually get a SSL/TLS library these days and just use standardized protocols. With ECC it is not so simple because standard protocols are only right now catching up with the possibilities. Yes, it is now possible to enable ECC on TLS handshakes, use ECC primitives for X.509 certificates and so on. But the real question is – can you forcibly use ECC and only ECC?

Imagine you can not. There are still implementations readily available. For us from the C++ development background there is Crypto++ library. It contains all the ECC primitives, ready to use without any bloat around. Actually implementing your own protocols from ECC primitives using Crypto++ counts easily as fun activity. Look at EDCH key exchange:

// Random pool and domain parameters
AutoSeededRandomPool rng;
ECDH<ECP>::Domain dhA(secp256r1()), dhB(secp256r1());

// Generate both pairs
SecByteBlock privA(dhA.PrivateKeyLength()), pubA(dhA.PublicKeyLength());
SecByteBlock privB(dhB.PrivateKeyLength()), pubB(dhB.PublicKeyLength());
dhA.GenerateKeyPair(rng, privA, pubA);
dhB.GenerateKeyPair(rng, privB, pubB);

// Agree upon shared secret
SecByteBlock sharedA(dhA.AgreedValueLength()), sharedB(dhB.AgreedValueLength());
dhA.Agree(sharedA, privA, pubB);
dhB.Agree(sharedB, privB, pubA);

This simple example is based upon http://www.cryptopp.com/wiki/Elliptic_Curve_Diffie-Hellman#Key_Agreement and it nicely illustrates the usage simplicity. At the end both
sharedA and sharedB contain the shared secret both parties agreed upon.

Now let us get back to TLS libraries. Yes, you can configure them to use ECC and only ECC but the other side might not have an up-to-date version installed and you limit which peers you can communicate with. Or look at the X.509 certificates – it is perfectly possible to generate certificates with ECDSA keys but you can never be sure if they will be usable everywhere. The legacy of the cryptography past will not easily disappear.

There are still applications in the wild using certificates with MD5 hashing which was successfully broken years ago. But this is just a part of a bigger picture – if we steer a bit to the world of symmetric cryptography we see the same problem with RC4 stream cipher being used a means of protecting HTTPS communication. And everybody is afraid to disable the support for such dinosaurs. You never know what you break with such radical step.

Ultimately the future will push a higher demand for deprecating legacy cryptography schemes. Not only the broken ones but also those less efficient – from various points of view. This push will – hopefully – lead to huge TLS specification cleanup or maybe will serve as a starting point for brand new encrypted layer protocol suite.

In the near future it is probably best to try to educate all the interested parties to disable inherently broken parts of the protocols used and promote encryption suites that have smaller footprint, higher security parameter and generally are designed with certain standard from ground up. This is gonna be a lengthy and boring task, but hey – they didn’t build Rome in a few days.

Anyway, see ya all next week!