Elliptic Curve Cryptography: computing shared key
If Alice and Bob want to exchange encrypted messages, they need to first agree on a Key. This shared key (also known as symmetric key) will be used to by both parties to encrypt messages. There are many ways of arriving at the shared key (including the old fashioned method where Alice calls up Bob) and the procedure is called Key Exchange. One of the relatively newer methods of key exchange uses a mathematical construct called Elliptic Curve.
Before we get into how Elliptic Curve Cryptography can be used to compute a shared key, let’s look at how it is done with the classical Diffie-Hellman protocol, which was published in the late seventies.
Diffie-Hellman (DH) is a protocol by which 2 parties can independently compute the same shared key even while communicating over an open channel. Even if the adversary sees the messages being exchanged, it will him take eons to compute the shared key. This is because the adversary will only see g^x and g^y [^1], and computing x and y from them requires computing discrete logarithms, which is a very hard problem when the numbers involved are huge. There is no efficient classical [^2] algorithm for computing discrete logarithms.
A few decades ago, 512 bit DH group provided adequate security against attacks. Now, 1024 bit is probably breakable with the resources available to a nation-state and therefore 2048 bit is the current recommendation. This is due to improvements in mathematical techniques over the years (the current champion is called NFS or Number Field Sieve) and the fact that this computation can be partitioned and performed on hundreds of thousands of relatively inexpensive computers. Attackers can also take advantage of the fact that for a given DH group, almost all of the work required to find the discrete logarithm can be precomputed ahead of time. This precomputed result (which, by the way requires several gigabytes of storage) can be used to significantly speed up all future discrete logarithm calculations as long as the 2 parties pick private keys from this group.
Export Quality and unintended consequences
Typically when we use the term export grade or quality, it means superior quality. However, when it comes to Crypto software, it is the exact opposite. ‘Export-grade’ crypto in software created in USA for some chosen countries has much less strength (40 bits for ciphers and 512 bits for key exchange). One can assume that these sizes were chosen so that they can be broken in a short time with the resources available to the US government agencies at that time. Needless to say that these agencies can break them in near real time today.
Though the US relaxed export controls by 2000, the export-control code was not removed from many crypto (TLS) libraries and this is where the unintended consequences comes in. The presence of this code, combined with bugs in the implementation, flaws in the TLS protocol and re-use of keys resulted in the discovery of two attacks this year, which were cleverly named FREAK (Factoring RSA Export Keys) and LOGJAM (a play on discrete logarithm), the former on RSA key exchange and the latter on Diffie-Hellman key exchange. LOGJAM attack is possible in real time during a TLS handshake because
-
man-in-the-middle attacker has fooled the 2 parties (or client and server) into using a very low strength 512 bit DH export group.
-
Due to a protocol flaw, the client doesn’t realize that the server is negotiating a 512 bit DH group.
-
80% of the web sites use one of two well known Diffie-Hellman groups and
-
the attacker, with the resources available to a nation-state, has precomputed the database for both the groups and can complete the second step in near-real time and compute the discrete logarithm! If the attacker needs a bit more time (say 30 or 40 seconds) to complete the second step, he can avoid handshake timeouts by sending messages to reset the timeout clock!
Increasing usage of Smartphones
Smartphones are increasingly being used for communication, eCommerce etc and while they are getting faster and faster, they have less CPU, memory and energy (battery) resources when compared to laptops and desktops. Therefore use of the recommended 2048 bit DH group on smartphones and embedded devices will take more CPU time and also consume precious battery resources. This is where Elliptic Curve Cryptography comes to the rescue.
Elliptic Curve Cryptography
Elliptic Curve Cryptography has 2 advantages:
-
A 256 bit Elliptic Key will provide the security equivalent to a 128 bit symmetric key. To get the same security using classical Diffie-Hellman it would take more than 3000 bits.
-
There haven’t been any improvements in algorithms in the past few decades, despite lot of research.
To get the security equivalent to 256 bit symmetric key, a 512 bit Elliptic key will suffice but with classical Diffie-Hellman you need a key with more than 15000 bits!
Daniel Julius Bernstein (djb), a professor of mathematics and computer science is well regarded for his contributions to Cryptography. He has published an elliptic curve and associated software and it has found wide use not only because it is very good but also because it didn’t originate from NIST! djb has named it Curve25519 because the prime number used is (2^255 – 19). The elliptic keys are of length 256 bits, providing the strength equivalent to a 128 bit symmetric key.
Say Alice and Bob want to independently compute a shared key so that can encrypt messages with that key. They are using Smartphones and so don’t want to use the recommended 2048 bit Diffie-Hellman keys for the reasons mentioned above. They can use djb’s 256 bit Elliptic Curve Diffie-Hellman (Curve25519) which will give them the strength equivalent to a classical Diffie-Hellman key of more that 3000 bits, while consuming lot less time, memory and energy.
Bernstein has provided a Curve25519 library to compute private and public keys and this has been ported to many languages. Alice and Bob use that library and do the following:
Steps:
1) Alice generates a 256 bit random key, her secret key.
2) Alice computes 256 bit private key from the secret key.
3) Alice computes 256 bit public key from the private key.
4) Bob generates a 256 bit random key, his secret key.
5) Bob computes 256 bit private key from the secret key.
6) Bob computes 256 bit public key from the private key.
7) Alice and Bob share each other’s public key.
8) Alice computes the shared key using her private
key and Bob’s public key.
9) Bob computes the same shared key using his private key and Alice’s public key.
These steps are shown in the figure below.
As you can see, both Alice and Bob compute the same 256 bit (32 byte) shared key 0x44793AEDC74C1C586BB8EF8223DBB12E267C18209477EC181145A5DF5AB27B4F.
Alice and Bob can now use the shared key as key material to derive shared keys and use them to communicate securely.
I have written programs that demonstrate the steps listed above. In fact, the picture above is taken from the windows version of the program. I also wrote Android and iOS versions of this demo.
The source code for the Windows version (written in C#) is available in github at https://github.com/babusri/EccDHWinC.
The code for the windows version in F# (lot more compact) is available at https://github.com/babusri/EccDHWinF.
You can use the free community version of Visual Studio 2015 to build and run them.
The source code for the Android version (written in C#, using Xamarin) is available in github at https://github.com/babusri/EccDHDroidC.
The source code for the iOS version (written in C#, using Xamarin) is available in github at https://github.com/babusri/EccDHIosC.
You can used the free starter edition of Xamarin Studio IDE or the free Xamarin plugin for Visual Studio to build the Android and iOS apps.
Or you can download the Android app and install it.
[^1]: actually (g^x) mod p and (g^y) mod p, where p is a large prime number.
[^2]: a quantum algorithm was published 20 years ago but it will be a while before we have h/w to run it!