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

From: Taylor R Campbell <[email-masked]>
Date: Wed, 20 Nov 2019 19:20:54 +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/

---

From: Dan Brown <[email-masked]>
Date: Wed, 20 Nov 2019 21:06:41 +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 <[email-masked]> On Behalf Of Taylor R Campbell
> Sent: Wednesday, November 20, 2019 2:21 PM
> To: [email-masked]
> 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.
> 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:
> 
> 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
protocol
> like Privacy Pass using Curve25519 -- or, more specifically,
> Ristretto255.)
> 
points
> of all attacks I have found here are:
> 
> 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.)
> 
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:
> 
> 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;
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.)
>   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=
> 
>   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=
> 
>   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=
> 
>   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=
> 
>   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=
> 
>   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=
> 
>   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=
> 
>   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=
> 
>   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=
> 
>   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
> [email-masked]
> 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.

---

From: Taylor R Campbell <[email-masked]>
Date: Fri, 22 Nov 2019 00:01:54 +0000

> Date: Thu, 21 Nov 2019 11:38:00 +0000
> From: Alex Davidson <[email-masked]>
> 
> 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.

To be clear: I don't mean to suppose limiting adversaries to 2^64
queries overall; rather, I mean to suppose limiting them to 2^64
queries made _one after the other_ -- not in parallel.

What matters is the _latency_ of a query, not the _bandwidth_ of the
global Cloudflare network.  And I think it is quite reasonable to
suppose limiting the latency of a query to at least a nanosecond:

- Even if scalar multiplication were instantaneous, Cloudflare would
  have to be physically located less than 15cm away from me in order
  for the information to propagate within one nanosecond -- unless I
  figure out something about physics that would earn me a lot more
  than a few captcha-skipping tokens are worth!

- Even if all the networking latency and parsing overhead were
  dispensed with (perhaps the oracle is on a shared VPS host), it's
  hard to imagine that computing a scalar multiplication could take
  less than a nanosecond to begin with.

---

From: "Filippo Valsorda" <[email-masked]>
Date: Fri, 22 Nov 2019 01:55:44 -0500

Thank you Taylor for the great summary. I was asked to look into this
for ristretto255 and my results match yours.

> suppose limiting the latency of a query to at least a nanosecond:

I think it's even reasonable to assume a latency of 10 nanoseconds,
meaning 684245902131068969 queries would take two centuries, leaving the
only realistic attack at 2^118.

For a query to take 10ns, all of the following need to be true:

* Every bus in the path needs to have a minimum bandwidth of 25.6 Gb/s
(unidirectional, assuming 32 bytes per query, not taking into account
query submission pauses)

* The target and the attacker can't be more than 1.5m (5ft) apart

* The target must be able to compute a scalar multiplication in 30
cycles on a 3GHz core (about the L3 cache latency on Skylake)

Importantly, many of these bottlenecks are under control of the target,
not the attacker, so there is no need to speculate about potential
attacker capabilities.

---

From: Alex Davidson <[email-masked]>
Date: Thu, 21 Nov 2019 11:38:00 +0000

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.

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.

> 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 <[email-masked]> wrote:

> where
> 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.
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Alex Davidson <[email-masked]>
Date: Fri, 29 Nov 2019 15:38:25 +0000

> On Fri, Nov 22, 2019 at 6:58 AM Filippo Valsorda <[email-masked]>
wrote:
> meaning 684245902131068969 queries would take two centuries, leaving
> the only realistic attack at 2^118.

Thanks for both of your inputs. I agree that in the Internet setting
assuming this kind of latency on sequential queries is very likely not
to constrain any plausible adversary.

However, my contention is that the current draft-irtf-cfrg-vorpf
document describes a protocol in the generic sense, and the notion of
latency is not factored into the security model. This mirrors the
security model that the original (V)OPRF design [JKK14] uses, and so we
can invoke the proof of security that they provide for making arguments
about the security of the protocol.

The reason for describing the protocol in this manner is that it ensures
that the (V)OPRF is agnostic to the setting that it is used in. In turn,
this ensures that the security of the protocol is evaluated against the
*strongest* possible adversary. This also makes it possible to easily
evaluate the expected lower bound of the security parameter for a
(V)OPRF ciphersuite in any setting. This includes settings that the
adversary, for whatever reason, may enjoy 0ms latency per query.

As you point out, perhaps instantiating such an adversary is impossible
in the real world. However, in my opinion it is imperative that we make
*no* assumptions about the adversarial setting that the generic (V)OPRF
protocol is being used in, for the reasons above.

[JKK14]: https://eprint.iacr.org/2014/650.pdf