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

From: RONDEPIERRE Franck <[email-masked]>
Date: Wed, 19 Nov 2014 16:06:40 +0000

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: +33 (0)1 78 14 73 64   | Fax : +33 (0)1 78 14 70 20
E-mail : [email-masked] <mailto:[email-masked]> | 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

---

From: Dan Brown <[email-masked]>
Date: Wed, 19 Nov 2014 18:20:57 +0000

>From: Cfrg [mailto:[email-masked]] On Behalf Of RONDEPIERRE Franck
>However when performances matters, why not taking Short Weierstrass curves
with a=0? Indeed, in such a case doublings 

Using a=0 seems to result in j=0 and a complex multiplication curve with
discriminant -3, which is arguably a rather special curve, and conjecturally
a greater risk than random j invariant. A complex multiplication
endomorphism by the cube root w of unity is (x,y) -> (wx,7). 

A precedent for an a=0 curve is secp256k1, which has apparently been used in
BitCoin.  In theory, the GLV method can speed-up ECC operations using the
endomorphism above, although I'm not personally aware of the practical gain.

Perhaps others in CFRG may agree that the risk of CM is worth the
performance gain, at least as an option.
 
 (Aside: also, the MOV test will rule half the prime field sizes because
they are supersingular when a=0.)

---

From: Watson Ladd <[email-masked]>
Date: Wed, 19 Nov 2014 20:33:59 -0800

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

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

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/
>
> [4] Zero-Value Point Attacks :
> https://www-old.cdc.informatik.tu-darmstadt.de/reports/TR/TI-03-01.zvp.pdf
>
>
>
> Franck RONDEPIERRE
>
> Oberthur Technologies
>
> E-mail : [email-masked] | 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
> [email-masked]
> 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

---

From: "Lochter, Manfred" <[email-masked]>
Date: Thu, 20 Nov 2014 09:01:53 +0100

> thus forcing larger, more expensive hardware.

Is there really a requirement for mobile devices to use a 384 bit curve? Why 
is 256 not sufficient? In which scenarios do you see the neccessity to use 
P-384? Which specific mobile devices are having issues with verification 
times? Are they having these problems only in connection with the proposed 
protocols you mention?
> deal with nonrandom p already.

Which specific more efficient blinding measures are you addressing? Could you 
provide sources?
What does efficient mean for these countermeasures? A better protection 
against SCA or higher speed? Or lower cost?
How is the patent situation for theses countermeasures?

Manfred

-- 
Lochter, Manfred
--------------------------------------------
Bundesamt für Sicherheit in der Informationstechnik (BSI)
Referat K21
Godesberger Allee 185 -189
53175 Bonn

Postfach 20 03 63
53133 Bonn

Telefon: +49 (0)228 99 9582 5643
Telefax: +49 (0)228 99 10 9582 5643
E-Mail: [email-masked]
Internet:
www.bsi.bund.de
www.bsi-fuer-buerger.de

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 20 Nov 2014 09:56:42 +0100

> implementation. Without this requirement, a point on curve test is needed to

I'd just like to emphasise that in many situations (including TLS with
uncompressed points and implementations using "standard" short Weierstrass
formulas, ie formulas that don't involve b) the point-on-curve test *is* needed
anyway, regardless of whether the curve is twist secure or not.

I'm sure you're already aware of that, but I think we should always be extremely
clear when speaking about it, since there are already people out there making
misinterpretations of what exactly twist security buys us and more importantly
what it doesn't. I really do not want to see, in a few month/years,
implementations skipping the point-on-curve test in a context where it is needed
just because they think using a twist secure curve protects them.

(Don't get me wrong: I think twist security is nice to have, and I'd like any
curve selected by the CFRG to have this property. I just don't want it to be
seen (by people outside this group) as a silver bullet.)

Manuel.

---

From: "Lochter, Manfred" <[email-masked]>
Date: Thu, 20 Nov 2014 10:29:27 +0100

__________ ursprüngliche Nachricht __________

