How long will my encryption remain private?

It is explained that our keys should expire and we should get new, stronger ones with time, reflecting more powerful decryption computing. Does that mean that emails encrypted today will become easier (even trivial) to decrypt in future, so emails encrypted today will eventually lose today's privacy?

If so, what is the general opinion on how this affects notions of privacy by encryption?

-
For modern algorithms with appropriate key lengths: until the algorithm is broken, the implementation is broken, the context you use it in is broken, the key is disclosed to a third party, or quantum computers become generally available (for current asymmetric algorithms, and for symmetric algorithms with key sizes smaller than 256). –  Stephen Touset Jan 27 at 6:48

@fgrieu has written a good answer but there's slightly more to be said on the topic.

It is entirely possible that a paper will someday be published that shows a practical attack on 2048-bit RSA. Equally, a new attack could be discovered that breaks AES in a reasonable amount of time. Finally, someone might find a collision in SHA-256!

This has happened before. When differential and linear cryptanalysis were discovered many designs fell to these attacks. Factoring algorithms have got faster over time, etc etc. A collision was recently found in MD5 and soon after there were tools that could do this in next to no time.

As @fgrieu pointed out, having planned obsolescence gives you opportunity to repair the fence: increase key-size, remove bad algorithms, introduce new algorithms etc etc.

That sad, there are no proofs of (absolute!) security for any of our primitives. Their security is based on the fact that everybody who has looked at these primitives has failed to break them.

Given this, it is difficult to know how long a ciphertext created today with AES-128 will remain secure.

On the one hand, it could well be "forever" and on the other hand a clever grad student somewhere might find a break on AES-128 in $2^{40}$ time tomorrow.

We just don't know.

-
Right. But that's mostly a reason to change algorithm, not key or key size (as asked in the question). And I can't recall a devastating cryptanalytic attack (as opposed to attacks on implementations) striking a widely deployed cryptographic algorithm in the last 30 years (if we discount attacks on keys that where deliberately shortened, like DES; and of course attacks on passwords). –  fgrieu Jan 26 at 21:21
Wait, isn't BitCoin based on people finding collisions in SHA-256? –  AJMansfield Jan 27 at 0:32
@AJMansfield No, only partial preimages afaik, such as "the first X bits of the hash must match this bitstring", which cannot be done efficiently as far as we know, hence the proof-of-work aspect of it (collisions do not matter for that part of bitcoin I believe). If a fast preimage attack on SHA-256 were discovered, bitcoin would be utterly broken, which is why it (or at least the proof of work part of it) has planned obsolescence in a few years were all blocks will have been mined - hopefully before SHA-256 is broken enough to matter. –  Thomas Jan 27 at 1:49
@Thomas: Bitcoin is still supposed to work past the data where no new coins can be minted. Miners are supposed to make their money through transaction fees in those days. –  Christian Jan 27 at 1:54
I think you've overreached @fgrieu. MD5 and A5/1 must surely qualify under you criterion? I'd even put RC4 in that bucket. –  Simon Johnson Jan 27 at 7:27

The main good reasons to change keys periodically are:

• to mitigate the risk of a key compromise; at least some ways keys get compromised are a one-time event, e.g. eavesdropping of the keyboard protecting the passphrase; changing the key thus restores security until the next leak, and only messages enciphered with the leaked key are compromised (and only those actively intercepted after the leak if the scheme provides forward secrecy)
• so that humans remember the procedure;
• addition per comment: in order to reduce the risk coming from using the same key of a block cipher for too many blocks; e.g. for 3DES in CBC mode: if the adversary has 32 GiB of known plaintext (e.g. all-zeroes of an idle link), chances that she can decipher 8 meaningful bytes from another 32 GiB worth of data are >63%.

The main reason to increase key size (which is, or at least should be exceptional compared to key change) is to induce retirement of the obsolete tools used to process the keys; not only is it business to security vendors, it often is the best way to increase security; for examples, if 1024-bit keys are deemed no longer usable, chances are that the Smart Card holding them will be replaced by newer ones, designed with better side-channel leakage protection. In my experience, resistance against brute force is rarely the real weak point in a commercial application (except if that was engineered-in, e.g. to meet some legal requirement).

-
Good answer. I think one important reason is the acceptable amount of use for a key. Especially algorithm with short block (like 3DES) in practice has to be changed because of this. –  user4982 Jan 26 at 19:48
@user4982: good point! I added it to the answer. –  fgrieu Jan 26 at 21:16

The key can be found using brute force, this will take some time and answers provided earlier are valid.

However there are other means to discover a key immediately in a specific context, without using lengthy brute force attacks.

I like this one based on sound emitted by the computer when dealing with encryption, : and this one using the time required to compute encryption keys.

These techniques don't try to discover the unknown key using multiple key values, but just observe how the computer works when processing the actual key.

When specific conditions are met, the strongest key can be discovered within second split unless the existing hardware is redesigned to prevent the methods to work and compromised hardware is removed from use. Note that increasing the key length only is not effective.

Your question about email privacy should be understood as excluding such specific conditions.

-