Subject: [Cfrg] When's the decision?

From: Watson Ladd <[email-masked]>
Date: Mon, 6 Oct 2014 08:26:51 -0700

Dear all,
We were promised on July 27 a process running for 6 weeks. Doubling I
get 12 weeks, which is three months, of which two (August, September)
have already gone. Am I correct in supposing that we're on track for a
decision by Halloween?

If we aren't, what remaining issues need to be addressed/when can we
expect a decision?

Sincerely,
Watson Ladd

---

From: Yoav Nir <[email-masked]>
Date: Mon, 6 Oct 2014 18:53:25 +0300

Hi Watson.

Just to be clear, you’re referring to the curve decision, right?  Because the WG is also discussing ChaCha, hash signatures and (supposedly) Dragonfly.

I think the conversation about the new curves has dried up, so it’s up to the chairs to call consensus if they can. If it were up to me, I would say that there’s very little separating the different proposals, especially for the ~128-bit strength, meaning that whichever one gets chosen is likely to be accepted (no “Oh, my, you got this so wrong! How could you!  Don’t you care about the kittens?”)  The differences in performance are small enough to not matter, and I don’t think anyone thinks that any of the proposals has some hidden weakness in the carefully chosen parameters.

So with implementer hat on, I’ll quietly wait CFRG to make the decision, and for AGL or DJB or one of the others who know how to write this kind of code securely to contribute code to OpenSSL, and then I’ll happily copy the code from there. If the wrong choice either (a) made my session rate 20% smaller or (b) made me stay up all night delivering security hotfixes, I’d feel strongly about this choice. As it is, I (and I’m sure some others on this list) don’t think it matters that much. They’re all good enough.

Yoav

On Oct 6, 2014, at 6:26 PM, Watson Ladd <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 06 Oct 2014 16:57:37 +0100

Hiya,

On 06/10/14 16:53, Yoav Nir wrote:
> They’re all good enough

Tend to agree. But CFRG, pretty-please don't pick them all!

If you do we'll just have to pick elsewhere (e.g. saag or
specific IETF wgs) with less clue immediately involved.

S.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 6 Oct 2014 16:28:02 -0700

> Tend to agree. But CFRG, pretty-please don't pick them all!

This ignores the significance of choices such as which coordinates to use
on the wire, whether to use compression, and which signature scheme to use.

These are not make or break items, and any curve could be used several
ways, but these issues do not go away with the choice of curve.
> specific IETF wgs) with less clue immediately involved.

Agreed: the buck stops here.

---

From: David Jacobson <[email-masked]>
Date: Mon, 06 Oct 2014 21:07:58 -0700

On 10/6/14, 4:28 PM, Watson Ladd wrote:
>
>
> On Oct 6, 2014 8:57 AM, "Stephen Farrell" <[email-masked] 
> <mailto:[email-masked]>> wrote:
> >
> >
> > Hiya,
> >
> > > They're all good enough
> This ignores the significance of choices such as which coordinates to 
> use on the wire, whether to use compression, and which signature 
> scheme to use.
>
I've implemented elliptic curve systems quite a few times.  But never 
with compression.  (The patent just expired.)  Could someone with 
experience implementing compression and with the short list of 
candidates, comment, for each curve, on how much of a hassle compression 
is to write, how much it expands the code, and how much it slows down 
the computation?

If the hassle, code bloat, and slowdown are minor, I suggest we just do 
compressed.  (Rationale:  Compression is always a win so do compressed.  
Keep it simple---no options)

If the hassle, code bloat, or slowdown are considerable, I suggest we 
require uncompressed and make compressed optional.  (Rationale: 
Compression is sometimes a win, e.g. for applications were bits on the 
wire are precious, and sometimes a lose.  For guaranteed 
interoperability there should be one variant that is always there, and 
that one should be the simpler, smaller.)

This probably interacts with the on-the-wire representation.  That will 
make the deciding a bit harder, but such is life.

    --David Jacobson

---

From: Watson Ladd <[email-masked]>
Date: Mon, 6 Oct 2014 21:56:56 -0700

On Mon, Oct 6, 2014 at 9:07 PM, David Jacobson <[email-masked]> wrote:
> This ignores the significance of choices such as which coordinates to use on
> the wire, whether to use compression, and which signature scheme to use.
>
> These are not make or break items, and any curve could be used several ways,
> but these issues do not go away with the choice of curve.
>>
> I've implemented elliptic curve systems quite a few times.  But never with
> compression.  (The patent just expired.)  Could someone with experience
> implementing compression and with the short list of candidates, comment, for
> each curve, on how much of a hassle compression is to write, how much it
> expands the code, and how much it slows down the computation?

Huh? The choice of formula doesn't have much of an impact. For any
prime not 1 mod 8, a single square root is pretty quick: equivalent to
a single modular exponentiation. Compression doesn't add much time.

Montgomery form never needs compression: the question is whether
Edwards points should be compressed. This reduces the size of
signatures, but isn't as critical for security as
compression/validation of points for use in ECDH.

The code bloat is another addition chain, but you can probably take
advantage of the relation between (p+1)/4 and p-1 when code size is a
concern.

Sincerely,
Watson Ladd

> require uncompressed and make compressed optional.  (Rationale:  Compression
> is sometimes a win, e.g. for applications were bits on the wire are
> precious, and sometimes a lose.  For guaranteed interoperability there
> should be one variant that is always there, and that one should be the
> simpler, smaller.)
>
> This probably interacts with the on-the-wire representation.  That will make
> the deciding a bit harder, but such is life.
>
>    --David Jacobson
>

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

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 6 Oct 2014 22:20:53 -0700

> On Oct 6, 2014, at 9:56 PM, Watson Ladd <[email-masked]> wrote:
> 
> On Mon, Oct 6, 2014 at 9:07 PM, David Jacobson <[email-masked] <mailto:[email-masked]>> wrote:

In particular, compression adds almost no time vs sending the point in affine, because you’re mostly just throwing away information.  Decompression costs about 10% of a variable-base scalarmul.  This doesn’t really depend on which curve is chosen.

Edwards point compression has a trick required to implement it efficiently, as described in the EdDSA paper.  But it isn’t terribly complicated.

> compression/validation of points for use in ECDH.

Depends on the form of your signature, of course.  Traditional Schnorr sigs don’t send the point anyway, and neither does ECDSA, but DJB’s "EdDSA" Schnorr variant does.

> advantage of the relation between (p+1)/4 and p-1 when code size is a

Yeah, it’s easiest to just base everything on a 1/sqrt(x) subroutine, or if 4th roots are needed for something in the same library, an x^(-3/4) subroutine.  That way the addition chain won’t add bloat.

For compression code bloat, I have some data.  The Ed448-Goldilocks reference code uses an unusually complicated compression mode for kicks: it’s compatible with the Montgomery ladder, conveys sign without a sign bit, and reduces the cofactor by encoding only even points.  According to nm, the code uses 528 bytes for compression and 592 for decompression on Mac clang -O3 with field additions inlined, but not multiplications.  The size doesn’t include the exception handling tables, which probably get stripped anyway because this is C and there are no exceptions.  This is comparable to 560 bytes for a point addition on the same settings.