Von:		"Manuel Pégourié-Gonnard" <[email-masked]>
Datum:	Donnerstag, 20. November 2014, 09:56:42
An:		RONDEPIERRE Franck <[email-masked]>, "[email-masked]" 
<[email-masked]>
Kopie:	
Betr.:	Re: [Cfrg] Requirements for elliptic curves with a view towards 
constrained devices

> > implementation. Without this requirement, a point on curve test is needed
> > to thwart the attacks.
>
> formulas, ie formulas that don't involve b) the point-on-curve test *is*
> needed anyway, regardless of whether the curve is twist secure or not.
>
> I'm sure you're already aware of that, but I think we should always be
> extremely clear when speaking about it, since there are already people out
> there making misinterpretations of what exactly twist security buys us and
> more importantly what it doesn't. I really do not want to see, in a few
> month/years, implementations skipping the point-on-curve test in a context
> where it is needed just because they think using a twist secure curve
> protects them.
>
> (Don't get me wrong: I think twist security is nice to have, and I'd like
> any curve selected by the CFRG to have this property. I just don't want it
> to be seen (by people outside this group) as a silver bullet.)
>
I would like to add another aspect. Having  a twist secure curve E means that 
E and its twist E' provide the same degree of security against purely 
mathematical attacks. However, if one takes SCA into accout the situation may 
change. One of the two curves will contain a point with x-coordinate zero. 
For this point projective randomisation will not work properly. 

Manfred 

Postfach 20 03 63
53133 Bonn

---

From: Watson Ladd <[email-masked]>
Date: Thu, 20 Nov 2014 07:21:50 -0800

> times? Are they having these problems only in connection with the proposed

When my mobile phone's browser connects to a website whose certificate
is signed by P384, a P384 verification better take place. Not
supporting P384 introduces an interoperability problem.

> How is the patent situation for theses countermeasures?

Most devices randomizing exponents compute xP as [aq+x]P where a is
some random number and q is the order. Random primes apparently permit
q, and thus aq+x to be smaller. But each arithmetic operation, and
thus each point addition or doubling, is twice as fast for a special
prime, and thus a can be the size of q, and we have equal performance
to an unblinded multiplication on a random prime curve. This is better
protection and it's faster. It's identical to the protection you
described, except we've increased the size of a.

This was described by DJB in an email to the list, titled "Primes vs.
hardware side channels", sent October 16th.

Of course, one can always continue to use brainpool. I don't see why
the new curves have to force a 50% slowdown on everyone for benefit of
a very restricted, largely unused class of devices.

Sincerelu.
Watson Ladd

---

From: "Lochter, Manfred" <[email-masked]>
Date: Fri, 21 Nov 2014 13:51:04 +0100

Von:		Watson Ladd <[email-masked]>
Datum:	Donnerstag, 20. November 2014, 16:21:50
An:		"Lochter, Manfred" <[email-masked]>
Kopie:	"[email-masked]" <[email-masked]>
Betr.:	Re: [Cfrg] Requirements for elliptic curves with a view towards 
constrained devices

> > Is there really a requirement for mobile devices to use a 384 bit curve?
> > Why is 256 not sufficient? In which scenarios do you see the neccessity
> > to use P-384? Which specific mobile devices are having issues with
> > verification times? Are they having these problems only in connection
> > with the proposed protocols you mention?
>

I'm glad that you agree with my previously stated position that 384-bit curves 
are needed. Following your reasoning 256/384/512(521) bit curves have to be 
supported. In this case I would rather see performance problems on the 
512/521 end. 
I would very much appreciate if you could also answer my other questions 
above.
You seem to say that car-to-car communication will use the curves proposed by 
the cfrg. This supports the inital position we took in the Brainpool position 
paper (eprint 832/2014). I'm glad that we seem to agree on that.

> > Which specific more efficient blinding measures are you addressing? Could
> > you provide sources?

Also thanks for this clarification. so, we both are talking about the same 
randomisation method but with different sizes of a. From the SCA perspective 
it is obvious that you have to use larger a for special primes than for 
random primes. Of course I've read Dan's posting. From your statement I was 
led to believe  you were talking about a new and different method.

