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

[Dan Brown <[e-mail]>]

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

> -----Original Message-----
> From: Cfrg <[e-mail]> On Behalf Of Taylor R Campbell
> Sent: Wednesday, November 20, 2019 2:21 PM
> To: [e-mail]
> 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
> [e-mail]
> 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.