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

Andy Lutomirski <> Mon, 08 September 2014 19:34 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 07D961A0326 for <>; Mon, 8 Sep 2014 12:34:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0.721
X-Spam-Status: No, score=0.721 tagged_above=-999 required=5 tests=[BAYES_50=0.8, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id VfgiTldF6yc0 for <>; Mon, 8 Sep 2014 12:34:25 -0700 (PDT)
Received: from ( []) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 56D671A02D4 for <>; Mon, 8 Sep 2014 12:34:25 -0700 (PDT)
Received: by with SMTP id 10so8501300lbg.16 for <>; Mon, 08 Sep 2014 12:34:23 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=HuCuKUO3KGqeRHMt2K3RdxycP8XoqDvC0RZPd4ivgQQ=; b=dXItXdbKTz8BKYw5JgqY22HHkeBakdi1EFdhUJjVqXUArhArjw4KQ9SGXreLCcSoCA N1Z7G4as27TXbZDEons3O3BLbmZdMjUiD8wHvIoLMqn+/QayWQpNg8zhhliOlVbvYiPP eXRF9pphLgYWAH8Iaj1eLr+Hny83Hh+o3q3FSYNyl4kMGwaDZmir3B56EwjGQNF5aEVy LA81s7CVLwcJnzyvbxv/ZaTal+RKZlf7TGNWwHiBNBNvWCDI6f7/ZbXBGXRPebmbPqGi 4YVp1MeHLevQehcP+N8+f6PtAuSi/wTPaNW/GzkqRU8A85S8rPAv/lyr6pij4i+ZqGsR +bqQ==
X-Gm-Message-State: ALoCoQkHkc8MoldL1NW1WoNLDkzI2J0UlqY7d3qqYP13AJT6tKyh3KVULLhw4evgS+pEsSAKrvfz
X-Received: by with SMTP id q2mr31305625laq.11.1410204863388; Mon, 08 Sep 2014 12:34:23 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Mon, 8 Sep 2014 12:34:03 -0700 (PDT)
In-Reply-To: <>
References: <> <> <> <> <>
From: Andy Lutomirski <>
Date: Mon, 08 Sep 2014 12:34:03 -0700
Message-ID: <>
To: Nico Williams <>
Content-Type: text/plain; charset="UTF-8"
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: Mon, 08 Sep 2014 19:34:27 -0000

On Mon, Sep 8, 2014 at 11:51 AM, Nico Williams <> wrote:
> On Wed, Sep 3, 2014 at 12:27 AM, Tanja Lange <> wrote:
>> What exactly do you think the security implications of key reuse are?
>> Defining ephemeral in a time-based manner ist quite normal; the important
>> thing to guarantee PFS is to delete the key afterwards, not whether it is
>> used for 1 connection or 10 seconds (with potentially 0 connections).
> +1.
> What matters is that the private key be destroyed some time after it's
> been used.  That amount of time cannot be zero (it could, with the
> right hardware, but that's another story).  It has to be some small
> amount of time.  .01 seconds or 10 seconds doesn't make much
> difference -- it doesn't make _any_ substantial difference.
> As for key reuse (as opposed to how long after use the key is
> destroyed), obviously it cannot be bad, otherwise we'd only have
> ephemeral-ephemeral DH.  But we've been using DH with static keys
> since DH was invented.
> No plausible case has yet been made against ephemeral DH key reuse.  I
> can't think of a plausible case against it.  I'm inclined to believe
> there is no plausible case to be made against it within the current
> published literature.

OK, I'll bite.

If the various standards are to be interpreted as permitting parties
to reuse their ephemeral DH keys for a short time, *which party* is
allowed to do so?  I bet that, if both parties in a DH exchange reuse
their ephemeral keys in multiple DH exchanges with each other, the
security properties of various protocols degrade in varying amounts
from "anything resembling a security proof is invalidated" to
"completely insecure".

Certainly the any exchange of the form K = H(g^(a+b)) followed by use
of most AEADs (e.g. GCM, most things using Poly1305, etc) starting
with IV 0 and key K (or a hash of K) will fail catastrophically.

In summary, I think that a protocol intended to allow ephemeral key
reuse needs to specify that reuse is allowed (so the proofs can be
designed correctly) and to specify *how* the keys may be reused (to
avoid catastrophic failure).

> PFS depends on timely destruction of private keys, not non-reuse.

And integrity, and possibly even confidentiality, depends on non-reuse
of derived keys... :)

I hope that OpenSSL doesn't already reuse ECDH keys on the client.
The code is entirely incomprehensible, so my five minutes of trying to
understand it went nowhere at all.