Manfred
>
> Sincerelu.
> Watson Ladd
>
> > Manfred
> >
> >> Sincerely,
> >> Watson Ladd
> >>
> >> > [1]
> >> > https://www.igvita.com/2012/07/19/latency-the-new-web-performance-bott
> >> >len eck/
> >> >
> >> > https://www-old.cdc.informatik.tu-darmstadt.de/reports/TR/TI-03-01.zvp
> >> >.pd f
> >> >
> >> >
> >> >
> >> > Franck RONDEPIERRE
> >> >
> >> > Oberthur Technologies
> >> >
> >> > P Please consider your Environmental Responsibility: Before printing
> >> > this e-mail or any other document, ask yourself if you need a hard
> >> > copy
> >> >
> >> >

Postfach 20 03 63
53133 Bonn

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 21 Nov 2014 13:43:29 +0000

On 21 November 2014 12:51:04 GMT+00:00, "Lochter, Manfred" <[email-masked]> wrote:

>> [Watson Ladd] When my mobile phone's browser connects to a website whose certificate is signed by P384, a P384 verification better take place. Not supporting P384 introduces an interoperability problem.
> [Manfred Lochter] I'm glad that you agree with my previously stated position that 384-bit curves are needed.

No, with respect, I think perhaps you may have simply misunderstood what he's saying here.

What Watson is talking about is simply the practical requirement that many TLS-supporting peers will have to continue to support the NIST curves in existing deployments - because existing ECC root CAs in the PKIX tree, such as Comodo's, are apparently all using ECDSA_P384_SHA384 (i.e., the NIST curve secp384r1), and naturally they will need to verify that chain of trust to remain secure.

However, the NIST curves are of course firmly outside the scope of our recommendations here; such a legacy consideration regarding the NIST curves has no bearing at all on what curves we may choose, or not, to recommend.

secp384r1 appears to have particularly unfortunate performance in software, and this can have some impact on mobile devices forced to use it for interoperability (they almost always have no hardware acceleration for it). That is the context of Watson's post, I believe?

As discussed previously, there are no particuarly efficient special primes in the immediate area of 2^384, and as a result there are several curves such as Curve41417 and Ed448-Goldilocks which are both faster (in software) and stronger than secp384r1.

Regarding side channel defences, I refer you to my previous replies and reference above. I note again that the NIST curves are themselves special primes, and are quite widely deployed with plenty of 'high-assurance' implementations of them already: clearly therefore, most competent vendors have had no insurmountable problems producing implementations with effective side-channel defenses for special prime fields.

- --
/akr

---

From: Watson Ladd <[email-masked]>
Date: Fri, 21 Nov 2014 08:58:39 -0800

> paper (eprint 832/2014). I'm glad that we seem to agree on that.

The V2V projects aren't. Despite high performance constraints they are
not making optimal choices. Batch signatures would seem a natural fit,
and yet ECDSA is still being used. P256 seems to be selected, despite
Koblitz curves existing. But blinding won't be used: the performance
hit is too much, and the security model doesn't require it. It doesn't
seem like they will switch to Curve25519 if the CFRG recommends it.

Performance problems don't show up where you want them to. Any time
the fastest implementation isn't fast enough, there is a performance
problem. I don't see why users who want to use more secure curves
wouldn't care about performance, or why users who care about
performance wouldn't want the option to use larger curves. I also
don't see why random primes are good from a security perspective: they
permit a smaller multiplier, but the speed advantage of a nonrandom
curve permits a much bigger multiplier at the same cost.

Users don't care if we give them extra security. They do care if their
performance requirements aren't met by curves with adequate security,
or vice versa.

The Brainpool position paper equates hardware with high-assurance
hardware designed to resist side channel attacks, arguing that because
we can't write echo servers correctly, more people will put keys in
hardware. But this doesn't mean they need to resist side channel
attacks with large amounts of physical access to the hardware, and
certainly doesn't mean they are willing to suffer a massive
performance loss for that benefit.

Most of the applications which Brainpool inexplicably calls "hardware"
aren't. They use off the shelf microcontrollers, which don't have
bignum acceleration, and likely can't make it faster than built in
arithmetic. (There is nothing magical about doing the same
computations in a hard-coded circuit). They are much closer to
yesterday's software. This includes several "HSMs".

