Re: [Cfrg] Outline -> was Re: normative references

Watson Ladd <watsonbladd@gmail.com> Thu, 16 January 2014 20:58 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 854E91ACCE4 for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 12:58:03 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.4
X-Spam-Level:
X-Spam-Status: No, score=-1.4 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, J_CHICKENPOX_12=0.6, 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 Ldm9YopldFPT for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 12:58:02 -0800 (PST)
Received: from mail-wi0-x229.google.com (mail-wi0-x229.google.com [IPv6:2a00:1450:400c:c05::229]) by ietfa.amsl.com (Postfix) with ESMTP id C7ECE1ACCE0 for <cfrg@irtf.org>; Thu, 16 Jan 2014 12:58:01 -0800 (PST)
Received: by mail-wi0-f169.google.com with SMTP id e4so1230247wiv.0 for <cfrg@irtf.org>; Thu, 16 Jan 2014 12:57:49 -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:content-transfer-encoding; bh=Zk/qicbIDXDekEzqFk6Qed0IRVjvs1hCMVS0WAbgQDY=; b=c2k4QeIz5OyCFYcrOATzhbeeUPC3dchWSQpjT6jqq+muvd0ZlejpOKzq2dtwNfSVIU tMIk9vImv7qV9cXpKo5vsUpRkNK54UsXYNz1qNqhoG5AkahTQjgYRyyzWlddkQJd59Ur ljx8ajdY+2FcOSQ/O03KKPuTma4Ls3yWEQmdQAbol04vJakYgqlUy1c57//DgVqrEMUm miIsFF7jFErCJcirX9ma+1vgh4n6wnunt+r5IdG0ugu4dHd79K+XVQZvgsCNVD01+ZNH Qr92vOOONh54SsYlxTOGj5wKSCDODsXmm9zQfmDHJ717smlRAEHefXMiPwK6jusWEif7 cdVg==
MIME-Version: 1.0
X-Received: by 10.180.86.9 with SMTP id l9mr10026189wiz.20.1389905869110; Thu, 16 Jan 2014 12:57:49 -0800 (PST)
Received: by 10.194.242.131 with HTTP; Thu, 16 Jan 2014 12:57:49 -0800 (PST)
In-Reply-To: <52D8417B.9030908@cisco.com>
References: <CEFC6B5C.2C6E8%paul@marvell.com> <CACsn0ckSMUbEJ4F3bQ5KVMbhdPQw1MTMCce6B8uhMfA_V0Nupw@mail.gmail.com> <CEFCBB2E.2C792%paul@marvell.com> <3C4AAD4B5304AB44A6BA85173B4675CABA9A493F@MSMR-GH1-UEA03.corp.nsa.gov> <52D8417B.9030908@cisco.com>
Date: Thu, 16 Jan 2014 12:57:49 -0800
Message-ID: <CACsn0c=pUvCX-GSSSn13ZdgaTQhQM3k0O_0FTYrXw1_TE9GhuA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: David McGrew <mcgrew@cisco.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: Yaron Sheffer <yaronf.ietf@gmail.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Outline -> was Re: normative references
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: Thu, 16 Jan 2014 20:58:03 -0000

On Thu, Jan 16, 2014 at 12:30 PM, David McGrew <mcgrew@cisco.com> wrote:
> Hi Kevin, Paul, and Watson,
>
>
> On 01/16/2014 02:42 PM, Igoe, Kevin M. wrote:
>>
>> Paul Lambert
>> On Thursday, January 16, 2014 1:43 AM Paul Lambert wrote:
>>
>>> A truly ‘unified' public key system would support both signatures and
>>> key establishment with the same key.
>>>
>> Received wisdom is that using the same key for both key establishment and
>> signatures is a bad idea.  I believe the concern is that one protocol
>> might be used an Oracle to subvert the other.
>
>
> Agreed on that point, but there is a background issue here that I want to
> ask about.
>
> Watson said in a previous email:
>
>>
>> Montgomery curves are here for their blazing speed in ECDH without large
>> tables.
>> Edwards curves are here for their blazing speed in signatures where we
>> can't toss out
>> one coordinate. I'ld much rather use Montgomery for ECDH and Edwards
>> for signatures than Edwards for everything.
>
> So, what would this mean for an implementation that uses both ECDH and an EC
> signature?   That the math routines for both Edwards and Montgomery need to
> be included?    Or is translation between the formats very efficient?  If a
> single curve type and a single set of math/algorithms could be used for
> both, then an implementation could be simpler and more compact, and could
> perform better in software.

Edwards curves can be used for ECDH and outperform short Weierstrass
over the same
field, so one could use ECDH on an Edwards curve along with
signatures. The one issue
is there is a critical check Edwards curves require that Montgomery
curves do not when
receiving points.

Mike Hamburg pointed out there are clever tricks to do signatures on
Montgomery curves, but they are still
slower than variable time radix k algorithms on Edwards curves
signature verification.

You can use an isogeny to take advantage of the radix-k algorithms in
Edwards curves for
points on a Montgomery curve: this is why T25519 is in the latest
version (along with tons of typos,
and some point checks need to be performed on it, and I've not
documented the algorithm yet)
Right now this is faster for ECDH, but with better differential-addition
chains Montgomery will be back on top. And there is that special check
which makes me worry about poor quality implementations:
send an invalid Edwards encoding, and things can go badly wrong.

>
> In any case, it makes sense to consider a complete system, rather than to
> optimize ECDH in isolation, and optimize a signature method in isolation.

On big servers and clients cold code size is really not an issue:
provided your inner loop and the data it accesses fit in L1, all is
good, so
Montgomery and Edwards make sense to get an extra little bit of
performance. On tiny systems with enough RAM for high performance
Edwards implementations, one could use the Edwards curves. If get
smaller you will lose performance to Edwards curves vs. Montgomery,
but as Mike Hamburg points out in an email below there are special
tricks that can be played.

For a small system I would stick with Edwards: the loss of robustness
might be worth the smaller code size. However, other people might
disagree,
and as new performance tricks come out this could change.
Unfortunately eBATS doesn't include a MSP430, so I really don't know
what life is like
down there.

>From just a pragmatic perspective, people want to use both: the TLS
people want Curve25519 yesterday on top of whatever signature schemes
are lying around already (RSA PKCS 1.5 (blegh!), ECDSA, etc.), while
people who want to verify lots of signatures very quickly want Edwards
curves.
I don't feel confident enough in my knowledge of what will work best
to remove the option of having both from protocol designers.

Sincerely,
Watson Ladd

>
> David



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