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

Tanja Lange <> Tue, 02 September 2014 16:30 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 888481A045C for <>; Tue, 2 Sep 2014 09:30:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id S1SRYFsaMjiJ for <>; Tue, 2 Sep 2014 09:30:01 -0700 (PDT)
Received: from ( []) by (Postfix) with SMTP id 422851A045B for <>; Tue, 2 Sep 2014 09:30:01 -0700 (PDT)
Received: (qmail 14815 invoked from network); 2 Sep 2014 16:29:59 -0000
Received: from (HELO ( by with SMTP; 2 Sep 2014 16:29:59 -0000
Received: (qmail 27304 invoked by uid 1000); 2 Sep 2014 16:29:59 -0000
Date: Tue, 02 Sep 2014 18:29:59 +0200
From: Tanja Lange <>
To: Brian LaMacchia <>
Message-ID: <>
References: <>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <>
User-Agent: Mutt/1.5.11
Cc: "" <>
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 02 Sep 2014 16:30:04 -0000

Dear Brian,
Most of this is going in circles; the points you raise were discussed 
on the mailing list before and during the Toronto meeting. I would 
appreciate it if instead of starting a new round of this you could 
reply to some earlier emails.

>    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.
As several people pointed out now and in previous discussions, this
is conflating wire format, implementation, and curve form.

For security and ease of correct implementation I prefer Montgomery-x
for the wire format for DH and a compressed (but uniquely decompressible)
wire format for signatures.

>    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.
This is arguing about one particular suggestion and, again, mixes
wire format, implementation, and curve form.

>    3.       Despite repeated claims to the contrary, there is little evidence
>    that there is a consistent and significant performance benefit to
>    X25519. Indeed, as both the performance numbers in
> as well as the more recent performance
>    numbers posted by Andrey Jivsov demonstrate, the performance of X25519
>    does not significantly differ from that of (twisted) Edwards curves for
>    (non-ephemeral) ECDH at the same size.  For the case of ECDHE,
>    Dan Bernstein has argued for a definition of "ephemeral" that would allow
>    keys to be re-used for some amount of time allowing X25519 implementations
>    to amortize the cost of operations which are particularly expensive for
>    X25519 over multiple uses of the same key.* Such arguments are intended to
>    wrap requirements around specific curves, which is inappropriate for this
>    process. There has been no legitimate argument put forward for repeated
>    use of ephemeral keys in ECDHE.  As a consequence, the adoption of a
>    definition of "ephemeral" that does not allow key re-use (as previously
>    recommended) means that implementations of X25519 would require
>    conversions between curve forms to avoid a significant loss in
>    performance. These conversions are a negative from an engineering
>    perspective.

This is mostly about curve choices, not requirements. As far as the 
requirement of 'ephemeral = once' is concerned we've been through 
this discussion. For a speed comparison one can choose to go for
"KG+DH" or for "KG+nDH" for some value of n or look at several data 
points. However, for the security of the implementation, the system
must not break if the DH key is reused. I already said that after my
talk in Toronto. 

To say it simpler:
Requirement: security MUST not decrease if DH keyis reused
Selection criterion: speed of KG+nDH (incl., maybe exclusively, n=1)

There has been enough ripping into items a0-e) already, 
so I skip that apart from pointing out that you're arguing 
against one particular curve and mixing that with the requirements.
How about my up and coming T255.5? (just kidding).