Sincerely,
Watson Ladd

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 21 Nov 2014 09:26:48 -0800

> seem like they will switch to Curve25519 if the CFRG recommends it.

Don't the V2V things need high *real-time* performance contraints?  To
me, that would seem to rule out batch signatures entirely, unless
there's a magic verifier that can retain good performance even in the
presence of an invalid signature.

--Andy

---

From: "D. J. Bernstein" <[email-masked]>
Date: 21 Nov 2014 23:12:33 -0000

My goal for curve selection, as I explained in Toronto, is to minimize
tensions between speed, simplicity, and security. My impression is that
there's consensus on at least one part of this: choosing a curve that
can be expressed in Edwards form, i.e., a curve that has a point of
order 4.

Microsoft has made a broader spectrum of proposals, apparently to be
prepared in case CFRG instead wants a curve of cofactor 1, but hasn't
actually been arguing that cofactor 1 is preferable. Nigel Smart claimed
at one point that cofactor 1 is "vital to avoid mistakes" but has never
given details. Meanwhile many people have pointed to the undisputed
benefits of Edwards curves, such as a very fast complete addition law.
I think CFRG could reasonably declare that a point of order 4 is a
requirement, simplifying subsequent discussion.

However, http://eprint.iacr.org/2014/832.pdf claims that cofactor 1 is
desirable because cofactors larger than 1 create "an additional
overhead" and "a source for implementation weaknesses" if a certain
"check is omitted or just forgotten". Similarly, a recent Oberthur
message claims that cofactor 1 should be "mandatory" to avoid "small
subgroup attacks" in careless implementations.

I find these claims quite puzzling, for several reasons:

   * Cofactors are already allowed by all of the usual ECC standards
     from IEEE, ANSI, and NIST. FIPS 186-4 sets the cofactor limit at
     2^14 for 255-bit primes. Certicom's pet SEC 1 standard has always
     allowed cofactor 4, and in 2009 started allowing even more.

   * Small-subgroup attacks were a big issue for pre-ECC discrete-log
     systems because those systems typically have huge cofactors---but
     for ECC everybody uses curves with vastly smaller cofactors, so the
     small-subgroup attacks learn almost nothing, even if nobody bothers
     defending against them. Invalid-curve attacks are a different
     story, but they have nothing to do with the minor difference
     between, e.g., cofactor 1 and cofactor 8 for the original curve.

   * The major ECC standards already eliminate _all_ of the information
     leakage from small-subgroup attacks. For example, ECDH in ANSI
     X9.63 computes a shared secret as "P=hdQ", where h is the cofactor
     and d is the secret key.

Notice that the cofactor multiplication in ANSI X9.63 etc. isn't a
"check" that can be "forgotten" by a careless implementation: such an
implementation would flunk every normal test vector for shared-secret
generation.

For comparison, a static-ECDH (or reused-ephemeral-ECDH) implementation
that doesn't check an incoming (x,y) against the curve equation will
leak its _entire_ secret key to a very fast attack. This huge security
problem _won't_ be caught by typical test vectors. This is vastly more
important than small-subgroup attacks.

Oberthur claims that checking the curve equation to stop these attacks
is "insignificant" compared to cofactor multiplication, but this is
exaggerating a tiny performance issue while ignoring the likelihood of
an omitted test and the security damage caused by the omission. We have
enough trouble getting crypto right without adding unnecessary traps!

The right way to eliminate the invalid-curve problem has two steps:

   (1) Require compressed points in protocols. This syntactically limits
       the input point to two curves: the original curve and its twist.

   (2) Choose twist-secure curves.

This also has many further benefits. Compressed points on curves with
points of order 4 also allow unmatched ECDH simplicity, at an excellent
performance level, via the Montgomery ladder. Serious hardware analyses
such as

   http://mhutter.org/papers/Wenger2011HardwareProcessorSupporting.pdf

consistently praise the Montgomery ladder---using compressed inputs and
outputs---for its simplicity, speed, and small resource consumption in
hardware. Of course, compressed points also reduce network traffic.

