[Cfrg] Hardware requirements for elliptic curves

[Joppe Bos <[e-mail]>]

The current discussion around the requirements, and the performance aspects,
have mainly been approached from a software implementation point of view. As
one of the authors of the NUMS curves, I have been responsible for this as
well. With this message I would like to provide a hardware perspective: more
specifically, I would like to put forward some requirements which are
concerned with hardware specific attacks. 


The current discussion is focused around deciding upon a set of requirements
in order to select new elliptic curves for usage in the TLS protocol.
However, this choice of curves can potentially have a significant impact on
the choice of the new "standard" elliptic curves used in a broader setting.
This is why a different (i.e. hardware) point of view might be a relevant
addition in the current discussion.

In the hardware setting, when implementing curve based cryptography, one
often has access to a generic modular multiplication (hardware)
implementation on a secure crypto co-processor. In this scenario, the
performance of a multiplication modulo a random prime is identical to the
performance of multiplication modulo a prime of a special shape. Not only
does the usage of specially shaped moduli not increase performance, it makes
it a lot harder to use a set of common counter-measures against certain
types of side-channel attacks (a requirement for meeting certain standards
such as Common Criteria and EMVCo). For example, scalar blinding is a
technique in which one adds a random multiple of the group order to the
scalar. If the prime p (in the definition of the finite field F_p) has a
special shape, then this shape carries (largely) over to the order of the
elliptic curve (by the Hasse-Weil bound). It is known that one can take
advantage of this special shape and attack schemes that apply scalar
blinding (e.g. see  <https://eprint.iacr.org/2014/191.pdf>
https://eprint.iacr.org/2014/191.pdf and the references therein). Therefore,
(also) specifying curves defined over random prime fields (more precisely,
an elliptic curve defined over the finite field F_p where p is a random
prime) would be a preferable additional design requirement from a hardware
point of view.

 

We will need to support prime order Weierstrass curves in the future since
we will need to keep supporting the NIST curves. Adding dedicated support
for curve arithmetic in different curve models (Edwards / Montgomery) would
increase the code size which in turn increases maintenance effort.
Furthermore, since Edwards / Montgomery curves cannot have prime order, this
requires changes to the current implementations in order to avoid
small-subgroup attacks. 
It is unclear (and an interesting question) if implementing the more
efficient group law on these different curve models is worth the increase in
code size, since the potential speedup is expected to be between a factor
one and two. Supporting Edwards / Montgomery curves in their corresponding
Weierstrass form has no advantage from a performance point of view and adds
complexity due to the composite group order. 

 

In conclusion, we think the current ongoing discussion about the
requirements needed for selecting new elliptic curves is very important.
Selecting new curves in a transparent fashion, which are more secure
compared to the current set of standardized curves by NIST, is the right
thing to do. From a hardware perspective, defining elliptic curves over
primes of a special shape has no positive performance effect and even rules
out using some common countermeasures to guard against types of side-channel
attacks. We have a strong preference for prime-order Weierstrass curves
defined over random primes. If this is not an option and if different curve
models are proposed then also providing such a curve defined over a random
prime field would be preferable. In this latter setting, it is not clear if
we would adapt the implementations to the curve model or transform to
Weierstrass form.

I hope this additional point of view is useful and will lead to further
discussion. 


Joppe Bos