Towards Elliptic Curve Cryptography

Cryptocat relies on generating 4096-bit Diffie-Hellman keys in order to secure conversations effortlessly without the need for parties to agree on a pre-shared key. This has the following advantages:

  1. Diffie-Hellman is relatively mathematically simple, and thus easier to implement.
  2. 4096-bit keys are considered very strong, in terms of asymmetric systems.
  3. Diffie-Hellman hasn’t lost its strength is still considered strong despite being around since 1976, and is used very widely today.

However, Diffie-Hellman suffers from the following disadvantages:

  1. Long keys result in more CPU-intensive key generation (to be fair, this is noticeable only on mobile devices) and some extra overhead for public key exchange.
  2. Even 4096-bit Diffie-Hellman asymmetric keys do not match the strength of a 256-bit symmetric AES key. In fact, when compared to AES, a 4096-bit Diffie-Hellman key would give around 170 bits of security. This means that the security of the AES-256 encrypted message is effectively reduced to 170 bits when encrypted using a 4096-bit Diffie Hellman key.

While the effective security mentioned in (2) is not by any means weak (even AES-128 is still considered strong,) we should strive to (a) find less CPU-intensive public key systems that (b) do not reduce the level of effective security provided by AES-256. The answer is Elliptic Curve Cryptography.

Consider this table, provided courtesy of the NSA:

As pointed out above, it would take a 15360-bit Diffie-Hellman key to match the effective security of AES-256. While 4096-bit keys are problematic on mobile devices, 15360-bit keys would be even more problematic on today’s desktops and are definitely out of the question. Furthermore, the overhead would be pretty ridiculous.

The Elliptic Curve key size, however, is very attractive. We can achieve public key strength that matches the cryptographic strength of AES-256 with almost eight times less the asymmetric key size. This single advantage would dramatically reduce both CPU usage during key generation, and network overhead during key exchange.

This is why future versions of Cryptocat will drop Diffie-Hellman and adopt Elliptic Curve Cryptography instead. Unfortunately, Elliptic Curve suffers from a relative lack of documentation when compared with Diffie-Hellman or RSA (being a relatively recent algorithm,) and uses much more complex math.

It will take time for a correct, efficient and tested implementation to appear in Cryptocat.

Update: here’s a collection of papers on Elliptic Curve Cryptography that may be useful to anyone trying to learn more about the subject.