Why would anyone talk about small-subgroup attacks as being stopped by a
"check" that might be "forgotten", the same way that a curve-equation
check can stop invalid-curve attacks but might be forgotten? Answer:
What I've described so far is

   * a computational (robust) defense against small-subgroup attacks,
   * a verifying (not robust) defense against invalid-curve attacks, and
   * a computational (robust) defense against invalid-curve attacks,

but there's also

   * a verifying (not robust) defense against small-subgroup attacks.

Specifically, instead of multiplying the incoming point Q by h, one can
check whether hQ = 0. This check runs a serious risk of being omitted,
the same way that a curve-equation check runs a serious risk of being
omitted, although the resulting damage is much less severe.

Note that Certicom's dwindling patent portfolio has a not-quite-dead-yet
patent 6563928 on this inferior method ("determining whether said public
information ... lies within a subgroup ... having less than a
predetermined number of elements and rejecting messages utilizing said
public information if said public information lies within such a
subgroup"), which makes it particularly strange that anyone would talk
about this as the normal thing to do. Does Oberthur have a license for
this patent?

Anyway, if there really are reasons that CFRG should seriously consider
curve proposals with cofactor 1 then I think it's important for those
reasons to be made clear.

---Dan

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 21 Nov 2014 16:57:02 -0800

Hi DJB,

To play devil’s advocate here, there are other sorts of “attacks" against
curves with cofactors.  They’re fairly narrow, but they should be noted.

In general, these attacks do not exist against properly defined protocols,
but the protocol may have suboptimal properties when used with a
cofactor, or it may require checks that are tempting to skip, or it may
require jumping through some hoops.  Three issues come to mind.

1)

With a prime-order short Weierstrass curve, (x,y) points transmitted on
the wire (compressed or otherwise) cannot be the identity, nor can they
have small order.  As a result, if the secret key is valid (and nonzero, and
not equal to the group order), then the output of ECDH cannot be the
identity.  Furthermore, the output is a 1:1 function of the input, at least if
the input is checked for reduction.

But with an Edwards curve, (x,y) points transmitted on the wire can be the
identity, and can have small order.  Likewise, if a curve with a cofactor
is used in short Weierstrass form, (x,y) cannot be the identity, but can
have small order.  Therefore, ECDH can output the identity, and a malicious
actor can cause ECDH to output the identity with non-negligible probability
(if your ECDH protocol clears the cofactor, then with probability 1.)  This
could cause an exception or error, or it might cause the system to output
a predictable value.

You documented this family of attacks on Curve25519 at cr.yp.to/ecdh.html:

“””
There are some unusual non-Diffie-Hellman elliptic-curve protocols that need
to ensure ``contributory'' behavior. In those protocols, you should reject the
32-byte strings that, in little-endian form, represent 0, 1, [several large
numbers].
“””

As this quote says, most protocols don’t need to worry about this because
they do not need to ensure “contributory” behavior.

The Goldilocks encoding reduces the complexity of dealing with this sort of
attack: the identity is encoded as 0, and no other low-order points can be
encoded.

2)

For curves with a cofactor, ECDH is not 1:1.  This affects Trevor Perrin’s
TripleDH protocol, which attempts to work around concerns about patents on
session-hashing (don’t ask me what those are, I haven’t studied them).  As
a result, TripleDH implementations are forbidden to clear the cofactor, and
secret keys must be invertible mod the cofactor (i.e. odd).  If this requirement
were violated, it probably wouldn’t lead to an attack, but it wouldn’t guarantee
that the sessions seen by both sides were exactly the same.

3)

Another form of “attack” would be to cause two implementations to produce
different results for a supposedly deterministic computation, eg a signature
check.  For example, in the Ed25519 paper, you specify:
""
The verifier is /permitted/ to check this stronger equation and to reject signatures
where the stronger equation does not hold.  However, this is not /required/;
checking that 8SB = 8R + 8H(_R_, _A_, M)A is enough for security.
“””

A similar warning is given in goldilocks.h for goldilocks_verify:
“””
/**
 * @brief Verify a signature.
 *...
 * Currently this function does not detect when the public key is weird,
 * eg 0, has cofactor, etc.  As a result, a party with a bogus public
 * key could create signatures that succeed on some systems and fail on
 * others.
 * ...
 */
