Imperfect Forward Secrecy: The Coming Cryptocalypse
tonyarcieri.com
tonyarcieri.com
----
This guy has not understood forward secrecy. The session key is never transmitted, not in clear text, nor in crypto text.
Forward secrecy over SSL is achieved by using Diffie-Hellman key exchange in combination with public key crypto. This makes sure that as long as the private keys are not compromised, the DH exchange is immune to a man in the middle-attack (which otherwise is the weak point of DH).
Recording the communication between the parties will therefore not yield any information even if the private keys are leaked or otherwise discovered in the future. So solving discrete logarithms or factoring numbers quickly in the future does not break contemporary forward secret communication.
(Read, for example, http://en.wikipedia.org/wiki/Perfect_forward_secrecy )
----
Okay, so after re-reading, I'm still inclined to believe he hasn't fully grasped forward secrecy, or at least is misrepresenting it here:
> If the NSA can break the public keys used for your sessions, and derive their corresponding private keys, it can decrypt all of your sessions, regardless of whether you used “perfect” forward secrecy.
This is still not true. What is true, though, is this: If the adversary can solve discrete logarithms (or whatever's the appropriate difficult problem) quickly, they can decrypt your session. Not simply because they get your private keys, but because they get your private keys and are able to defeat DH.
----
And finally I understand why I'm wrong and he's right: Elliptic Curve Diffie-Hellman, unlike "regular" DH, uses public and private keys. The passage I quoted above is indeed talking about breaking the DH exchange. TIL :)
Here's how, in a simplified nutshell:
- A sends g^x to B;
- B sends g^y to A;
- A and B agree on the session key H(g^xy);
- An attacker that can solve the discrete logarithm finds x from g^x;
- The attacker finds the session key by computing H((g^y)^x).
I was thinking that the adversary would discover the private keys and then learn nothing, but he can of course attack the DH exchange. My bad.
Alice and Bob want to compute a shared secret with ECDHE. I'll use Wikipedia's notation:
https://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93...
Alice has private key dA and public key QA. Bob has private key dB and public key QB.
Alice can compute a shared secret S (I'll simplify here for brevity)using scalar multiplication as follows:
S = dA * QA
Bob can compute the same shared secret as:
S = dB * QB
Do you notice the inputs to the scalar multiplication operation? They're the elliptic curve public keys.
For Alice and Bob to arrive at a shared secret, they much have each others' public keys.
For forward secrecy to work, Alice and Bob can't use well-known public keys they found in advance. They generate ephemeral public keys for the session, and transmit them to each other as part of the protocol.
Still don't believe me? Let's look at CurveCP, an advanced transport encryption protocol that provides both passive and active forward secrecy:
http://curvecp.org/packets.html
The "hello packet" is:
Hello packet:
(C',0,Box[0'](C'->S))
where C' is the client's short-term public key
If you can solve the discrete logarithm problem, using future computers or future algorithms, you can derive the short-term private key, the shared secret, and with it the entire session.
I was thrown off by the fact that Elliptic Curve Diffie-Hellman has public and private keys. I figured you weren't talking about the DH part when you talked about public and private keys.
Today I learned more about Elliptic Curve Diffie-Hellman. A good day. Thank you :)
Why bring up OTPs if current symmetric encryption is quantum-computing proof (modulo Grover)? If anything, OTPs just leave you with a much bigger (literally) key exchange problem, without any meaningful advantage.
With all that said, "scalable quantum computers" are very much like the year of the Linux desktop, or cold fusion: always just a few years from now.
And yes, we won't know when (or for the true pessimists, if) quantum computers capable of breaking today's public keys will be available. And as another counterpoint, D-Wave's technology appears to be a bit overblown: