Subject: [Cfrg] E-521 vs. numsp512t1

From: "D. J. Bernstein" <[email-masked]>
Date: 22 Oct 2014 21:34:47 -0000

Rob Granger and Mike Scott have posted a new paper "Faster ECC over
\F_{2^521-1}" (https://eprint.iacr.org/2014/852) reporting ECC speeds
mod 2^521-1, and in particular the first (as far as I know) serious
implementation of E-521.

Granger and Scott haven't contributed the software to SUPERCOP yet, and
they report only Haswell speeds, while Microsoft's paper reports only
Sandy Bridge speeds, so comparison isn't easy. I downloaded the E-521
software and tried it on Sandy Bridge:

   * E-521: slightly under 1.12 million cycles.

   * numsp512t1 (ed-512-mers): 1.293 million cycles, according to the
     Microsoft paper.

To summarize, on the microarchitecture selected by Microsoft for
benchmarks, Microsoft's claimed numsp512t1 speeds are about 15% slower
than these higher-security E-521 speeds.

At a lower level, the new paper reports 155 Haswell cycles for field
multiplication, a noticeable improvement over the 167 Haswell cycles
mentioned in Mike Hamburg's message

   https://www.ietf.org/mail-archive/web/cfrg/current/msg04984.html

(using a different technique). Mike had already estimated that his
approach to E-521 would beat the Microsoft results for numsp512t1.

For comparison, Microsoft claimed in July to "show that ... moving from
512 bits to 521 bits ... degrades performance by a factor 1.2". This is
yet another example of the dangers of measuring _some_ implementation
rather than measuring the _best_ implementation. There's clearly a big
difference in performance between

   * a 2^521-1 implementation from someone who never had an incentive to
     use state-of-the-art techniques and
   * a 2^521-1 implementation from someone who wants it to run fast.

The new E-521 code is also surprisingly short; we're not talking about
some difficult tradeoff between simplicity and performance.

The code actually works mod 2^(58*9)-c where c=2, and relies heavily on
c being very small. This appears to add even more evidence for the idea
that "make everything as fast as possible" creates rigidity: there are
many primes that provide tolerable speeds but there are only a few
primes that provide truly top speeds. (When I say "truly top" I mean
something even better than Pareto-optimal; see my message

   https://www.ietf.org/mail-archive/web/cfrg/current/msg04894.html

for details.)

If further analysis continues to support the statement that 2^521-1 is
exceptionally fast, how many people will argue that downgrading to
2^512-569---sacrificing security and sacrificing speed---is a good idea?

I don't understand how the "512 is a power of 2" statement is supposed
to be relevant. I also don't understand the "match 2^256" argument. As
Adam Langley wrote:

   Above the 120ish bit level one is no longer fighting stronger
   attackers, but hedging against a breakthrough (but not too much of
   one). Matching 192 or 256 bit security levels is a *misunderstanding*
   in the wider community, and is thus of the lowest priority.

I realize that the TLS WG requested "128-bit" and "256-bit" and maybe
"192-bit" but all indications are that this was a knee-jerk list---not
something CFRG should take seriously, and certainly not something that
should override CFRG's security judgment. If there's doubt about this
then surely the TLS WG can provide more clarification as to its needs.

I don't mean to suggest that it's obvious that CFRG should pick _any_
curve at this stratospheric >500-bit size. I simply don't see the
argument for picking 2^512-569 rather than 2^521-1.

---Dan

---

From: David Leon Gil <[email-masked]>
Date: Wed, 22 Oct 2014 19:19:44 -0400

> mod 2^521-1, and in particular the first (as far as I know) serious

The implementation djb mentions is available on their website:

http://indigo.ie/~mscott/{ed521,ws521}.cpp

--

I've put this code in a GitHub repo, as it needed to be modified
slightly to work with Clang++ HEAD:*

https://github.com/coruus/E521

* This is the first time I've encountered a compiler taking advantage
of the fact that undefined behavior ensues when a function not
declared void doesn't return a value. Clang++ generates code that just
continues to some other function...and eventually SIGSEGVs.

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 23 Oct 2014 02:42:58 +0300

> http://indigo.ie/~mscott/{ed521,ws521}.cpp

Watch out (from ed521.cpp):

void mul(int *w,ECp *P)
{
	ECp W[33],Q;
	precomp(P,W);

	copy(&W[w[86]],P);  
	for (int i=85;i>=0;i--)
	{
		if (w[i]>=0) copy(&W[w[i]],&Q);
		else         neg(&W[-w[i]],&Q);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
		window(&Q,P);
	}
	norm(P); 
}

That does not look constant-time...

-Ilari

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 23 Oct 2014 10:06:36 -0700

> 		if (w[i]>=0) copy(&W[w[i]],&Q);
Also, on curves at moderncrypto dot org, Samuel Neves is reporting (and 
I can confirm) that the performance numbers do not account for 
TurboBoost.  He measured a slower but still impressive ~884kcy.

That said, the Granger-Scott implementation does not take advantage of 
vectorization or assembly optimizations, even to the degree that 
Goldilocks does (asm wide multiply and accumulate, mostly there to 
constrain the scheduler and register allocator).  It would be 
interesting to check its performance with more optimization.

On a related note, one of the numbers I reported for Goldilocks (~480k 
Haswell cycles) also did not account for TurboBoost.  DJB's Titan0 
SUPERCOP measurement of 529kcy on Haswell is accurate.  It turns out 
that on Ubuntu at least (Linux 3.13.0-29), disabling HyperThreading 
re-enables TurboBoost, so be careful what order you do it in.

Cheers,
-- Mike

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 23 Oct 2014 10:51:30 -0700

On Thu, Oct 23, 2014 at 10:06 AM, Mike Hamburg <[email-masked]> wrote:
> Also, on curves at moderncrypto dot org, Samuel Neves is reporting (and I
> can confirm) that the performance numbers do not account for TurboBoost.  He
> measured a slower but still impressive ~884kcy.
>
> vectorization or assembly optimizations, even to the degree that Goldilocks
> does (asm wide multiply and accumulate, mostly there to constrain the
> scheduler and register allocator).  It would be interesting to check its
> performance with more optimization.
>
> Haswell cycles) also did not account for TurboBoost.  DJB's Titan0 SUPERCOP
> measurement of 529kcy on Haswell is accurate.  It turns out that on Ubuntu
> at least (Linux 3.13.0-29), disabling HyperThreading re-enables TurboBoost,
> so be careful what order you do it in.
>

I haven't tried it for these types of tests, but something like:

$ perf stat ./whatever_benchmark

will count cycles directly.  As long as the benchmark isn't too
memory-heavy and as long as it runs enough loops to wash out the
startup time, it might be a much simpler way to do this kind of
benchmarking.

--Andy