“””
The implemented behavior will accept public keys with 2-torsion components or
which are the identity, but not ones which are incorrectly encoded or are on the
twist. It does not permit any laxity in the signature itself.  But there would be some
incentive to be lax about cofactor in the signature during a batch verify.

In both these systems, implementations are allowed to differ when given inputs
that are wrong by a small-order amount.  There are more ways to specify this
sort of laxness with cofactored curves, though behavior should be testable by
vectors if the specification goes one way or the other.

Again, it’s not clear that this constitutes an attack, but it is something to
consider when deploying such a system.

Cheers,
— Mike

> On Nov 21, 2014, at 3:12 PM, D. J. Bernstein <[email-masked]> wrote:
>

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 21 Nov 2014 18:34:54 -0800

> On Nov 21, 2014, at 4:57 PM, Michael Hamburg <[email-masked]> wrote:
> 
> 2)
> 

Trevor has corrected me: TripleDH no longer forbids clearing the cofactor, because
that’s weird.  Instead it deals with this issue in a different way.

— Mike

---

From: Watson Ladd <[email-masked]>
Date: Fri, 21 Nov 2014 22:00:22 -0800

> presence of an invalid signature.

Most signatures are valid: while its true that a significant number of
bad signatures will slow batch verification, that number can be quite
large. For example, http://cr.yp.to/badbatch/badbatch-20120919.pdf
claims that 10 bad signatures out of 64 can be identified faster then
separate verification for each signature. It's clear that no matter if
verification or bandwidth is the limiting factor, malicious attackers
can carry out a denial of service.

Of course, there are several more predictable and simpler
optimizations that can be done, even if one has to stick with
NIST-approved curves. Amusingly, while Bitcoin uses a Koblitz curve,
it is only recently that bitcoin-core has been modified to take
advantage of this, due to verification becoming quite time consuming.

The gold standard for verification speed is e=3 RSA. But signing is
very, very slow.

Sincerely,
Watson Ladd

---

From: Natanael <[email-masked]>
Date: Sat, 22 Nov 2014 09:00:55 +0100

> check.  For example, in the Ed25519 paper, you specify:

[...]

> consider when deploying such a system.

The type of attacks that come to mind are consensus breaking attacks,
rather than pure cryptographic attacks.

Making some people believe everybody had received a valid order while some
will believe they were sent a bogus one which they reject (insider
sabotage?) over some broadcast medium. Would be detectable after the fact,
but could cause enough damage to be worth it for the attacker before then.

In the worst case scenario you could frame somebody this way if you know
the implementation they use right now will respond in one way but will soon
be updated/replaced to behave in the other way, and in which his superiors
already use the latter method. This provides for a very slim attack window,
but the risk is real.
You can make the verification fail, which he later would be unable to prove
after the change when he is asked why he didn't follow orders.
Or vice versa, make him follow an order that the software used by the
superiors will reject the signature on. Again, a claim he can't prove after
the change.

Also, for cryptocurrencies you could cause a fork between clients using
different signature verification implementations, making one side believe
the blockchain with a certain transaction to be invalid while the other
side doesn't.

---

From: William Whyte <[email-masked]>
Date: Sat, 22 Nov 2014 07:13:14 -0500

> seem like they will switch to Curve25519 if the CFRG recommends it.

Given the scale of the V2V projects and the difficulty of upgrading devices
in the field, there's a strong argument that the risk-minimizing approach
in V2V is to use the flavor of ECC that's had widespread deployment for the
longest and which has best availability in hardware. Performance isn't the
only consideration. The auto industry isn't particularly interested in
being the first mover in adoption of a newer curve, and there's already
been significant product development work focused on the NIST curves.

