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

Dan Brown <danibrown@blackberry.com> Wed, 20 November 2019 21:06 UTC

Return-Path: <danibrown@blackberry.com>

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 0B6D3120178
for <cfrg@ietfa.amsl.com>; Wed, 20 Nov 2019 13:06:49 -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 iGVvmm3N4AUJ for <cfrg@ietfa.amsl.com>;
Wed, 20 Nov 2019 13:06:45 -0800 (PST)

Received: from smtp-pc10.blackberry.com (smtp-pc10.blackberry.com
[74.82.81.42])
(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 46EE1120045
for <cfrg@ietf.org>; Wed, 20 Nov 2019 13:06:44 -0800 (PST)

Received: from pps.filterd (mhs400cnc.rim.net [127.0.0.1])
by mhs400cnc.rim.net (8.16.0.27/8.16.0.27) with SMTP id xAKL2ZwL043254;
Wed, 20 Nov 2019 16:06:43 -0500

Received: from xct199ykf.rim.net (xct199ykf.rim.net [10.2.25.7])
by mhs400cnc.rim.net with ESMTP id 2wcb0ym4a6-1
(version=TLSv1 cipher=ECDHE-RSA-AES256-SHA bits=256 verify=NOT);
Wed, 20 Nov 2019 16:06:43 -0500

Received: from XCH214CNC.rim.net (10.3.27.119) by XCT199YKF.rim.net
(10.2.25.7) with Microsoft SMTP Server (TLS) id 14.3.408.0; Wed, 20 Nov 2019
16:06:42 -0500

Received: from XCH210YKF.rim.net (10.2.27.110) by XCH214CNC.rim.net
(10.3.27.119) with Microsoft SMTP Server (version=TLS1_2,
cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1847.3; Wed, 20 Nov
2019 16:06:42 -0500

Received: from XCH210YKF.rim.net ([fe80::ac8d:3541:704c:478a]) by
XCH210YKF.rim.net ([fe80::ac8d:3541:704c:478a%5]) with mapi id
15.01.1847.003; Wed, 20 Nov 2019 16:06:42 -0500

From: Dan Brown <danibrown@blackberry.com>

To: Taylor R Campbell <campbell+cfrg@mumble.net>, "cfrg@ietf.org"
<cfrg@ietf.org>

Thread-Topic: [Cfrg] Static-DH oracles, strong-DH security

Thread-Index: AQHVn9euiWYRGsH/Hk2H91qx5FjiPqeUerPw

Date: Wed, 20 Nov 2019 21:06:41 +0000

Message-ID: <ab5526dbe5d04b12b896d56b94824158@blackberry.com>

References: <20191120192055.7A27A6067F@jupiter.mumble.net>

In-Reply-To: <20191120192055.7A27A6067F@jupiter.mumble.net>

Accept-Language: en-US

Content-Language: en-US

X-MS-Has-Attach: yes

X-MS-TNEF-Correlator:

x-originating-ip: [100.64.97.28]

Content-Type: multipart/signed; protocol="application/x-pkcs7-signature";
micalg=2.16.840.1.101.3.4.2.1;
boundary="----=_NextPart_000_00A4_01D59FBC.7EE320E0"

MIME-Version: 1.0

X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, ,
definitions=2019-11-20_07:, , signatures=0

X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0
priorityscore=1501
malwarescore=0 suspectscore=0 phishscore=0 bulkscore=0 spamscore=0
clxscore=1011 lowpriorityscore=0 mlxscore=0 impostorscore=0
mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx
scancount=1 engine=8.0.1-1911140001 definitions=main-1911200175

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

Subject: Re: [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 21:06:49 -0000

Hi Taylor, I sent a note to CFRG about static-DH and Curve25519: https://mailarchive.ietf.org/arch/msg/cfrg/JqeGAse5ZzWCvf1v6vRntM9Lv9Q You may wish to double-check how compatible that note is to your results. Further back, I suggested to CFRG including criteria for p+/-1 in its curve recommendations, to better resist static-DH attacks. A downside of these criteria would be that it restricts the class of curves (similar to the restriction provided by twist security): the risk being that this somehow increases the chance of falling into some weak class of curves, etc. Not sure how many CFRG want to revisit this. SEC1 version 2.0 includes some kind of recommendation against static-DH for new curves, and maybe IEEE 1363a warns about it. Static-DH on the twist is only relevant against Montgomery ladder multipliers, but is fixable using public-key validation PKV (implicit in Ristretto?). A downside of PKV is, for x-only DH, however, a cost of a Legendre symbol computation (similar cost to an inversion, but perhaps mergeable with an inversion???). Dan Brown BlackBerry, Security in Motion +1 (289) 261-4157 > -----Original Message----- > From: Cfrg <cfrg-bounces@irtf.org>; On Behalf Of Taylor R Campbell > Sent: Wednesday, November 20, 2019 2:21 PM > To: cfrg@ietf.org > Subject: [Cfrg] Static-DH oracles, strong-DH security > > 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://urldefense.proofpoint.com/v2/url?u=https- > 3A__eprint.iacr.org_2004_306&d=DwICAg&c=yzoHOc_ZK-sxl- > kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql- > UonsW647lYqnsrbXizKI6MgkEw&m=iK0Ds2TXM5rVIck8uZZ1UG5f_6TpvdfDkQq > 70DOklmo&s=ncKI9Vc2_2BBReYe-5yMSxlq4jFnMEN_YhHMT7gP2PU&e= > > 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://urldefense.proofpoint.com/v2/url?u=https- > 3A__link.springer.com_chapter_10.1007_11761679- > 5F1&d=DwICAg&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q- > lhj0sp26wE&r=qkpbVDRj7zlSRVql- > UonsW647lYqnsrbXizKI6MgkEw&m=iK0Ds2TXM5rVIck8uZZ1UG5f_6TpvdfDkQq > 70DOklmo&s=5nu8IK7X9_K3F01CIdeYs1Oc7PI5BK_1OASKiWWiKnc&e= > > 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://urldefense.proofpoint.com/v2/url?u=https- > 3A__link.springer.com_chapter_10.1007_978-2D3-2D540-2D73489-2D5- > 5F17&d=DwICAg&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q- > lhj0sp26wE&r=qkpbVDRj7zlSRVql- > UonsW647lYqnsrbXizKI6MgkEw&m=iK0Ds2TXM5rVIck8uZZ1UG5f_6TpvdfDkQq > 70DOklmo&s=bE2gR9Kf5IuQ2n3nepbi1xcPDeH_cADEgQy6g0bw7Zg&e= > > 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://urldefense.proofpoint.com/v2/url?u=https- > 3A__eprint.iacr.org_2009_058&d=DwICAg&c=yzoHOc_ZK-sxl- > kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql- > UonsW647lYqnsrbXizKI6MgkEw&m=iK0Ds2TXM5rVIck8uZZ1UG5f_6TpvdfDkQq > 70DOklmo&s=wAe6e9Xzg5e8hmgB21PL5d1F1ZPsCIHBdo0fZ9Fqpec&e= > > 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://urldefense.proofpoint.com/v2/url?u=https- > 3A__link.springer.com_article_10.1007_s00145-2D009-2D9047- > 2D0&d=DwICAg&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q- > lhj0sp26wE&r=qkpbVDRj7zlSRVql- > UonsW647lYqnsrbXizKI6MgkEw&m=iK0Ds2TXM5rVIck8uZZ1UG5f_6TpvdfDkQq > 70DOklmo&s=MLDOb3K3UQ0rnbZpG_nHGF0tsTRtJl_1iEjMHY80SDg&e= > > 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://urldefense.proofpoint.com/v2/url?u=https- > 3A__link.springer.com_chapter_10.1007_978-2D3-2D642-2D17373-2D8- > 5F17&d=DwICAg&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q- > lhj0sp26wE&r=qkpbVDRj7zlSRVql- > UonsW647lYqnsrbXizKI6MgkEw&m=iK0Ds2TXM5rVIck8uZZ1UG5f_6TpvdfDkQq > 70DOklmo&s=BBZ-sUXBJX6w9DdBnFUYU4SYJ1coabcRYyDljxreELk&e= > > 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://urldefense.proofpoint.com/v2/url?u=https- > 3A__eprint.iacr.org_2012_609&d=DwICAg&c=yzoHOc_ZK-sxl- > kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql- > UonsW647lYqnsrbXizKI6MgkEw&m=iK0Ds2TXM5rVIck8uZZ1UG5f_6TpvdfDkQq > 70DOklmo&s=Ozyl7pDwcOQnEHntcXqSIYOchKq_FGJ5IBsD6BqZ0kQ&e= > > 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://urldefense.proofpoint.com/v2/url?u=https- > 3A__www.ams.org_journals_mcom_2014-2D83-2D288_S0025-2D5718- > 2D2014-2D02813-2D5_&d=DwICAg&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q- > lhj0sp26wE&r=qkpbVDRj7zlSRVql- > UonsW647lYqnsrbXizKI6MgkEw&m=iK0Ds2TXM5rVIck8uZZ1UG5f_6TpvdfDkQq > 70DOklmo&s=DRnU2zHZJ7eOREiO2Z6zeKXR6NnbJ9t_x2F5hBSfpUo&e= > > 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://urldefense.proofpoint.com/v2/url?u=https- > 3A__link.springer.com_chapter_10.1007_978-2D3-2D662-2D48797-2D6- > 5F8&d=DwICAg&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q- > lhj0sp26wE&r=qkpbVDRj7zlSRVql- > UonsW647lYqnsrbXizKI6MgkEw&m=iK0Ds2TXM5rVIck8uZZ1UG5f_6TpvdfDkQq > 70DOklmo&s=NFrZgE5trX1NwGgego3flsTPZJefvk7YPBNjTCPkQ2I&e= > > 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://urldefense.proofpoint.com/v2/url?u=https- > 3A__blog.cloudflare.com_supporting-2Dthe-2Dlatest-2Dversion-2Dof-2Dthe- > 2Dprivacy-2Dpass-2Dprotocol_&d=DwICAg&c=yzoHOc_ZK-sxl- > kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql- > UonsW647lYqnsrbXizKI6MgkEw&m=iK0Ds2TXM5rVIck8uZZ1UG5f_6TpvdfDkQq > 70DOklmo&s=smj3xrxm8wUJBFx2F2qSVImSZaFeyeu_hRjh2LbH7Tw&e= > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > https://urldefense.proofpoint.com/v2/url?u=https- > 3A__www.irtf.org_mailman_listinfo_cfrg&d=DwICAg&c=yzoHOc_ZK-sxl- > kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql- > UonsW647lYqnsrbXizKI6MgkEw&m=iK0Ds2TXM5rVIck8uZZ1UG5f_6TpvdfDkQq > 70DOklmo&s=xe0u7qeRCOOhLenc919VLXb_zpR_b-mGbS5CuSsJTpY&e= ---------------------------------------------------------------------- This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

- [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