A more traditional compression method would be somewhat smaller than this.

>> Keep it simple---no options)

I concur.  I think the code bloat and slowdown will only be a problem for embedded machines, and those are the ones which will feel the size advantage most.  The only exception is that some protocols may have required point formats, but that will be annoying anyway.

Cheers,
— Mike

> [email-masked] <mailto:[email-masked]>
> http://www.irtf.org/mailman/listinfo/cfrg <http://www.irtf.org/mailman/listinfo/cfrg>

---

From: David Jacobson <[email-masked]>
Date: Mon, 06 Oct 2014 22:35:43 -0700

On 10/6/14, 10:20 PM, Michael Hamburg wrote:
>
>> On Oct 6, 2014, at 9:56 PM, Watson Ladd <[email-masked] 
>> <mailto:[email-masked]>> wrote:
>>
>> On Mon, Oct 6, 2014 at 9:07 PM, David Jacobson 
>> <[email-masked] <mailto:[email-masked]>> wrote:
> In particular, compression adds almost no time vs sending the point in 
> affine, because you’re mostly just throwing away information. 
>  Decompression costs about 10% of a variable-base scalarmul.  This 
> doesn’t really depend on which curve is chosen.
>
> Edwards point compression has a trick required to implement it 
> efficiently, as described in the EdDSA paper.  But it isn’t terribly 
> complicated.
>
> Depends on the form of your signature, of course.  Traditional Schnorr 
> sigs don’t send the point anyway, and neither does ECDSA, but DJB’s 
> "EdDSA" Schnorr variant does.
>
> Yeah, it’s easiest to just base everything on a 1/sqrt(x) subroutine, 
> or if 4th roots are needed for something in the same library, an 
> x^(-3/4) subroutine.  That way the addition chain won’t add bloat.
>
> For compression code bloat, I have some data.  The Ed448-Goldilocks 
> reference code uses an unusually complicated compression mode for 
> kicks: it’s compatible with the Montgomery ladder, conveys sign 
> without a sign bit, and reduces the cofactor by encoding only even 
> points.  According to nm, the code uses 528 bytes for compression and 
> 592 for decompression on Mac clang -O3 with field additions inlined, 
> but not multiplications.  The size doesn’t include the exception 
> handling tables, which probably get stripped anyway because this is C 
> and there are no exceptions.  This is comparable to 560 bytes for a 
> point addition on the same settings.
>
> I concur.  I think the code bloat and slowdown will only be a problem 
> for embedded machines, and those are the ones which will feel the size 
> advantage most.  The only exception is that some protocols may have 
> required point formats, but that will be annoying anyway.
>
> Cheers,
> — Mike
>
>>>  Compression
We should probably wait a day or two to see if there are any opposing 
opinions.  But given the response from people who have implemented 
compression, I'd lean towards compressed as the only option.

    --David

---

From: "D. J. Bernstein" <[email-masked]>
Date: 8 Oct 2014 17:31:54 -0000

According to an announcement at ECC today, the Brainpool team is
completing a paper regarding curve requirements. Obviously Brainpool has
been a bit slow to join this discussion, and is already grandfathered
into TLS etc., but it sounds like they're serious about providing input
that might be useful in selecting new curves. It's also not clear to me
whether other teams (such as Barreto et al.) will have curve submissions
once the CFRG requirements are finalized.

Even if there are no other submissions and no changes to the draft
requirements, remember that there's a requirement for wiggle room to be
"quantified". For curves that take the as-fast-as-possible approach,
such as Curve25519, this is mostly answered by Mike Hamburg's "Rigidity
and performance" analysis of wiggle room in as-fast-as-possible primes,
but the chairs might want more information. For the Microsoft curves, I
presume that Microsoft is working on coming into compliance with this
requirement, and we're also doing our own analysis.

---Dan

---

From: "Parkinson, Sean" <[email-masked]>
Date: Wed, 8 Oct 2014 18:51:34 -0400

I have concerns about a decision being made about which curves to recommend 'before Halloween'.
I am unaware of 3rd parties implementing and confirming all the curves that have been proposed.
Making a decision on new elliptic curves based on data that hasn't been corroborated by a 3rd party is bad practice.

I have been implementing as many of the curves as I can and my performance results, so far, do not always match those that I have seen in papers.

Also, I am concerned that, while some curves are being implemented to be constant time, not all curves are being implemented to be cache attack resistant. Either all implementations need to be resistant or all implementations not. Only then can a true comparison be made.

Until these issues are dealt with I feel there is not sufficient information to make a decision.

Sean
--
Sean Parkinson | Consultant Software Engineer | RSA, The Security Division of EMC
Office +61 7 3032 5232 | Fax +61 7 3032 5299
www.rsa.com

---

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Oct 2014 18:33:33 -0700

> Making a decision on new elliptic curves based on data that hasn't been corroborated by a 3rd party is bad practice.

As far as I can tell, the implementations are all publicly available,
and I believe recent eBATS has included quite a few.
> I have been implementing as many of the curves as I can and my performance results, so far, do not always match those that I have seen in papers.

How good are your implementations? Being fast is hard.

> Also, I am concerned that, while some curves are being implemented to be constant time, not all curves are being implemented to be cache attack resistant. Either all implementations need to be resi…

All of them should be: this is annoying but straightforward to check
by looking at implementations.
> Until these issues are dealt with I feel there is not sufficient information to make a decision.

Most of this information is independent of which parameters are picked.

---

From: "Parkinson, Sean" <[email-masked]>
Date: Wed, 8 Oct 2014 21:55:45 -0400

Not all curves are implemented in a common place. Comparisons need to be made between 'equal' implementations.
Is there a complete list of curves under consideration?

For legal reasons I'm not going to be able to look at some libraries.
If someone can confirm one way or another it would be appreciated.

I believe mitigating the cache attack has a significant effect on the performance of Twisted Edwards curves. If we ignore this attack then how a Montgomery curve is implemented changes and this may swing the advantage back to using Montgomery for key exchange and Twisted Edwards for signatures.

If a larger bit length curve was as fast as or faster than a curve that is a multiple of 128 bits would this change the decision?

Sean

-----Original Message-----
From: Watson Ladd [mailto:[email-masked]] 
Sent: Thursday, 9 October 2014 11:34 AM
To: Parkinson, Sean
Cc: [email-masked]
Subject: Re: [Cfrg] When's the decision?

> Making a decision on new elliptic curves based on data that hasn't been corroborated by a 3rd party is bad practice.

As far as I can tell, the implementations are all publicly available, and I believe recent eBATS has included quite a few.

> Also, I am concerned that, while some curves are being implemented to be constant time, not all curves are being implemented to be cache attack resistant. Either all implementations need to be resi…

All of them should be: this is annoying but straightforward to check by looking at implementations.

>
> Sean
> --
> Sean Parkinson | Consultant Software Engineer | RSA, The Security 
> Division of EMC Office +61 7 3032 5232 | Fax +61 7 3032 5299 
> www.rsa.com
>

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

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 08 Oct 2014 20:42:32 -0700

> Is there a complete list of curves under consideration?
Supposedly we're still in the "collecting requirements" phase.

