Re: [Cfrg] Extra ECC desideratum: hard static DH and q-strong DH problems
Dan Brown <dbrown@certicom.com> Fri, 08 August 2014 20:43 UTC
Return-Path: <dbrown@certicom.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 E79EF1A0417 for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 13:43:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] 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 pF1NTiJYtTw3 for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 13:43:20 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id 56B9E1A04B1 for <cfrg@irtf.org>; Fri, 8 Aug 2014 13:43:19 -0700 (PDT)
Received: from xct103cnc.rim.net ([10.65.161.203]) by mhs210cnc.rim.net with ESMTP/TLS/AES128-SHA; 08 Aug 2014 16:43:19 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT103CNC.rim.net ([fe80::b8:d5e:26a5:f4d6%17]) with mapi id 14.03.0174.001; Fri, 8 Aug 2014 16:43:18 -0400
From: Dan Brown <dbrown@certicom.com>
To: "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Extra ECC desideratum: hard static DH and q-strong DH problems
Thread-Index: Ac+zO2olqd6fcUhCTcKUsaKirkBrtwAJRbgAAAc48XA=
Date: Fri, 08 Aug 2014 20:43:17 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5CC9EC5@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF5CC9D28@XMB116CNC.rim.net> <CACsn0cnuowCYmpnikmO094Qzw1yvCa_QognhTJTBe1KmSNz=DA@mail.gmail.com>
In-Reply-To: <CACsn0cnuowCYmpnikmO094Qzw1yvCa_QognhTJTBe1KmSNz=DA@mail.gmail.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.250]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg="SHA1"; boundary="----=_NextPart_000_0073_01CFB327.DB0A8570"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/RZOQ5FhfeT0cSfZVEb0fzvyMQYI
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 20:43:23 -0000
From: Watson Ladd [mailto:watsonbladd@gmail.com] >> 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. > 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 irrelevant? > 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 >