January 17, 2014

Misconceptions about forward-secrecy

---

Lately, there has been a lot of interest in forward-secrecy, mostly in the context of TLS/HTTPS. Some people seem to think it’s a magic bullet that will thwart all the NSA’s efforts. I am not against forward-secrecy, to the contrary, I think any encrypted communications protocol should use it, but I think it is important that people keep realistic expectations about what forward-secrecy protects them against. The worst security is security that you assume you have, but don’t actually have.

Misconception #1: “More keys, so more work to break.”

What some people seem to think is that forward-secrecy implies that to break the encryption of n sessions, n times as much computational power is necessary compared to breaking 1 session, because it involves n different session keys.

This is not automatically the case. Not only does forward-secrecy not imply it, common protocols which have forward-secrecy based on Diffie-Hellman key exchanges do not have this property.

To break a number of Diffie-Hellman negotiated keys all using the same Diffie-Hellman group, a number of different attacks are known. Many of these scale pretty well in the number of sessions.

Take for example a naive brute force search. We start generating g, g² mod p, g³ mod p, … until we find the key we want. This requires modular multiplication of a huge number (lets say at least 1024 bits), so the multiplication step is quite an intensive computation. Comparing numbers (even 1024 bit numbers) is by comparison much easier. So it doesn’t matter much if we need to compare g^x mod p to one, two or n different numbers (if we have a lot of keys, we have other options like sorted tables to optimize this further). If the NSA captured the ciphertext of you logging in 50 different times, then it’s 50 times as easy to obtain your password by decrypting at least one of the sessions compared to if they only captured one login.

Misconception #2: “They can’t break future sessions.”

Many people think 1024-bit RSA keys can be cracked by the NSA. If they would do this to a key used for a TLS handshake that didn’t use ECDHE/DHE, every captured TLS session using that key would be trivially decryptable.

The brute force attack on Diffie-Hellman I described under #1 does not break future sessions: it can only break the sessions that have already been captured. When new keys come in, the process has to start all over again.

But using the index-calculus algorithm instead, the attacker first needs to pre-compute lots of data before the actual key is necessary in the computation. The attack has 3 steps: find some powers of g which factorize into a small set of primes (the factor base). Then taking the log_g of the equations g^x = p₁^s₁ … p_r^s_r creates linear equations with the logarithms of the primes as unknowns. When enough equations are found, they can be solved using linear algebra mod (p - 1). In the final stage, the key is multiplied with g until a number is found that factors into the factor base. From this, it is easy to compute the discrete log of the key.

The first two steps do not use the key at all, their result can be stored for later use to decrypt future keys. There is a trade-off here, though: the larger the factor base, the slower the first and second stages are, but the faster the third stage is. It’s unlikely that it is worth the effort to make the third stage as efficient as decrypting a session with a RSA private key is, but it’s not impossible.

Misconception #3: “It’s automatically more secure!”

We can conclude from #1 and #2 that attacks on Diffie-Hellman groups exist that can reveal as much as an RSA private key.

It is generally assumed that Diffie-Hellman and RSA offer approximately equal security for the same bit length. So breaking 1024-bit RSA would be as hard as breaking 1024-bit Diffie-Hellman.

Therefore, if you’re using a 1024-bit Diffie-Hellman group (if you’re using Java and DHE, you’re using a 1024-bit group, if you’re not using the very latest version of Apache, you’re using a 1024-bit group) you effectively have the same security level as somebody using a 1024-bit RSA key, but for one exception: the RSA private key can be stolen (by NSA hackers or court orders). But please keep in mind that this is the only benefit forward-secrecy gives you.

What does this mean for OTR?

Every OTR conversation uses a DH key exchange with the same 1536 bit prime from RFC 3526. While I have no idea how much it would cost, there is a finite amount of work, somewhere in the order of breaking RSA-1536, the NSA needs to do after which they are capable of decrypting every OTR encrypted session with an hour of work. Is it realistic to hope the NSA never had enough interest/budget against OTR to carry out such an attack?

Remember this news article from September 2013 about the NSA’s capabilities:

“For the past decade, N.S.A. has led an aggressive, multipronged effort to break widely used Internet encryption technologies,” said a 2010 memo describing a briefing about N.S.A. accomplishments for employees of its British counterpart, Government Communications Headquarters, or GCHQ. “Cryptanalytic capabilities are now coming online. Vast amounts of encrypted Internet data which have up till now been discarded are now exploitable.”

I don’t think the amount of OTR traffic is “vast”, but other than that, this seems spot on.

---