6
$\begingroup$

PFS suites suffer from the same defects as any other salt-less password hashing scheme.
Why is everyone promoting Perfect Forward Secrecy (PFS) ciphersuites so fiercely?

Namely, when the group/hash weakens, then the attacker can invests into a massive pre-computation, after which individual connections/hashes can be broken with minimal additional cost. This property allows the big players to amortize the cost of the massive pre-computation over the massive ammount of cracked connections. Consequentially, it promotes mass snooping over targetted attacks.

This question is motivated by the WeakDH/LogJam paper.

EDIT, thanks @steffen-ullrich, It does not make sense to include the salt in "the secret", so the DHE equivalent of salt-less is "everyone uses the (few) same groups".

$\endgroup$
  • $\begingroup$ Yes, I know PFS can be implemented without this defect, but currently, they are not. $\endgroup$ – user185953 May 9 at 13:05
  • 3
    $\begingroup$ PFS does not imply vanilla DH. Vanilla DH with ephemeral keys does not imply LogJam-style attacks. And using DH with or without a fixed prime does not imply PFS. $\endgroup$ – Future Security May 9 at 14:53
16
$\begingroup$

Salt-less password hashing is only a problem since the amount of passwords actually used in practice is comparably small and also not evenly distributed. Thus it is both in terms of time and memory possible to generate a table with pre-computed hashes and then check the salt-less hashes against this table to reverse the hash. The protection against this are thus salts (increase of time and memory needed for pre-computation) and slow hashes (increase of time).

But, this pre-computing will no longer be feasible if the choice of passwords is not biased against "few" often chosen passwords but if instead there would be a huge amount of possible passwords and none of these would be more likely than the other. It would simply not be practically possible in terms of time and memory to pre-compute and store the hash for all possible passwords. And that's exact the case you have with PFS - it is simply impossible to pre-compute even a relevant small part of all the possible values.

$\endgroup$
  • 3
    $\begingroup$ Oh, right. Salt-less is primarily bad because of the immediate consequences for weak passwords, not because of consequences of future improvements to attacks. $\endgroup$ – user185953 May 9 at 14:05
  • $\begingroup$ In other words, you say attackers are already building tables for all those weak RNGs that are out there. PS: Wasn't "lower client RNG requirements" one of the selling points of D-H KEX over KEX_RSA? I wish a good RNG to you! $\endgroup$ – user185953 May 9 at 14:07
  • 2
    $\begingroup$ @user185953 Everyone's favourite weak RNG is Dual EC DRBG. It has the novel property of containing an asymmetric backdoor - the party who chose its constants (widely believed to be the NSA) can predict future outputs from past outputs, but a typical observer cannot. Other weak RNGs exist (badly written code that uses LCGs, embedded devices without good sources of true entropy), but are not believed to be common enough for most attackers to bother attacking them. $\endgroup$ – James_pic May 9 at 16:41
  • $\begingroup$ Salt can also make it so two identical passwords get hashed differently. That feature is also unneeded here. $\endgroup$ – ikegami May 10 at 13:58
8
$\begingroup$
  1. We choose groups like RFC 3526 Group #14 or larger so that the precomputation is so large it is not feasible. The main problem with weakdh/logjam is that the chosen groups were originally chosen to be breakable for ‘export-grade’ cipher suites, or what I like to call ‘US imperialism-grade’ cipher suites.

    The scheme was that US companies—which are the only companies in the world who can sell cryptography products because the US is the best—were required by the NSA to use bad DH groups for any products they sold overseas, so that all cryptography outside the US would be breakable.

    When we eventually realized that it was possible for cryptography to happen in lesser lands than the United States and the whole scheme fell apart, the TLS maintainers forgot (or ‘forgot’—malice and incompetence are conveniently hard to distinguish) to remove the bad DH groups.

  2. Even better, in newer systems we choose groups that don't admit such precomputations like X25519. There is a batch advantage to attacking many X25519 targets simultaneously, but no known precomputation that speeds up any particular target, and the cost to break even the first target is still $2^{128}$.

  3. That said, ‘perfect forward secrecy’ is a value-loaded word that is best avoided because it confuses people. It is much better to say when keys are erased, because then, in order to be honest, you have to think about holes like TLS session resumption design mistakes where the keys were not erased despite using ‘PFS’ cipher suites. Key erasure means that without breaking the cryptosystem the plaintext can no longer be recovered. Of course, with a breakthrough in cryptanalysis, all bets are off.

There is a looming threat of quantum cryptanalysis in a couple decades that would enable retroactive decryption of all past TLS sessions with pre-quantum key agreement. That's why work is ongoing to deploy post-quantum key agreement as promptly as we can get confidence in it, with, e.g., the NIST PQCRYPTO competition.

$\endgroup$
  • $\begingroup$ 2. Yes, but we never know if "don't" isn't simply "didn't until now". 4. Yes, with a (quantum) breakthrough the bets are off. I'd just prefer a "salted" PFS scheme where Lim[(cost of breaking N connections) / N] won't converge to (almost)zero. $\endgroup$ – user185953 May 9 at 15:29
  • 4
    $\begingroup$ You can hypothesize all you want about cryptanalytic breakthroughs, but there's not much predictive power to it; someone could break AES tomorrow too. After over three decades of work by the smartest cryptanalysts on the planet, nobody has found any plausible way to reduce the cost of breaking X25519 substantially past Pollard's rho. The best-known cost for breaking $n$ X25519 targets is $2^{128} \sqrt n$. The problem with weakdh/logjam was not the possibility of precomputation; it was the practicality of the specific attacks (which happen to involve precomputation). $\endgroup$ – Squeamish Ossifrage May 9 at 15:53
  • $\begingroup$ Until 7919 in '16 TLS standards never specified any integer-DH(E) groups, or even the size for nonexport suites, although IKE/Oakley and SSH did and some implementers reused those because they were lying about. 1.1 in '06 deleted the export suites, along with their limit of DHE to 512, although of course most implementations continued to support 1.0 until well into the '10s, and OpenSSL until (IIRC) 1.1.0 actually allowed export suites even in 1.1 and 1.2, technically violating the RFC. $\endgroup$ – dave_thompson_085 May 10 at 1:25
  • $\begingroup$ @dave_thompson_085 I deliberately left it vague who the ‘TLS maintainers’ meant, because the story, as you observe, is rather complicated; suffice it to say that in many/most TLS stacks the bad DH groups were still readily available and often on by default. $\endgroup$ – Squeamish Ossifrage May 10 at 1:46
  • $\begingroup$ Helpful, but ignores the question. It is not about LogJam. It is inspired by how the lack of "salt" in both password storage and deployed DHE amplifies the attack from "Meh, why would anyone target me?" to "I am already hacked." $\endgroup$ – user185953 May 13 at 16:28

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.