0

How long would it take to bruteforce a PGP-Encrypted-Mail? If I'm rightly informed, it depends on the bitsize of the encryption Key.

1

OpenPGP (including the widely-used "GnuPG" program gpg) typically uses two keys when encrypting an email: the content itself is encrypted with a symmetric key (which is randomly generated by the sender), and then the symmetric key itself is encrypted (by the sender) using the recipient's public key. Brute-forcing either of these keys is sufficient to decrypt the message.

However, asking "how long will it take to brute-force a key?" is kind of like asking "how long will humanity survive as a species?". There are some factors we can control today (key size, cipher used, and entropy source), some that we can imperfectly prognosticate about based on past trends (Moore's law, total amount of compute resources available to an individual or an organization, etc.), and some that are basically total guesses that might have a breakthrough tomorrow or might never get further (with specific relationship to the algorithms in question) than they are today (quantum computing, theoretical mathematics, cryptanalysis in general). Finally, who is doing the breaking? The NSA has access to a lot more compute resources, and possibly more advanced algorithms, than either of us is likely to have available. The timelines (for reasonable choices among the stuff we can control today) range from "a few months" to "beyond the heat death of the universe".

A few more specific points:

  • The asymmetric (public) key used to wrap the symmetric key is probably the weakest point most of the time. People tend to not rotate public keys very often, so they're most likely to have been generated relatively weakly (using strength that was considered sufficient years ago but might not be considered sufficient anymore) or using an old random number generator that was found to have weaknesses. For RSA public keys in particular, see https://crypto.stackexchange.com/questions/8687/security-strength-of-rsa-in-relation-with-the-modulus-size for a discussion of the relationship between key size and amount of entropy. For other public key algorithms, though, the relationship is quite different (elliptic-curve keys, for example, achieve what are considered the same amount of entropy as RSA keys in vastly shorter key sizes).
  • Public key algorithms in general (and RSA in particular) are also more likely to be vulnerable to quantum computing, if that ever goes anywhere. For a symmetric algorithm, quantum computing would probably roughly halve the effective key length; a quite-secure 128-bit key would become effectively a dangerously-insecure 64-bit key, but a 256-bit key would remain very secure at 128 bits of effective entropy. If you expect quantum computing to go anywhere within the time window that you need your email to remain secure, you may want to treat our current algorithms and recommended key strengths as being as obsolete as Enigma machines.

Some math (and its underlying assumptions):

  • Assume a modern cryptographic processor can try 2^30 (roughly a billion) keys per second. This isn't too far off from what a typical commercial Intel or AMD CPU can achieve using its hardware-accelerated support for the AES symmetric cipher.
  • Assume that the attacker has access to a decent cluster of such processors - nothing you'd need to be a nation-state to have, but something a well-resourced individual could assemble or purchase in cloud compute time - of perhaps 2^10 (1024) such processors.
  • Assume that the increase in compute power per money goes at a rate of doubling every two years (this is roughly in line with Moore's Law, a little lower than it historically ran but it has been seeming to run into limits recently).
  • Multiply that all up, and an attacker can try 2^40 possible keys per second right now, and that exponent will increase by one every two years.
  • Assume that if the brute-forcing attempt will take longer than 2^25 seconds (just over a year), it'll be faster/more effective to wait and build the brute-forcing rig with more-advanced future technology.
  • Assume quantum computing doesn't go anywhere, and there's no major breakthrough in cryptanalysis of the encryption or key-generation algorithms that were used.
  • Here's how long it'd take to fully brute-force a given key strength (measured in entropy; maps exactly to size for symmetric keys but you'll need to apply the appropriate transformation for asymmetric keys) given the above assumptions:
    • 56-bit key: Less than half a day.
    • 64-bit key: Half a year (starting today).
    • 80-bit key: One year of brute-forcing after 30 years of tech improvement (or roughly 33 thousand years with today's tech).
    • 96-bit key: One year of brute-forcing after 62 years of tech improvement (or over two billion years with today's tech).
    • 128-bit key: One year of brute-forcing after 126 years of tech improvement (or many times the expected lifetime of the universe, with today's tech).
    • 192-bit key: One year of brute-forcing after 254 years of tech improvement.
    • 256-bit key: One year of brute-forcing after 382 years of tech improvement.

Remember that these are numbers for what a moderately wealthy / capable individual could do, and that we're assuming they're willing to work on it for a year per key. A large company, university, or government agency could certainly throw more resources at the problem, cutting the brute-forcing time to a fraction of the estimates above (or cutting a decade or more off the development time... but not both).

Of course, the high-end numbers are totally meaningless here; the sheer number of assumptions of "things continuing as they have" that go into them - including no major breakthroughs that make decryption easier, the continued increase in availability of compute power, and the continued existence of humanity or anything else that would care - mean that they have error bars possibly larger than their already-large timeframes.

| improve this answer | |

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.