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

[Alex Davidson <[e-mail]>]

Hi Taylor,

Thanks very much for your points. I agree that the analysis in
draft-irtf-cfrg-voprf-02 is quite conservative currently. Providing a
deeper understanding of the effect that Static-DH attacks have in the
draft would be very welcome.

>From my point-of-view, the inclusion of a ciphersuite based on
Curve25519 (or Ristretto255) in the draft is based purely on whether
the ciphersuite can guarantee something close to 128-bits of security
against the best known attacks. This is just so that implementers can
choose configurations that are not subject to interpretation regarding
whether the ciphersuite is sufficiently future-proof, or not. This is
also because the draft is currently somewhat agnostic to specific
curve choice, and is more concerned with the prime-order group that is
instantiated. For version -02, the choice was made to simply choose
ciphersuites that could plausibly guarantee > 128 bits of security.
However, we recognise that this is probably too cautious.

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

So, my only comment on your analysis is that I think restricting the
number of queries to 2^64 is something that I would personally like to
avoid. This places assumptions on the types of attacks that can be
performed, which then comes with a requirement to carefully specify
the implied security level of the system. In general, I would like to
instead focus (in draft-irtf-cfrg-voprf) on what security is provided
by a ciphersuite against the best-known attacks (from a theoretical
perspective, ignoring whether such oracles are likely to be
instantiable in the real world). I would prefer any analysis to be
geared towards providing the adversary with the oracle that allows
them to launch the most effective cryptanalysis of each ciphersuite.

With this in mind, a viable alternative in the draft is to just state
exactly what the security parameter based on the known best-case
attack. My understanding is that the Static-DH oracle provides the
most effective cryptanalysis so far in the VOPRF use-case. By doing
this, we could then include a Ristretto255 ciphersuite and just state
that we believe this configuration provides 118 bits of security (or
lower if a higher number of initial queries reduces this further). For
performance reasons, including a Ristretto255 configuration would be
very useful, and if it's possible to be very precise about the
security that is provided then this could be preferable to adopting
the conservative approach that is currently used.

> Have I missed anything important in the literature? Should the newer
> references be included in draft-irtf-cfrg-voprf?

I think the new references would be very welcome, thanks for bringing
them up. I would be happy to include them in a future version of the
draft. However, if you would like to contribute them yourself in a PR
to the draft repo, along with a more specific analysis of these
attacks (and against specific choices of curves), then that would be
great.

Thanks,
Alex

On Wed, Nov 20, 2019 at 9:07 PM Dan Brown <[e-mail]> wrote:

> 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.
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>