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

Andy Lutomirski <luto@amacapital.net> Mon, 08 September 2014 19:34 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 07D961A0326 for <cfrg@ietfa.amsl.com>; Mon, 8 Sep 2014 12:34:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.721
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VfgiTldF6yc0 for <cfrg@ietfa.amsl.com>; Mon, 8 Sep 2014 12:34:25 -0700 (PDT)
Received: from mail-lb0-f171.google.com (mail-lb0-f171.google.com [209.85.217.171]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 56D671A02D4 for <cfrg@irtf.org>; Mon, 8 Sep 2014 12:34:25 -0700 (PDT)
Received: by mail-lb0-f171.google.com with SMTP id 10so8501300lbg.16 for <cfrg@irtf.org>; Mon, 08 Sep 2014 12:34:23 -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=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 10.152.5.66 with SMTP id q2mr31305625laq.11.1410204863388; Mon, 08 Sep 2014 12:34:23 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.152.36.106 with HTTP; Mon, 8 Sep 2014 12:34:03 -0700 (PDT)
In-Reply-To: <CAK3OfOjfSxHOE4fZzgVNmxEsF4ss_Bh+x7sc0rYTBRRznsbNqw@mail.gmail.com>
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com> <20140902165340.17284.qmail@cr.yp.to> <d4322ec172d74aab83a1d17cf4dcf786@BL2PR03MB242.namprd03.prod.outlook.com> <20140903052704.GM8540@cph.win.tue.nl> <CAK3OfOjfSxHOE4fZzgVNmxEsF4ss_Bh+x7sc0rYTBRRznsbNqw@mail.gmail.com>
From: Andy Lutomirski <luto@amacapital.net>
Date: Mon, 8 Sep 2014 12:34:03 -0700
Message-ID: <CALCETrU-rMBE7_VD+5yT_MuXsXXHZ_OhSywfuez3x2ohEQ+Hjw@mail.gmail.com>
To: Nico Williams <nico@cryptonector.com>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/I2RZG9D24OwgNiGSEisJ5RF69IY
Cc: "cfrg@irtf.org" <cfrg@irtf.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, 08 Sep 2014 19:34:27 -0000

On Mon, Sep 8, 2014 at 11:51 AM, Nico Williams <nico@cryptonector.com>; wrote:
> On Wed, Sep 3, 2014 at 12:27 AM, Tanja Lange <tanja@hyperelliptic.org>; 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.

--Andy