### [Cfrg] Static-DH oracles, strong-DH security

Taylor R Campbell <campbell+cfrg@mumble.net> Wed, 20 November 2019 19:21 UTC

Return-Path: <campbell@mumble.net>

X-Original-To: cfrg@ietfa.amsl.com

Delivered-To: cfrg@ietfa.amsl.com

Received: from localhost (localhost [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id 6658312007C
for <cfrg@ietfa.amsl.com>; Wed, 20 Nov 2019 11:21:02 -0800 (PST)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -1.899

X-Spam-Level:

X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, SPF_HELO_NONE=0.001, SPF_PASS=-0.001,
URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no

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 ef5XBOzBi_DY for <cfrg@ietfa.amsl.com>;
Wed, 20 Nov 2019 11:20:58 -0800 (PST)

Received: from jupiter.mumble.net (jupiter.mumble.net [74.50.56.165])
(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 96921120020
for <cfrg@ietf.org>; Wed, 20 Nov 2019 11:20:58 -0800 (PST)

Received: by jupiter.mumble.net (Postfix, from userid 1014)
id 7A27A6067F; Wed, 20 Nov 2019 19:20:55 +0000 (UTC)

From: Taylor R Campbell <campbell+cfrg@mumble.net>

To: cfrg@ietf.org

Date: Wed, 20 Nov 2019 19:20:54 +0000

Sender: Taylor R Campbell <campbell@mumble.net>

MIME-Version: 1.0

Content-Type: text/plain; charset=us-ascii

Content-Transfer-Encoding: quoted-printable

Message-Id: <20191120192055.7A27A6067F@jupiter.mumble.net>

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/YDVS5Trpr6suig_VCFEOH6SOn8Q>

Subject: [Cfrg] Static-DH oracles, strong-DH security

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.29

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>,
<mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Wed, 20 Nov 2019 19:21:02 -0000

A static-DH oracle in an additive group is an oracle for P |---> n*P where n is a secret scalar. Access to a static-DH oracle may reduce the cost of computing the discrete log n. Protocols like Privacy Pass may rely on the difficulty of computing n*Q for any point Q not fed to the oracle -- roughly, on the strong-DH security assumption. What's the state of the art in strong-DH attacks and countermeasures? Curve25519 was designed under the premise of P |---> H(n*P) oracles only, but how well does it hold up under P |---> n*P oracles instead? The summary in draft-irtf-cfrg-voprf-02 is that a q-query static-DH oracle reduces security by lg q bits: The assumption that this problem is hard was first introduced in [BB04]. Since then, there have been a number of cryptanalytic studies that have reduced the security of the assumption below that implied by the group instantiation (for example, [BG04] and [Cheon06]). In summary, the attacks reduce the security of the group instantiation by log_2(Q) bits. This seems to be a bit of a simplification, based on the literature I've found in my cursory search. I'd like to get a clearer idea of the attacks -- both to see whether (say) Curve25519 is actually hurt by static-DH oracles, and if so to confirm whether a larger curve like Curve448 is adequate to prevent strong-DH attacks. (Disclosure: I work at Brave, and we recently deployed a VOPRF-based protocol like Privacy Pass using Curve25519 -- or, more specifically, Ristretto255.) Suppose the group has prime order p for the moment. The two crucial points of all attacks I have found here are: 1. The number of queries must be _at least_ a divisor d of p - 1, or twice a divisor d of p + 1. 2. The queries must be done in sequence: query at P to find n*P, query at n*P to find n^2 * P, query at n^2 * P to find n^3 * P, &c. The best attacks seem to cost O(sqrt(p/d) + sqrt(d)) group operations, or O(sqrt(p/d) + d) in the case of d | p + 1, to compute a discrete log. (The attacks were originally described in [BG04] and [Cheon06] with large memory using BSGS, but they can be done in more or less constant memory and can probably be parallelized with distinguished-point searches, so the time seems to be a reasonable proxy for optimal AT cost.) Even a global network like Cloudflare can't answer more than 2^64 sequential queries: at one nanosecond per query that would be nearly five hundred years. So we really only need to worry about divisors d of p +/- 1 where p is the order of the group in which the oracle operates and where d is below 2^64. Consider the subgroup of Curve25519 used for, e.g., X25519. The order is p = 2^252 - 27742317777372353535851937790883648493, and p +/- 1 factor into: p - 1 = 2^2 * 3 * 11 * 198211423230930754013084525763697 * 276602624281642239937218680557139826668747 p + 1 = 2 * 3 * 5 * 7 * 103 * 684245902131068969 * 1466936914520620440380580414586728830413895967152734051 What do we get if we naively evaluate the O(sqrt(p/d) + sqrt(d)) and O(sqrt(p/d) + d) formulas neglecting constant factors? - For the p-1 attack, the largest plausible divisor d is 132 = 2^2 * 3 * 11, in which case the attack cost is about sqrt(2^252/132) + sqrt(132) ~= 2^122 group operations. Not a huge improvement over the ~2^125 group operations for Pollard's rho, so not really concerning. - For the p+1 attack, the largest divisor d under the cutoff of 2^63 seems to be 6842459021310689690 = 2 * 5 * 684245902131068969 ~= 2^62.5 (recall we need q >= 2d for the p+1 attack) which case the attack cost is about sqrt(2^252/2^62.5) + 2^62.5 ~= 2^94. That's not so good. However, that's 2^94 cost that must be spent _after_ 2^63.5 sequential queries, which is over 400 years at one query per nanosecond. If we do 21630 = 2 * 3 * 5 * 7 * 103 ~= 2^14 queries, the attack cost is about sqrt(2^252/2^14) + 2^14 ~= 2^118. That's a factor of about 100 cheaper than Pollard's rho, but the next higher advantage that can be had requires 684245902131068969 ~= sequential queries, which is about 21 years at one query per nanosecond. So it seems like even annual rotation of a key is enough to thwart this attack. Of course, that's not the whole story for Curve25519: protocol designers might have to worry about cofactors and twists, and the twist of Curve25519 has smoother p-1 and p+1. But we can dispense with those worries by just using Ristretto255, I think. In contrast, e.g., NIST P-256 as used by Privacy Pass today (but perhaps not in the near future according to [Davidson19]) is about the worst case for static-DH oracles: lots of small factors of p-1; secp256k1 also has lots of small factors of p+1. Curve448 seems to be hurt more by p+/-1 factors than Curve25519, though of course it aims for higher security to begin with so the strong-DH attack cost is still higher against Curve448 than Curve25519. (Perhaps we could also select a curve by the RFC 7748 procedure with the additional criteria that both p-1 and p+1 have only very small or very large factors.) Have I missed anything important in the literature? Should the newer references be included in draft-irtf-cfrg-voprf? [BG04]: Daniel R.L. Brown and Robert P. Gallant, `The Static Diffie-Hellman Problem', Cryptology ePrint Archive: Report 2004/306. https://eprint.iacr.org/2004/306 If q >= d | p - 1, then after q _sequential_ queries we can learn a strong-DH tuple (P, n*P, n^d * P) and compute n with O(log(p)*(sqrt(p/d) + sqrt(d))) _scalar multiplications_ and storage for O(sqrt(p/d)) group elements. [Cheon06] Jung Hee Cheon, `Security Analysis of the Strong Diffie-Hellman Problem', in Serge Vaudenay (ed.), Advances in Cryptology---EUROCRYPT 2006, Springer LNCS 4004, pp. 1--11. https://link.springer.com/chapter/10.1007/11761679_1 1. If q >= d | p - 1, then after q _sequential_ queries we can learn a strong-DH tuple (P, n*P, n^d * P) and compute n with O(log(p)*(sqrt(p/d) + sqrt(d))) _group operations_ and storage for O(sqrt(p/d)) group elements. 2. If q >= 2d | p + 1, same but O(log(p)*(sqrt(p/d) + d)) group operations. [KKM07]: Shunji Koazaki, Taketeru Kutsuma, and Kazuto Matsuo, `Remarks on Cheon's Algorithms for Pairing-Related Problems', in Tsuyoshi Takagi, Tatsuaki Okamoto, Eiji Okamoto, and Takeshi Okamoto (eds.), Pairing-Based Cryptography---Pairing 2007, Springer LNCS 4575, pp. 302--316. https://link.springer.com/chapter/10.1007/978-3-540-73489-5_17 Knocked a factor of log(p) off [Cheon06] for O(sqrt(p/d) + sqrt(d)) group operations if q >= d | p - 1 or O(sqrt(p/d) + d) group operations if q >= 2d | p + 1. [Satoh09]: Takakazu Satoh, `On Generalization of Cheon's algorithm', Cryptology ePrint Archive: Report 2009/058. https://eprint.iacr.org/2009/058 Extended to q >= d | Phi_n(p) where Phi_n is the nth cyclotomic polynomial in time O~(n^2 (n log p + w + n^3 + sqrt(Phi_n(p)/d))), where w is another parameter. Practical applicability of the algorithm is unclear; [KCL14] concluded it is not an improvement. [Cheon10]: Jung Hee Cheon, `Discrete Logarithm Problem with Auxiliary Inputs', Journal of Cryptology 23(3), pp. 457--476. https://link.springer.com/article/10.1007/s00145-009-9047-0 Adapted [Cheon06] to probabilistic search with essentially constant memory. [Granger10]: Robert Granger, `On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields', in Masayuki Abe (ed.), Advances in Cryptology---ASIACRYPT 2010, Springer LNCS 6477, pp. 283--302. https://link.springer.com/chapter/10.1007/978-3-642-17373-8_17 Applied static-DH oracles to discrete logs in curves over extension fields. Not relevant to Curve25519 or Curve448, but perhaps relevant to, e.g., FourQ. [KC12]: Taechan Kim and Jung Hee Cheon, `A New Approach to Discrete Logarithm Problem with Auxiliary Inputs', Cryptology ePrint Archive: Report 2012/609. https://eprint.iacr.org/2012/609 Extended to q >= d where d is the degree of a polynomial f with t irreducible factors of f(x) - f(y) over F_p[x,y] in time for O~(sqrt(p/t) + d) scalar multiplications. Unclear to me what the practical consequences are. [KCL14]: Minkyu Kim, Jung Hee Cheon, and In-Sok Lee, `Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs', Mathematics of Computation 83(288), 2014, pp. 1993--2004. https://www.ams.org/journals/mcom/2014-83-288/S0025-5718-2014-02813-5/ Concluded generalization in [Satoh09] does not improve attack costs. [Kim14]: Taechan Kim, `Discrete Logarithm Problem with Auxiliary Inputs', PhD dissertation, Seoul National University, 2014. [Kim16]: Taechan Kim, `Multiple Discrete Logarithm Problems with Auxiliary Inputs', in Tetsu Iwata and Jung Hee Cheon (eds.), Advances in Cryptology---ASIACRYPT 2015, Springer LNCS 9452, pp. 174--188. https://link.springer.com/chapter/10.1007/978-3-662-48797-6_8 Extended to multi-target attack: Given L different strong-DH tuples (P, n_i*P, n_i^d * P) for 1<=i<=L, compute _all_ the n_i in O(sqrt(L*p/d) + sqrt(L*d)) scalar multiplications and O(L) storage, provided that L << (p/d)^{1/4} and L << d^{1/4}. [Davidson19]: Alex Davidson, `Supporting the latest version of the Privacy Pass Protocol', Cloudflare blog post, 2019-10-28. https://blog.cloudflare.com/supporting-the-latest-version-of-the-privacy-pass-protocol/

- [Cfrg] Static-DH oracles, strong-DH security Taylor R Campbell
- Re: [Cfrg] Static-DH oracles, strong-DH security Dan Brown
- Re: [Cfrg] Static-DH oracles, strong-DH security Taylor R Campbell
- Re: [Cfrg] Static-DH oracles, strong-DH security Filippo Valsorda
- Re: [Cfrg] Static-DH oracles, strong-DH security Alex Davidson
- Re: [Cfrg] Static-DH oracles, strong-DH security Alex Davidson