Comment by hnolable | Hacker News Reader

Comment by hnolable | Hacker News Reader

Parent Full thread

I believe the weakest link in OTR is its Diffie-Helman key exchange. If you break that you get the symmetric key and can decrypt everything passively. OTR has been using a 1536 bit modulus for its Diffie-Helman exchange since 2004 [1] (The weakest one from RFC 3526 [2]). Seems they are still using the same one today.

In 2004 this was probably a fine choice, especially considering the tradeoff between CPU processing (usability) and security. But considering the NSA scandal, specifically them recording all encrypted communications forever, and Bruce Schneier increasing his key lengths [3], and the ability for CPUs to process higher keylengths without any noticeable slowdown, I don't feel confident it is strong enough today.

Other than this gripe OTR is amazing and everyone should be using it.

Edit: xnyhps's post [4] concludes that only a single "cracking" of the 1536 bit group would need to occur to then decrypt any past or future OTR conversation "instantly".

[1] https://web.archive.org/web/20041215062523/http://www.cypher... [2] http://www.ietf.org/rfc/rfc3526.txt [3] https://news.ycombinator.com/item?id=6376954 [4] https://blog.thijsalkema.de/blog/2014/01/17/misconceptions-a...

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.

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

Can somebody weigh in on the feasiblity of cracking Diffie Helman? In Cryptography Engineering, Schneir et al say "there is no known formula" for computing x & y -- but this is a different kind of problem than ciphers, and a suitably advanced mathematical formula could potentially be discovered. It seems to me that the NSA are probably pretty advanced when it comes to prime number mathematics, and it's highly likely that they have teams of cryptographers chasing exactly such a formula.

There are definitely methods for solving the discrete log problem. Start by looking up "index calculus".

Reply on news.ycombinator.com