But IIRC, these have come up:
* Curve25519
* MS NUMS ed-{256,384,512}-mers
* The untwisted Edwards curves which are isogenous to the NUMS curves, 
or some other minor variant
* Curve41417
* Ed448-Goldilocks
* E-521

> I believe mitigating the cache attack has a significant effect on the performance of Twisted Edwards curves. If we ignore this attack then how a Montgomery curve is implemented changes and this may…
The Goldilocks microbenchmarks include measurements of a 5-bit SABS 
fixed-window algorithm with and without constant-time table lookups.  By 
those numbers, the lookup costs about 6% of the total time on Haswell, 
10% on Tegra2 (ARM Cortex-A9, no NEON) and a whopping 14% on BeagleBone 
(ARM Cortex-A8, NEON).  This is a large part of why the Montgomery 
ladder is faster, especially on NEON. But it's still not *that* much faster.
> If a larger bit length curve was as fast as or faster than a curve that is a multiple of 128 bits would this change the decision?
This is basically the point of Ed448-Goldilocks.  It's received a mixed 
response in this forum, since some people would prefer the most 
constrained curve, for some definition of "constrained" which doesn't 
consider performance.

Cheers,
-- Mike

---

From: "Parkinson, Sean" <[email-masked]>
Date: Thu, 9 Oct 2014 00:13:04 -0400

Thanks Mike. These are the curves I was thinking are under consideration.

I thought the mitigation to the cache side-channel attack in OpenSSL was to read/write all entries rather than to use an index that is data dependent. Please correct me if I'm wrong.

Sean

-----Original Message-----
From: Mike Hamburg [mailto:[email-masked]] 
Sent: Thursday, 9 October 2014 1:43 PM
To: Parkinson, Sean; Watson Ladd
Cc: [email-masked]
Subject: Re: [Cfrg] When's the decision?

But IIRC, these have come up:
* Curve25519
* MS NUMS ed-{256,384,512}-mers
* The untwisted Edwards curves which are isogenous to the NUMS curves, or some other minor variant
* Curve41417
* Ed448-Goldilocks
* E-521

> I believe mitigating the cache attack has a significant effect on the performance of Twisted Edwards curves. If we ignore this attack then how a Montgomery curve is implemented changes and this may…
The Goldilocks microbenchmarks include measurements of a 5-bit SABS fixed-window algorithm with and without constant-time table lookups.  By those numbers, the lookup costs about 6% of the total time on Haswell, 10% on Tegra2 (ARM Cortex-A9, no NEON) and a whopping 14% on BeagleBone (ARM Cortex-A8, NEON).  This is a large part of why the Montgomery ladder is faster, especially on NEON. But it's still not *that* much faster.
> If a larger bit length curve was as fast as or faster than a curve that is a multiple of 128 bits would this change the decision?
This is basically the point of Ed448-Goldilocks.  It's received a mixed response in this forum, since some people would prefer the most constrained curve, for some definition of "constrained" which doesn't consider performance.

Cheers,
-- Mike

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 9 Oct 2014 01:20:38 -0400

On Wed, Oct 8, 2014 at 11:42 PM, Mike Hamburg <[email-masked]> wrote:

> response in this forum, since some people would prefer the most constrained
> curve, for some definition of "constrained" which doesn't consider
> performance.

I am happy to consider performance but only if the differences are
large and consistent.

This is not a competition where more is better. I don't want more than
exactly one high strength curve and exactly one exceptionally high
curve. I don't want to see any options or parameters either. Either we
are all doing the twist again or nobody is. Either we are all doing
compression or not.

And if there isn't a clear basis for a decision we can throw darts.

Some performance issues are show stoppers. Anything that is not less
than a clean multiple of a power of 2 is going to cause severe
performance hits on future architectures. 512 bit memory buses are
common in graphics cards, 521 bit buses are not.

If ED448 is twice as fast as the exactly 512 bit curve then there is a
decisive performance advantage. Anything less than 20% is noise.

The point is elimination, to vote people off the island so we can have
a winner, not to get more people in.

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 08 Oct 2014 23:43:01 -0700

> are all doing the twist again or nobody is. Either we are all doing
I agree, which is why I prefer "NUMS but untwisted" over the current 
NUMS.  Everyone else avoided specifying twisted curves because of the 
incomplete addition formulas.
> common in graphics cards, 521 bit buses are not.
Maybe.  It depends what's the limiting factor in the algorithm.  It 
might not be the memory bus.
> decisive performance advantage. Anything less than 20% is noise.
Ed448 is about twice as fast as ed-512-mers, and about 6% slower than 
ed-384-mers using currently published implementations.  That is, using 
the last round of benchmarks I took on my SBR machine before selling it, 
and the published NUMS numbers.

