Thursday, May 21, 2015 - 15:51

LogJam: Beating TLS and DH with a MITM attack and precomputation

Researchers found a pretty disturbing problem with TLS and DH. It's mostly relevant for export grade encryption. But it's here to stay and needs to be tackled more properly in the near future.

The attack goes like this. The entry point is a TLS protocol design flaw. An attacker in the middle can downgrade the connection to export grade encryption by rewriting a request for DHE to DHE_EXPORT (from client to server) and then again rewrite that DHE_EXPORT to DHE. This is possible due to said design flaw which makes it impossible for a client to tell if the request was honored or not. From the client's POV it looks like it got a DHE while in fact it's just export crap. This attack vector is similar to the FREAK attack. Just that it attacks DH instead of RSA.

Interestingly they found another oddity. Quite a few of the tested servers supported 512bit primes on non export grade DHE, which eliminates the requirement to downgrade the encryption.

This export grade encryption can now be decrypted with a precomputation attack. According to the researchers precomputation took about 7 days after which computing individual logs took only about 90 seconds on average. Or in other words...the encryption is useless. A huge problem with this attack is that it does not have to be done for every target. Very few primes are used. In fact most servers use the very same. 8% of Alexa's Top 1M sites are affected by the TLS downgrade and 82% (Apache) of those use a single prime. 10% (mod_ssl) a second. The rest is sharing 463 distinct primes. 

The last revelation from those probes was that a certain percentage of servers had distinct but bad primes. Bad primes are primes where p or (p - 1) / 2 are composites.

The researchers believe an attack on 1024bit might be possible by attackers with vast resources (NSA anyone?). The numbers are staggering but considering the NSA's resources they are feasible to tackle. It's really just a money problem. And that's the only problem the NSA does not have. I don't think NSA can do it in days or weeks. You get other problems than just money with that. But months? Possibly.

I don't think they enjoyed reading the paper as much as I did.