3 ms·
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 http://eprint.iacr.o
by teraflop 13y ago
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 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.
- donrhummy 13y agoAssuming there's no known exploit. The NSA might know of an exploit for that algorithm.
- chinpokomon 13y agoMaybe the message is another encrypted message with a different algorithm?
- nknighthb 13y agoAt 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.
- doublepop 13y agoThat's not the only form of "exploit" http://www.scip.ch/en/?vuldb.2721 http://www.scip.ch/en/?vuldb.2721
- nknighthb 13y agoUh, 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.
- doublepop 13y agoYou're missing the more obvious form of attack http://lists.gnupg.org/pipermail/gnupg-announce/2006q4/000246.html http://lists.gnupg.org/pipermail/gnupg-announce/2006q4/00024...