Does a Logjam attack calculate a group of probable Diffie-Hellman private keys for a user and then try them one at a time to see if it can decrypt the message - or does it directly calculate the one specific instance of a user's private key?

  • 3
    $\begingroup$ It's a precomputation of reusable intermediate values for cracking private keys for some given DH prime. It allows you to find probable keys faster. Then you can reuse this to crack any private key under that DH prime. It's basically one half (the difficult half) of a batch attack. $\endgroup$ – Natanael May 10 at 23:45
  • $\begingroup$ So it doesn't require checking the message itself to ensure that you got the correct private key and calculated the shared key? By the time you get done calculating, you are just sure that you got the right private key? $\endgroup$ – CBruce May 11 at 0:27
  • 1
    $\begingroup$ @CBruce The attack can be performed without ever even recording someone's key exchange session. $\endgroup$ – forest May 11 at 1:44
  • $\begingroup$ @CBruce it's a two-step attack 1: precompute (slow, only feasible for small primes). 2: aquire key exchange transcripts, crack them (very fast) using the data from step 1. $\endgroup$ – Natanael May 11 at 8:45
  • $\begingroup$ @Natanael To be fair it's not that fast (it requires a pretty powerful computer, though an intelligence agency could probably do it real time), but it's significantly faster than cracking the handshake on its own. $\endgroup$ – forest May 11 at 9:29

Logjam is a two-step process. First, you take a group and apply a precomputation to it. Most people use one of a few different groups, so breaking a single group effectively breaks every single key exchange done by anyone using that group. If a group is "broken", then any key exchange done with Diffie-Hellman using that group can be broken quite easily, revealing the shared secret. This is the second step to the process, using values derived from the precomputation to quickly determine the shared secret.

Logjam does not attack any one user's individual key and it does not rely on any information specific to any single key exchange event. In fact, the initial precomputation step of the attack could be performed for a group even if no one has ever used that group before. All it means is that when anyone does use that group, the derived shared key could be passively recovered by an eavesdropping party.

There are three ways to mitigate this attack:

  1. You can generate your own DH modulus instead of an existing group. This would force an attacker to perform an extremely complicated precomputation step tailored specifically to your system, making it impractical to attack. After all, $10,000,000 to break a third of the Internet's key exchange is nothing to a powerful adversary, but it's probably too much to spend on a single target.

  2. You can use an existing but large (2048-bit or greater) group. While the precomputation attacks are still possible and breaking the group would allow mass recovery of shared secrets, the size of the modulus would make it impossible to attack with modern technology.

  3. Finally, you can switch away from finite-field Diffie-Hellman and instead use elliptic curve Diffie-Hellman. ECDH, in addition to being faster and more secure even at smaller key sizes, is not vulnerable to precomputation attacks. It performs calculations as points on a curve, rather than modulo a large prime number (your potentially exploitable group).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.