yeah, I was wondering about how strong GPG was. Back in the day, i.e. the 90's, the assumption was it would take years for then-current NSA supercomputers to factor the keys. Nowadays, with all sorts of new attacks, analyses, and cheap as hell compute time, I would wager that time requirement has gone significantly down.
AFAIK, the current publicly-known record for breaking RSA keys is the factorization of RSA-768 in 2010: http://eprint.iacr.org/2010/006.pdf That paper says it took about 1500 CPU-years to break a 768-bit key, and that the difficulty increases 1000x for each additional 256 bits of key length.
For a back-of-the-envelope cost estimate, I'm going to assume that there have been no major theoretical breakthroughs in the last couple of years, and that the machines they used were roughly equivalent to an EC2 "medium" instance. That puts the cost of breaking a 768-bit key, using spot instances for cost-efficiency, at about US$200k.
That sounds small, but encryption/decryption are still reasonably efficient with larger keys, while factorization becomes vastly harder. Breaking a 2048-bit key would take something like 200 quadrillion dollars worth of CPU time. A 4096-bit key, like the one used for this message, would be vastly more secure than that.
At the moment, the NSA still permits use of 2048-bit RSA for classified information up to SECRET. It would be highly questionable for them to do so if they knew of easily exploitable weaknesses, as they're taking the chance that other governments won't find them.
Remember, the NSA's mandate is twofold: They are a signals intelligence agency, but they are also charged with protecting government communications, much of which occur with commercially-available cryptography.
RSA does make people nervous for some valid reasons, and that's why there's a gradual transition to ECC underway, but there's little reason to expect a practical attack on RSA at 2048+ bits in the near term.
Absent an operational error on the part of Wired or Snowden, I seriously doubt the NSA will be decrypting that message in Snowden's lifetime, and almost certainly not before changes in the political climate.
Uh, the existence of a buffer overflow (which doesn't even cause disclosure of an encrypted message) has nothing to do with the strength of the RSA algorithm, which is what the comment I replied to was talking about.
I remember 768 bit asymetric keys in the mid 90's, and the paranoid had perhaps a 1024 bit key (I'm not very paranoid, and I got a 2048 bit key before 2000). A 768 bit RSA key was factored in 2009; the NSA could probably do it earlier. The default now is 2048 bits, and the key used by Wired is 4096 bits.
That's a lot of doublings of the difficulty to brute force a key. 2^3328 increase in difficulty.
RSA factoring does not increase with keysize increases like you might expect. Factoring, while still very hard, is much better than brute-force and continues to see improvements.
