### Re: [Cfrg] Curves as groups

Ilari Liusvaara <ilari.liusvaara@elisanet.fi> Sat, 09 August 2014 11:45 UTC

Return-Path: <ilari.liusvaara@elisanet.fi>

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 B9C4D1B27CC
for <cfrg@ietfa.amsl.com>; Sat, 9 Aug 2014 04:45:31 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: 0.699

X-Spam-Level:

X-Spam-Status: No, score=0.699 tagged_above=-999 required=5
tests=[BAYES_05=-0.5, J_CHICKENPOX_12=0.6, J_CHICKENPOX_22=0.6,
RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=no

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 RXPA3nSLmfWd for <cfrg@ietfa.amsl.com>;
Sat, 9 Aug 2014 04:45:29 -0700 (PDT)

Received: from emh02.mail.saunalahti.fi (emh02.mail.saunalahti.fi
[62.142.5.108])
(using TLSv1 with cipher ADH-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 0C57C1B27CA
for <cfrg@ietf.org>; Sat, 9 Aug 2014 04:45:27 -0700 (PDT)

Received: from LK-Perkele-VII (a88-112-44-140.elisa-laajakaista.fi
[88.112.44.140])
by emh02.mail.saunalahti.fi (Postfix) with ESMTP id 9419581870;
Sat, 9 Aug 2014 14:45:23 +0300 (EEST)

Date: Sat, 9 Aug 2014 14:45:22 +0300

From: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>

To: Michael Hamburg <mike@shiftleft.org>

Message-ID: <20140809114522.GA21774@LK-Perkele-VII>

References: <0C413841-D0E9-4D74-B390-8996C7EE77D2@qut.edu.au>
<798E796F-EE52-4EC5-A003-1C1EF07C2AA9@shiftleft.org>

MIME-Version: 1.0

Content-Type: text/plain; charset=utf-8

Content-Disposition: inline

Content-Transfer-Encoding: 8bit

In-Reply-To: <798E796F-EE52-4EC5-A003-1C1EF07C2AA9@shiftleft.org>

User-Agent: Mutt/1.5.23 (2014-03-12)

Sender: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>

Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/ytDiu2ZmnUmRXKxo-jCii0fg5DY

Cc: "cfrg@ietf.org" <cfrg@ietf.org>

Subject: Re: [Cfrg] Curves as groups

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, 09 Aug 2014 11:45:31 -0000

On Fri, Aug 08, 2014 at 06:14:58PM -0700, Michael Hamburg wrote: > > It’s some and some. Exposing only a kP+lQ allows you to expose an API > that deals only with affine points, or even only serialized points, > which avoids committing to the internal point representation format. > Furthermore, the curve might be specified one way for safety or clarity, > but implemented another way for speed. > > The MSR NUMS library operates on Twisted Edwards curves over a 3 mod 4 > field, which have an incomplete addition formula. This formula can be > used safely only if the protocol is is designed to avoid the troublesome > points, eg by clearing the cofactor. The kP+lQ actually computes > k(4P) + l(4Q) or something similar to avoid this problem. So there’s a > good reason not to expose the point addition function in the API. Some I-D (and probably some RFCs too) have ECC algorithms that need point addition and scalar multiplication without extra factors. Eg, equations of type: Y = a(Z + bX). Yes, one could premultiply scalars to cancel out extra factors, but: - There may be not-premultiplied points (e.g. Z above). - Applications would probably not appriciate having to do the premults.[1] So the library should also expose: - Point addition without prefactors - Scalar multiply without prefactors And these need to to be correct w.r.t. projection along <G>[2], and result in points in <G> if inputs are in <G>. Also: The primary curve specified SHOULD be complete. Rationale: Using incomplete primary curves awards bad implementations as it is not at all obvious what the exact failure cases are, probably resulting in lots of bad implementations (that appear to work, until attacker appears). MSR "NUMS" Edwards curves fail this (all are incomplete twisted Edwards). -x^2+y^2=1+(1-1/121666)*x^2*y^2 (mod 2^255-19) would pass, since it is complete despite being twisted. Library taking shortcuts is another matter, and then the library maker should know what they can get away with. Here's my own list of functions that I think ECC lib should provode for each Edwards curve (all constant time except failures or if said otherwise, group ops produce correct projection along <G>, produce elements in <G> if given inputs in <G>[3]): - Get curve by name (and possibly by OID). - Compute X=kG, where X is in Montgomery-x integer form (DH first step) - Compute Y=kX, where X and Y are in Montgomery-x integer form (DH second step) - Load (un)compressed group element in native/Weierstrss coordinates, erroring out on invalid point. - Save (un)compressed group element in native/Weierstrss coordinates - Get base prime - Get number of bits in base prime - Get order field size - Get number of bits in order field size - Group generator (actually generator of order-l subgroup) - Group (i.e. E) addition - Group substraction - Group scalar multiply - Group scalar multiply with G as base. - Group double-scalar multiply (can be variable-time?) - Check for low-order element in group (hX = 0? Edwards curves have tricks to do this fast, might not be constant-time) - Are two group elements equal? - Get native X coordinate as integer. - Get native Y coordinate as integer. - Get Weierstrass X coordinate as integer. - Load integer as (nonzero) scalar field[2] element, erroring out on invalid value - Reduce integer to (nonzero) scalar field (Z_l) element (timing depends on input length) - Are scalar field elements equal? - Is scalar field element zero? - Scalar field addition - Scalar field substraction - Scalar field negation - Scalar field multiplication - Scalar field reciproal - Convert scalar field element to integer The underlying types should depend on kind of thing but not the curve and can be opaque (hint: don't inline the sizes of various structures into whatever uses the library[4]). Additionally, the methods should wipe all temporaries from memory after completion, including from the stack[5]. This list was chosen so that widest variety of different ECC algorithms (excluding very specialized ones like pairing-based ones[6]) can be supported with minimum knowledge about curves or annoying[7] math in the application, and supporting multiple curves is as easy as possible. The Weierstrss coordinate methods are there in order to support legacy algorithms like ECDSA. [1] Those mults are in order field, which tends to be nastier to work with than the base field (due to the prime not being too close to power of two). [2] All practical ECC curves have well-defined projections along <G> and scalar fields (nobody uses the pathologic or infinite curves that don't). [3] This is weaker condition than producing correct answers for ever curve point, but should be sufficient to handle bad inputs safely. [4] Such inlining creates maintenance problems later. [5] Yes, I heard somebody complain about this loudly. [6] These also need specialized MOV-weak curves. [7] Any such math is likely done using bignum library. Which will be a disaster if it is e.g. calculation of S for ECDSA. -Ilari

- [Cfrg] Curves as groups Douglas Stebila
- Re: [Cfrg] Curves as groups Michael Hamburg
- Re: [Cfrg] Curves as groups Ilari Liusvaara