Re: [Cfrg] On the use of Montgomery form curves for key agreement

Andy Lutomirski <luto@amacapital.net> Mon, 01 September 2014 18:55 UTC

Return-Path: <luto@amacapital.net>
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 272951A0340 for <cfrg@ietfa.amsl.com>; Mon, 1 Sep 2014 11:55:11 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.979
X-Spam-Level:
X-Spam-Status: No, score=-1.979 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_LOW=-0.7, 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 LNs5BncAhGKY for <cfrg@ietfa.amsl.com>; Mon, 1 Sep 2014 11:55:08 -0700 (PDT)
Received: from mail-la0-f47.google.com (mail-la0-f47.google.com [209.85.215.47]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 62F101A0292 for <cfrg@ietf.org>; Mon, 1 Sep 2014 11:55:08 -0700 (PDT)
Received: by mail-la0-f47.google.com with SMTP id s18so6433308lam.6 for <cfrg@ietf.org>; Mon, 01 Sep 2014 11:55:06 -0700 (PDT)
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=sWsBe8mB7YuXjPf+PJgJSFhfP/i73s6tuO5a5MEbkXU=; b=U7R28M9aMAqHmzXNEh3B6MNKFrSYS2k3N0JvN7NgfQHYjj2nyLojA0GXx0BUDOmuDd q4SoNTDx9qLeoYWa2Brsnz2llQCF8r/r2/bZjr9AcbHSkAI5aT2NOb2ZG0q7MrJANviP 5AheEFhc1RpJXoj0KTeLXs3JKGrtosdL84J/0Fu/JK4dDjHPFFHIbdEv8LBFmDISovos pYEenczA7ccQ8efX26xyAzOp+mpAFlJQ2dOrKd5a3uPWb3jgqirca3HvBYUjP0NKLg1W ejyFZhfsBI0VllBtA2zuTQbvhUVqBgPI73MoEaPrQqIsLBbgbE11I8HqCgtmeIeEYo2e ZNrw==
X-Gm-Message-State: ALoCoQnZWoairOPnC3PhJTc5hSglCRBNy0z0/JFqUfItUfSki80j5sBEZdS4Z4+/HG/SDRjOuVrg
X-Received: by 10.112.50.230 with SMTP id f6mr28858282lbo.56.1409597706717; Mon, 01 Sep 2014 11:55:06 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.152.36.106 with HTTP; Mon, 1 Sep 2014 11:54:46 -0700 (PDT)
In-Reply-To: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com>
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com>
From: Andy Lutomirski <luto@amacapital.net>
Date: Mon, 1 Sep 2014 11:54:46 -0700
Message-ID: <CALCETrUby2o5O3=tMkv20JTVkahSo5Wan4oSCPOspRnXhFCg+g@mail.gmail.com>
To: Brian LaMacchia <bal@microsoft.com>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/a3hj-wyVbjXhWkGOl_DPa4xd8fk
Cc: "cfrg@ietf.org" <cfrg@ietf.org>
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
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: Mon, 01 Sep 2014 18:55:11 -0000

On Mon, Sep 1, 2014 at 11:46 AM, Brian LaMacchia <bal@microsoft.com>; wrote:
> Folks,
>
>
>
> Here are the points that must be considered regarding the potential
> selection of a Montgomery form curve (and its realization using the
> Montgomery ladder):
>
>
>
> 1.       Requiring a Montgomery form curve for key agreement and for a
> particular security level means that implementations of protocols with both
> key agreement and digital signatures must implement both Montgomery curve
> arithmetic and additionally curve arithmetic for another curve form.  From
> an engineering perspective there is thus a clear drawback to requiring
> different curve forms for key agreement and digital signature at the same
> security level.

You can do arithmetic on a curve points given in Montgomery form
without a Montgomery ladder implementation by converting to a
different coordinate system.  I'm not sure why you'd want to in
anything other than the tiniest embedded implementation, but you
could.

Also, can we please stop claiming that things are "clear" problems?
This isn't clearly a problem.  As has been noted as nauseum on this
list, most of the work is in the field arithmetic, and a Montgomery
ladder and, say, Edwards EC arithmetic can share that.

>
> 2.       Assuming that implementations will implement more than one security
> level, choosing X25519 for ECDHE at the 128 bit security level will require
> implementations to use different curve arithmetic for the 128 bit security
> level than other security levels.  Again from an engineering standpoint this
> is a negative.

You're pre-supposing that other security levels wouldn't use
Montgomery coordinates.

[...]

>
> Those arguing for adoption of X25519 are requesting that CFRG
= (a) treat the
> 128 bit security level different from other security levels,

This is the first time that I've seen this request on this list.

> (b) force
> implementations of multiple security levels of key agreement to implement
> different curve arithmetic for different security levels,

I really don't see any justification for this claim.

> (c) force
> implementations of protocols with both key agreement and digital signatures
> to implement different curve arithmetic for those two operations, even at
> the same security level,

This would be an option available to implementers, not a requirement.

> (d) force point conversions between curve forms to
> avoid efficiency loss in ECDHE, and

Now I'm completely lost.  I honestly have no idea what you mean by this.

> (e) to do (a)-(d) for no clear gain in
> performance. These points overwhelmingly contradict arguments in favor of
> forcing the use of the Montgomery form for key agreement, especially for
> only a single security level.
>

--Andy