[Cfrg] Extra ECC desideratum: hard static DH and q-strong DH problems
Dan Brown <dbrown@certicom.com> Fri, 08 August 2014 19:17 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 C16741A0380 for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 12:17:10 -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 XeoAqAMuW3q0 for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 12:17:08 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id 5B9DF1A029C for <cfrg@irtf.org>; Fri, 8 Aug 2014 12:17:08 -0700 (PDT)
Received: from smtp-pop.rim.net (HELO XCT103CNC.rim.net) ([10.65.161.203]) by mhs210cnc.rim.net with ESMTP/TLS/AES128-SHA; 08 Aug 2014 15:17:07 -0400
Received: from XCT114CNC.rim.net (10.65.161.214) by XCT103CNC.rim.net (10.65.161.203) with Microsoft SMTP Server (TLS) id 14.3.174.1; Fri, 8 Aug 2014 15:17:06 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT114CNC.rim.net ([::1]) with mapi id 14.03.0174.001; Fri, 8 Aug 2014 15:17:06 -0400
From: Dan Brown <dbrown@certicom.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: Extra ECC desideratum: hard static DH and q-strong DH problems
Thread-Index: Ac+zO2olqd6fcUhCTcKUsaKirkBrtw==
Date: Fri, 08 Aug 2014 19:17:05 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5CC9D28@XMB116CNC.rim.net>
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_005B_01CFB31B.D0689F00"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/uXVgV30OoAAsLl4n2AZ6yDkD1d0
Subject: [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:17:10 -0000
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. 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