Re: [Cfrg] Curve manipulation, revisited

[Watson Ladd <[e-mail]>]

On Mon, Dec 29, 2014 at 2:57 AM, Benjamin Black <[e-mail]> wrote:
> 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.

What do you think we should do about signatures? The Microsoft
proposal of ECDSA with Edwards points has all the disadvantages of
ECDSA and none of the "advantages" of being already standardized. It's
remarkable that when presenting a draft after the deadline, you
haven't discussed fundamental details of what you want the result to
look like. What goes on the wire?

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

You've said repeatedly you're committed to supporting the result:
seems to me that we can pick whatever we like. Horse trading and
logrolling is not the way to do things.

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

I don't think this is right: I seem to remember the difference being
explained by isogeny vs. isomorphism.

Base points do not affect ECDH security. Why wouldn't you change it
for backwards compatibility?

You've changed the 128 bit prime to increase performance. Why not
apply the same logic to the choice of 384 bit prime?

The question is not about changing the logic of the proposals: rather
it's about applying that logic inconsistently, and gratuitously
breaking deployed implementations.

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

DJB sent a lengthy email to the list titled "Curves, Coordinates, and
Computations". In this email he explained that what an implementation
written by highly skilled and careful implementors for the ultimate in
performance does is not the same as one written for a maximum of
simplicity. The sentence you quoted had the word simple in it: that
word has a meaning you happily ignored.

Tweetnacl.c is probably the most widely used Curve25519
implementation. It's been translated into just about every language I
can think of. It can be very simple because it uses the Montgomery
ladder.

Should I take this email as saying you won't make the changes needed
to get Curve25519?

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

This is not a property of the curves, but of your implementation: the
same comb table optimization could be used by a Curve25519 optimized
implementation. That is, if it wasn't patented by Microsoft.

AGL's described implementation uses a table with 512 entries,
representing x^{16^(2*i+1)j} for i zero, j potentially zero. But one
can also use 512 entries to store a comb of 8 bits: the LSB of each
exponent byte, the 2nd to LSB of each exponent byte, etc, as the
Microsoft implementation of NUMS whatever does, and use 8 additions
and 8 doublings to compute the result. This has nothing to do with the
choice of curve or prime.

(There is a cost to what I outlined: the table has to be read in its
entirety each time through. There are several better choices here

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

What about the additional flexibility introduced by your new draft? A
user who listened to your old draft's claims of rigidity, shouldn't
accept the new drafts. Or is it that the "rigidity" claims have far
more to do with marketing than reality?

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

I think the entire idea that one can backdoor curves involves "alien
technology". But even granting that, if 1/2 of all curves are weak,
even a completely rigid process (assuming one exists) isn't much
better. It's only interesting when rare properties are being targeted.

If you actually read the BADA55 paper you would see they targeted
Brainpool, which had used the hash of a fundamental constant to
generate parameters.

By contrast there are only 100 primes or so meeting the kinds of
performance constraints we have. Shake up the requirements, maybe we
get 4 curves on each prime, so about 400 curves. This is a wild
overestimate.

With the NUMS approach, despite rhetoric of "a single curve for each
security level", users will actually accept a great deal more curves.

The additional performance of 2^255-19 vs 2^256-big costs nothing. It
exists on hardware ranging from 64 bit desktop machines to 32 bit
embedded processors and 18 bit FPGA and GPU multipliers. (GPUs got
better recently). In exchange for this hit you give us exactly
nothing.

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



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