7
$\begingroup$

When I send encrypted data to a website, using public key encryption, what is stopping someone who is listening from storing my encrypted data, and decryption it in a few years after they have determined the private key?

From my understanding, private keys can be discovered after a few years using a fast computer. Are there any time-sensitive safeguards used with public key encryption so that my info won't be useful in a few years?

$\endgroup$
  • 4
    $\begingroup$ What is your definition of "a few years"? The common crypto in use today (128 bit AES, 2048 bit RSA, etc) should be secure for a few decades. Given, we don't know that for a fact. $\endgroup$ – mikeazo Aug 26 '15 at 0:15
  • 4
    $\begingroup$ The safeguard is to use Ephemeral key exchange (perfect forward secrecy) and large key sizes that take longer to attack $\endgroup$ – Richie Frame Aug 26 '15 at 0:43
  • 3
    $\begingroup$ The short answer is, nothing is stopping you from doing that and it is a real threat to consider. This is one of the reasons why encryption key strength is sometimes estimated in how many years from now the key will be secure. Ideally you could use this information to pick a key that is secure until your information is no longer sensitive (say, 10 years from now, maybe you don't care about that work email you just sent being secret). $\endgroup$ – Guut Boy Aug 26 '15 at 7:06
  • 2
    $\begingroup$ The NSA is supposed to do this according to Snowden: Safe TLS encrypted traffic and wait for more computing power or access to the secret key (with e.g. Heartbleed). $\endgroup$ – Martin Schröder Aug 26 '15 at 19:54
6
$\begingroup$

What is stopping someone from saving encrypted info, and decoding it later?

Nothing. That's exactly why certain three letter institutions build large data centers... Waiting for the first large quantum computer to be built or for new attack techniques that allow to break e.g. RSA for the key sizes used today.

Are there any time-sensitive safeguards used with public key encryption so that my info won't be useful in a few years?

No, and obviously this is also not really possible if you think of something like a self-destruction mechanism. The attacker can copy the data today, store it and prevent any execution of integrated code for example.

The only things you can do to protect data from such an attack are either

  • preventing adversarial access, i.e. you must not send the data on a public wire / store it on a publicly accessible device (which includes web servers, cloud services etc.pp.), or

  • use information theoretically secure encryption like the one-time pad. (Remember this requires the keys to have the same length as your data AND there are only secret key schemes for this setting).

Summing up: There are solutions but they are not really practical. So far we simply failed to provide a reasonable solution for this issue.

$\endgroup$
  • $\begingroup$ A third possibility is to use something like "everlasting security," based on an assumption that the adversary is space-bounded. $\endgroup$ – Chris Peikert Aug 27 '15 at 2:16
  • $\begingroup$ @ChrisPeikert agreed, see my edit. Do you agree? $\endgroup$ – mephisto Sep 2 '15 at 1:45
  • $\begingroup$ Everlasting security uses a different model, where there is a high-throughput stream of public random numbers coming from a "beacon." The assumption is that the attacker can't store the whole stream over any moderate length of time, and if this is true, encryption is information-theoretically secure. Encryption and decryption don't require much storage, only reading a very small part of the beacon's stream as it goes by. $\endgroup$ – Chris Peikert Sep 2 '15 at 1:50
  • $\begingroup$ Ok, I just reverted, I guess your comments give the idea now. $\endgroup$ – mephisto Sep 2 '15 at 3:25
6
$\begingroup$

First, let me address the assumption that private keys will be found in a few years using a fast computer. Unless there are serious algorithmic improvements in the cryptanalysis of a scheme, this simply is not true. Of course, the length of the key is of importance, and if you need security for the far future then you should be using 4096-bit keys (or even more), but 2048 are expected to secure for a very long time. Note that plaintexts encrypted with 3DES 20 years ago remain perfectly safe today, and our expectation is that the same will be true of AES encryptions 20, 30 and even 50 years from now (at least for AES-256). There are recommendations made by both NIST and ENISA for key lengths, factoring in how long you want security to hold for. These are all very conservative estimates, and it isn't that we really think that the algorithms can be broken in this time. So, no - unless something surprising happens, we strongly expect our encryption schemes to give security for a very long time.

Having said the above, when you talk about interacting with a web server, if forward secure protocols are used, then even if the server's RSA key is broken (or stolen), it is still necessary to break the Diffie-Hellman key exchange for each session separately. This provides good security for a very long time into the future, unless something really surprising happens (that DH can be broken very fast or likewise AES which is used to encrypt with the session-key generated by the DH key exchange).

$\endgroup$
  • 3
    $\begingroup$ ... or that a quantum computer is built.. $\endgroup$ – mephisto Aug 27 '15 at 1:11
6
$\begingroup$

Decoding information within a time frame is of absolute importance.

Say X is an terrorist, the information of his attack will be useful today, not years after the attack has happened. And similarly decoding your message is important today, not years later. Also there might be a possibility that when somebody has decoded your key for future use, you might have already changed it.

$\endgroup$
  • 2
    $\begingroup$ Decoding information within a time frame is of absolute importance. – Not really. Information can still be very valuable at a later time! Taking your example: While you indeed might not be able to prevent the attack itself, the later decrypted information could enable you to identify and nail down the individuals involved in the attack (assuming you haven’t caught him/her/them in the meantime) and it might even help identifying whole terrorist networks. It’s exactly for that reason why govenmental agencies store and analyze intercepted ciphertext (and related data) for decades, not days. $\endgroup$ – e-sushi Aug 26 '15 at 18:48
  • $\begingroup$ #e-sushi yes, I agree thats an aspect we should consider too $\endgroup$ – CuriousCurie Aug 27 '15 at 10:42
1
$\begingroup$

Seems like the correct answer to the question, as initially asked by the poster, is forward secrecy.

"Nothing" is the wrong answer.

Assuming Alice (with public key $PK_A$) and Bob (with public key $PK_B$) know each other's public keys, then they can exchange an ephemeral key $k$. The ephemeral key $k$ can be exchanged in such a fashion that its security is independent of private key compromise.

Alice and Bob can negotiate a session key as follows:

  1. Alice and Bob agree on a group $G$ and a generator $g$ for $G$. For instance, $G$ can be $G \subset \mathbb{Z}_p, |G| = q$, where $p = 2q+1$, $p$ and $q$ are both prime.
  2. Next, they can perform an authenticated Diffie-Hellman (DH) key exchange.
  3. Alice picks a random $a \in \mathbb{Z}_q$ (DH secret)
  4. Alice computes $g^a \pmod p$ (DH public key)
  5. Bob picks a random $b \in \mathbb{Z}_q$ (DH secret)
  6. Bob computes $g^b \pmod p$ (DH public key)
  7. Alice sends Bob, $g^a$ and a signature on it $\mathsf{Sign}_{SK_A}(g^a, \text{"Alice"}, \text{"Bob"})$
  8. Bob sends Alice, $g^b$ and a signature on it $\mathsf{Sign}_{SK_B}(g^b, \text{"Alice"}, \text{"Bob"})$
  9. (Some additional freshness info should probably be included in the signature, to avoid reuse.)
  10. Alice and Bob can compute $g^{ab}$ as $(g^a)^b$ and $(g^b)^a$ respectively.
  11. Next, a key derivation function should be used on $g^{ab}$, obtaining the final key $k = \mathsf{KDF}(g^{ab})$

The signatures on the DH public keys prevent man in the middle attacks.

Compromise of the secret key $SK_A$ and/or $SK_B$ will not lead to compromise of $k$.

If Alice and Bob's keypairs should not be used to sign[1], or if deniable authentication is a goal for the key exchange, then you can look at the SKEME key-exchange protocol, which, if I recall correctly does not use signatures but maintains forward secrecy.

[1] Maybe because they are encrypt-only keypairs, as signing and encrypting with the same keypair can be disastrous.

$\endgroup$
  • 2
    $\begingroup$ Forward secrecy will not save you if someone stores all ciphertexts. It only means that it makes the adversary's life harder as he now has to break many symmetric keys or DH key exchanges....which for example gets easy if someone has a quantum computer. $\endgroup$ – mephisto Sep 2 '15 at 1:31
  • $\begingroup$ I agree that ultimately nothing will save you. However, the way I understood the original question is that the adversary only discovers the private key after some time (maybe by extracting it from the public key). If we assume the adversary can capture and break the DH exchange in the same way he extracts the private key from the public key, then, yes, we are in trouble. $\endgroup$ – Alin Tomescu Sep 2 '15 at 11:57

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.