Subject: [Cfrg] Montgomery yet again (was Re: Adoption of draft-agl-cfrgcurve-00 as a RG document)

From: Watson Ladd <[email-masked]>
Date: Fri, 9 Jan 2015 10:37:09 -0500

(Replace this email with the discussions had in May on teleconference,
and over this summer as shown in "Progress on curve recommendations
for TLS WG", http://www.ietf.org/mail-archive/web/cfrg/current/msg04760.html
and the ensuing discussion. The last note is from
http://www.ietf.org/mail-archive/web/cfrg/current/msg04966.html. If
you've read these, you don't need to read this email )

On Fri, Jan 9, 2015 at 8:59 AM, Joppe Bos <[email-masked]> wrote:
> Hi all,
>
> The current version of the draft contains methods for parameter selection
> (section 6) and a single recommended curve (section 7).
> IMO the natural approach would be to first agree upon a parameter selection
> procedure (one draft) and subsequently, when a large portion of the
> community agrees that this selection procedure is sound, use this procedure
> to select new curves (another draft). Currently, we are changing the
> selection procedure to match an existing curve. If we want curve25519
> because it is fast and widely deployed then we should state this clearly and
> refrain from modifying the selection procedures because this might have a
> negative impact on the potential selection of curves in the future.

How does the existence of a selection procedure that gives Curve25519
and particular choice of an isogeny equal "changing the selection
procedure to match an existing curve?" In fact, there are good reasons
to favor the particular twist security criteria and use the given
isogeny in any case.

>
> Please find below some comments on the current version of the draft.
>
> Section 7:
> - The specification of the parameters is done either in formula form (p), in
> decimal (d) or a formula + hexadecimal (order). Maybe use the same notation
> (e.g. either decimal or hexadecimal) everywhere to avoid confusion?
> - For completeness it might be good to give the corresponding (short)
> Weierstrass form of the curve(s).

Not sure why we want forms that won't be used. I agree we should
explain the isogeny in more detail.

>
> Section 8-10:
> These sections are curve25519 specific, this should be stated much clearer.
>
> Section 8:
> As far as my understanding goes there was no consensus on the wire format of
> field elements.
> This section states that "when transmitting field elements in the
> Diffie-Hellman protocol below, they MUST be encoded as an array of bytes, x,
> in little-endian order". Maybe some notation got confused here, what is this
> x-coordinate? The only x defined are on the Edwards curve while I think here
> the Montgomery curve is meant (the u-coordinate from section 7). This should
> be fixed or stated clearer to avoid confusion.

Good catch!

>
> Section 9:
> - It is not entirely clear to me why such low-level details are provided in
> this draft. Is it expected from the CFRG to deliver implementation details
> for algorithms or just a specification of curves plus related info (such as
> wire formats)? If we want to provide such low-level details then why not
> also state how to implement the field arithmetic?

Paul Lambert argued that we need implementation details, and I think he's right.

Field arithmetic is going to look different on 32 and 64 bit
platforms, and on some architectures might be very strange. Maybe it's
worth it: I don't have strong feelings one way or the other. I do
agree that side-channel free algorithms may be worth presenting,
particularly as the textbook algorithms are not.

