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

Benjamin Black <b@b3k.us> Sat, 13 December 2014 04:39 UTC

Return-Path: <b@b3k.us>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id AA1A71A1B75 for <cfrg@ietfa.amsl.com>; Fri, 12 Dec 2014 20:39:55 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.977
X-Spam-Level:
X-Spam-Status: No, score=-1.977 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id fj-nRtlWuh1u for <cfrg@ietfa.amsl.com>; Fri, 12 Dec 2014 20:39:51 -0800 (PST)
Received: from mail-wg0-f46.google.com (mail-wg0-f46.google.com [74.125.82.46]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5C4331A00BF for <cfrg@irtf.org>; Fri, 12 Dec 2014 20:39:51 -0800 (PST)
Received: by mail-wg0-f46.google.com with SMTP id x13so10729807wgg.33 for <cfrg@irtf.org>; Fri, 12 Dec 2014 20:39:49 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=ICdgMlwouuinI2wbR8GpeeunnjmeFGVVebFGiqG3X4o=; b=gyyxD+455PtHk1vE3fEB1ysLk2OoqHlM29ynGCxDy4zkuOEcAy9srZstGVzquDKzEL tC71SPAM11x1XRk1FNq3/+QsLj36drd/MebgS39wAKrlWnDjfWNuyvhwM+M85xmGQzI1 p8nfjwg04eNX4ue6VKDWsUAIYWrT+fu43l17qKl6dx5mLG7MuihEstMbfVKDfcVpy3QK 5mfcZw/84nQQ9ZxmezVp5JODUvlnEwNk7q5MDCFtpxpXX2fMJ44DHvxTuBsSQMN2cpXJ bUc8cCjvomAN+UwyhyQnXce68/VqwjzAuLx42XnrtaovQ7aMQc1+ZC4CO4U8xCG2Waen TWmQ==
X-Gm-Message-State: ALoCoQlGPLC1h53/GoanutwUj1J2U37HUcK1Ki7hzrCB2FTvhBxHpKuitb2Lofs3J8J4rY+zKOVp
X-Received: by 10.194.178.231 with SMTP id db7mr32493928wjc.112.1418445589631; Fri, 12 Dec 2014 20:39:49 -0800 (PST)
MIME-Version: 1.0
Received: by 10.217.191.195 with HTTP; Fri, 12 Dec 2014 20:39:28 -0800 (PST)
In-Reply-To: <D0B0DC9F.39BD0%kenny.paterson@rhul.ac.uk>
References: <CA+Vbu7ye3bytMZ-j8pfZixrjF8irTOoWmRo_GwjB0LphwjXq+Q@mail.gmail.com> <20141202092847.29027.qmail@cr.yp.to> <CA+Vbu7yQoYf3ei3MADhJ1iV6BcuqVUmkg8SkQ4ud=8m7pz7AvQ@mail.gmail.com> <D0B0DC9F.39BD0%kenny.paterson@rhul.ac.uk>
From: Benjamin Black <b@b3k.us>
Date: Fri, 12 Dec 2014 20:39:28 -0800
Message-ID: <CA+Vbu7w=uq9C2_LNUX=2boDqKS0zekniOWPd+mk42eWOS3ZVXQ@mail.gmail.com>
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
Content-Type: multipart/alternative; boundary="089e01419fc080eb1b050a11999e"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/zLuLm07UpHnNKzKARNHI8P9IMpI
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 13 Dec 2014 04:39:55 -0000

Kenny,

While we remain convinced there is no compelling technical reason to make
the change, we will acquiesce to the will of the co-chairs in the interest
of seeing this move forward.


b


On Fri, Dec 12, 2014 at 2:13 AM, Paterson, Kenny <Kenny.Paterson@rhul.ac.uk>
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.
>
> 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" <b@b3k.us> 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
> ><djb@cr.yp.to> 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
> >Cfrg@irtf.org
> >http://www.irtf.org/mailman/listinfo/cfrg
> >
> >
> >
> >
> >
> >
> >
>
>