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

Dan Brown <> Fri, 08 August 2014 20:43 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id E79EF1A0417 for <>; Fri, 8 Aug 2014 13:43:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id pF1NTiJYtTw3 for <>; Fri, 8 Aug 2014 13:43:20 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id 56B9E1A04B1 for <>; Fri, 8 Aug 2014 13:43:19 -0700 (PDT)
Received: from ([]) by with ESMTP/TLS/AES128-SHA; 08 Aug 2014 16:43:19 -0400
Received: from ([fe80::45d:f4fe:6277:5d1b]) by ([fe80::b8:d5e:26a5:f4d6%17]) with mapi id 14.03.0174.001; Fri, 8 Aug 2014 16:43:18 -0400
From: Dan Brown <>
To: "''" <>
Thread-Topic: [Cfrg] Extra ECC desideratum: hard static DH and q-strong DH problems
Thread-Index: Ac+zO2olqd6fcUhCTcKUsaKirkBrtwAJRbgAAAc48XA=
Date: Fri, 8 Aug 2014 20:43:17 +0000
Message-ID: <>
References: <> <>
In-Reply-To: <>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
x-originating-ip: []
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_0073_01CFB327.DB0A8570"
MIME-Version: 1.0
Subject: Re: [Cfrg] Extra ECC desideratum: hard static DH and q-strong DH problems
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: Fri, 08 Aug 2014 20:43:23 -0000

From: Watson Ladd []
>> On Aug 8, 2014 12:17 PM, "Dan Brown" <> 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.

I don't remember if I mentioned all of the above previously CFRG, but I 
thought it worth reviewing.

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

Below this paragraph, my previous email mentioned a few ideas and a few other 
papers, not just the paper of Cheon.  Specifically, the text below tries to 
explain the relevance of Cheon's algorithm towards theoretical security 
assumptions about hashed Diffie--Hellman, not towards a practical attack. 
Should I assume you think all of the text, or at least its gist, below is 

> 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 (  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 (
> 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
> ( relies on some assumptions PRF-ODH and a
> similarly-named problem Strong DH from (
> 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