> - Why is only the approach based on the Montgomery ladder stated in this
> section? There is nothing wrong with the Montgomery ladder but it is not the
> best solution for all reasonable definitions of best. The implementer has
> the choice, as stated before on this list, to compute DH on (for instance)
> the corresponding Edwards or Weierstrass curve. Currently it looks as if the
> CFRG recommends to use the Montgomery ladder for all scenarios;  something
> we know is suboptimal in terms of performance for higher security levels.
> Moreover, imagine the scenarios where people use (twisted) Edwards curves
> for signatures. Then implementing DH using the Montgomery ladder implies
> managing code for both the Montgomery and the twisted Edwards curve and,
> following the reasoning expressed by some people on this list, a larger code
> base implies more room for errors which implies a less secure approach.
> - This ladder implementation defines the usage of cswap ("due to the
> existence of side-channels in commodity hardware"). Although this adds some
> protection this algorithm is not secure in many realistic threat models
> (e.g. in hardware security). To me, it looks quite arbitrary to just protect
> against one type of attack and not against a whole range of other
> side-channel attacks. The threat model should depend on where the
> implementation will be used and therefore it is up to the implementer to
> make the appropriate design decisions and introduce the adequate
> countermeasures.

While the hardware threat model is "realistic", I don't see why we
should ignore settings in which cache-based and timing-based attacks
are of concern and DPA isn't, and I don't see why we should remove
information about protections that are adequate to this setting,
because they aren't for all settings. The setting this algorithm is
designed for is rather common. Implementors are free to ignore it if
they have the understanding and need for a more appropriate algorithm
for their setting.

Right now many implementations are not side channel secure at all. We
keep hearing about the implementor having to do this and that and the
other thing, and it's all their fault when it doesn't work. Well, has
anyone bothered to check if the implementor can do the job? I have,
and the results are pretty ugly. We should err on the side of
providing more assistance and guidance rather than chuck the plans
over the wall, and come back to investigate the damage. There are real
risks with using twisted Edwards form for DH that don't exist for
ECDSA style signatures, or signatures that send r and s instead of R
and s in Schnorr.

As for complexity, we are discussing whether or not an additional 20
lines of code (if that!) will make maintenance more difficult.
Certainly, more test vectors and the like will need to be added, but
that's true anyway for signatures and DH. I'm surprised that this
argument is getting made: OpenSSH has adopted Curve25519 and Ed25519,
without worrying about the increased code size. Likewise, implementors
of TLS libraries haven't raised this as a major concern. It's true
that x-coordinate only DH isn't compatible with some protocols like
HMQV, but these are rather uncommon.

Sincerely,
Watson Ladd

>
> Best regards,
>
> Joppe
>
> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Alexey Melnikov
> Sent: Monday, January 05, 2015 8:15 PM
> To: [email-masked]
> Subject: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document
>
> This message starts 2 weeks adoption call (ending on January 19th 2015) on:
>
> https://www.imperialviolet.org/cfrgcurve/cfrgcurve.xml
>
> as the starting point for the CFRG document which describes an algorithm for
> safe curve parameter generation for a particular security level and also
> recommends a specific curve (2^255-19) for the 128-bit security level.
>
> Please reply to this message or directly to CFRG chairs, stating whether you
> support (or not) adoption of this document. If you do not support adoption
> of this document, please state whether you support adoption of any
> alternative document or whether you want a particular change be made to the
> document before adoption.
>
> Chairs ask not to reiterate previously expressed technical opinions or
> arguments. But clarifying questions on the adoption call are welcome.
>
> While making your decision, please keep in mind
>
> http://www.ietf.org/mail-archive/web/cfrg/current/msg05813.html
>
> Alexey,
> On behalf of CFRG chairs.
>
> P.S. Editors of draft-black-rpgecc-01 and
> draft-turner-thecurve25519function-01 can become co-editors of the adopted
> document, if they choose to do so. Email chairs directly if you are willing
> or not willing to do so.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> 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

---

From: Paul Lambert <[email-masked]>
Date: Fri, 9 Jan 2015 10:24:34 -0800

On 1/9/15, 7:37 AM, "Watson Ladd" <[email-masked]> wrote:

>for TLS WG", 
>http://www.ietf.org/mail-archive/web/cfrg/current/msg04760.html

Thanks - yes.  Section 9 is my favorite section :-)  I amy be an
extremist, but the closer algorithms are to real code the better Š with
and emphasis on readable code over optimizations.

The CFRG should not fall into the trap of just defining the parameters
associated with a curve.  We are clearly now very focused on algorithms
using the curve parameters that have specific security properties.

As a systems designer, if we consider the object model, the methods
associated with the data are of critical importance.  The details of the
methods now must go beyond just interoperability, they must include the
detailed steps to describe both optimizations and the demonstration of
constant time performance.

One of the failing now with the NIST curves is their lack of well
documented constant time implementations.  Yes - I know technical papers
abound that describes approaches.  What¹s published now as a Œcookbook
type¹ algorithm is: https://www.nsa.gov/ia/_files/nist-routines.pdf
There¹s also: http://www.rfc-base.org/txt/rfc-6090.txt

Paul