The footing is surely not entirely even.  The Ed448 software uses a 
Montgomery ladder for ECDH and has a unified compressed point format, 
whereas MS ECCLib uses fixed-window Edwards with no point compression.  
Ed448 uses vectorized Karatsuba with C+asm as its lowest level (except 
on NEON where it's basically all asm), and ECCLib uses Comba in all 
asm.  They're benchmarked on different platforms with different loops.  
And so on.

Ed448 also has a pretty efficient ARM NEON implementation.  I believe it 
will have a larger advantage over NUMS on that platform, because I kept 
32-bit vector performance in mind when designing it.
> a winner, not to get more people in.
Sounds like a plan.

-- Mike

---

From: "Parkinson, Sean" <[email-masked]>
Date: Thu, 9 Oct 2014 03:23:22 -0400

Phillip,
I can agree that stepping just over a power of 2 is only going to hurt performance in the future.

Sean

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Phillip Hallam-Baker
Sent: Thursday, 9 October 2014 3:21 PM
To: Mike Hamburg
Cc: Parkinson, Sean; Watson Ladd; [email-masked]
Subject: Re: [Cfrg] When's the decision?

On Wed, Oct 8, 2014 at 11:42 PM, Mike Hamburg <[email-masked]> wrote:

>
> This is basically the point of Ed448-Goldilocks.  It's received a 
> mixed response in this forum, since some people would prefer the most 

I am happy to consider performance but only if the differences are large and consistent.

This is not a competition where more is better. I don't want more than exactly one high strength curve and exactly one exceptionally high curve. I don't want to see any options or parameters either. Either we are all doing the twist again or nobody is. Either we are all doing compression or not.

Some performance issues are show stoppers. Anything that is not less than a clean multiple of a power of 2 is going to cause severe performance hits on future architectures. 512 bit memory buses are common in graphics cards, 521 bit buses are not.

If ED448 is twice as fast as the exactly 512 bit curve then there is a decisive performance advantage. Anything less than 20% is noise.

The point is elimination, to vote people off the island so we can have a winner, not to get more people in.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 10 Oct 2014 07:18:47 -0000

Parkinson, Sean writes:
> Making a decision on new elliptic curves based on data that hasn't
> been corroborated by a 3rd party is bad practice.

More than 1500 implementations of various cryptographic functions have
been contributed to, and are publicly available as part of, the
state-of-the-art SUPERCOP benchmarking framework:

   http://bench.cr.yp.to/supercop.html

Practically all of the implementations are free to use, and many of them
are in fact widely used. Most of the researchers producing speed records
for cryptography are contributing their software to the same system.

The eBACS benchmarking project systematically and reproducibly measures
these implementations on more than 20 different microarchitectures:

   http://bench.cr.yp.to/computers.html

It's easy for other people to download and run the benchmarks on their
favorite CPU, and to contribute the results to the central system, where
detailed speed reports are posted publicly for other people to see and
verify. eBACS has practically eliminated the measurement errors and
disputes that plagued previous approaches to cryptographic benchmarking.
eBASH, the hash component of eBACS, was mentioned 30 times in NIST's
final report on the SHA-3 competition.

As a concrete example, now that Mike has sent crypto_dh/ed448goldilocks
in for benchmarking, eBACS is automatically filling lines into

   http://bench.cr.yp.to/results-dh.html
   http://bench.cr.yp.to/impl-dh/ed448goldilocks.html

whenever machines finish benchmark runs: 529066 cycles on titan0, 689020
cycles on hydra8, 757676 cycles on h6sandy, etc. These don't exactly
confirm Mike's comparisons to the Sandy Bridge numbers that Microsoft
claimed in http://eprint.iacr.org/2014/130.pdf---although they do seem
adequate to support his point about ed448goldilocks hitting a sweet spot
on the security/speed curve while Microsoft's design strategy
compromises the security/speed tradeoff:

   * ed448goldilocks isn't quite twice as fast as numsp512t1
     (ed-512-mers): 757676 cycles vs. 1293000 cycles.

   * ed448goldilocks is about 23% slower than numsp384t1 (ed-384-mers):
     757676 cycles vs. 617000 cycles.

Of course, if Mike or anyone else thinks that ed448goldilocks can be
computed more efficiently, he's welcome to prove it by contributing a
better implementation of that function to SUPERCOP, and then the
benchmarks will be updated appropriately. He can also raise reasonable
questions about the accuracy of Microsoft's claims; if Microsoft's
numbers are actually correct then Microsoft can dispel the skepticism
by contributing their own code to SUPERCOP.

As a more detailed example of reproducibility, let's look at what the
benchmarks say about X25519 on Haswell. Checking

   http://bench.cr.yp.to/results-dh.html

we see a median of 145907 cycles (quartiles: 144894 and 147191 cycles)
for the crypto_dh/curve25519 software on an Intel Xeon E3-1275 V3.
Clicking on "titan0" shows more information: the best speeds found for
crypto_scalarmult/curve25519 on this machine used

   gcc-4.8.1 -m64 -O -march=native -mtune=native -fomit-frame-pointer

to compile the "amd64-51" implementation. Anyone can use the same free
implementation with the same free compiler and will obtain the same
compiled code running in the same number of Haswell cycles:

   wget https://hyperelliptic.org/ebats/supercop-20140924.tar.bz2
   tar -xf supercop-20140924.tar.bz2
   cd supercop-20140924
   # compile and measure everything: nohup sh data-do &
   # alternatively, extract X25519 as follows:
   mkdir x25519
   cp measure-anything.c x25519
   cp crypto_scalarmult/measure.c x25519
   cp crypto_scalarmult/curve25519/amd64-51/* x25519
   cp include/randombytes.h x25519
   cp cpucycles/amd64cpuinfo.h x25519/cpucycles.h
   cp cpucycles/amd64cpuinfo.c x25519/cpucycles.c
   cp cpucycles/osfreq.c x25519/osfreq.c
   cd x25519
   ( sed s/CRYPTO_/crypto_scalarmult_/ < api.h
     echo '#define crypto_scalarmult_IMPLEMENTATION "amd64-51"'
     echo '#define crypto_scalarmult_VERSION "-"'
   ) > crypto_scalarmult.h
   echo 'static const char cpuid[] = {0};' > cpuid.h
   gcc -m64 -O -march=native -mtune=native -fomit-frame-pointer \
   -D COMPILER='"gcc"' \
   -D LOOPS=1 \
   -o measure measure-anything.c measure.c cpucycles.c \
   mont* fe*.c *.s
   ./measure

For example, on one core of Andrey's 3.4GHz i7-4770 (Haswell), this
X25519 code will take the same ~146000 cycles: i.e., more than 23000
operations/second, whereas the latest Haswell-optimized OpenSSL NIST
P-256 ECDH code that he measured was only 15000 operations/second.

This is, by the way, rather old Curve25519 code optimized for Nehalem,
the microarchitecture of the first Core i7 CPUs in 2008---but on Intel's
latest Haswell CPUs it's still solidly beating NIST P-256 code that's
optimized for Haswell. There's ample literature explaining that

   * reductions mod 2^255-19 are faster than reductions mod
     2^256-2^224+2^192+2^96-1 on a broad range of platforms, and that
     
   * Montgomery scalarmult is faster than Weierstrass scalarmult,

so the performance gap is unsurprising.

Why did Andrey report only 17289 operations/second for X25519 on
Haswell? The answer, in a nutshell, is that there's an active ecosystem
of Curve25519/X25519/Ed25519 implementations, and it's easy to find
implementations that prioritize simplicity over speed---including the
one implementation included in Andrey's manual benchmarks. Of course,
any application developer who needs more speed will look for, and find,
the faster X25519 implementations.

---Dan

---

From: David Jacobson <[email-masked]>
Date: Fri, 10 Oct 2014 08:44:25 -0700

> the faster X25519 implementations.
You have amassed a lot of data.  Wow!  But this seems to be concerned 
with raw speed.  It would be nice if you tagged implementations (of 
algorithms where it matters) into according to leakage resistance.  
There could be a tag for optimized solely for speed,  another for 
implementations that are timing leak resistant (either constant time or 
blinded), etc.

    --David Jacobson

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 10 Oct 2014 12:00:44 -0700

I’ll add a +1 in favor of SUPERCOP as a better-than-all-the-others reproducible benchmarking system.  It’s a bit finicky, though; in particular, typing “sh do” and waiting a week isn’t the most convenient development cycle.  Furthermore, some of the machines on bench.cr.yp.to have quirks (turboboost, mismatched cycle counter frequency, etc) which can make the data difficult to interpret and reproduce.

If you are considering submitting a system, I’d strongly recommend testing on https://github.com/jschanck-si/supercop-fastbuild, You should also make sure to install the compilers DJB uses (GCC 4.8.1 and Clang 3.2 on titan0, or GCC 4.6.3 and Clang 3.0 on h6sandy, for example) to make sure that your system compiles and runs passably well using those compilers.  I didn’t do this last time, which is (part of?) why the numbers from my own benchmarks do not match DJB’s numbers; see below.

> On Oct 10, 2014, at 12:18 AM, D. J. Bernstein <[email-masked]> wrote:
> 
> Parkinson, Sean writes:

For the next SUPERCOP release, please pull the latest BAT from http://shiftleft.org/upload/ed448goldilocks-20141010.tgz

The build on bench.cr.yp.to has a bug which prevents compilation on older 64-bit clangs, such as clang 3.2 on titan0, and clang 3.0 on h6sandy.

So for example on ProteusMachine (Haswell Core i7-4790 CPU @ 3.60GHz, HT and TB disabled) with supercop-fastbuild's clang_-g_-O3_-march=native_-mtune=native_-fomit-frame-pointer 4.2.1_Compatible_Ubuntu_Clang_3.5_(trunk), the timings are 160431 keypair cycles and 479118 dh cycles.

Thanks,
— Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Sat, 11 Oct 2014 19:54:47 -0700

>     -o measure measure-anything.c measure.c cpucycles.c \

Thank you for this information. I added timing code and built the 
"measure" program in the x25519 directory (see above) on

    Intel(R) Core(TM) i5-3550 CPU @ 3.30GHz, Ivy Bridge (not Haswell).

3 results are in op/sec:

above x25519 variable base : openssl : curve25519-donna:

18167.7 : 11030.5 : 14098.2

18167.7/11030.5 = 65%

The ./measure reported 182112 cycles for variable base before and after 
my changes (which looks correct: 3300000000 Hz/182112=18120 sec). 
Specifically, I timed the crypto_scalarmult().

I won't have access to my Haswell machine for a few days.

> the faster X25519 implementations.

It's natural for a developer, the consumer of these open source 
libraries, to test-drive the speed tests the way I did. If the sequence 
of steps needed to run the tests is clear and short, the results are 
easily verifiable.

In case of openssl the results depends on:
* the exact version of the source code
* the exact version of the compiler and assembler tools
* the options given to the config, configure
* CPU

OpenSSL will autodetect the gcc and build the binary by excluding or 
including certain highly-optimized pieces without any relevant reports. 
Some beneficial configuration options are not always the defaults. Not 
surprisingly, the openssl that comes with the latest OS I test on, 
Fedora Core 20, is 3+ times slower than what I report above.

I find that the quickest way for me to confirm that I am timing the 
right code is to use the debugger. For example, I confirmed that 
./measure is spending time in 
crypto_scalarmult_curve25519_amd64_51_ladderstep in a hand-written 
assembler file.

http://bench.cr.yp.to looks like an excellent way to try code on 
platforms one doesn't own.

---

From: Watson Ladd <[email-masked]>
Date: Sat, 11 Oct 2014 21:15:42 -0700

On Sat, Oct 11, 2014 at 7:54 PM, Andrey Jivsov <[email-masked]> wrote:
> Thank you for this information. I added timing code and built the "measure"
> program in the x25519 directory (see above) on
>
> The ./measure reported 182112 cycles for variable base before and after my
> changes (which looks correct: 3300000000 Hz/182112=18120 sec). Specifically,
> I timed the crypto_scalarmult().
>
> It's natural for a developer, the consumer of these open source libraries,
> to test-drive the speed tests the way I did. If the sequence of steps needed
> to run the tests is clear and short, the results are easily verifiable.
>
> including certain highly-optimized pieces without any relevant reports. Some
> beneficial configuration options are not always the defaults. Not
> surprisingly, the openssl that comes with the latest OS I test on, Fedora
> Core 20, is 3+ times slower than what I report above.
>
> I find that the quickest way for me to confirm that I am timing the right
> code is to use the debugger. For example, I confirmed that ./measure is
> spending time in crypto_scalarmult_curve25519_amd64_51_ladderstep in a
> hand-written assembler file.

Take a look at http://bench.cr.yp.to/impl-scalarmult/curve25519.html.
There are multiple hand-written assembly implementations, with
differing performance characteristics and portability. In particular
AMD and Intel chips favor different implementations. Furthermore,
there are multiple ways to compile code by fiddling with options.
eBATS handles most of this transparently.

Most applications will not need to go to these extremes. But for those
that do, customized assembler per processor version and automated
compiler tickling is not uncommon. Measurement techniques that don't
account for this will not produce realistic results. Asking about
minimax (the implementation with the fastest slowest speed) is a
reasonable question, or maximal performance from pure C, is reasonable
as these are common industrial constraints. But I think there will be
very few cases where public key crypto speed is the limiting factor.

Sincerely,
Watson

>
> http://bench.cr.yp.to looks like an excellent way to try code on platforms
> one doesn't own.
>
>

---

From: "Parkinson, Sean" <[email-masked]>
Date: Sun, 12 Oct 2014 18:58:07 -0400

Is there a REST API to the benchmark data?

Sean

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
Sent: Sunday, 12 October 2014 2:16 PM
To: Andrey Jivsov
Cc: [email-masked]
Subject: Re: [Cfrg] Publicly verifiable benchmarks

On Sat, Oct 11, 2014 at 7:54 PM, Andrey Jivsov <[email-masked]> wrote:
>> More than 1500 implementations of various cryptographic functions 
>> have been contributed to, and are publicly available as part of, the 
>> Practically all of the implementations are free to use, and many of 
>> them are in fact widely used. Most of the researchers producing speed 
>> records for cryptography are contributing their software to the same system.
>>
>> The eBACS benchmarking project systematically and reproducibly 
>> measures these implementations on more than 20 different microarchitectures:
>>
>> It's easy for other people to download and run the benchmarks on 
>> their favorite CPU, and to contribute the results to the central 
>> system, where detailed speed reports are posted publicly for other 
>> people to see and verify. eBACS has practically eliminated the 
>> measurement errors and disputes that plagued previous approaches to cryptographic benchmarking.
>> As a concrete example, now that Mike has sent 
>> crypto_dh/ed448goldilocks in for benchmarking, eBACS is automatically 
>> filling lines into
>>
>> whenever machines finish benchmark runs: 529066 cycles on titan0, 
>> 689020 cycles on hydra8, 757676 cycles on h6sandy, etc. These don't 
>> exactly confirm Mike's comparisons to the Sandy Bridge numbers that 
>> Microsoft claimed in http://eprint.iacr.org/2014/130.pdf---although 
>> they do seem adequate to support his point about ed448goldilocks 
>> hitting a sweet spot on the security/speed curve while Microsoft's 
>> design strategy compromises the security/speed tradeoff:
>>
>> benchmarks will be updated appropriately. He can also raise 
>> reasonable questions about the accuracy of Microsoft's claims; if 
>> Microsoft's numbers are actually correct then Microsoft can dispel 
>> the skepticism by contributing their own code to SUPERCOP.
>>
>> we see a median of 145907 cycles (quartiles: 144894 and 147191 
>> cycles) for the crypto_dh/curve25519 software on an Intel Xeon E3-1275 V3.
>> to compile the "amd64-51" implementation. Anyone can use the same 
>> free implementation with the same free compiler and will obtain the 
>> same compiled code running in the same number of Haswell cycles:
>>
> The ./measure reported 182112 cycles for variable base before and 
> after my changes (which looks correct: 3300000000 Hz/182112=18120 
> sec). Specifically, I timed the crypto_scalarmult().
>
>> This is, by the way, rather old Curve25519 code optimized for 
>> Nehalem, the microarchitecture of the first Core i7 CPUs in 
>> 2008---but on Intel's latest Haswell CPUs it's still solidly beating 
>> NIST P-256 code that's optimized for Haswell. There's ample 
>> literature explaining that
>>
>> Haswell? The answer, in a nutshell, is that there's an active 
>> ecosystem of Curve25519/X25519/Ed25519 implementations, and it's easy 
>> to find implementations that prioritize simplicity over 
>> speed---including the one implementation included in Andrey's manual 
>> benchmarks. Of course, any application developer who needs more speed 
>> will look for, and find, the faster X25519 implementations.
>>
>> ---Dan
>
>
> libraries, to test-drive the speed tests the way I did. If the 
> sequence of steps needed to run the tests is clear and short, the results are easily verifiable.
>
> including certain highly-optimized pieces without any relevant 
> reports. Some beneficial configuration options are not always the 
> defaults. Not surprisingly, the openssl that comes with the latest OS 
> I test on, Fedora Core 20, is 3+ times slower than what I report above.
>
> crypto_scalarmult_curve25519_amd64_51_ladderstep in a hand-written assembler file.

Take a look at http://bench.cr.yp.to/impl-scalarmult/curve25519.html.
There are multiple hand-written assembly implementations, with differing performance characteristics and portability. In particular AMD and Intel chips favor different implementations. Furthermore, there are multiple ways to compile code by fiddling with options.
eBATS handles most of this transparently.

Most applications will not need to go to these extremes. But for those that do, customized assembler per processor version and automated compiler tickling is not uncommon. Measurement techniques that don't account for this will not produce realistic results. Asking about minimax (the implementation with the fastest slowest speed) is a reasonable question, or maximal performance from pure C, is reasonable as these are common industrial constraints. But I think there will be very few cases where public key crypto speed is the limiting factor.

Sincerely,
Watson

---

From: "D. J. Bernstein" <[email-masked]>
Date: 13 Oct 2014 11:36:07 -0000

More notes on how SUPERCOP documents various things.

> Intel(R) Core(TM) i5-3550 CPU @ 3.30GHz, Ivy Bridge (not Haswell).

http://bench.cr.yp.to/computers.html lists four "IB+AES" machines
(Ivy Bridge is actually two different microarchitectures: Core i3 CPUs
don't have AES instructions), namely hydra8, ares, khazaddum, and h9ivy.

The last column of the table shows that the latest reports contributed
from ares and khazaddum are from 2013 and 2012, which is why they're
marked in gray; hydra8 and h9ivy are reasonably up to date. If you then
check, for example,

   http://bench.cr.yp.to/results-dh.html#amd64-hydra8

you see that crypto_dh/curve25519 takes 182544 cycles (quartiles: 182424
and 182664) on hydra8. As I mentioned, this X25519 code was actually
written years ago (optimized for Nehalem), so you can also find the same
speed in the 2013 report from ares, but in general it's good to focus on
the up-to-date speed reports.

> Is there a REST API to the benchmark data?

The underlying compressed database is hundreds of gigabytes, creating
serious performance problems for most standard tools. We're working on
supporting more client-side manipulation of data but for the moment the
best way to get additional reports onto the web pages is to talk to us.

David Jacobson writes:
> It would be nice if you tagged implementations (of algorithms where it
> matters) into according to leakage resistance.

Yes. Some implementors advertise constant-time software, but right now
SUPERCOP doesn't provide a structured mechanism for this advertisement.
One of the difficulties here is that some people are more stringent than
others in what they mean by "constant time"; I'll write a separate
message about this.

Michael Hamburg writes:
> some of the machines on bench.cr.yp.to have quirks
> (turboboost, mismatched cycle counter frequency, etc) which can make
> the data difficult to interpret and reproduce.

Turbo Boost is noted as "boost" in red (as is Turbo Core), and is also
easy to spot as unusually large gaps between the quartiles. See, e.g.,
http://bench.cr.yp.to/results-dh.html#amd64-hydra3.

The SUPERCOP documentation has a "Reducing randomness in benchmarks"
section that tells people how to turn off hyperthreading and Turbo
Boost. Eventually we'd like to measure what the actual Turbo Boost
speedup is, but this isn't as easy as it sounds.

Some CPUs don't give the OS full control over clock frequencies. Of
course, clock frequency makes far less of a difference in cycle counts
than it makes in other metrics such as operations per second, but it
does sometimes make a noticeable difference, especially for code that
doesn't fit into L1 cache. Clicking on machine names shows pages such as

   http://bench.cr.yp.to/web-impl/armeabi-h7green-crypto_dh.html

with a "CPU cycles/second" line showing the range of frequencies
observed by SUPERCOP (highly variable for h7green---this particular
Cortex-A9 CPU seems quite hard to control), along with information about
which cycle counter SUPERCOP is using (in this case cpucycles/cortex.c).

> You should also make sure to install the compilers DJB uses (GCC 4.8.1
> and Clang 3.2 on titan0, or GCC 4.6.3 and Clang 3.0 on h6sandy, for
> example) to make sure that your system compiles and runs passably well
> using those compilers.

The compiler versions are noted parenthetically in the same machine
pages mentioned above. But they do change every now and then when
systems are upgraded (for example, titan0 just switched to gcc 4.8.2),
and when people contribute more machines they usually have different
compilers. The real-world situation is that people use many different
compilers, and it isn't safe to assume that those compilers all behave
the same way. Of course, asm code produces much less variability.

---Dan

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 13 Oct 2014 10:49:49 -0700

> On Oct 13, 2014, at 4:36 AM, D. J. Bernstein <[email-masked]> wrote:

> others in what they mean by "constant time"; I'll write a separate

You used to have int timingattacks(void) { … }.  Or was that just a BATMAN thing?

> speedup is, but this isn't as easy as it sounds.

It sure doesn’t sound easy.

> doesn't fit into L1 cache.

At least on Intel CPUs, the counter read by RDTSC runs at a constant rate which may or may not have anything to do with the CPU’s actual frequency.  So for example, on a Haswell MacBook Air 1.7GHz (boost to 3.3GHz), the counter runs at 2.2GHz even when TurboBoost is disabled.  This also means that unless you have privilege to read the pcr cycle counter, boosting does ruin the cycle counts just as much as the ops/second.

In the past I’ve seen data on bench.cr.yp.to which looked like it may have been affected by this problem: it showed reasonable quartiles but noticeably faster or slower speeds across all benchmarks.  But that was some time ago, so maybe it’s gone now.

>  Of course, asm code produces much less variability.

That’s a good point.  The downside is that you have to target a specific architecture (eg choose for each directory what vector support you have), but that’s no different from what most library packagers do.

Cheers,
— Mike

---

From: "D. J. Bernstein" <[email-masked]>
Date: 14 Oct 2014 09:36:40 -0000

Parkinson, Sean writes:
> Also, I am concerned that, while some curves are being implemented to
> be constant time, not all curves are being implemented to be cache
> attack resistant.

When I say "constant time", I don't merely mean making the _total_ time
constant: I mean systematically avoiding all data flow from secrets to
the CPU's instruction timing, providing full immunity to cache-timing
attacks, branch-prediction attacks, etc.

On typical CPUs this means avoiding all data flow from secrets to branch
conditions, load addresses, and store addresses. On some CPUs there are
other timing leaks: for example, if there are early-abort multipliers,
then for me "constant time" says, for each multiplication instruction in
the code, that the abort condition is independent of secret data.

Unfortunately, I've often seen "constant time" used for code that
doesn't even try to meet the same requirements, or that tries and fails:

   * OpenSSL added "constant-time" code where there was no dependence on
     secret data in the choice of _cache lines_ being accessed. However,
     https://cryptojedi.org/peter/data/chesrump-20130822.pdf showed that
     this strategy actually produces variable timings and is thus
     inadequate to guarantee protection against cache-timing attacks.

   * Section 1.2 of http://cr.yp.to/hecdh/kummer-20140218.pdf gives two
     examples of DH implementations that were incorrectly claimed to
     take constant time.

I _think_ that all of the CFRG curve proposers are imposing the same
stringent requirements upon their speed reports that I impose upon mine.
For example, Microsoft says that one "should" avoid "leaking access
patterns" and should write "code which does not contain branches
depending on secret data". However, I haven't seen a clear statement of
exactly what protections _are_ actually provided by Microsoft's ECCLib.
Everything that ECCLib says---"regular, constant-time execution" and
"full protection against timing and cache attacks" and "no correlation
between timing and secret data"---is something that could just as easily
have been said about the broken OpenSSL code mentioned above. It would
be helpful for Microsoft to clarify the situation.

I don't mean to suggest that there's a huge performance difference
between constant-time ECC and non-constant-time ECC---usually the gap is
below 20%. I do mean to suggest that getting things right takes work.
What really bugs me about the NIST curves (and the Brainpool curves and
to a smaller extent Microsoft's curves) isn't their slowness but rather
their excessive complexity, leading to security problems:

   http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf

We know how to eliminate many of these problems by choosing our
cryptographic systems more carefully.

---Dan

---

From: David Jacobson <[email-masked]>
Date: Tue, 14 Oct 2014 06:14:08 -0700

> cryptographic systems more carefully.
Sometimes data dependent branches cannot be avoided without a serious 
performance penalty.  I'm thinking of modular inversion using the binary 
method. But it that case it is easy to use blinding.

1/k = b * (1 / (b * k))

where b is a random blinding value.

In this case, I think it is still fair consider this leakage resistant, 
even though the inversion is actually full of data dependent branches.

Of course, the time to compute b has to be included in the benchmark.  
But do those blinding values  have to be generated with heavy-weight 
schemes such as the algorithms in NIST SP 800-90A, or is it, in 
practice, safe to use something fast like the keystream from RC4?

     --David Jacobson

---

From: Adam Langley <[email-masked]>
Date: Tue, 14 Oct 2014 06:22:47 -0700

> where b is a random blinding value.

In practice, field inversion is done using Fermat's little theorem. I
agree that a blinded binary inversion should be faster, but Fermat's
little theorem is simple and safe.

Quoting from the curve25591 paper: "[Inversion] is about 7% of the
Curve25519 computation. An extended-Euclid inversion of z, randomized
to protect against timing attacks, might be faster, but the maximum
potential speedup is very small, while the cost in code complexity is
large."

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Yoav Nir <[email-masked]>
Date: Tue, 14 Oct 2014 16:49:02 +0300

Doesn’t it become better (or at least safer) at some point to set a timer before beginning the operation and then not use the results until the timer expires?

Sure this has a cost in memory, but any fool can write an implementation with an upper bound on processing time, whereas true constant time is both hard and has a 20% overhead (according to DJB’s message upthread).

Yoav

---

From: Watson Ladd <[email-masked]>
Date: Tue, 14 Oct 2014 08:05:47 -0700

> Sure this has a cost in memory, but any fool can write an implementation with an upper bound on processing time, whereas true constant time is both hard and has a 20% overhead (according to DJB’s m…

Any fool can download tweetnacl.c and get an implementation of
curve25519 that is constant-time. Likewise any fool can rip
implementations out of eBATS. We don't need custom implementations and
we certainly don't need people who can't write constant time code
doing crypto.

Furthermore, setting a timer doesn't deal with cache-based attacks. If
you want more speed than current proposals provide, let me interest
you in genus 2 Jacobians, endomorphisms, exotic uses of base change,
long before you get any benefit from removing timing-attack
resistance. Is Curve25519 really too slow?

Sincerely,
Watson Ladd

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 14 Oct 2014 10:42:56 -0700

>> Sure this has a cost in memory, but any fool can write an implementation with an upper bound on processing time, whereas true constant time is both hard and has a 20% overhead (according to DJB’s…
This ends up working very poorly for many reasons, beyond (as Watson 
said) not solving your problem.  Estimating maximum time is difficult, 
especially across different platforms, and especially on a loaded system 
where you might miss cache or be descheduled.  It will probably be more 
than 20% overhead, whereas DJB's dataflow-constant-time definition 
usually has *less than* 20% overhead (from my numbers, ~6% for 
Goldilocks on Haswell).  Worse, you will need to figure out how to 
measure time, and how to sleep. That means threading libraries or 
busy-waiting, neither of which is appealing.

It is also important to recognize that timing isn't the only side 
channel.  In particular, constant-time array indexing (with logic 
operations) will be much leakier than direct lookups for a power-channel 
adversary.  So for software which runs on a PC or server, then timing- 
(, cache-, branch-) invariance is the important thing, but on an 
embedded device, power, EM and possibly fault resistance are more 
important.  This will necessitate blinding instead of constant-time 
array indexing, and usually has a much higher overhead.  As Torsten 
said, smart cards don't even use constant-time multiply.

I skimmed the ECClib code.  They seem to take efforts to avoid leaking 
data to addresses, with a masking approach to constant-time lookups.  
They use cmovc; is that constant-time?  IIRC it is at least on recent 
Intel chips.  Anyway, I think the authors clearly intended to avoid 
dataflow to addresses or branches, though a confirmation would be nice.

I agree that they should have used untwisted Edwards instead of twisted 
Edwards, but that's easy enough to fix: CFRG can just adopt the 
isogenous untwisted curves instead.  Is this what you mean by "excessive 
complexity"?  Is there another problem with those curves, that other 
curves with the same field size would not have?

For the record, since DJB seems to be calling people out on precision: 
my Ed448-Goldilocks software is designed not to let secret data flow to 
addresses, branch conditions or operations which are variable-time on 
most CPUs.  If it does, that's a bug.  However, secret data can flow to 
multiply and multiply-accumulate instructions, which are variable-time 
on some embedded CPUs. Furthermore, my code is mostly in C and so is at 
the mercy of the compiler and optimizer.  Finally, while I'm not using 
any blinded variable-time algorithms today (such as blinded EGCD), I 
consider them to be a safe and reasonable thing to do in the right 
circumstances.

Cheers,
-- Mike

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 16 Oct 2014 16:34:40 +0000

Sean,

Are you planning to bring additional information on the issues that you
refer to below to the list?

Your additional input would be most welcome of course, but without
concrete details, it's difficult to factor your initial comments below
into our deliberations.

Thanks

Kenny 

On 08/10/2014 23:51, "Parkinson, Sean" <[email-masked]> wrote:

>Making a decision on new elliptic curves based on data that hasn't been
>corroborated by a 3rd party is bad practice.
>
>I have been implementing as many of the curves as I can and my
>performance results, so far, do not always match those that I have seen
>in papers.
>
>Also, I am concerned that, while some curves are being implemented to be
>constant time, not all curves are being implemented to be cache attack
>resistant. Either all implementations need to be resistant or all
>implementations not. Only then can a true comparison be made.
>
>Division of EMC

---

From: "Parkinson, Sean" <[email-masked]>
Date: Fri, 17 Oct 2014 04:42:09 -0400

While I still think that X25519 has speed and implementation simplicity advantages over numsp256t1, the fact that it can only be used for key exchange makes it difficult to recommend - you need another curve implementation anyway.
X25519 is already in use and, even if the CFRG don't recommend it, I believe it will be used - any speed advantage, despite code complexity cost, will be taken by implementers.

How this relates to other possible Montgomery curves I don't know. When a decision is made on the stronger curve a Montgomery equivalent may appear.

Sean

-----Original Message-----
From: Paterson, Kenny [mailto:[email-masked]] 
Sent: Friday, 17 October 2014 2:35 AM
To: Parkinson, Sean; [email-masked]
Subject: Re: [Cfrg] When's the decision?

Sean,

Are you planning to bring additional information on the issues that you refer to below to the list?

Your additional input would be most welcome of course, but without concrete details, it's difficult to factor your initial comments below into our deliberations.

Thanks

Kenny 

On 08/10/2014 23:51, "Parkinson, Sean" <[email-masked]> wrote:

>attack resistant. Either all implementations need to be resistant or 
>all implementations not. Only then can a true comparison be made.
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 17 Oct 2014 12:04:27 +0300

On Fri, Oct 17, 2014 at 04:42:09AM -0400, Parkinson, Sean wrote:
> While I still think that X25519 has speed and implementation simplicity
> advantages over numsp256t1, the fact that it can only be used for key
> exchange makes it difficult to recommend - you need another curve
> implementation anyway.

One can transform it to forms that support signatures, sharing the
base field implementation, which is by far the most annoying
part.

Unfortunately, all known EC signatures also require scalar field,
which is even more annoying to implement than base field (and
one can't use generic bignums there).

ECDSA is practicularly annoying here, because it needs inversion
in scalar field for signing. E.g. ECGDSA does not.

IIRC, The MS ECCLIB software (at least 1.1) does not implement
the corresponding scalar fields.

I earlier posted a message that gave list of suggested
operations. That also included fair amount of scalar field
operations (in order to support various ECC protocols).

-Ilari

---

From: Yoav Nir <[email-masked]>
Date: Fri, 17 Oct 2014 12:31:23 +0300

> X25519 is already in use and, even if the CFRG don't recommend it, I believe it will be used - any speed advantage, despite code complexity cost, will be taken by implementers.

I disagree. X25519 is in use in some specialized places, sure. But a recommendation from CFRG will lead to a standards-track document (or two) from TLS and another one from IPsecME. That leads to implementations in the major TLS libraries (OpenSSL, NSS, SCHANNEL) which then means it’s implemented in Chrome, Firefox, Internet Explorer and on the server side, most deployments of Apache and nginx. 

That’s a whole different scale of “used” compared with what we have now.

Yoav

---

From: "D. J. Bernstein" <[email-masked]>
Date: 18 Oct 2014 20:30:17 -0000

Michael Hamburg writes:
> I didn’t do this last time, which is (part of?) why the numbers from
> my own benchmarks do not match DJB’s numbers; see below.

Numbers are now coming into eBATS (see http://bench.cr.yp.to) for Mike's
fixed ed448goldilocks software, and confirm what Mike said about speed
compared to Microsoft's claimed speed. Here's the updated comparison
chart on Sandy Bridge, the microarchitecture selected by Microsoft for
benchmarks in http://eprint.iacr.org/2014/130.pdf:

    617000 cycles claimed: numsp384t1 (ed-384-mers),    ~2^192 security.
    666544 cycles measured on h6sandy: ed448goldilocks, ~2^224 security.
   1293000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.

These DH ratios don't _perfectly_ predict ratios for other operations---
the instruction mix changes, and speeds of other operations depend on
choices of precomputed table size---but at this point it's unsurprising
to see ed448goldilocks close to numsp384t1 for signature generation:

    231000 cycles claimed: numsp384t1 (ed-384-mers),    ~2^192 security.
    234844 cycles measured on h6sandy: ed448goldilocks, ~2^224 security.
    446000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.

Also signature verification:

    624000 cycles claimed: numsp384t1 (ed-384-mers),    ~2^192 security.
    729152 cycles measured on h6sandy: ed448goldilocks, ~2^224 security.
   1320000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.

Microsoft says that its goal is to justify "all choices" in NUMS with
"undisputable efficiency arguments"; but the actual measurements show
considerably better efficiency/security tradeoffs for other curves.
There's a lot more wiggle room for achieving not-quite-the-best speeds
than there is for achieving the best speeds.

---Dan

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 21 Oct 2014 00:24:41 +0300

>    1293000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.

IIRC, Mike has said that Ed448 software is not quite optimized as far
as it would go.

Also, these all are apples-to-apples comparisions (either all uncompressed
or all compressed), right?

>    1320000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.

Here Ed448 seems to be slightly slow for some reason.

I would have estimated (on very dubious grounds) ~680k.

-Ilari

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 20 Oct 2014 15:48:48 -0700

> On Oct 20, 2014, at 2:24 PM, Ilari Liusvaara <[email-masked]> wrote:
> 

Maybe not "as far as it would go”, but those numbers are for recent, optimized code, and fixes to the bug which was holding it back in previous SUPERCOP benchmarks.

> or all compressed), right?

No, Goldilocks is compressed and NUMS is uncompressed.

I’ll see if I can get (possibly untwisted) NUMS curves working in the Goldilocks source tree, which would make a slightly more apples-to-apples comparison.

> I would have estimated (on very dubious grounds) ~680k.

It’s due in large part to point decompression.  Point compression costs about the same as affine serialization.

For signing, Goldilocks needs to compress points but not decompress them, so it doesn’t take a speed penalty.  Also, its precomputed tables are slightly bigger than the ECCLib tables.  On the other hand, the signature is a bit slower than I’d have guessed; it might just be that the constant-time selection is vectorized, and SBR doesn’t have AVX2 and so uses SSE2 instead.

For ECDH, Goldilocks uses the Montgomery ladder, which avoids decompression at the cost of a slightly slower scalarmul.  So it has a small disadvantage vs ECCLib.

For verification, Goldilocks has to decompress and ECCLib doesn’t, which costs almost 10%.

Cheers,
— Mike

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 21 Oct 2014 14:09:10 +0300

> For verification, Goldilocks has to decompress and ECCLib doesn’t,

Signature verification uses double-sclar multiply, right?

Is your ds multiply constant-time? Because the one in ECClib
apparently isn't (everything else should be).

-Ilari

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 21 Oct 2014 10:11:55 -0700

> On Oct 21, 2014, at 4:09 AM, Ilari Liusvaara <[email-masked]> wrote:
> 

Yeah, it uses pretty much the same WNAF algorithm ECCLib uses, but it burns 60 or 70kcy first to decompress the public key.

— Mike