Re: [Cfrg] Curve manipulation, revisited

[Benjamin Black <[e-mail]>]

Adam has accurately described our position, and thanks to him for taking up
the slack while many of us were on holiday.

The request might've come from the TLS-WG, but it is almost inconceivable
that something CFRG recommended to TLS-WG would not be quickly adopted by
many other WGs. It is disingenuous to argue that since the request came
from TLS-WG nothing outside TLS-WG should be a consideration while also
arguing that things like cofactors for 1 (mod 4)  curves must be exactly
(8,4) without giving an example of how it matters to TLS-WG. The latter is
an implicit acknowledgement that the scope extends beyond TLS-WG.
Similarly, suggesting that TLS-WG could be given only X25519 without
Ed25519 being pulled in is either naive or an attempt to sneak them both in
the back door.

My use of the term "compromise" when presenting the current draft seems to
have opened the door to some misunderstanding. I used the term in the sense
of finding common ground rather than in the sense of introducing flaws. I
would not expect anyone in this process to find it acceptable to introduce
what they believe to be a security flaw, conspiracy theorists aside. As
Adam said, it would be a failure if the consensus that emerged from CFRG
did not include Microsoft, as it would be if it didn't include Google or
Akamai or anyone else with direct responsibility for protecting a billion
people online. We have chosen to move some on what is acceptable to us
because it is more important that there is a result that includes enough of
the things we believe are essential for delivering that protection than
that we get to be "right".

I've included more specific responses below.


Thanks,
b

--

The view voiced by several people that the 128-bit security level curve in
the draft is Curve25519 is a bit off base. First, the draft describes
generation of (twisted) Edwards curves and the 128-bit curve has minimal d
(given the addition of the newly manufactured cofactor constraint), while
Ed25519 does not. This is an advantage for both performance and rigidity
with a tiny reduction in simplicity of implementation, achieving a better
balance between security, performance, and simplicity. Second, the
specified base point is not the same and can't be the same without forcing
the (arbitrary) choice. The result is that it is straightforward to modify
existing Curve25519 implementations to use the new curve, but modification
is likely required.

On Wed, Dec 24, 2014 at 2:47 PM, D. J. Bernstein <[e-mail]> wrote:

> Once upon a time, Microsoft said that it was a "requirement" to have
> "rigid parameter generation for primes and curve constants" given the
> "security level".


Once upon a time, Dan said that is was a "requirement" to use single
coordinate ladders to eliminate invalid curve attacks against DH
implementations:

On Tue, Dec 2, 2014 at 1:28 AM, D. J. Bernstein <[e-mail]> wrote:
>
> Invalid-curve attacks completely break the simplest DH implementations
> in Montgomery coordinates _and_ in Edwards coordinates. Rather than
> blaming the implementor, we eliminate these security failures by
>
>    * adding twist security, for both Montgomery and Edwards, and
>    * switching to single-coordinate ladders.
>

Yet for Curve41417, ladders suddenly become optional, just as we've said
all along they should be:

"We use a windowing method with fixed window width for constant-time
single-scalar multiplication on Curve41417 in Edwards form. Our analysis
also
allows good estimates of, e.g., the cost of signature verification using
Curve41417.
Another option for single-scalar multiplication is the Montgomery ladder
for the
Montgomery form of Curve41417; this is not quite as fast as the Edwards form
but has the advantage of fitting the computation into less SRAM."

It seems performance is the real priority here and you will happily discard
things you insist are necessary for security when they conflict with
performance. At the 128-bit security level the ladder can be faster. At the
200-bit+ security levels the ladder is slower. Should we blame the
implementor who elects not to use a single-coordinate ladder? Should we
wonder why you would choose not to eliminate these security failures?