There are also regulatory concerns. In the US, it's not clear that devices
that implement a curve other than the NIST curves would be
FIPS-certifiable, should this turn out to be a requirement (which also
isn't clear). In Europe, BSI are strongly lobbying for the use of random
curves. In an industry that's more heavily regulated than the internet, it
makes sense to be biased towards solutions we already know the regulators
will accept.

I agree that ed25519 has very nice properties and all other things being
equal it would be good to see it used in V2V. (I also feel that until we're
told where the seeds came from, any continued use of the NIST curves is
rewarding bad practice). The batching in particular seems like it could
result in actual reductions in hardware cost for the verify-everything
approach. (Not all incoming signatures need to be verified, though
obviously if you do verify everything it gives you more flexibility in
processing after reception). I will say though that I haven't heard crypto
hardware suppliers in the V2V space making the argument that they could
reduce costs and prices by moving to ed25519 and batching, and unless we do
hear that it'll be very hard to make a change.

Cheers,

William

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 22 Nov 2014 14:51:50 +0200

> omitted, although the resulting damage is much less severe.

Also keep in mind for what CFRG is giving recommendations.

Small subgroup attacks: TLS can easily deal with small-subgroup attacks
without extra checks.

Invalid-curve attacks: The only realistic way of avoiding checks there
is to pick complete twist-secure Montgomery curve.

Implementation environment: Software-only uses of ECC in TLS utterly
dwarf any hardware implementations (embedded does not mean hardware).

And number of software implementations that need serious timing attack
protections dwards hardware implementations that need advanced side
channel protections (and those software protections are very nasty to
implement unless curve is complete).

-Ilari

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 22 Nov 2014 13:50:18 +0000

>From the point of view of someone (still!) waiting on CFRG to
pick some curves, this thread seems a bit odd.

I would hope CFRG would first pick something and then document
the inevitable corner cases, not argue in such detail about a set
of corner cases that don't really distinguish anything usefully
different about the different options.

So... please pick. If that doesn't happen soon, I am concerned
that implementers will just go ahead and use whatever they prefer
and the IETF will just have to deal with that.

I'm also not seeing really new arguments on the list recently,
and am seeing some repetition, so isn't it now time to just get
the selections done and move on to the next good bit of work (and
I also do see those starting to queue up.)

Thanks,
S.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 23 Nov 2014 00:52:33 -0000

RONDEPIERRE Franck writes:
> It seems that the current CFRG discussion quickly swiped the
> "hardware" point of view, qualifying it as out of the topic.

Many people here consider hardware important. Fortunately, within the
scope that CFRG is considering (elliptic curves over big prime fields),
the best curves for software are also the best curves for hardware.

> For some devices, the code size is the main limitation and hence has
> to be taken into account prior to speed performances.

This isn't a software-vs.-hardware issue. Unnecessarily complex crypto
(the NIST P-256 prime, Weierstrass failure cases, ECDSA inversion, etc.;
see http://blog.cr.yp.to/20140323-ecdsa.html for many details) produces
crypto software that's hard to write, even harder to get right, a royal
pain to audit, and a huge source of security failures.

Fortunately, we know how to make ECC much simpler. This doesn't cause
trouble for the people who care about speed; it even improves speed.

I realize that IETF has historically done a very bad job of managing
migrations---people seem to think that the primary goal is to add new
options (e.g., TLS 1.3) rather than to eliminate the code for the bad
options (e.g., SSLv3); that "agility" means waving your arms rather than
getting your feet out of the tar pit. But some migrations do succeed.
There are many Internet protocols that haven't even started using ECC
yet, and it's easy to envision a path towards future implementations
that don't have to suffer through NIST's obsolete version of ECC.

> We analyze hereafter the impact of switching to Edwards curves while
> keeping Short-Weierstrass ones for backward compatibility.

Obviously, until a migration is complete, there's a certain minimum
level of code complexity required to handle the obsolete options. Adding
support for the new options costs very little code---even if new point
formats are used on the wire, as I recommend; the conversions are easy.

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

No.

It's true that people _who want top speed_ will write separate code for
the fast new options (to the extent that it isn't written already), the
same way that they've already written separate code for, e.g., NIST
P-256 reduction.

It's obviously not true that people will write separate code if "the
code size is the main limitation". In that case they'll stick to a
merged code base using the obsolete Weierstrass approach to scalar
multiplication, because that's the only thing that the old curves
support. The new curves support this option too.

Obviously the reuse-old-code implementation option isn't the fast
implementation option---but if we stick to cofactor 1, as you recommend,
then we're _eliminating_ the fast option. What's the advantage supposed
to be? This is bad for all of the people who want more speed; it also
destroys the possibility of eventually migrating to a simpler code base
that throws away the obsolete Weierstrass approach.

> Furthermore, google.com, which is by far the most consulted website,
> currently processes around 10^5 requests per second

Searches are not connections; connections are not ECC operations; and,
most importantly, clients are not servers---often they're rather slow
smartphones. Google has already shown many times that it's willing to
sacrifice server performance for the sake of reduced client latency.

The bottom line, in any case, is that Google has already stated that it
cares about curve speed: "We're looking for a replacement [for P-256]
because we think that we can get something much faster and simpler."

> However when performances matters, why not taking Short Weierstrass
> curves with a=0?

That's an extremely special type of curve called a "GLV curve", adding
extra structure (an "endomorphism") for speed---but the main GLV speedup
is subject to Certicom patents 7100538 and 7995752. There are also nice
speeds from "GLV+GLS curves", including GLV+GLS Edwards curves, but all
of this is subject to the same patents. (Side question to Dan Brown:
Weren't you required to mention these patents when you suggested that
CFRG might be interested in these speeds?)

In the patent-free world, scalar multiplication for a=0 ends up being
slower than Montgomery and Edwards. The curve shape is also incompatible
with most primes (even if CFRG doesn't require twist-security), creating
larger gaps from powers of 2 and causing further slowdowns.

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

A moment ago you were insisting on measuring the code size for an
implementation that can handle the old options; now you're suddenly
advocating a requirement that eliminates, e.g., NIST P-224. This is a
strange notion of "backward compatibility".

Anyway, your underlying assessment of code size is incorrect. There's a
considerable cost in code size to handling NIST P-224 efficiently (see
http://cr.yp.to/papers/sqroot.pdf for the fastest options), but it's
very easy to handle primes that are 5 mod 8, such as Curve25519.

> intermediate result in the computation of the scalar multiplication, and that
> zero-value cannot be randomized with classical countermeasures.

False. For example, Coron's second countermeasure (more than 15 years
old now!) converts the input point into a random point, so the zero
disappears. There are many other important countermeasures against
side-channel attacks; would you rather have your resources devoted to
those countermeasures, or to unnecessarily slow curve computations?

---Dan

---

From: "D. J. Bernstein" <[email-masked]>
Date: 25 Nov 2014 13:08:33 -0000

Michael Hamburg writes:
> the wire (compressed or otherwise) cannot be the identity

No, it's not that simple. As I wrote earlier: "For cofactor 1 the
implementor has to go digging through obscure, poorly tested code to
figure out how the point at infinity might end up being communicated
(e.g., does the implementation treat input points off the curve as
infinity?) and then represented internally. Isn't TLS actually moving to
something much more confidence-inspiring than such patches, namely
hashing more inputs?"

> The Goldilocks encoding reduces the complexity of dealing with this

No. Checking for output 0 from the Montgomery ladder is guaranteed to
catch all non-contributory inputs for X25519, and is the simplest
imaginable check. (The local factor 8 clears all of those inputs, and
the main theorem says that the ladder always multiplies correctly.)

Further compression---e.g., specifying a constant top byte, avoiding the
top bytes of non-contributory inputs---would move the check inescapably
into the syntax, although it would slow down key generation somewhat.

> behavior should be testable by vectors

Sure. On the other hand, people often put together test vectors that
cover only "normal" cases and not unusual cases. Protocols should be
designed to be robust against likely implementation errors.

---Dan

---

From: Adam Langley <[email-masked]>
Date: Tue, 25 Nov 2014 07:01:39 -0800

On Tue, Nov 25, 2014 at 5:08 AM, D. J. Bernstein <[email-masked]> wrote:
> Isn't TLS actually moving to

Yes, the extended-master-secret draft[1] (i.e. what the master secret
should always have been) is in last call at the moment.

I believe this requires less thinking than worrying about requiring
contributory behaviour in the DH operation.

[1] https://tools.ietf.org/html/draft-ietf-tls-session-hash-03

Cheers

AGL