Next week at ESORICS, I am going to present our newest research paper on attacking elliptic curve implementations (it is a joint work with Tibor Jager and Jörg Schwenk). It might be of interest especially for people who like practical crypto attacks...or for anybody who hates Java, since the attacks were applicable to two out of eight analyzed libraries: Bouncy Castle and Java Crypto Extension (JCE). The result is quite interesting since the attacks allow an attacker to recover private EC keys from different applications, for example, TLS servers.
For cryptographic purposes, elliptic curves have to be chosen very carefully, because from the curve points we want to establish our keys. Thus, a careful selection should give us a curve with a large set of points. These points form a group G with a generator point P (base point) with order n. The order defines the smallest number such that (n+1) * P = P. In other words, if we execute the ADD operation with the base point (n+1) times, we visit all the points on the curve and get back to the base point.
Generating a secure elliptic curve is not that easy. Therefore, predefined elliptic curves like brainpool or NIST are typically used in security protocols like TLS. Note that the described attacks apply only to the curves described by the equation y^2 = x^3 + ax + b, in particular to the NIST curves.
If you want to get more information on this topic, you can for example take a look at the articles of Andrea Corbellini: http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
This may seem to be strange, but it could have serious consequences. The problem is that the invalid point could belong to a different curve E', which consists of a very small number of elements.
Let me give you an example. Consider a server using NIST-256 (secp256r1) elliptic curve. This curve has a huge number of elements. However, if we force the server to compute with a given curve algorithm and the point
x: 82794344854243450371984501721340198645022926339504713863786955730156937886079
y: 33552521881581467670836617859178523407344471948513881718969729275859461829010
(which does not belong to this NIST curve), we get only five possible results (four points and a point in infinity). The resulting group of this invalid curve has an order 5. See the following figure.
If you want to play with elliptic curves or use it in your lectures, you can take a look at this tool I built some time ago:
https://github.com/RUB-NDS/EccPlayground
Ok...but what does this bring us?
This is quite simple. We now know all the points on the invalid elliptic curve E'. If we send the invalid point P' to the server, the server computes secret sP'. The secret can have only 5 possible values. If we are able to learn the result sP', we then also learn s1 = s mod 5.
We repeat this for points with orders of 7, 11, 13..., until we can compute a CRT and thus learn the server private key. Easy :)
There are some complications since we typically learn only the x-coordinate of the resulting point, see our paper for more details:
https://www.nds.rub.de/research/publications/ESORICS15/
These attacks are also sometimes referenced as invalid point attacks.
Elliptic Curve Crypto
Elliptic Curve Cryptography (ECC) is one of the cornerstones of modern cryptography, due to its security and performance features. It is used in key exchange protocols as well as for computing signatures, or for constructing secure random number generators with backdoors (Dual_EC_DRBG).
In order to understand the basic idea behind our attacks, you just need to know that an elliptic curve E in cryptography is a set of points over a finite field satisfying the following equation:
E: y^2 = x^3 + ax + b
On the elliptic curve, a single operation can be executed: point addition.For cryptographic purposes, elliptic curves have to be chosen very carefully, because from the curve points we want to establish our keys. Thus, a careful selection should give us a curve with a large set of points. These points form a group G with a generator point P (base point) with order n. The order defines the smallest number such that (n+1) * P = P. In other words, if we execute the ADD operation with the base point (n+1) times, we visit all the points on the curve and get back to the base point.
Generating a secure elliptic curve is not that easy. Therefore, predefined elliptic curves like brainpool or NIST are typically used in security protocols like TLS. Note that the described attacks apply only to the curves described by the equation y^2 = x^3 + ax + b, in particular to the NIST curves.
If you want to get more information on this topic, you can for example take a look at the articles of Andrea Corbellini: http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
Elliptic Curve Diffie Hellman in TLS
The goal of an elliptic curve Diffie Hellman (ECDH) key exchange is to establish a common secret between two parties, for example between a client and a server. Let us assume both parties compute the secret using an elliptic curve E with a base point P. The client has a private key q and public key qP and the server has a private key s and public key sP. In order to establish a common secret, they exchange their public keys and establish a secret: q(sP) = s(qP). Typically, the x coordinate of the computed point is used as a secret.
In case of TLS, this key exchange is used to compute a common premaster secret. For this purpose, the server sends its public key in the certificate message. The client sends its public key in the ClientKeyExchange message. Afterwards, both parties are then able to compute premaster secret pms = q(sP) = s(qP). From this premaster secret, master secret and further keys are derived. The client and server prove the possession of these keys by computing correct Finished messages.
Invalid Curve Attacks
Now, we know how to use elliptic curves for exchanging keys and that it is crucial for the key exchange to use secure elliptic curves, containing elements with high order. However, what happens if the client forces the server to compute a common secret using a point outside of the defined curve?
This may seem to be strange, but it could have serious consequences. The problem is that the invalid point could belong to a different curve E', which consists of a very small number of elements.
Let me give you an example. Consider a server using NIST-256 (secp256r1) elliptic curve. This curve has a huge number of elements. However, if we force the server to compute with a given curve algorithm and the point
x: 82794344854243450371984501721340198645022926339504713863786955730156937886079
y: 33552521881581467670836617859178523407344471948513881718969729275859461829010
(which does not belong to this NIST curve), we get only five possible results (four points and a point in infinity). The resulting group of this invalid curve has an order 5. See the following figure.
If you want to play with elliptic curves or use it in your lectures, you can take a look at this tool I built some time ago:
https://github.com/RUB-NDS/EccPlayground
Ok...but what does this bring us?
This is quite simple. We now know all the points on the invalid elliptic curve E'. If we send the invalid point P' to the server, the server computes secret sP'. The secret can have only 5 possible values. If we are able to learn the result sP', we then also learn s1 = s mod 5.
We repeat this for points with orders of 7, 11, 13..., until we can compute a CRT and thus learn the server private key. Easy :)
There are some complications since we typically learn only the x-coordinate of the resulting point, see our paper for more details:
https://www.nds.rub.de/research/publications/ESORICS15/
These attacks are also sometimes referenced as invalid point attacks.
Attacking TLS Implementations
Attacking TLS is not that straightforward since a TLS server does not respond directly with the computed premaster secret sP'. Instead, first the client has to prove he is in possession of a correct premaster secret, by sending a ClientFinished message.
This is however not a big deal. Everything what we need to do for learning sP' is to establish several TLS handshakes. Given a point P' of a small order, we just need to compute premaster secrets pms1=P', pms2=2P', pms3=3P' etc., and use them to compute ClientFinished messages in the handshakes. If the server accepts the ClientFinished message, we know our guess was correct. See the simplified process below.
This way, we can establish our oracle from a TLS server.
Evaluation
We evaluated 8 crypto libraries and their vulnerabilities to invalid curve attacks. We found out that the Bouncy Castle library and the Oracle JCE provider were vulnerable and we could extract private keys from the TLS servers running these libraries. The attacks are quite powerful. For Bouncy Castle, we needed about 3300 real server queries. For Oracle JCE, we needed about 17000 real server queries. We tested with the NIST-256 curve. The high number of requests needed for the Java servers results from a strange behaviour (bug?) in the Java EC computation. You can get more information on the evaluation in our paper.
If you use these libraries for EC, you better update them and possibly revoke your old EC keys.
FAQ
What is the difference to the Heartbleed attack?
The Heartbleed attack was also used to recover private keys. However, it could be applied to OpenSSL (which is much more widely used) independently of the used key types. Our attack can only be used against Java implementations using static EC keys (e.g., TLS servers using TLS_ECDH_* ciphersuites). On the other hand, our attack is more general, since it does not apply only to TLS, but can be independently used of the protocol. In our work, we analyzed TLS servers just to prove feasibility of the developed attacks (and because if you nowadays hack TLS, everybody is scared).When were the vulnerabilities fixed?
Bouncy Castle was fixed in version 1.51. Java was fixed with the critical security update in July 2015: http://www.oracle.com/technetwork/topics/security/cpujul2015-2367936.html (CVE-2015-2613). If you used your EC keys before the updates, we better encourage you to update these keys...
The implementations now check whether the incoming points belong to the elliptic curve.
The implementations now check whether the incoming points belong to the elliptic curve.
Is my application vulnerable, if I use only ephemeral ECDHE ciphersuites?
In case of an ephemeral Diffie Hellman, the server generates an EC key dynamically with each client request. This makes our attacks infeasible, since we rely on the fact that the server reuses the same key.
The attack could still be applicable if the server would cache the EC keys and reuse them in several connections, as is the default case in OpenSSL. However, we could not observe this behaviour in Java servers.
UPDATE: Please note that JSSE per default uses static ECDH ciphersuites if you initialize it with an EC key (i.e. an ECDSA certificate). This is also the default case for other servers based on JSSE. Just tested with the default config for Apache Tomcat 7.0.64.
UPDATE: Please note that JSSE per default uses static ECDH ciphersuites if you initialize it with an EC key (i.e. an ECDSA certificate). This is also the default case for other servers based on JSSE. Just tested with the default config for Apache Tomcat 7.0.64.
What is actually new about this attack and what is your contribution?
The attack was (to the best of our knowledge) first described by Ingrid Biehl, Bernd Meyer, and Volker Müller at CRYPTO 2000: Differential fault attacks on elliptic curve cryptosystems. We showed that the attack is still relevant to some widely used implementations and we analyzed how to overcome a strange behavior of Java (see our paper).
Are you going to make the code public?
Yes, in the future...
I am the admin of www.xyz.com and I lost my private key. Could you recover it?
Of course, for this reason we closely cooperate with the Hacking Team. Send your inquiries to ec@hackingteam.it
What is the name of the attack? What is the logo?
Invalid Curve Attack 3000++. No logo. Yet.
Great, where can I learn more about crypto attacks?
You can for example visit our workshop at Deepsec ;)
Maybe, you will learn about more implementations vulnerable to these attacks...
