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

[Taylor R Campbell <[e-mail]>]

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/