How long would it take to break a 1024 bit OpenPGP encrypted email?

Question

For WPA, there are calculators to determine the time needed to crack a passphrase, but I have found nothing for OpenPGP.

How long would it take to break a 1024 bit OpenPGP encrypted email (depending on CPU power)?

I'm also interested in other keysizes like 2048 and 4096.

Answer 1

While @Jens Erat's answer was rather comprehensive, I did research into breaking RSA (the algorithm behind OpenPGP), so I wanted to opine:

I'll break with the norm and give the TL;DR first: It is impossible for you to break that key. If we are looking at this realistically, there is no way for you to factor a 1024-bit integer. Your best possible bet would be trying to break some other part of the security chain (e.g. the desktop where the receiver checks his email).

With realism out of the way, let's consider possible strategies:

• Blind guessing/Brute Forcing. With a 1024-bit semiprime, there is little chance that this will ever work. It would be better use of your time randomly trying to guess lottery numbers.

• Generating a Rainbow Table. Take the guesswork out of factoring by taking every prime under 2^1024 and multiplying it by every other prime, storing the result in a table. Then all you would have to do is lookup the correct pair. As you can imagine, this too is impossible. This would involve x! pairs for x number of primes. By the prime-counting function, you're looking at about 2.95 * 10^307 primes--for comparison, it is estimated that the number of atoms in the obserable universe is on the magnitude of 10^83, so even if we could make every atom store two primes and their product in a way our computer could index it would be impossible.

• Use the General Number Field Sieve. The GNFS is your best bet to factoring a large semiprime. It was used by Kleinjung and his team to factor RSA-768, a 768-bit semiprime. Unfortunately, that took his team over three years to accomplish, and it is orders of magnitude smaller than the numbers you wish to factor. Even if you spent millions of dollars (per day) renting out the top supercomputers at full capacity, it would be near impossible to factor the number. The first step of GNFS is to find enough "relations" that allow the subproblems to be solved, and this can take very long amounts of time.

Your last resort is to use a quantum computer, which would allow you to factor the numbers in a feasible amount of time. Unfortunately, these have yet to be developed to a point of any usefulness. So for now, we cannot factor 1024-bit and greater semiprimes (and thus the algorithms that rely on them).

Answer 2

First, I'm assuming you're speaking of RSA 1024 bit encryption.

Generally, the topic is far too complicated for providing a simple number.

tl;dr: Cracking an OpenPGP encrypted message on a single CPU is not feasible, and probably takes years even with large computing clusters. Yet unknown (to the public) mathematical flaws could change this by order of magnitude, as quantum computers might do at some time in future (far, from an "internet age" point of view).

The slightly longer version:

Cracking the Asymmetric Encryption (RSA 1024 bit key)

In addition to RSA 1024 bit keys, this also applies to larger key sizes. Larger keys provide more security (in form of computing power to crack them), but remember the security does not increase linearly with the key size.

There's a nice post on the Information Security Stack Exchange, "How to estimate the time needed to crack RSA encryption?", which does not complete with an estimate like "Using an Core i7 model xy, you'll be able to crack an RSA 1024 bit key in estimated z hours", but the answers agree on "RSA 1024 bit keys cannot be cracked by individuals with usually available computing power (ie., a handful of high-end machines) in a reasonable time.

The discussion of breaking 1024 bit keys with much more computation power was only considered from an academic point of view:

I recently learned that the selection of the parameters for a 1024-bit number factorization has begun (that's the "brainy" part); the sieving is technically feasible (it will be expensive and involve years of computation time on many university clusters) but, for the moment, nobody knows how to do the linear reduction part for a 1024-bit integer. So do not expect a 1024-bit break any time soon.

This probably also applies to large, well-funded institutions with lots of computing power like the NSA.

Things could change rapidly if

• somebody finds a mathematical flaw, which reduces RSA's complexity by orders of magnitude (some institutions like the NSA employ a vast number of great mathematicians), or
• quantum computers finally work and get powerful enough and capable of running certain algorithms. Not expected to occur within the next few years.

For DSA/ElGamal, things are a little bit different. A DSA key of the same size of an RSA key provides more security, but at the same time DSA is more vulnerable to bad random numbers (compare with the Debian random number generator flaw). Elliptic curve cryptography which is upcoming for OpenPGP right now does not have known attacks for the algorithms supported yet and generally considered safe, but there is some doubt left especially on the NIST-recommended curves (NIST has lost quite some reputation for making a broken random number generator a standard), and some implementation nitpicks.

Cracking the Symmetric Encryption

For performance rasons, OpenPGP uses hybrid encryption, thus the message gets encrypted with symmetric encryption and a random symmetric key (in OpenPGP, often called "session key"). This session key again is encrypted using the asymmetric encryption algorithm, eg. RSA.

If you're able to crack the symmetric encryption key of a message, you could also read the message (unlike cracking the asymmetric key, where you could read all messages encrypted to this key).

Unlike with very early versions of PGP (which used a symmetric encryption algorithm designed by Zimmermann himself called BassOmatic, which is considered broken), all symmetric algorithms defined for OpenPGP do not have relevant known attacks.

Unless somebody chose to use no symmetric encryption (which is actually possible!), breaking a message using the symmetric encryption algorithm should not be considered feasible at the time being.