5 ms·

> OTR uses DH in a ratcheting protocol that requires attackers to continuously break new DH exchanges; it's not like TLS, where one exchange at the beginning of

by xnyhps 13y ago

> OTR uses DH in a ratcheting protocol that requires attackers to continuously break new DH exchanges; it's not like TLS, where one exchange at the beginning of the session gives you the whole session. Please correct me if I'm wrong, but as far as I know the required effort to break multiple DH exchanges doesn't scale linearly in the number of exchanges. A single successful index-calculus attack on the used group will make breaking additional key exchanges much easier.

pbsd 13y ago
You're not wrong. The current state of the art puts the precomputation step at complexity L_n(1/3, 1.923)§, and additional individual discrete logs at L_n(1/3, 1.232). So individual logarithms are still subexponential and nothing to scoff at, but they do become easier, yes. Ignoring constant factors, for a 1536-bit prime this would mean cost ~2^102 for the initial precomputation, and ~2^66 for each individual log. § L_n(a, c) is the usual exp(c(1 + o(1)) (log n)^a (loglog n)^(1-a)).
- bhitov 13y ago
  > The current state of the art puts the precomputation step at complexity L_n(1/3, 1.923)§, and additional individual discrete logs at L_n(1/3, 1.232). Could you cite that? Not skeptical, just interested.
  - pbsd 13y ago
    Razvan Barbulescu's PhD thesis [1]. Note that the best asymptotic complexities are a little different: the 'best' is really L_n(1/3, 1.902), but that variant is hopeless in practice (it would require truly gigantic inputs for it to pay off). Similarly, there is a "discrete logarithm factory" method, based on Coppersmith's factorization factory, but that also has very large initial costs that make it not very attractive in practice. [1] http://tel.archives-ouvertes.fr/docs/00/92/52/28/PDF/these_avec_resume.pdf http://tel.archives-ouvertes.fr/docs/00/92/52/28/PDF/these_a...
    - bhitov 13y ago
      Much appreciated =). I looked for references after reading the parent discussions and xnyhps's blog post but was unsuccessful.

by xnyhps 13y ago

pbsd 13y ago

You're not wrong. The current state of the art puts the precomputation step at complexity L_n(1/3, 1.923)§, and additional individual discrete logs at L_n(1/3, 1.232). So individual logarithms are still subexponential and nothing to scoff at, but they do become easier, yes. Ignoring constant factors, for a 1536-bit prime this would mean cost ~2^102 for the initial precomputation, and ~2^66 for each individual log. § L_n(a, c) is the usual exp(c(1 + o(1)) (log n)^a (loglog n)^(1-a)).

bhitov 13y ago
> The current state of the art puts the precomputation step at complexity L_n(1/3, 1.923)§, and additional individual discrete logs at L_n(1/3, 1.232). Could you cite that? Not skeptical, just interested.
- pbsd 13y ago
  Razvan Barbulescu's PhD thesis [1]. Note that the best asymptotic complexities are a little different: the 'best' is really L_n(1/3, 1.902), but that variant is hopeless in practice (it would require truly gigantic inputs for it to pay off). Similarly, there is a "discrete logarithm factory" method, based on Coppersmith's factorization factory, but that also has very large initial costs that make it not very attractive in practice. [1] http://tel.archives-ouvertes.fr/docs/00/92/52/28/PDF/these_avec_resume.pdf http://tel.archives-ouvertes.fr/docs/00/92/52/28/PDF/these_a...
  - bhitov 13y ago
    Much appreciated =). I looked for references after reading the parent discussions and xnyhps's blog post but was unsuccessful.