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

[Watson Ladd <[e-mail]>]

On Wed, Nov 19, 2014 at 8:06 AM, RONDEPIERRE Franck
<[e-mail]> wrote:
> 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.

The code to compute a map from one model to another is quite short.
This means that whatever algorithm is used to compute on short
Weierstrass can be used to compute on Edwards curves: the additional
cost is a few extra calculations. The efficiency of doing this is
obviously only slightly less than for the "native" form.

>
> 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.

The latencies you quote are serial, not simultaneous. Furthermore,
some applications may be more constrained than others, or have power
requirements more stringent than a desktop or laptop computer.

Of course, you don't need to take my word for it: Cloudflare was very
clear that widespread ECDSA support was essential to making TLS free.
Mobile devices are having issues with verification times for NIST
P384. V2V proposals involves a staggering number of verifications a
second, but oddly enough don't use batching or efficient signatures,
thus forcing larger, more expensive hardware.

>
> 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.

As mentioned by Dan Harkins, these are special. I don't see any real
security concern: they've been around for a long time, and there is a
speedup. The extent of that speedup is unclear: I don't know of any
eBATS results using them. If we are willing to increase End(E),
GLV/GLS is
the current, patented champion. I guess old fashioned Koblitz isn't
that fast in comparison, but don't know for sure. Of course, this can
be combined with Edwards form, to get even more speedup.

But in general when it comes to performance, the easiest way to get
believeable results is to submit to eBATS.

>
>
>
> 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.

The impact of a small subgroup confinement attack vs. a wrong curve or
twist attack is very different. A small subgroup confinement attack
reveals a limited number of key bits. A twist attack or wrong curve
attack gives away the store. Attacks based on manipulation of key
exchange algorithms are stopped by standard measures like hashing
transcripts. The absence of such measures is a weakness in the key
exchange protocol.


>
> 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.

Which paper at CHES in particular? The Tromar-Pipman-Genkin one seems
to have exploited data-dependent execution, rather than arithmetic
paths.

>
>
>
> 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)

I have never seen an adequate explanation of why p random is needed
for security. What I have seen is an explanation of particular
blinding measures that only work with p random. But there are blinding
measures that don't depend on random p, that are more efficient.
Furthermore, if hardware already deals with the NIST curves, it has to
deal with nonrandom p already.

Sincerely,
Watson Ladd
>
>
>
>
>
> [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] | Web : 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
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin