Re: [Cfrg] Curve manipulation, revisited

[Watson Ladd <[e-mail]>]

On Mon, Dec 29, 2014 at 1:25 PM, Benjamin Black <[e-mail]> wrote:
> On Mon, Dec 29, 2014 at 5:36 AM, Watson Ladd <[e-mail]> wrote:
>>
>>
>> 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?
>>
>
> The proposal to use ECDSA with Edwards points allows use of the new curves
> with the only EC-based signature scheme currently supported by TLS.
> Proposing that does not preclude a new signature scheme and I expect such a
> scheme would be welcome. I don't see that there needs to be one draft with
> the kitchen sink.

The problem is that ECDSA requires Weierstrass curves. It's not ECDSA
if you do what you propose. I understand the idea, but I think it is
too clever by half.

As it is, given the use of X-Montgomery coordinates for the key
exchange, it will no longer be possible to use exactly the same
implementations for signatures and key exchange. We could finesse the
issue by using short Weierstrass points, but no one has an appetite
for that.

>
>>
>> >
>> > 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.
>>
>
> We will continue to implement things as appropriate for our customers and
> our business, neither of which are problems you have. We would prefer those
> things be what we believe are best. I don't see horse trading here, I see
> debate and collaboration. I understand in academia things are usually more
> adversarial.

Are you saying that customers won't use Curve25519, but will use your
proposed PinkBikeShed? What is the reason that PinkBikeShed is fine
and Curve25519 isn't?

About 6 months ago you insisted that Curve25519 wasn't acceptable to
your customers, and that Montgomery form wasn't either. Now magically
they are. Is this because your customer's views changed, or you invoke
them to support your own views, and never actually talked to them?

As for debate and collaboration, your current proposal uses the same
384 bit curve as before, despite the same issues as the old 256 bit
curve, which has been almost entirely replaced by Curve25519. Far from
deciding on an agreeable set of principles, you decide to make the low
security option more performant, and not change the higher security
option, while tacitly accepting E521, all choices which you had
previously strenuously argued against.

>
>>
>> >
>> > 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.
>>
>
> Curve25519 is the isogenous Montgomery curve to the generated twisted
> Edwards curve. Perhaps we are getting crossed by the confused and confusing
> naming and renaming of the various parts of Curve25519?

I thought that was PinkBikeShed. To be clear: you have added the (8,4)
requirement to the draft, and so get a curve whose isogenous
Montgomery curve is Curve25519, but haven't updated the draft yet?

>
>>
>> Base points do not affect ECDH security. Why wouldn't you change it
>> for backwards compatibility?
>>
>
> I said it is an issue, as did Adam. I didn't say anything beyond that.
>
>>
>> You've changed the 128 bit prime to increase performance. Why not
>> apply the same logic to the choice of 384 bit prime?
>>
>
> We did not change the prime to increase performance.

In original NUMS the prime was 2^256-189. In the rpg-00 draft it is
2^255-19. Looks like a performance motivated change to me. But at 384
the choice remains the same.

>
>>
>> The question is not about changing the logic of the proposals: rather
>> it's about applying that logic inconsistently, and gratuitously
>> breaking deployed implementations.
>>
>
> You side-stepped every fact in my earlier email enumerating many
> inconsistencies in Dan's choices and continue to do so. The differences
> between the draft and twisted Edwards Curve25519 are because the draft is
> consistent. You are demanding consistency and then complaining when it
> doesn't produce the result you wanted. If Curve25519 were being designed
> today, based on the last 7 years of advancement, it would look like what is
> in the draft.

Oddly enough, the Montgomery form in the draft is PinkBikeShed, which
was examined and rejected for Curve25519.

>
>>
>> >
>> > 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.
>>
>
> Dan said single-coordinate ladders are required, full stop: "Rather than
> blaming the implementor, we eliminate these security failures by...switching
> to single-coordinate ladders." I'm not ignoring any part of the quoted text.
> Whether the the ladder is simpler has no bearing.
>
>>
>> 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.
>>
>
> donna is the most widely used implementation.

Eeh, we could go back and forth on this one: Tor vs. everyone using tweetnacl.js

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

Cofactor requirements to go from PinkBikeShed to Curve25519, and
changes to the basepoint.

>
>>
>> >
>> > 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.
>>
>
> You aren't a lawyer and you, and everyone else on this list, needs to stop
> speculating in public about patents and how a given implementation might
> infringe them.
>
>>
>> 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.
>>
>
> Yes, a given curve performs differently depending on the exact
> implementation techniques used. Different techniques deliver different
> space/time trade-offs. That makes statements like "objectively better"
> dependent on the specifics of a given scenario, not some abstract Platonic
> ideal.

No, all curves with the same shape can use the same formulas and
coordinates and algorithms for computing scalar multiplies. The big
difference will be field arithmetic and size of constants. Which
techniques are used are orthogonal to which curves are picked.

Of course, if you want to unscrupulously promote a particular curve,
you can insist that well known optimizations for any group will only
apply to some groups, avoid using publicly verifiable benchmarks, and
make certain to implement optimizations for one curve that could be
applied to another, and screw up the benchmarking by borking the
setup.

Benchmarking is extremely tricky: all of the above can be done by
accident, and I've done them by accident.

>
>>
>> >
>> > 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?
>>
>
> What flexibility exactly?

A user who accepted NUMS, and now accepts this draft, is accepting how
many curves? Earlier you claimed that users who accepted Curve25519
were accepting too many curves. Now they aren't. Unless, that is, that
rigidity as you use it, has nothing to do with resistance to
backdooring, nothing to do with what users will accept, nothing to do
with how BADA55 defined it, and everything to do with marketing.


>
>>
>> >
>> > On Mon, Nov 3, 2014 at 8:37 AM, Watson Ladd <[e-mail]>
>> > wrote:
>> >
>> > 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.
>>
>
> Brainpool uses the two most common constants. BADA55 relies on carefully
> picking far less common constants. It's great marketing if your goal is to
> discredit work you think competes with your own. But if Brainpool is
> compromised, why would I trust anything from anyone responsible for
> producing it?

So you don't actually think actual rigidity matters, just how good a
marketing job you can do? Do you think the definition in BADA55 is
correct, or not?

>
>>
>> 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 draft is not NUMS.
>
>>
>> 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.
>>
>
> The draft has 2^255-19, what are you talking about?

You are correct, I meant 2^384-big vs. 2^383-31 or 2^389-21. But
neither of these are as good as 2^448-2^224-1: there are no good
choices of prime around 2^384. I and Mike Hamburg gave 2^389-21 a try,
and we couldn't compare to your listed numbers for 2^384-big directly:
I think we concluded they were in the same ballpark. We can get a lot
more security for very little drop in speed with 2^448-2^224-1.

To be clear, I don't like the fact that x-coordinate Montgomery isn't
mentioned in the draft, the poor choice of high security prime, and
gratuitous differences from existing software.

Sincerely,
Watson Ladd

>
>
> b



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