[Cfrg] Requirements for elliptic curves with a view towards constrained devices

[RONDEPIERRE Franck <[e-mail]>]

Dear all,

Please find below the Oberthur Technologies position in the current CFRG curve selection.

It seems that the current CFRG discussion quickly swiped the "hardware" point of view, qualifying it as out of the topic.
We think that all the points raised by Joppe Bos are relevant about the hardware context and may deserve a second thought if we take into account the range of possible devices that will implement the new TLS curves. Indeed, more and more devices are connected via the Internet and all those devices don't share the characteristics of a PC. For instance, embedded constrained devices such as secure elements in smartphones may have to process TLS authentication/key agreement in the future.
In what follows, we investigate the impact of migrating to Edwards curves, the performances needs, and finally we suggest some new security considerations in the curve selection/generation.

For some devices, the code size is the main limitation and hence has to be taken into account prior to speed performances. We analyze hereafter the impact of switching to Edwards curves while keeping Short-Weierstrass ones for backward compatibility.
The efficient implementations of Short-Weierstrass and Twisted Edwards (or Montgomery) formulae are quite different. Not only the group law operation is different but also the precomputations and the internal point representations are different. It thus doubles all the multiplication implementations: fixed-base case, variable-base case, double-scalar case.
Hence being compliant with all these implementations has a high impact on the code size, which may become impractical for some devices.
Besides, it also has a huge impact on the required time to develop in assembly language the corresponding code. To ensure up to date security and performances, hardware is constantly changing and so must be the drivers. However the development has to be as short as possible to respect the time to market strong constraints which cannot afford a double development period.

For us, it still remains unclear whether the performances are the main limitation of the TLS deployment or not. It is unclear too if the performances of the cryptography layer (especially the asymmetric part) is/would be the bottleneck in communications over the Internet. Indeed, best current latency values are around few milliseconds [1] while a Signature and a Key Agreement on a Short-Weierstrass 256-bit curve is around 250 µs (according to the Microsoft publication [2] and taking a 2GHz CPU). Stated like this, it seems that the network is the main limitation rather than cryptography. Furthermore, google.com, which is by far the most consulted website, currently processes around 10^5 requests per second (according to 2013 figures in [3] and assuming that 80% of the daily requests are made in 12 hours). It means that only 25 2GHz CPUs are needed for Google to open secure channels with their customers in the world. Hence performances may not be the overwhelming criteria in a curve selection for the internet use.
However when performances matters, why not taking Short Weierstrass curves with a=0? Indeed, in such a case doublings are evaluated roughly as fast as in the Twisted Edwards case (2M+5S+12A against 3M+4S+6A) especially in a PC context (where S<M and A<<M). Hence, by using the large amount of memory available in such a context to decrease the number of point additions in a scalar multiplication, one can obtain faster implementations compared to what is currently possible with a=-3 curves. The gap between such curves and Twisted Edwards ones would not be that large (about 5-10%, Edwards curves remaining best). The choice a=0 may hence benefit to both software and hardware worlds.

For the sake of simplicity, the twist security is viewed as mandatory. Indeed, this allows to get rid of attacks without relying on the implementation. Without this requirement, a point on curve test is needed to thwart the attacks.
At the opposite, the cofactor=1 is not viewed as mandatory. So in this case, thwarting the attacks (here, small subgroup attacks) would rely on the implementation. Several countermeasures exist which often imply an additional scalar multiplication.
We think that this situation is not coherent, especially since the countermeasure for the twist security is insignificant compared to the ones for the small subgroup.
Also for convenience, we think that the new curves should keep p=3 mod 4 as it is the case for most NIST and Brainpool curves: it allows simpler implementations and backward compatibility.

Eventually, it would be greatly appreciated that a curve design takes into account side-channel attacks against Short Weierstrass curve format such as the attack in [4] (even in the selection of Twisted Edwards curves in case those are used with their Short Weierstrass form).
This side-channel attack uses the fact that a zero value may appear in an intermediate result in the computation of the scalar multiplication, and that zero-value cannot be randomized with classical countermeasures. However, selecting a curve with cofactor equals to 1 avoids points such as (x,0) and having b a quadratic non-residue avoids the points (0,y). Furthermore, having a=0 and either 5 a QR value or 4.5^{-1}.b a non-cubic residue also prevents zero-values to appear in any doubling operations.
Even in the context of PCs, it seems that side-channel security should be more and more of concern as shown at the CHES conference last September and especially for this kind of attack.

In conclusion, we consider this curve selection as very important since it fits the needs of two different worlds. Reaching a consensus will greatly benefit to the development of EC cryptography for the best of our everyday life. In order to reach this goal, we propose the following curve characteristics to obtain good security, performances and backward compatibility:
    - Short-Weierstrass curve with a=0 (good performances with backward compatibility)
    - b being a QNR value and either 5 being a QR value or 4.5^{-1}.b being a non-cubic residue (resistance against some side-channel attacks)
    - Cofactor = 1 (resistance against some side-channel attacks and easy implementation)
    - p=3[4] (easy square roots, classical requirement)
    - p a random value (security)


[1] https://www.igvita.com/2012/07/19/latency-the-new-web-performance-bottleneck/
[2] https://eprint.iacr.org/2014/130.pdf
[3] http://www.statisticbrain.com/google-searches/
[4] Zero-Value Point Attacks : https://www-old.cdc.informatik.tu-darmstadt.de/reports/TR/TI-03-01.zvp.pdf

Franck RONDEPIERRE
Oberthur Technologies
Technology & Innovation , R&D Cryptography Engineer
420 rue d'Estienne d'Orves | 92700 Colombes | France
Phone: [phone]   | Fax : [phone]
E-mail : [e-mail] <mailto:[e-mail]> | Web : www.oberthur.com <http://www.oberthur.com>
P Please consider your Environmental Responsibility: Before printing this e-mail or any other document, ask yourself if you need a hard copy