Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document

Watson Ladd <watsonbladd@gmail.com> Fri, 09 January 2015 00:50 UTC

Return-Path: <watsonbladd@gmail.com>
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 2F90C1A701D for <cfrg@ietfa.amsl.com>; Thu, 8 Jan 2015 16:50:17 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] 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 uygogwZG_Dys for <cfrg@ietfa.amsl.com>; Thu, 8 Jan 2015 16:50:15 -0800 (PST)
Received: from mail-yh0-x22a.google.com (mail-yh0-x22a.google.com [IPv6:2607:f8b0:4002:c01::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EB5A61A7017 for <cfrg@irtf.org>; Thu, 8 Jan 2015 16:50:14 -0800 (PST)
Received: by mail-yh0-f42.google.com with SMTP id v1so2824682yhn.1 for <cfrg@irtf.org>; Thu, 08 Jan 2015 16:50:14 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=8a2ASOiH0MBzq19zMtDv9FdGeZhYrlW9cav149xZpXU=; b=LvBDqb68YntvyHYQikThsE7Wy6SgISWmYKkpRacB0U6ybWnw/jj4Lwomw+Hi9FRy3/ zO+mSRTw/AKXhbSHjF8OBg1961OHX2XKcYzqCsHS9M8Upka01eUJwYmySWn9/onFMGjs 99EYJLF6nlB5S9d1ZkwN7G+BigvMYpZCBpbrdcoe19jUmq+Y1JhFT8wEJ6BfJVs3gno/ 5FWO+Fmx29Mdl4qxGC3ZK+0qN8y7nVxeaIqyJRgJ1MPg6HPx6lllADslDzSbVxAs3aqW mRz8hUOKWnYPPlMFEVnDF9r/+iebRi3/U1EPVMi3FQuvx+86rQdaRIZIlKKFt/P5vnyR h1ZQ==
MIME-Version: 1.0
X-Received: by 10.236.26.233 with SMTP id c69mr9049598yha.49.1420764614107; Thu, 08 Jan 2015 16:50:14 -0800 (PST)
Received: by 10.170.207.6 with HTTP; Thu, 8 Jan 2015 16:50:14 -0800 (PST)
In-Reply-To: <54AF1C99.5070308@brainhub.org>
References: <54AAE2CA.1080701@isode.com> <54AEF855.4090100@brainhub.org> <CACsn0cm01o4vhwwzs_WNpLq6vnA_cBchvLNS+Eyg5YZH_hQyMg@mail.gmail.com> <54AF1C99.5070308@brainhub.org>
Date: Thu, 8 Jan 2015 19:50:14 -0500
Message-ID: <CACsn0cmY1wVLTTznxz_gkHpP101sOXVwg+R9K_Lf4ODTJseSqg@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Andrey Jivsov <crypto@brainhub.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/CdCTzJPstwM13JCoyK5Rm6gqYpg>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document
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: Fri, 09 Jan 2015 00:50:17 -0000

On Thu, Jan 8, 2015 at 7:11 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
> On 01/08/2015 01:51 PM, Watson Ladd wrote:
>>
>> Three points:
>>
>> 1: There are recurring security issues caused by not sending
>> compressed points, as well as additional complexity
>> 2: We're not talking about signatures in this draft.
>> 3: Options are bad.
>
>
> Regarding options, this draft is a foundational document of a low-level
> crypto primitive. Protocols above can still pick a single wire format.
>
> The spec should allow, for example, S/MIME to select (x) for space saving,
> while TLS to select (x,y) for performance. (I am not making these choices
> here).

The performance gain you've been repeatedly citing is nonexistent for
variable base multiplications, and can be achieved for fixed based
mults anyway. Let's look at Curve25519 in detail:

A Montgomery ladder implementation does 255 rounds of a differential
addition and doubling, each differential addition 8.2 multiplications
(z=1 initially) This is a total cost of 2091 multiplications. At the
end there is an inversion, cost around 400 multiplications, grand
total 2491.

An Edwards-based implementation, using the fastest coordinates (which
are incomplete: I'll neglect this) with a window of width 5 will first
compute 31 multiples of the basepoint, then carry out 51 additions and
254 doublings. Each point addition costs 9.8 muls, each doubling 6.2
muls. The cheapest computation of the table is 15 doublings and 15
additions. At the end there is again an inversion, cost around 400
multiplications. The cost of this computation is 2714 multiplications.

Now, you could object that I've not used a large enough window, but
larger windows slow down side-channel protected lookups. You could
also object to my eschewing wNAF or some other advanced encoding, but
these are harder to protect against side-channels due to an irregular
pattern of additions. You could try to add in additional inversions to
save on multiplications by forcing z=1, but for curves this size the
gains are small. You could object to my inversion numbers: they are
probably too large.

For fixed based multiplications we use combs, so there is a speedup,
but Montgomery wire format doesn't interfere with this operation.

Furthermore, the TLS WG doesn't know nearly as much about cryptography
as we do. Other WGs are likely to know even less.

>
> The entire document is an optional primitive. SuiteB and Brainpool curves
> will be around for awhile.
>
> One might say that the proposed tweak retains a single format, which is
> (x,y), with an available (internal) optimization to use x with a Montgomery
> ladder.
>
>
> Re: security issues, the easiest fix would be to add one paragraph to to
> check that (x,y) is on the curve. The spec already deals with the cofactor>1
> in section 9.1.

An implementer who omits clearing the low bits isn't going to
completely break everything. One who omits this check will. Despite
lots of documents explaining the necessity of validation, plenty of
implementations fail to do it consistently.

Sincerely,
Watson Ladd

>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin