2
$\begingroup$

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?

$\endgroup$
  • 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
4
$\begingroup$

Simple description of Logjam

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.

Slightly more accurate description

A simplified view of Diffie-Hellman is that it involves Alice and Bob agreeing on a generator $g$, and a prime modulus $p$. All operations are done modulo $p$, making it a finite cyclic group. Alice generates a secret integer $x$ and sends the result of $g^x$ to Bob. Bob generates a secret integer $y$ and sends the result of $g^y$ to Alice. Now Alice calculates $(g^y)^x$ and Bob calculates $(g^x)^y$. It just happens to be that $(g^y)^x = (g^x)^y = g^{xy}$, so now $g^{xy}$ is the shared secret. DH gets its security from the fact that Eve has access to $g$, $p$, $g^x$, and $g^y$, but is unable to calculate the value of $g^{xy}$. Seems all rosy, right?

Recall that all of the above operations are done modulo $p$. Unfortunately, it turns out that a one-time computationally-intensive calculation done on $p$ allows an attacker to derive information that allows them to calculate $g^{xy}$ from only $g^x$ and $g^y$, despite never having direct access to either $x$ or $y$. They can re-use the information derived from the analysis for any exchange done modulo that same prime $p$.

Full description

https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf

Mitigations

There are three ways to mitigate this attack:

  1. Use a custom modulus - 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. This is an option if you don't want reduced performance from a larger modulus.

  2. Use a large modulus - 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 any modern technology. This is a risky option if technology significantly improves in the near future.

  3. Use elliptic curve cryptography - 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).

* It still requires some serious computing power, don't get me wrong, but it's nothing compared to the initial precomputation step. A powerful ASIC cluster could break each key exchange using the broken group in real time.

$\endgroup$

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.