Re: [Cfrg] Extra ECC desideratum: hard static DH and q-strong DH problems

Watson Ladd <watsonbladd@gmail.com> Fri, 08 August 2014 19:28 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 9F1211A0386 for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 12:28:52 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 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, HTML_MESSAGE=0.001, 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 ZCHTbkHZ3DPe for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 12:28:50 -0700 (PDT)
Received: from mail-yk0-x231.google.com (mail-yk0-x231.google.com [IPv6:2607:f8b0:4002:c07::231]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C174F1A00A8 for <cfrg@irtf.org>; Fri, 8 Aug 2014 12:28:49 -0700 (PDT)
Received: by mail-yk0-f177.google.com with SMTP id 79so4143919ykr.22 for <cfrg@irtf.org>; Fri, 08 Aug 2014 12:28:49 -0700 (PDT)
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; bh=oSlNgyLaI7pVB6eV3a3S3yms4RBHm6HBUrhggefRY0g=; b=xgBr/SFnHXtvQZS7O3QVuX8xbNTmM1Fa3NiJyIP+PjPdZ+UtYq3VZbmkgoKODUq0Rj /FCbH9d5I0dKte1iXvk8bLZ8EFS+kJvJzRyfqylflDefjwnMBH7iVHTkOwzDRiR2N97S 261zBgip1xUs3SzWEf8AdZ7XqKF9HsFEvpSl6MTe8FK3mUE35Trw1FDMjr8g80pW244l yr7697/d7NduFGC/zB3Ta0keCEYY7mIe+ZYSSCM7c3VcxEajx31HGbsjUCRBh2A0W2nB O5uq5z7ztWfXsyXzxK7EAVp1W3vr9DZx2QYq2Drqgj34tHZx6AO/5uJSqGnWiHKjnX6N Rc4A==
MIME-Version: 1.0
X-Received: by 10.236.134.208 with SMTP id s56mr17492860yhi.4.1407526128969; Fri, 08 Aug 2014 12:28:48 -0700 (PDT)
Received: by 10.170.202.8 with HTTP; Fri, 8 Aug 2014 12:28:48 -0700 (PDT)
Received: by 10.170.202.8 with HTTP; Fri, 8 Aug 2014 12:28:48 -0700 (PDT)
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5CC9D28@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF5CC9D28@XMB116CNC.rim.net>
Date: Fri, 8 Aug 2014 12:28:48 -0700
Message-ID: <CACsn0cnuowCYmpnikmO094Qzw1yvCa_QognhTJTBe1KmSNz=DA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Dan Brown <dbrown@certicom.com>
Content-Type: multipart/alternative; boundary=20cf303a2bbbedf24b05002336d2
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/5LzJm4KFFqlholw5yjw6cYWDDdA
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Extra ECC desideratum: hard static DH and q-strong DH problems
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: Fri, 08 Aug 2014 19:28:52 -0000

On Aug 8, 2014 12:17 PM, "Dan Brown" <dbrown@certicom.com> wrote:
>
> Three reasons that static ECDH key agreement should still be considered in
> the CFRG curve recommendation:
>
> 1. Existing versions of TLS allow static DH for sever authentication, and
> allow ephemeral re-use in DHE, and if I understand, these allowance would
> carry if implemented with ECC.  Also, IKE allows ephemeral reuse.
> 2. Other IETF protocols using ECC, e.g. CMS, may require static DH keys,
due
> to less interaction being available.  Perhaps JOSE uses static ECDH too?
> 3. Perhaps future versions of TLS will drop signature uses for
> authentication, and instead use static DH keys for authentication.
> (Something like in MQV or some other key agreement scheme.) Or, maybe IETF
> will later adopt protocols that use the esoteric blinding properties of
raw
> static DH.
>
> So, I think it desirable for the choice of curve to be one that fares well
> static DH keys are used.
>

This was mentioned prior to the CFRG interim. As I pointed out at that
meeting, hashing points renders the paper of Cheon irrelevent.

> In particular, there are two variants of the Diffie--Hellman problem
related
> to static DH keys whose difficulty potentially varies with the curve:
>
> 1. The static DHP from (http://eprint.iacr.org/2004/306).  If the static
DHP
> is easy for a given target public key, then the static DH applications
above
> are insecure for the target public key.
> 2. A variant (*) of the q-strong DHP from (http://eprint.iacr.org/2004/171
).
> If the q-strong DHP is hard, then static DH applications above resist a
> total break attack in the sense that it is infeasible the adversary to
> extract the static DH private key.
>
> (*) the variant I have in mind is one in which that adversary succeeds
when
> it recovers the static private key, rather than performing some special
> operation with it.
>
> An algorithm from the 2004/306 eprint, and extended by Cheon, has opposite
> effects on these two problem: making the q-strong easier, but providing
> evidence that the static DHP is hard.  This effectiveness algorithm
depends
> on the factorization of n-1 and n+1 where n is the large prime factor in
the
> order of the group. I think it is desirable for both of these problem to
be
> hard, and I think that if n has the right properties, then we can get good
> assurances for both problems.
>
> If I had to choose which of the two problems to accommodate, I'd choose
the
> q-strong DHP, because one can just make a strong, but plausible assumption
> that the static DHP is hard.  In other words, instead of assuming that the
> DHP is hard, as usual, we further assume that the DHP is hard for every
> single key, i.e. the DHP has no negligible fraction weak keys.  Assuming
> this covers that case that your static DHP has enough entropy to be
> unguessable, but not enough to escape falling into a subset that is
> negligible fraction of all keys.  E.g. suppose your 256-bit key has only
> 128-bits of entropy (but is pseudorandom of course).
>
> I also add that one of the security proof for TLS
> (http://eprint.iacr.org/2013/339) relies on some assumptions PRF-ODH and a
> similarly-named problem Strong DH from (http://eprint.iacr.org/1999/007)
> which may have may relationship with the q-strong DH problem.  For
example,
> I've got a hunch that if we assume the variant of the q-strong DHP is
hard,
> then I think that imply the hardness of PRF-ODH and the ABR StrongDH
> problems.  Because of the short time frame, I sharing this thought before
> really confirming it.
>
> Of course, this desideratum is a theoretical one, but some of the other
> desiderata seem to be better-safe-than-sorry or helpful to make
> implementations more robust, so I wanted to add it the list.
>
> Also, Certicom has some IPR around the method.
>
> Best regards,
>
> Daniel Brown
> Research In Motion Limited
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>