Re: [Cfrg] Curve manipulation, revisited

[Benjamin Black <[e-mail]>]

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.


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


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


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


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


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


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


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


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


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


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


b