Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]

[Watson Ladd <[e-mail]>]

On Fri, Dec 12, 2014 at 2:13 AM, Paterson, Kenny
<[e-mail]> wrote:
> Dear Ben,
>
> Thanks for your continued contributions to this discussion. I think you
> make quite powerful arguments for keeping  draft-black-rpgecc-00 the way
> it is and not adding an extra criterion concerning divisibility of
> co-factors.
>
> Nevertheless, based on previous discussions on list (and discussions off
> list that Alexei and I have been having in our role as co-chairs), we have
> reason to believe that we will have a strong chance of making progress as
> a group, and unblocking our current logjam, if your team were to add this
> criterion to the draft.
>
> If you were also to add explicit isogenies enabling mapping to Montgomery
> form curves for the specific primes/curves at the 128-bit and 192-bit
> security levels, then this would also help move things along too.
>
> As co-chairs, then, we would like to strongly recommend that your team
> take these two significant steps to modify your draft. Modulo my
> understanding of IRTF processes, we would then be in a position to call
> for consensus on formal adoption of the draft by CFRG.

Why can't the turner-curve25519 draft be adopted? We could add the
curves for the 2^389-21 prime that Ilari has computed. As one of the
coauthors I'm surprised that no discussion of the shortcomings of this
draft, has taken place, instead we've been modifying a draft that was
further from being useful until it can be adopted.

I'm also surprised that we aren't using 2^389-21 for the same reasons
cited for using 2^255-19. We do not need complete agreement to go
forward. If we want a consensus result we'll still have gratuitous
incompatibilities and an unforced loss of additional performance, in
order to get one particular group on board. A process justified as
being driven by technical criteria has devolved into an openly
political horse trade, where we're supposed to be happy that the
2^255-19 prime is used, and ignore the issues with 2^384-317.

I'm happy to assist in writing whatever material is required to
specify the algorithms that we need to produce, such as a signature
algorithm and standalone description of the key exchange method.
Existing drafts and RFCs have fallen short here in the past. I can
only hope this does not take another 9 months.

>
> As a side note to *everyone* who has been contributing to our discussions
> to date: we are rapidly getting to the point where the process might well
> be taken away from us and solutions imposed from outside. CFRG's inability
> to reach a decision will not stand us in good stead as the preferred
> supplier of "crypto clue" to IETF.

Honestly, if the past 9 months is the best we can do, we deserve it.
(Not that the IETF works much better: the codec debate in RTCweb,
etc.) It would be a shame if the result was no clue in the IETF at
all, and I hope that we can figure out a way to make the CFRG more
effective.

While this conversation was going on I caught yet another draft with a
crypto problem, which got fixed. The authors had probably not realized
that there was a possible issue.

Sincerely,
Watson Ladd

