7

The answer

https://security.stackexchange.com/a/25392

has seemingly shown that AES-256 will not be directly cracked for at least the next 200 years (unless we manage to harvest the energy output of distant stars). The only available attacks will continue to be indirect attacks like brute-forcing the original password, etc.

Questions:

  1. I repeat the first question to the above answer that nobody answered: What about quantum computing?

  2. Does the same hold for RSA 2048 and ECDSA? Will those be cracked (factorable) any time soon? I understand that RSA 1024 will be cracked very soon - is that true?

  3. What about SHA-1 or SHA-256? Will those be cracked (reversed) any time soon?

I'm sorry for my cluelessness. I'm essentially trying to understand

  • whether my PGP encrypted emails (RSA 2048)
  • whether Bitcoin (SHA-256 and ECDSA)

will be safe for the next 200 years or so. Bitcoiners especially talk about its money supply after 150 years, so I'm wondering whether there is any basis for their confidence!

Community
  • 1
cryptonamus
  • 309
  • 2
  • 7

2 Answers2

9

RSA-2048, ECDSA (on a 256-bit curve), SHA-1, SHA-256 and AES-256 are all "equally" uncrackable in that they are all in the wide category of "we don't know how to break them with existing or foreseeable technology".

(SHA-1 resistance to collisions, but not to preimages, is not in that category. That one we know how to break -- it would be quite expensive, but not beyond our collective reach.)

We can make some asymptotic estimates that state that if computers are allowed to increase in power in arbitrary amounts (but there are good reasons why this will probably not happen), then RSA-2048 will fall first (approximately 2112 resistance), then ECDSA with P-256 (2128), then SHA-1 (2160), then SHA-256 and AES-256 (2256). But such comparisons are quite meaningless, since they rely on an hypothesis which does not seem wholly compatible with laws of physics as we know them.

Quantum computers, if they can ever be built, will make short work of RSA and ECDSA. They will only weaken SHA-* and AES, down to levels which will still be somewhere between "fiendishly hard to break" and "unbreakable".

Prospective on technology evolution for 150 years are pure guesswork. Nobody really knows what the World will look like 100 years from now. Personally I do not make prophecies beyond 40 years.

Community
  • 1
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • You said that RSA-2048 is 2^112. What is the 2^x of RSA-4096? Do you recommend using RSA-4096 over RSA-2048 for PGP encrypted emails? Maybe those will stand strong against the Quantum computers like AES-256? – cryptonamus Apr 26 '14 at 10:37
  • I'm also a bit confused by the difference in RSA and AES. Cracking RSA means factoring prime numbers. Cracking AES sounds different. Can you explain the difference? Is there any risk of being able to factor RSA 4096/2048 by accident? – cryptonamus Apr 26 '14 at 10:39
  • For estimates of strength of _asymmetric_ keys, see [this site](http://www.keylength.com/). No, a QC can eat RSA keys of any length at breakfast. As for the difference between RSA and AES, well, let's say that it is simpler to list ways in which they are similar: namely, both are named with 3-letter acronyms. Everything else is different: concept, architecture, usage and building elements. – Thomas Pornin Apr 26 '14 at 13:25
  • "By accident" I could become the next Pope. Probability is low, though. – Thomas Pornin Apr 26 '14 at 13:26
7

The problem isn't that these algorithms might have their keys/inputs brute-forced. Given large enough keys and/or input sizes, they almost assuredly won't.

The problem is that there exists no crystal ball with which to assert whether or not a particular algorithm will still be considered strong through the next two hundred years of cryptanalysis. We currently believe these algorithms are strong, but these beliefs are either based upon empirical evidence (e.g., the AES algorithm itself hasn't been broken by the world's foremost cryptographers) or mathematical assumptions (e.g., RSA is "hard" to break assuming factoring is "hard", and ECDSA is "hard" to break assuming the DLP is "hard").

Additionally, we have no generic way of asserting that complex use-cases of secure cryptographic primitives is strong. GPG is built upon RSA, AES, and SHA. Even if we take as an axiom that each of those primitives are strong, the specific composition used by GPG may be found to be weak. For something more real-world, TLS has gone through many revisions, each thought at the time to be relatively secure, and each time discovered later to be subtly (or egregiously) broken.

Even if we somehow demonstrated that the primitives and compositions are secure, we still run into problems. These algorithms are written in software, and software is written by humans. Humans are imperfect, and we make mistakes. The Debian distribution of GNU/Linux, for instance, made seemingly-innocuous changes to OpenSSL that resulted in its random number generator being extremely predictable. In many cryptographic use-cases, if your random number generator is broken, the entire system is broken. Heartbleed is recent example of something that wasn't necessarily insecure being implemented in an insecure fashion — leading to catastrophic compromise of sensitive data on servers worldwide.

Finally, even if we have a bug-free, formally verified implementation of mathematically-proven cryptographic protocols, the other software on the computer could be insecure or improperly-configured and vulnerable to compromise. Your Bitcoin wallet may be strongly-encrypted, but this doesn't matter if your Windows machine gets a virus that snoops on your keystrokes. People themselves are also a weak link; research has repeatedly demonstrated that people will pretty much hand over whatever sensitive information is asked of them for a piece of candy or an animated GIF of a cat.

TL;DR, will your data today be safe in two hundred years? I wouldn't bet on it.

Stephen Touset
  • 5,736
  • 1
  • 23
  • 38