Additional Security Requirements

Security requirements

While the security requirements are specified mainly to address the known attacks on the ECDLP, there are plenty of other desirable criteria that should be met in order to guarantee secure and efficient implementation of ECC systems. Even when all the suggestions from this section are respected, there are still other possible attacks that are based on the weakness of some cryptographic protocols. Thus, Bernstein and Lange (2015)Daniel J. Bernstein and Tanja Lange. Safecurves: Choosing safe curves for elliptic-curve cryptography. http://safecurves.cr.yp.to, 2015. Accessed: 2018-11-19. argue that elliptic curves may be attacked if they are not implemented properly, although they have been designed in order to achieve ECDLP security. Thus, they define some additional requirements on their webpage SafeCurves, arguing that “there’s a gap between FCDI.P difficulty and FCC security.” SafeCurves also provides a security evaluation of different standard curves. But there are also technical requirements that should be met, which include the selection of the underlying finite field and the choice of coefficients in order to provide efficient modular arithmetic operations and efficient point compressing. However, selecting elliptic curvesDaniel J. Bernstein and Tanja Lange. Safecurves: Choosing safe curves for ellipticcurve cryptography. http://safecurves.cr.yp.to, 2015. Accessed: 2018-11-19. for cryptography is often a trade-off between efficiency and security.

Invalid curve attack

A special type of attack that addresses the weakness of cryptographic protocols is the so-called invalid curve attack, which was introduced by Biehl et al. (2000)Ingrid Biehl, Bernd Meyer, and Volker Müller. Differential fault attacks on elliptic curve cryptosystems. In Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO '00, pages 131-46, London, UK, 2000. Springer-Verlag. and later developed by Antipa et al. (2003)Adrian Antipa, Daniel R. L. Brown, Alfred Menezes, René Struik, and Scott A. Vanstone. Validation of elliptic curve public keys. In Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, PKC '03, pages 211-23, London, UK, 2003. Springer-Verlag.. The invalid curve attack exploits public-key encryption protocols that improperly validate external public keys $\mathrm{Q}$ (i.e., if the receiver of a public key does not verify if the point $\mathrm{Q}$ lies on the correct elliptic curve), which use addition and doubling formulas that are independent of a curve parameter.

For example, we can see that the formulas we defined in this proposition :Explicit_formulas_for_addition don’t involve the coefficient $B$. Thus, any elliptic curve $E^{\prime}$ whose short Weierstrass equation differs from $E$ only in the curve parameter $B$, maintains the same addition laws. Hankerson et al. (2006) refer to these kinds of curves $E$ as invalid curves relative to $E$.

Hence, an attacker can provide a public key $Q$ that lies outside of the corresponding curve, but on a different one. Since the formulas don’t depend on all domain parameters, the protocol then normally computes any scalar multiplication $k Q$ with the secret integer $k$. If the invalid point $Q$ is chosen such that the incorrect curve is weak (i.e., $Q$ has low order), the attacker is able to recover the secret key $k$ by a small subgroup key recovery attack.

This kind of attack was presented by Lim and LeeChae Hoon Lim and Pil Joong Lee. A key recovery attack on discrete log-based schemes using a prime order subgroup. pages 249-63. Springer-Verlag, Berlin, Heidelberg, 1997. and works efficiently if the cofactor $h$ has many small factors. Thus, a cofactor greater than one may enable subgroup attacks, therefore the cofactor is typically chosen very small, i.e., $h \leq 4$ by most standards.

However, an invalid curve attack can easily be avoided if the receiver of a public key $Q$ checks that $Q$ satisfies the correct given curve equation and that $n Q=\mathcal{O}$. This guarantees that $Q$ lies on the original curve (Adrian Antipa et al. (2003)Adrian Antipa, Daniel R. L. Brown, Alfred Menezes, René Struik, and Scott A. Vanstone. Validation of elliptic curve public keys. In Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, PKC '03, pages 211-23, London, UK, 2003. Springer-Verlag.).