Follow Slashdot stories on Twitter


Forgot your password?

How Is the NSA Breaking So Much Crypto? ( 217

schwit1 writes: There have been rumors for years that the NSA can decrypt a significant fraction of encrypted Internet traffic. In 2012, James Bamford published an article quoting anonymous former NSA officials stating that the agency had achieved a "computing breakthrough" that gave them "the ability to crack current public encryption." The Snowden documents also hint at some extraordinary capabilities: they show that NSA has built extensive infrastructure to intercept and decrypt VPN traffic and suggest that the agency can decrypt at least some HTTPS and SSH connections on demand.

However, the documents do not explain how these breakthroughs work, and speculation about possible backdoors or broken algorithms has been rampant in the technical community. Yesterday at ACM CCS, one of the leading security research venues, we and twelve coauthors presented a paper that we think solves this technical mystery.

If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. There seemed to be no reason why everyone couldn't just use the same prime, and, in fact, many applications tend to use standardized or hard-coded primes. But there was a very important detail that got lost in translation between the mathematicians and the practitioners: an adversary can perform a single enormous computation to "crack" a particular prime, then easily break any individual connection that uses that prime.

This discussion has been archived. No new comments can be posted.

How Is the NSA Breaking So Much Crypto?

Comments Filter:
  • by turkeydance ( 1266624 ) on Thursday October 15, 2015 @04:22PM (#50738551)
    and all that....
  • by TechyImmigrant ( 175943 ) on Thursday October 15, 2015 @04:23PM (#50738565) Homepage Journal

    We've long past the point where we knew RSA, simple Diffie Hellman, Sha-1 and NIST curves need to go in the bin. This is one more nail in the coffin.
    The standards I'm working in have gone Ed25519, Curve25519 ECDH, Shake128, AES, etc. 128 bits, sane curves, modern hashes. Rearranging the TLS deck chairs won't help.

    • by jonwil ( 467024 ) on Thursday October 15, 2015 @05:50PM (#50739249)

      If you use 2048 bit or 4096 bit RSA and you dont make mistakes in generating the key, RSA is still perfectly fine to use short of a quantum attack (even if the NSA had a classified supercomputer that was more powerful than all the supercomputers on the top 100 list combined filled with custom RSA-cracking ASICs they still can't crack high-strength RSA using any known mathematical formula)

      I do agree that TLS needs replacing with a new protocol that only supports the strongest encryption (that means 256 bit AES, at least 2048 bit RSA, ECDH with perfect forward secrecy and SHA2/SHA3 for hashing) and has no mechanism to downgrade to any older protocols or to weaker encryption like MD5, SHA1, RC4 etc.

      • by Burdell ( 228580 ) on Thursday October 15, 2015 @06:17PM (#50739481)

        There's no need for a new protocol; TLS allows you to configure servers and clients to restrict the available ciphers. That's why the browser vendors have been able to push out MD5 (and moving on SHA-1), RC4, RSA 2048 bit, etc. No protocol changes were necessary; just remove ciphers from the supported list used to negotiate the connection.

        BTW: research indicates that AES256 may in fact be slightly weaker than AES128, in some use cases. Both are still have no practical attacks, even for nation-state level attacks; at this time, there is no evidence that AES256 would be "more secure" in practical terms (i.e. billions of years to break one encrypted message) than AES128. Given that, there is no reason to replace AES128 with AES256, now or in the foreseeable future. Odds are that if some attack vector against AES is found, it will be time to move to a new algorithm, not just more bits/rounds.

        • by Bengie ( 1121981 )
          There is a related key attack that doesn't affect AES128 but reduces AES192 to 2^176 ops and AES256 to 2^119 ops. It does require that the key you're trying to attack does not change during the duration of the attack and requires you to have a way to influence the generation of new keys in known ways. By sending in data to the remote server and having it encrypt the data, you can see how the data changes.

          A practical attack like trying to attack a web sever's session key would require that you generate at
    • Same problem remains. If you keep using the same initial paramter (large prime, elliptic curve, etc) then once that is cracked you have very easy access to what is derived from that parameter. The keys/secrets/whatever still need to be refreshed periodically. Ie, the hardcoded public key may be quite secure for awhile, but over several years it loses security. If the NSA really wants to break your system then they just need to break that one public key, maybe they put their best computers on it for a co

    • by gweihir ( 88907 )

      SHA1 does not need to go into the bin for all applications. For password-hashing it is still fine, if iterated and salted appropriately. Please stop spreading FUD.

      • Can you offer a reason to prefer it over a better algorithm with better properties that takes less compute power and has been subject to a rigorous standardization process? E.G. Shake128. I can't.

        There are existing deployments by the millions. But wherever there is a choice for new deployments, going with the old thing is the behavior that has led us to where we are today with TLS.

    • This is all pretty academic as the Quantum Computer Juggernaut [] is almost here.
  • Influence the outcome.
  • by Panaflex ( 13191 ) <convivialdingo AT yahoo DOT com> on Thursday October 15, 2015 @04:31PM (#50738649)

    When the NSA leaks happened, investigates this and promoted this as a possible attack vector.

    NOTE - You can generate a new set of moduli like so:

    # ssh-keygen -G moduli-2048.candidates -b 2048
    # ssh-keygen -T moduli-2048 -f moduli-2048.candidates

    Put the results in /etc/ssh/moduli

    WARNING: This takes forever. Also, according to man ssh-keygen:

    It is important that this file contains moduli of a range of bit lengths and that both ends of a connection share common moduli.

    It's not possible to regenerate and share many moduli quickly - hence the reuse of moduli. SSH has support for x25519 algorithms - this definitely means I'll be moving away from pre-computed DH moduli also.

  • by JoshuaZ ( 1134087 ) on Thursday October 15, 2015 @04:33PM (#50738659) Homepage
    Scott Aaronson has an excellent summary of this research on his blog: [] One point that Scott makes that is easy to lose track of is how much working this out required people on both the theoretical crypto end and the practical crypto end to work together. This is a combination of multiple vulnerabilities and some clever number theory.
  • by geekmux ( 1040042 ) on Thursday October 15, 2015 @04:33PM (#50738671)

    "...many applications tend to use standardized or hard-coded primes."

    If the suggested theory of static primes holds true, during application design, what part of of the definition of random did we not quite understand?

    Given the impact, this stands as the golden example of what not to do Ever again.

    • An issue is that random typically doesn't mean what it's taken to mean in plain language. True randomness is actually hard since you've got to have some mechanism chugging away spitting out numbers. Understanding how (pseudo) random is defined goes a long way to reducing the reducing the size of the haystack in your search for the needle.

  • Maybe they're not (Score:5, Insightful)

    by wonkey_monkey ( 2592601 ) on Thursday October 15, 2015 @04:34PM (#50738685) Homepage

    How Is the NSA Breaking So Much Crypto?

    Maybe they're not. They're hardly going to tell you what they can't crack.

    • Another site's take was if they couldn't crack it they'd be in line with the FBI for back doors in software.

      That they aren't nearly as vocal can be construed to mean it doesn't matter to them since they don't need the back doors.
      • by Bogtha ( 906264 )

        Another site's take was if they couldn't crack it they'd be in line with the FBI for back doors in software.

        In that case, the NSA don't ned to crack the crypto, they just need to crack the FBI.

        • by rtb61 ( 674572 )

          Crack the FBI, it seems pretty much like both the NSA and CIA have shattered the FBI with purposefully planted agents as well as recruited FBI agents. If anyone needs to crack crypto it is the FBI and they need to crack both the CIA and NSA otherwise democracy in the US is likely to collapse under the corruptive weight of extortion schemes ("we will let you continue to commit crimes as long as you do these things for us").

  • by sstamps ( 39313 ) on Thursday October 15, 2015 @04:35PM (#50738691) Homepage

    So, in short, they're not breaking crypto, they are breaking shitty implementations of crypto.

    So basically, like using a one-time pad multiple times.

    Well, I guess it's time to start sorting the wheat from the chaff and start ditching fixed-prime implementations wholesale.

    • What they are really saying is that rubber-on-the-road crypto (see, a car analogy) is very hard. So you're likely to be doing it wrong, whatever it is that you're doing.

    • So, in short, they're not breaking crypto, they are breaking shitty implementations of crypto.

      No. They are estimating the cost of breaking standardized crypto and pointing out that it is within reach of state agencies.
      There are standards that don't suffer these problems and other problems and yet still use pre-defined static primes.

    • It's very difficult to actually implement crypto unless you are a highly capable mathematician with a specialism in number theory. That's why the sensible thing is always to use libraries that have been vetted by people who know what they are doing.

  • by grahamsz ( 150076 ) on Thursday October 15, 2015 @04:35PM (#50738693) Homepage Journal

    While there are a few alternatives to RSA (though they share some mathematical similarity) i'm not aware of any non-quantum replacement for DH. That obviously makes it a natural candidate for any kind of focussed attack.

    I honestly had no idea that most implementations fixed p. It seems obvious in retrospect that this could lead to the creation of a giant LUT

    • by delt0r ( 999393 )
      The reason people did this was to make checking easier. If i use a big prime and then a subgroup (typical for DH) that is randomly generated. I must check everything to make sure that everything matches the required mathematical properties. For example i can use a random curve for EC, but first i must check it is not one of the known weak curves. Then i need to calculate the order of the curve, which can be fairly slow. Hence agree before hand on a fixed curve.
  • by Lennie ( 16154 ) on Thursday October 15, 2015 @04:42PM (#50738755)

    This is the original logjam attack from May this year.

    Even the PDF points to the same site: []

  • All of your chips and transmission devices also have direct backdoors.

    Yes, all of them.

  • The NSA isn't "breaking crypto".

    It was pre-broke for them.

  • This will separate the wheat from chaff. People who know security and take it seriously will make sure they spend the resources to find a couple of large primes and base their keys on them. The equivalent of script kiddies who just download some binaries with security hashing algorithms who use it without understanding them will get cracked. Not just by NSA. Anyone with a budget and determination will. All the governments.
    • by skids ( 119237 )

      Well, for the more-BYOD-than-BYOD sector, what will happen is we'll install a new VPN that is not quite as crusty as our old one which always "just worked" and so never got budgeted for an upgrade, configure it for best practices security, and then weaken it when 10% the must-have clients turn out to be too crummy to deal and don't support installation of a 3rd party client, even if we could get front-row to shoulder the support burden involved in doing that (or doing an on-site CA and dealing with cert ins

  • Anybody else seeing the headline as:

    How Is the NSA Breaking So Much


  • They can MITM anyone they want and they almost certainly have the ability to mint any certificate they wish....

    • That's great for targeted interception, but you can't use it for large-scale surveillance. Try that and it won't be long before someone notices the suspicious mismatch of certificate hashes.

  • I read about how DH works years ago and this was the first thing that came to mind. It's there. Just go read.
  • I'm certain you've got codebreakers breaking codes. If you're able to do this, and you'd like to establish a shred of good will, would you kindly package it into simple-to-use applications that will allow users to decrypt files held ransom by Cryptowall? You'd be strengthening your image while simultaneously hurting the economy of the sketchy side of the internet.

    Warm regards,

    • The sketchy side of the internet (in part) supplies them with the tools of their trade. Given all the other sh*t these agencies have been up to, I wouldn't be surprised to find out they were in charge of some ransomware so that they could fund other extra-curricular activities (via suitable layers of third parties, of course).

  • by IWantMoreSpamPlease ( 571972 ) on Thursday October 15, 2015 @06:26PM (#50739541) Homepage Journal

    Say you can crack it, even if you can't. Security researchers around the world will try to figure out how you did it, and in the end, show you what to do.

    Sort of like Reagan-era Star Wars. Drove the Russians crazy (and broke) trying to replicate non-existent technology because they took our word for it, that we had done it.

  • The ability to create, shape, sell, and attack weak international crypto would be the easy key to decades of "the ability to crack current public encryption".
    A "computing breakthrough" could just be in cheap storage, fast sorting that allows a collect it all ability after getting plain text.
    Nothing much has really changed from the ideas of the 1950's. Set weak junk encryption, get the majority of users accepting a weak standard and then collect it all.
    It worked for diplomatic hardware in the 1950-90's. J
  • The journal article cited addresses Diffie-Hellman (DH) certificates with 1024 bits. For browsers, such certificates are being deprecated. Certification authorities are not supposed to issue intermediate certificates or sign subscriber certificates that have less than 2048 bits, and Mozilla reserves the right to require even larger certificates.

    Furthermore, the OpenPGP format allows even larger DH parts of the DH/DSS encryption keys. My own DH/DSS key is 4096/1024. The 4096 is the size of the DH part.

  • by RubberDogBone ( 851604 ) on Thursday October 15, 2015 @07:02PM (#50739765)

    In the hacking/spy drama movie Sneakers, there is a scene where Robert Redford's character is confronted with an office door protected by a keypad lock, which cannot be picked. But he needs to get into that office. The lock looks impenetrable. Surely the mission is about to fail.

    So he asks his support team for help with the lock. What they tell him is never shown on screen, only Redford mumbling and agreeing to try it.

    He takes a couple steps back and KICKS IN THE DOOR. The lock was completely irrelevant, in the end.

    The lesson from that scene is extremely powerful when you understand the same lesson applies to ANY problem. When you are faced with a heavily secured door, or an encryption standard, the attack vector is often going to be something other than going through the face of the door or the front end of the encryption. What you'd do is KICK IN THE DOOR. And the TLAs know this and do exactly that. Their people have always kicked in doors while normal people look at the locks and shrug and walk away.

    • Don't forget they use social engineering in Sneakers as well, involving Mary McDonnell's character to get past the voiceprint lock of character actor Stephen Tobolosky's character Werner Brandes

      "My name is Werner Brandes, my voice is my passport."

      Prescient film, underrated in my opinion.

    • by MrKaos ( 858439 )

      Their people have always kicked in doors while normal people look at the locks and shrug and walk away.

      Lock are only there to remind honest people that they aren't supposed to be in there.

    • by bentcd ( 690786 )

      The lesson from that scene is extremely powerful when you understand the same lesson applies to ANY problem. When you are faced with a heavily secured door, or an encryption standard, the attack vector is often going to be something other than going through the face of the door or the front end of the encryption. What you'd do is KICK IN THE DOOR. And the TLAs know this and do exactly that. Their people have always kicked in doors while normal people look at the locks and shrug and walk away.

      In this case the lock has performed its function: it prevented Redford from effecting a clandestine break-in. It is now obvious to the office owner when he returns that he has been burgled and he can take steps to minimize the damage that will result from it.

      In the security business it is accepted that ultimately you cannot prevent a determined attacker from gaining access to a physical location. The best you can do is 1) delay him and 2) force him to leave evidence that he was there.

    • Shit, somebody beat me to this movie reference, and then I went and posted it further downthread like an idiot.

      Welp, it was nice knowing you guys, I guess :(
  • It seems more like overt surveillance now.

  • Wasn't this the plot of Sneakers?

Our business in life is not to succeed but to continue to fail in high spirits. -- Robert Louis Stevenson