[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
forward secrecy
Folks,
I would like to raise a few issues regarding forward secrecy
that, I believe, have received insufficient discussion to date.
First of all, the attack scenario that a typical "perfect forward
secrecy" protocol using ephemeral Diffie-Hellman guards against
has always been implicit, and not explicit. I would like to
make the assumptions of this attack more explicit, and discuss
other attacks of a different nature that also affect forward
secrecy.
The attack that an ephemeral DH exchange guards against is compromise
of a long-term secret. If long-term secrets are properly guarded (e.g.
tamper resist token devices, encrypted under passwords etc.) then such an
attack to compromise the long-term secret is an active attack, and in
cases of tamper resist hardware token devices it is an active physical
attack.
It is important to observe that an ephemeral Diffie-Hellman
exchange needs to be efficient, (since it happens interactively in
real time) and in order to be efficient the sizes of the DH
parameters have to be chosen carefully. With Diffie-Hellman there is a
clear tradeoff between efficiency and security. The greater the
sizes of the DH parameters (exponent, modulus) the greater the
security but the slower the speed of the operation.
Another observation is that the DH problem, over time,
becomes more tractable. Let's take as an example an ephemeral
DH protocol that might have been used 10 years ago. For
reasons of efficiency the modulus size for such a
DH exchange would very likely have been 512 bits. Clearly now,
10 years later, it is possible to mount attacks on a 512
bit DH problem, especially for well funded adversaries.
Now assume the adversary is someone like the NSA. For
purposes of this discussion, this could also be the foreign
equivalents of the NSA. The NSA is primarily a signals
intelligence agency. If the NSA performs field operations,
they are probably of a very limited nature. The same is
true of the foreign equivalents of the NSA. Such agencies
operate primarily using *passive* attacks.
What the NSA (and their foreign equivalents) are far more
likely to do is to record all cipherbits, and if necessary,
store them for a few years/decades, until they can be
broken. A recently disclosed case of such a passive
attack revealed that the NSA saved ciphertext for 40+
years, waiting for the moment it could be broken.
I would like to argue that this passive attck a more likely
form of attack, especially considering signals intelligence
agencies as the enemy. What the ephemeral DH exchange is
doing is hardening against the active attack (I argue, a less
likely scenario) while *weakening* the protocol
(for practical efficiency reasons) against a passive
sit-on-it-until-it-can-be-crunched form of attack.
To summarize: There are two forms of attacks that
pertain to forward secrecy. The active attack, and a passive
time delayed attack, mountable by tenacious and well-funded
adversaries. So far, the discussion on forward secrecy has
focused on the active attack.
The forward secrecy solution that I described on this
list and presented at Dallas (pre-certified short lived
Diffie-Hellman keys), in the context of SKIP, has the advantage
that none of the DH operations needs to be performed in real
time. They can all be precomputed. This makes it feasible
to use much larger DH parameters, say 4000 bit DH
exponents/modulus, than is practical today with an
interactive ephemeral DH exchange.
This provides much more effective hardening against a time
delayed passive attack.
Now, one could argue, that with lots of ephemeral DH
exchanges, occurring every few minutes/hours, the enemy doesn't
have to break just one DH exchange, there are many such exchanges
to break. Unfortunately, the work factor of a time delayed
passive attack only goes up by a small linear factor, even with
many ephemeral DH exchanges. With a much larger DH exponent/modulus,
the work factor goes up in a super-polynomial fashion, assuming
Number Field Sieve as the best attack on classic DH. (Again
taking the 512 bit DH case as an example, if the NSA can break
one of these, it could also break a few thousand of these.
On the other hand, breaking a single 1024 bits DH today is
probably infeasible).
Therefore, I argue that we need to provide hardening against
*both* the active and the passive attack. The question is
what attack should the protocol be better hardened against,
since there is a clear tradeoff involved.
If we believe that the active attack is a more
likely form of attack, then frequent ephemeral DH exchanges
(e.g. as in Photuris) provide a better forward secrecy solution.
However, if we believe that the passive attack is more likely,
then the pre-certified short lived DH keys, in conjunction with
much larger DH parameters, provides a better forward secrecy
solution. I hesitate to use the term "perfect", since this
is an overstatement in either case. (The only way to get
really perfect forward secrecy is to use a one-time pad,
which is destroyed after use).
[There are other issues, apart from forward secrecy, that could
be considered, such as the real-time response to a large number of
simultaneous connection attempts, etc., but this discussion can focus
solely on forward secrecy issues.]
Comments?
Ashar.
Follow-Ups: