Elliptic Curve Crypto
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
Invalid Curve Attacks
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
(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:
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:
These attacks are also sometimes referenced as invalid point attacks.
Attacking TLS Implementations
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?
The implementations now check whether the incoming points belong to the elliptic curve.
Is my application vulnerable, if I use only ephemeral ECDHE ciphersuites?
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.