This section of your paper raises another interesting point. It seems a
slight performance drop in exchange for consuming less SRAM can be a
desirable property to you. In Adam's Faster Curve25519 post (
https://www.imperialviolet.org/2013/05/10/fastercurve25519.html), he
achieves significant performance improvements at a cost of 24KB of cache
for tables. Our NUMS 256 curve performs slightly slower than this, but only
requires 9KB for tables. The 15KB difference represents almost 25% of the
64KB L1 cache in a typical Xeon and almost 50% of the 32KB L1 data cache in
a typical ARM. It's not quite as fast but has the advantage of fitting the
computation into less SRAM.

On Mon, Dec 22, 2014 at 5:54 PM, Tanja Lange <[e-mail]>
 wrote:
>
> I think a competition has more to offer than a 'collaboration' where
> parties get more influence by having more people send emails to the list.
>

I'm not sure what point you are trying to make here. The people who haven't
submitted curves should remain silent? That is antithetical to the IETF
process. If you are suggesting it shouldn't be a process whereby a minority
attempts to "stuff the ballot box" by getting a few people to yell loud and
often to drown out differing opinions, then I agree. However, I don't think
we would agree on who might be doing that.


> What should count are the merits of papers, implementations, and internet
> drafts so that proposals get more influence by being objectively better.
>

"Objectively better" is unrealistic as it depends on which implementation,
which architectures, which benchmarks and which priorities people have for
various properties of the curves. The example above for different L1 cache
footprint shows how slippery "objectively better" can be. Another example
would be the large d in Ed25519 compared to the minimal d in the rpgecc
draft. The smaller d is "objectively better" both in terms of performance
and rigidity, but isn't quite as simple to move between twisted Edwards and
Montgomery.

On Thu, Dec 25, 2014 at 12:55 PM, Salz, Rich <[e-mail]> wrote:
>> desirable. But, to make progress, people need to try and understand
>> Microsoft's position.)
>
>Then perhaps, as you stated earlier in the note, it would be good if we
didn't have to guess.
>
>It's kinda funny that NUMS curve has us now wanting a NUMS rationale.  But
perhaps funny isn't the right word, maybe sad or >pathetic is.

You've been in this from the start, so I find it odd you don't recall any
of the numerous times this has been covered, Rich. We don't see the small
potential performance gains as worth the additional flexibility introduced
by manipulating prime selection like this. You are of course free to
disagree, but there is no "objectively better" answer as it is a trade-off.
You might also consider not calling things you don't understand or with
which you disagree "sad" or "pathetic".

On Mon, Nov 3, 2014 at 8:37 AM, Watson Ladd <[e-mail]> wrote:

> On Mon, Nov 3, 2014 at 8:18 AM, Paterson, Kenny
> <[e-mail]> wrote:
> > Alyssa,
> >
> <snip>
> >
> > However, if there's a reasonably simple way to ensure the highest
> possible
> > levels of trustworthiness in our recommendations with unduly compromising
> > efficiency and security, then I am prepared to sacrifice some extra time
> > to achieve it.
>
> That assumes that picking a generation method would "ensure the
> highest possible levels of trustworthiness". It's not clear to me that
> it would. Opponents of the performance approach can demonstrate the
> flexibility they insist exists by putting BADA55 in the hexadecimal
> form of the coefficients obtained by taking the minimal equation
> satisfying reasonable constraints on a performance-oriented prime.


There are at least two, possibly three, fallacies present in this
challenge. The first is that the enormous flexibility required to insert
such a string in the coefficients is at all a relevant metric. The second
is that the BADA55 work used what anyone who wasn't pushing a very
particular agenda would call "reasonable constraints". The third is that
the "performance approach" represents much additional performance, that the
performance gains are certain regardless of architecture or protocol, or
that any additional performance is free.

It's worth noting that we have at least two rather different
interpretations of BADA55 present in these discussions. Your interpretation
seems to be that if you can't insert BADA55 in the coefficients then the
process is rigid. Adam's interpretation (which might match Dan's) is that
any claim of rigidity in generation is necessarily limited.