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

["Paterson, Kenny" <[e-mail]>]

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.

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.

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