NSA's statement wasn't "we've got an RSA-breaking machine" or anything like that; the highlights are 0) folks are using RSA-1024, which public sources only ascribe 80 bits' worth of security to, smaller than the usual margin; 1) RSA gets slow with long keys: according to public sources, 256-bit security requires RSA-3072, which is 64x slower than the equivalent ECC-512; 2) RSA-breaking implementations keep getting gradually better over time, whereas ECC's effort-to-break has basically stood still.
Their own ("Suite B") guidelines for use of public algorithms to protect classified data tell the US government to use ECC, not RSA. (AES-256 is fine, though.) They licensed patents for particular implementation techniques:
http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography
Bruce Schneier, reacting to Bamford's statement about a cryptographic breakthrough, said: "Another option is that the NSA has built dedicated hardware capable of factoring 1024-bit numbers. There's quite a lot of RSA-1024 out there, so that would be a fruitful project. So, maybe."
(There's a lot of RSA-1024 out there partly because old 1024-bit SSL certs die hard, and people are lazy about switching to bigger keys if, for example, it would make establishing SSL sessions more expensive.)
Finally, perhaps not related to public-key crypto but really interesting, the XKeyScore deck had the bullet point "Show me all the VPN startups in country X, and give me the data so I can decrypt and discover the users" as one of the things you can tell the system to do. That could just refer to one of those protocols that everyone knows is broken but is still in use (MS-CHAP/PPTP) or to either a protocol/implementation break or something else affecting VPNs we currently think are secure.
Maybe the best argument against a crypto breakthrough is that it's clearly extremely hard (none of the brilliant mathematicians working in the open are close) whereas attacks on implementations and protocols are relatively easy. If you have a big bag of 0-days, have stolen some certificates (as Stuxnet seemed to indicate), and are inside a bunch of service providers, it seems almost redundant to put a lot of effort into factoring big numbers, unless some big technical improvement basically falls in your lap.
The Snowden comment about VPN startups has intrigued me for a while. My theory is that the NSA have filter boxes placed at the exit points of these VPNs. They sit and wait to see what pops out (at the VPN unencrypted endpoint) and then vacuum it all up. Most VPN endpoints are at major networking points. I.e London, New York, Frankfurt, etc.
It is then a simple matter of waiting for a user to leak personable identifiable information. A visit to Facebook or an email account, etc whilst connected to the VPN is all it takes, and then you can group and map browser headers (roughly) to VPN users.
Maybe they can break small key length SSL when they really need to. If there is TLS traffic of interest popping out from the VPN exit, then they store it and process it later, probably in some massive AWS compute intensive cloud service even.
VPN users have to remember that their traffic is protected from your machine as far as the VPN exit node. After that exit point onwards to the requested web server, you are as naked as before. Worse is that it lulls users into a false sense of security.
Not that NSA probably has the resources to do, and are probably doing all of it at the same time. Having smart thinkers spending time trying to come up with analytical solutions isn't that costly in comparison to a lot of other venues of attacks.
Comments
Breaking RSA keys up to 1024 bits is one less-outlandish-than-some possibility.
NSA published a note advocating use of ECC in 2009: http://www.nsa.gov/business/programs/elliptic_curve.shtml
NSA's statement wasn't "we've got an RSA-breaking machine" or anything like that; the highlights are 0) folks are using RSA-1024, which public sources only ascribe 80 bits' worth of security to, smaller than the usual margin; 1) RSA gets slow with long keys: according to public sources, 256-bit security requires RSA-3072, which is 64x slower than the equivalent ECC-512; 2) RSA-breaking implementations keep getting gradually better over time, whereas ECC's effort-to-break has basically stood still.
Their own ("Suite B") guidelines for use of public algorithms to protect classified data tell the US government to use ECC, not RSA. (AES-256 is fine, though.) They licensed patents for particular implementation techniques: http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography
Bruce Schneier, reacting to Bamford's statement about a cryptographic breakthrough, said: "Another option is that the NSA has built dedicated hardware capable of factoring 1024-bit numbers. There's quite a lot of RSA-1024 out there, so that would be a fruitful project. So, maybe."
(There's a lot of RSA-1024 out there partly because old 1024-bit SSL certs die hard, and people are lazy about switching to bigger keys if, for example, it would make establishing SSL sessions more expensive.)
Finally, perhaps not related to public-key crypto but really interesting, the XKeyScore deck had the bullet point "Show me all the VPN startups in country X, and give me the data so I can decrypt and discover the users" as one of the things you can tell the system to do. That could just refer to one of those protocols that everyone knows is broken but is still in use (MS-CHAP/PPTP) or to either a protocol/implementation break or something else affecting VPNs we currently think are secure.
Maybe the best argument against a crypto breakthrough is that it's clearly extremely hard (none of the brilliant mathematicians working in the open are close) whereas attacks on implementations and protocols are relatively easy. If you have a big bag of 0-days, have stolen some certificates (as Stuxnet seemed to indicate), and are inside a bunch of service providers, it seems almost redundant to put a lot of effort into factoring big numbers, unless some big technical improvement basically falls in your lap.
The Snowden comment about VPN startups has intrigued me for a while. My theory is that the NSA have filter boxes placed at the exit points of these VPNs. They sit and wait to see what pops out (at the VPN unencrypted endpoint) and then vacuum it all up. Most VPN endpoints are at major networking points. I.e London, New York, Frankfurt, etc.
It is then a simple matter of waiting for a user to leak personable identifiable information. A visit to Facebook or an email account, etc whilst connected to the VPN is all it takes, and then you can group and map browser headers (roughly) to VPN users.
Maybe they can break small key length SSL when they really need to. If there is TLS traffic of interest popping out from the VPN exit, then they store it and process it later, probably in some massive AWS compute intensive cloud service even.
VPN users have to remember that their traffic is protected from your machine as far as the VPN exit node. After that exit point onwards to the requested web server, you are as naked as before. Worse is that it lulls users into a false sense of security.
Not that NSA probably has the resources to do, and are probably doing all of it at the same time. Having smart thinkers spending time trying to come up with analytical solutions isn't that costly in comparison to a lot of other venues of attacks.