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

[Benjamin Black <[e-mail]>]

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