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

[Paul Lambert <[e-mail]>]

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

>(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 <[e-mail]> 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.

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

>
>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:[e-mail]] On Behalf Of Alexey Melnikov
>> Sent: Monday, January 05, 2015 8:15 PM
>> To: [e-mail]
>> 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
>> [e-mail]
>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>> _______________________________________________
>> 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
>
>_______________________________________________
>Cfrg mailing list
>[e-mail]
>http://www.irtf.org/mailman/listinfo/cfrg