Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Say I encrypt a message with the public key of a party whom I want to contact with and then send the ciphertext over an insecure channel.
Naturally, an adversary who listens to this channel can obtain the ciphertext. This adversary can simply wait some years for computation speed to increase and then might launch a brute force attack once it becomes feasible.
What methods do we have to prevent such attacks?
This adversary can simply wait some years for computation speed to increase and then might launch a brute force attack once it becomes feasible.
TL;DR: we don't need to protect against brute force attacks because we can choose a key size large enough to withstand those kind of attacks.
Computation speed is often linked to Moore's law. That used to say that the number of transistors / the size of the transistors doubles every two years or so. Moore's law, however, hasn't held for the last 6 years or so and is slowing down (and Intel's 10 nm roadmap is slipping as we speak, slowing it down even more).
Let's assume that computational speed doubles every two years as well. It obviously doesn't as the speed of memory / cache operations doesn't double every two years, but OK. In that case, after 10 years you would gain a speedup of 2 * 2 * 2 * 2 = $2^5$. That means that an AES-128 bit key would be $2^5 = 32$ times easier to break. You could say that AES would not offer 128 bits of security but 123 bits of security because ${2^{128} \over 2^5} = 2^{123}$. However, 123 bits of relative security is still plenty to disallow brute force.
There are other physical limits that prevent brute force, for instance, power requirements to perform the calculations. It requires 1/100th of the power consumption of the world to attack a 128-bit symmetric key, if each try uses the absolute minimum of energy required to perform the calculation. You'd better have a nuclear fusion reactor sitting next to your CPU.
So does that mean that - for instance, 128 bit AES - is enough for the foreseeable future? Not necessarily.
First of all, a fully operational quantum computer, with enough reliable, interconnected qubits, could use Grover's algorithm to bring down the security strength to $2^{64}$. Although such a quantum computer is still a very distant possibility it could be that such a QC would be fast enough to perform that many operations. You should switch to AES-256 if you're afraid of this situation. However, this won't work for many asymmetric ciphers such as RSA. You would need to switch to another algorithm that protects against attacks using quantum computers; so called post-quantum cryptography / PQC.
Furthermore, neither AES nor RSA cannot be proven to be secure. So it is theoretically possible that an attack on AES can be found that allows attacks that are faster than brute force (and do not use impossible amounts of memory). In that case, AES-128 and even AES-256 could become insecure. Fortunately, these algorithms have withstood years of attacks and we know much more about cryptography and crypt-analysis than we did in the entire human history, so finding an attack will be very hard.
Then again, modern crypto has only existed for about 50 years and many algorithms have been broken (let's assume 1970 or so to be the emergence of publicly available crypto) so it might be wise to assume that crypt-analysis will advance even more. Crypto is a relatively new field after all.
Practically speaking you may just want to monitor the advisories on key size of the different agencies in the world. One website that does this is https://keylength.com and it helpfully links to the documents issued by the agencies themselves.
Or you could go all the way and implement quantum-based key establishment and use a one-time-pad to encrypt your messages. This is provably secure against brute force attacks. It's very cumbersome though, and initial implementations fell quite ungracefully against side channel attacks.
Of course an adversary can collect ciphertext pieces passively and eventually obtain the decryption key in an hypothetical break of the encryption algorithm in a matter of years.
The most remarkable case is found on the online world, wherever you connect to a server using TLS (i.e HTTPS). Here you can notice that if RSA is used to establish the session key, and that in some years the private key is obtained, all the communications can be read by obtaining the session key associated to every message.
That won't happen for example when using DHE, since it will select a different private value in the session key negotiation. If it gets broken in the future then you can recover the communications associated to a private value. It will only make your process slower, since you can compute all the private keys as seen in LogJam. But this is a supposition, since obtaining a private value can be an expensive time-consuming but feasible task, thus calculating $n$ private keys can be exhausting, or not.
There's another fact, we are talking about recovering the session key by breaking asymmetric algorithms, but what if the session key can be found if the symmetric algorithm gets broken in the future? That's the point.
