Hacker News Reader

Comment by tptacek | Hacker News Reader

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.

Also, while a 1536 bit modulus isn't the best you can do in 2014 (we should all be using curves now instead of doing DLP crypto), it's probably not within reach of attackers right now. Effort doesn't scale linearly from those 1024 bit factoring problems.

View on HN

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

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

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

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

Much appreciated =). I looked for references after reading the parent discussions and xnyhps's blog post but was unsuccessful.

Yes I get that, I think there is a new DH for almost every message, much better than TLS. The problem is we have no idea what the NSAs abilities are in terms of actual cryptanalysis/cracking, but we do know that they have an immense desire for it.

RFC 3526 puts the low end of the 1536 bit group's strength at 90 bits. If some unknown weakness was found that lowers that significantly that doesn't leave things very safe.

Agreed that curves would be ideal.

Reply on news.ycombinator.com