>
> Regards,
>
> Kenny
>
>
> On 09/12/2014 05:56, "Benjamin Black" <[e-mail]> wrote:
>
>>>Benjamin Black writes:
>>>> The concerns do not apply to the twisted Edwards curve we generated,
>>>> only to the isogenous Montgomery curve.
>>>
>>>False.
>>>
>>>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.
>>>
>>>This is the primary motivation for twist security (and a closer look,
>>>as I've explained in detail, shows a twist-security criterion that's met
>>>by Curve25519 and not by PinkBikeShed). This has nothing to do with the
>>>superficial differences between the Montgomery x and the Edwards y, both
>>>of which support ladders.
>>>
>>
>>
>>The additional criterion you are describing is difficult to see as "twist
>>security". The curves in the draft are twist secure by any reasonable
>>definition, including your own SafeCurves twist security requirements.
>>Looking at your Curve25519 paper there
>> is a single mention of requirements on cofactors: "Multiply the secret
>>key by a small power of 2 to account for cofactors in the curve group and
>>the twist group". There is no reading of this that indicates selection of
>>(8,4) is needed or was even a consideration
>> at the time. In the recent Curve41417 paper I similarly find a single
>>mention of cofactor requirements: "For security we ... insist on the same
>>level of twist-security as Curve25519 ‹ the cofactors of the curve and
>>its twist are in {4, 8}." No mention of either
>> requiring the cofactors be equal or that they be minimal (which they
>>aren't).
>>
>>
>>Suggesting that (4,8) vs (8,4) introduces security risk is not a
>>technical argument about the strength of the curve. A sloppy implementor
>>could just as easily misread guidance and clear cofactor 4 on Curve25519.
>>A sloppy implementor could even more easily
>> skip checks for weak keys when using Montgomery Curve25519 outside of
>>DH. All Curve25519 documentation makes clear all 32-byte strings are
>>valid keys. That this is so only for DH is easily forgotten and I've not
>>found a Curve25519 implementation that performs
>> the required check.
>>
>>
>>Further, using p = 1 mod 4 primes introduces the concern you are raising.
>>Rather than blaming the implementor for clearing the "wrong" cofactor, we
>>can eliminate this "security failure" by using p = 3 mod 4 to ensure the
>>cofactors are equal, which is the
>> choice you made for both Curve1174 and Curve41417. Looking to SafeCurves
>>rigidity criteria we see Curve1174 described with "Curve and twist orders
>>chosen as {4*prime,4*prime} for security", but for Curve25519 we see
>>"Curve and twist orders required to be {4*prime,8*prime}
>> for security". Once again, no indication that (8,4) is required.
>>
>>
>>Looking through all the curves you list, we see a wide variety of
>>justifications for any given choice, with qualitative comments about
>>"security", "performance", or "efficiency", but little consistency in the
>>results:
>>
>>
>>Curve1174: "Curve and twist orders chosen as {4*prime,4*prime} for
>>security"
>>Curve25519: "Curve and twist orders required to be {4*prime,8*prime} for
>>security"
>>Curve41417: "Curve and twist cofactors limited to {4,8} for security"
>>
>>
>>Curve1174: "Edwards curve shape x^2+y^2=1+dx^2y^2 chosen for efficiency."
>>Curve25519: "Montgomery curve shape y^2=x^3+Ax^2+x chosen for efficiency"
>>Curve41417: "Edwards curve shape x^2+y^2=1+dx^2y^2 chosen for efficiency"
>>
>>
>>Curve1174: "Complete Edwards curve chosen for security."
>>Curve25519: No such statement.
>>Curve41417: "Complete Edwards curve chosen for security."
>>
>>
>>It is difficult to see this as rigidity.
>>
>>
>>I do not agree with your assertion that "adding twist security" _and_
>>"switching to single-coordinate ladders" is the solution against security
>>failures when it comes to invalid-curve attacks. Windowing
>>implementations on complete Edwards curves can be
>> implemented securely and eliminate any risks against those attacks. So
>>it is correct to say that in practice "the concerns do not apply to the
>>twisted Edwards curve we generated, only to the isogenous Montgomery
>>curve". In fact, looking at the Curve41417 paper,
>> you eschew the Montgomery (or Edwards) ladder in favor of windowing. In
>>this case, the performance advantages of Edwards trump the irrefutable
>>and essential requirement for eliminating "security failures" above via
>>use of single-coordinate ladders. Obviously,
>> single-coordinate ladders are not a hard requirement.
>>
>>
>>>If you disagree, please explain why you're requiring _any_ type of twist
>>>security for Edwards curves. Why aren't you saying something like "The
>>>larger d forced by 'twist security' is a violation of rigidity" and
>>>objecting to the whole concept of twist security for Edwards curves?
>>
>>
>>I am not objecting to twist security and the curves in the draft are
>>twist secure. I am objecting to the notion that cofactors (8,4) are in
>>any way more secure than (4,8). Your own statements on SafeCurves and in
>>the Curve25519 and Curve41417 papers support
>> there being no difference. I am also objecting to your repeated claims,
>>contradicted by your own work, that single-coordinate ladders are
>>required. And since there is no such requirement and no security
>>difference, I want the curve generated via the process
>> with fewest qualitative, opinion-based constraints.
>>
>>
>>
>>
>>b
>>
>>
>>
>>
>>
>>
>>On Tue, Dec 2, 2014 at 1:28 AM, D. J. Bernstein
>><[e-mail]> wrote:
>>
>>Benjamin Black writes:
>>> The concerns do not apply to the twisted Edwards curve we generated,
>>> only to the isogenous Montgomery curve.
>>
>>False.
>>
>>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.
>>
>>This is the primary motivation for twist security (and a closer look,
>>as I've explained in detail, shows a twist-security criterion that's met
>>by Curve25519 and not by PinkBikeShed). This has nothing to do with the
>>superficial differences between the Montgomery x and the Edwards y, both
>>of which support ladders.
>>
>>If you disagree, please explain why you're requiring _any_ type of twist
>>security for Edwards curves. Why aren't you saying something like "The
>>larger d forced by 'twist security' is a violation of rigidity" and
>>objecting to the whole concept of twist security for Edwards curves?
>>
>>---Dan
>>
>>_______________________________________________
>>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