Re: [Cfrg] Curves as groups

Michael Hamburg <mike@shiftleft.org> Sat, 09 August 2014 01:15 UTC

Return-Path: <mike@shiftleft.org>
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 6E2F31A02FB for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 18:15:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.156
X-Spam-Level: **
X-Spam-Status: No, score=2.156 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, HTML_MESSAGE=0.001, J_CHICKENPOX_22=0.6, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, 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 z4ECkja3g0He for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 18:15:01 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6D6D31A02F9 for <cfrg@ietf.org>; Fri, 8 Aug 2014 18:15:01 -0700 (PDT)
Received: from [10.184.148.249] (unknown [209.36.6.242]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 1C8C83AA27; Fri, 8 Aug 2014 18:14:07 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1407546847; bh=/Q7Fu1xe46S5+BnT66EUjsO9dmpspWQP5XcK44vg8gM=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=P3l6sloLOt6uVeCjimxWLQa2hGaBE+npAgW+/yXzyv0h/rOZL6g5/ge1lNZViscrB /98mzmSfr2urda8WL3taCw6ZdHoJ7XI0LpWn07rNMZQATHqTYlNCr4YpYdDFQwze67 sIGzL15bBl8req8JAtbFwXj1aMDwvV6JsNlOvDeQ=
Content-Type: multipart/alternative; boundary="Apple-Mail=_9D3EC503-1DF8-475D-A29A-31E66FC6FC50"
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1971.5\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <0C413841-D0E9-4D74-B390-8996C7EE77D2@qut.edu.au>
Date: Fri, 8 Aug 2014 18:14:58 -0700
Message-Id: <798E796F-EE52-4EC5-A003-1C1EF07C2AA9@shiftleft.org>
References: <0C413841-D0E9-4D74-B390-8996C7EE77D2@qut.edu.au>
To: Douglas Stebila <stebila@qut.edu.au>
X-Mailer: Apple Mail (2.1971.5)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/RoUNnyD4WXob_cGzHOlf5CyhJdo
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 01:15:03 -0000

> On Aug 8, 2014, at 3:36 PM, Douglas Stebila <stebila@qut.edu.au> wrote:
> 
> Do members of CFRG think it important that the curve(s) we recommend be usable as arbitrary groups?  By this I mean that the implementations readily expose both a scalar point multiplication operation and a point addition operation.  

I think that’s a good idea.

> Utility as arbitrary groups would I think imply criteria R3 (Desired: re-use components between signatures and key exchange algorithms) but the reverse is not necessarily true.  

Right.  For example, you can do Schnorr signatures with Curve25519’s scalar multiplication API, so long as the signature is in (kG, s) form.

> Curve25519+Ed25519 together give key exchange and signatures, but are high-level cryptographic functions, not groups.  The Curve25519 private API has scalar point multiplication functions but not point addition; the Ed25519 private API has both.  The NUMS library has public interfaces for scalar point multiplication and kP+lQ, but arbitrary point addition is only in the private API with a disclaimer on context of use.  To what extent are these a choice by implementers to only implement the functions needed to achieve their desired cryptographic scheme versus inherent to the mathematical design?

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.

Likewise, my own curve, Ed448-Goldilocks, is specified as an Edwards curve.  But internally my implementation uses an isogenous twisted Edwards curve for speed.  The isogeny clears the cofactor, so this approach is also completely safe.  The library doesn’t need to add points on the untwisted curve, so it doesn’t have that API, but it would be easy and safe to write if it were needed.  By the way, specifying untwisted and implementing twisted is a carefully thought out strategy, and I would recommend adopting it for any CFRG-approved cofactor-4 curves; see http://eprint.iacr.org/2014/027 .

> While criteria R3 will ensure we have something that we can use for key exchange and signatures immediately, I think it would be good for cryptographers to also have good, plain old groups from elliptic curves, for whatever new schemes we may invent or try to implement over the next 10 years.  Prior IETF initiatives (RFC 3526, RFC 5114) seem to have focused on groups rather than key exchange / signature functions.
> 
> Douglas

Agreed.

Cheers,
— Mike