No Really, the NSA Can’t Brute Force Your Crypto

National Security ServerI’ve talked to many people who assume that the NSA, the world’s most powerful and well-funded spy agency, can easily crack the encryption on messages they intercept by brute force. They speculate: “What if Big Brother has a massive cluster of supercomputers guessing keys at full power in a top secret and shadowy lab a mile beneath Maryland?” Even then, they still can’t crack your crypto.

Don’t get me wrong. There are many implementation flaws, bugs, misconfigurations, user errors, and rubber hose attacks that could lead to crypto being compromised. I’m referring to the NSA’s ability to use massive computing power to guess a crypto key.

The length of keys is measured in bits. So a 128 bit key is a random string of 128 ones and zeros. Something like this:

10001010011011011100010010011100000110000101010000111010110101100001000000000110100010110111001001010000111001011111101111011100

That same number in decimal instead of binary is 184,003,411,495,303,822,475,448,869,063,584,250,844. Here’s another example:

11011010110111010101100000100110010000101111111111101100111011101101100011110111000111100010001100110100100101001001111011100010

In decimal, that number is 290,920,988,570,298,559,704,636,864,265,180,192,482.

As you can see, randomly generated 128 bit keys are really big numbers. The total number of possible keys is 2 to the power of 128 (which I’ll write as 2^128), or 340,282,366,920,938,463,463,374,607,431,768,211,456.

Here’s a scenario. Let’s pretend NSA has intercepted a message encrypted with a 128 bit key and they really want to crack it. Keep in mind: your phone easily encrypts messages with 128 bit keys in a couple milliseconds. This sort of crypto is nothing special, and your computers do crypto operations like this each time you use a web browser.

To do this, NSA needs to build a cluster of parallel processors trying to decrypt the message with different keys until they get it right. They’ll guess that the key is 0, then 1, then 2, then 3, then 4, then 5, and so on. By the time they get to 2^128, they will have completed an exhaustive search of the keyspace and definitely will have cracked it.

Now let’s pretend the NSA has a budget of $100 trillion (in reality, they don’t have nearly that much money). Let’s also say that they can buy $50 computers that can test 100,000 keys a second (try making your Raspberry Pi do that, I dare you). Spending the entire $100 trillion at $50 a pop, they can afford two trillion computers. At 100,000 guesses per second, the entire cluster of two trillion computers can make 200,000,000,000,000,000 guesses per second.

So how many seconds will it take to guess all 2^128 possible keys?

1,701,411,834,604,692,317,316 seconds.
Which is 28,356,863,910,078,205,288 minutes.
Which is 472,614,398,501,303,421 hours.
Which is 19,692,266,604,220,975 days.
Which is 53,951,415,354,030 years.
Which is 53,951,415,354 millennia.

Since the key could be any number between 0 and 2^128, chances are the key will be found in half that time. So 27 billion millennia then?

That’s a long time to wait to crack the crypto on a single message. And I greatly exaggerated the resources of the NSA. In reality, they’d be waiting a lot longer. Another way to put it is this: If all the combined computing power currently available to the human race were devoted to decrypting this one single message, the sun would die out before it was cracked.

In Cypherpunks: Freedom and the Future of the Internet, Assange, Appelbaum, Muller-Maguhn and Zimmermann refer to crypto’s unbreakability as a physical law of the universe. Pretty cool stuff.

So no, really, the NSA can’t break your crypto.

I’d like to thank Stanford crypto professor Dan Boneh and his excellent (and free) Coursera class, Introduction to Cryptography. A homework assignment included a similar math problem, and it blew my mind. I recommend you take his class.

Thanks, XKCD

Thanks, XKCD

25 thoughts on “No Really, the NSA Can’t Brute Force Your Crypto

    1. micah Post author

      :). Of course they would.

      But the point is that the math is powerful. Encryption software isn’t perfect, but if were it would be uncrackable. That’s pretty cool. It means that people with little resources have a fighting chance against the surveillance state.

      Reply
  1. Sure

    That works if your key is s76f%^56d7agsjdhast65%$687673tgjhasd
    But not if it’s made up of dictionary/numbers/punctuation.

    These are all currently crackable:
    Larry26_pw
    banana99
    123@Leopards!Cool!

    etc…

    So, chances are most real-world passwords are indeed crackable – not hypothetically – but truly currently crackable.

    Reply
    1. micah Post author

      Those are passwords, not keys. The actual encryption key is (in the example in this blog post) is a string of 128 random bits. In practice it’s common for us to symmetrically encrypt a crypto key with a passphrase, e.g. GPG encryption. But in order t o break that the attacker needs a copy of your encrypted secret key.

      Let’s say the attacker only has a copy of an email that you received that someone encrypted with your public key, but doesn’t have a copy of your passphrase-protected secret key. Trying to decrypt that email doesn’t have anything to do with passwords or passphrases. It has to do with finding the most efficient way to guess the actual string of bits that’s protecting the email, and that’s what I believe they can’t do.

      However that doesn’t mean you can just use GPG and everything is safe. Your computer can get hacked, they can access your secret key and brute-force the passphrase, they can confuse and get you to send encrypted messages to the wrong public key, they can rubber hose attack you for the info they want, or they can not care about the content when it’s encrypted and gather everything they want from the metadata.

      But the whole point of this is that there are some math problems that, until there’s some breakthrough in mathematics, make it so crypto (done correctly) actually works.

      Reply
  2. TK-999

    And yet, I saw a cryptography expert claim this very thing in an article on an online news site in my country. Thanks for clearing up the confusion, it seems to be a common misconception.

    Reply
  3. e-sushi™

    Let’s wrap this up:

    1. You are assuming that the cryptographic algorithms which are “promoted” by the NSA are safe,
    2. You are assuming there is no “backdoor” key build into those algorithms, and
    3. You are assuming mathematical problems used in such algorithms have not been broken or partially broken.

    That’s a lot of assumptions and only “if” all those assumptions are all true, you could start to be a bit confident that you and your article are correct.

    Let me give you something to think about: speaking in the terms of Kerckhoffs’ principles, you are trusting “the enemy” to provide you with a safe algorithm which “the enemy” can not reverse-engineer, hack, break, or otherwise decrypt. That’s a courageous bet when you’re talking about cryptographic security.

    Reply
    1. smeghead

      PGP the most common encryption used for email and other messaging is not endorsed d by the NSA. In fact the NSA tried to stop its distribution in the 90s when it was first published, until the supreme court intervened saying they were protected by their 1st amendment right to free speech and allowed to distribute their program/algorithms.

      Reply
    2. jack

      1. I would seriously doubt that if there were inherent issues in encryption algorithms that academia would not find them also.

      2. After the Edward Snowden leaks, how much do we really know? How much of this information is just interpreted dramatically by news agencies trying to make a big buck?

      3. There’s design, and then there’s implementation. There are open source implementations of encryption algorithms that academia and anybody has access to study and pull apart. If the NSA creates an implementation of a design, technically no one is forced to use it.

      The NSA is doing some pretty disturbing things. Let’s hope academia and normal citizens can keep them penned in.

      Reply
    3. TheSecondaryThing

      I figured the author was talking about encryption created by us. The reason why I found this article is because I just programmed one in between the time I started and finished reading it. The great thing about encryption is that it’s so damn easy to institute, but a bitch to break.

      Reply
  4. Xezlec

    Bet you feel dumb now, eh? Lord knows I do.

    Turns out the NSA baked in “exploitable” algorithms, so the crypto methods we thought were secure (I’m betting this includes ssh and all the other major critical pieces) actually never were. They’ve always been able to see and control everything. We’re living in exactly the kind of state I never believed was even possible in the real world until today’s headline.

    The idea that they would actively weaken the security of Americans in order to more easily control us was so unthinkable to me that now I’m forced to admit that things like our votes very likely aren’t as real and legitimate as I’d always assumed they were either. Now I’m wondering who really runs the country…

    Reply
    1. Aaron Toponce

      Quantum computing is still light years away. Sure, the NSA might be spending billions to build a quantum computer, but what they’ll end up with is something exceptionally limited, difficult to maintain, and in all reality, not very useful for general cryptography.

      Reply
  5. Kenichi Mori

    āāāĀĀĀèèèÈÈÈÉÉÉéééȄȄȄȅȅȅȇȇȇȆȆȆĒĒĒēēēìììÌÌÌÍÍÍíííȉȉȉȈȈȈȊȊȊȋȋȋīīīĪĪĪĪÒÒÒòòòóóóÓÓÓȌȌȌȍȍȍȏȏȏȎȎȎŌŌŌōōōùùùÙÙÙÚÚÚ
    ÀÀÀáááÁÁÁȀȀȀȁȁȁȂȂȂȃȃȃāāāĀĀĀÈÈÈèèèéééÉÉÉȄȄȄȅȅȅȇȇȇȆȆȆĒĒĒēēēÌÌÌìììÍÍÍíííȈȈȈȉȉȉȊȊȊȋȋȋĪĪĪīīīÒÒÒòòòÓÓÓóóóȌȌȌȍȍȍȏȏȏ
    ŔŔŔȐȐȐȒȒȒȓȓȓȑȑȑŕŕŕčččČČČŽŽŽžžžšššŠŠŠĐĐĐđđđĆĆĆćććÌÌÌìììíííÍÍÍȈȈȈȉȉȉȋȋȋȊȊȊĪĪĪīīīĒĒĒēēēȇȇȇȆȆȆȄȄȄȅȅȅéééÉÉÉÈÈÈĀĀĀāāā
    ÒÒÒòòòÓÓÓóóóȌȌȌȍȍȍŌŌŌōōōÙÙÙùùùÚÚÚúúúȗȗȗȖȖȖŪŪŪūūūòòòÒÒÒĪĪĪīīīȋȋȋȊȊȊȈȈȈȉȉȉíííÍÍÍÌÌÌìììēēēĒĒĒȆȆȆȇȇȇȅȅȅÉÉÉÈÈÈ
    ŔŔŔȐȐȐȒȒȒȓȓȓȑȑȑŕŕŕčččČČČĆĆĆćććĐĐĐđđ𩩩šššŽŽŽ
    Zereata Fonoizo Returneoro Cryptonsoneo neo neo Sundero neo shooter neo ereerollingos ereo ereo retrunreo reo eo oO.,
    Kenichi Mori UGM/S/OpenWall.,Inc/openwall.com/Irish Army Connector /1996/12/01/ take start openwall ., project.,
    Every Open Wall firewall dance fever.,

    Reply
  6. Aaron Toponce

    When I teach entropy as it relates to crypto, such as cracking passwords on 128-bit keys, I usually show my students http://stats.distributed.net.

    One if the projects is finding the 72-bit RSA key that decrypts an encrypted message. The overall rate is greater than 400 billion keys per second. Currently, the project has searched through only 3% of the keyspace, and it’s taken over ten years to get that far.

    Now, they could find the key tomorrow. You don’t know. That’s the thing with entropy. Each key is equally as likely. But with a keyspace that large, it could also be one hundred years before the key is found.

    Reply
    1. Scott Suhr

      How do you know when you have “found” the key? ? ?
      I presume there is an algorithm that “recognizes” English text. . .
      If you perform even a minor substitution algorithm on the text before you encrypt with PGP, doesn’t that foil the entire brute-force effort?

      Reply
  7. Stuart

    How do you know that the NSA hasn’t compromised the hardware or software that is used to generate the random 128 bits in the first place? When I make up my passphrase and use it to generate my public/private key pair, what happens internally to transform my passphrase to those keys? Some random number generation goes on in there? Except there is no such thing as a truly random number. Computers use or make up a seed value to help them generate a random number. So, the “random number” is really generated via an algorithm. Where does the seed come from? It’s not, itself, truly random, right? Is it derived from the software reading values from your PC hardware? Hardware that may, itself, be compromised in some way?

    So, how do you know that the ways this task (of, ultimately, creating a public/private key pair) is accomplished aren’t compromised in some way that may not allow the NSA to calculate the exact private key, but may allow them to narrow down or focus their attack so much that brute forcing the private key becomes quite feasible?

    Reply
    1. Adamantish

      It’s years later but I thought it worth responding to this well reasoned fear. The seed data GPG uses comes from linux `/dev/random` which collects data from keyboard, mouse inputs and device activity. http://stackoverflow.com/questions/5635277/is-dev-random-considered-truly-random
      It won’t actually return values until it’s satisfied enough “random” things have happened. As the linked Q&A says there are still some biases in its output – clearly humans and exhibit some broadly predictable patterns – but this is much too broad to practically narrow down the search space much. i.e. I can predict that there’s a 1% chance you might type a particular word but could I guess that the first letter would be at exactly at microsecond number 8337593 and the second one at 9129483 and so on?

      If the NSA were to somehow hide pieces of malice in linux they probably wouldn’t do it here, rather they’d choose to promote an encryption methods for which they had discovered systemic flaws.

      In fact, we know their methods are not so much to rely on testing the limits of theoretical possibility but instead to
      – use legislation to try banning good encryption such as PGP.
      – use certain cultural and organisational channels to promote practice which they know (or many people know) to be insecure e.g. HTTPS

      PGP looks to be holding out: http://www.theverge.com/2014/12/28/7458159/encryption-standards-the-nsa-cant-crack-pgp-tor-otr-snowden

      Reply
      1. Adamantish

        I take it all back. Just found this and realised how I had forgotten Linus really is the dictator of Linux.
        https://news.ycombinator.com/item?id=6336505

        I was going to joke ‘hey perhaps Linus Torvalds really works for the NSA” but really it’s not so far fetched.
        A lot of ideas are far fetched e.g. the weird guy in the office is a Government spy.
        But this would not be a surprising headline: “US Government makes secret deal with the one of the most powerful people in the world” Some points which make him amongst the most powerful people in internet security.

        1) He has autocratic power over many Linux distributions.
        2) Linux runs the great majority of the internet’s servers.
        3) Unlike a CEO in charge of CPUs there isn’t a chain of command to get down to the engineers doing the deed.

        So he’s a very high value target for them. What might put him in the sweet spot of also being an easy target?

        1) Unlike a politician he is under little journalistic scrutiny.
        2) Unlike a business leader he has no worries about board oversight, customers or many powerful stakeholders.
        3) By his own admission he is motivated by a love of programming and selfish desires, not an ideology like open source or privacy: http://www.ted.com/talks/linus_torvalds_the_mind_behind_linux#t-731551
        4) His reputation for rudeness and ‘Linus just being Linus’ serve as a good pretext for his regular overruling of other contributors. Helps deflect suspicion.
        5) If saying no to the Government is illegal and dangerous, whereas saying yes is law-abiding and carries benefits (like maybe American citizenship) you’d need a strong moral fear about the effect on your country to resist. America isn’t his only country so he might perhaps feel a bit more distant from its troubles.

        Although his autocratic technical actions are out in the open for skilled reviewers to see we can see just how big a wave their biggest protests produce. Just look back up at that obscure hackernews thread.

        Reply
  8. Stuart

    For that matter, how do you know that the low level Windows or Linux APIs that are being used to calculate a seed or use the seed to generate a random number aren’t themselves compromised to make it easy for the NSA to reduce the number of possible private keys to a crackable number.

    If you say “well, Linux is open source, so we would see the evidence of that compromise” I would say “okay, maybe. Or maybe not. Especially if the experts you rely on for review are actually NSA conscripts.” But, even if it’s just Windows that is compromised, that still means there would be a LOT of not-so-private private keys.

    Reply
  9. Michah

    See, you forgot that they can tap into the schools in the US they partner with, plus they have huge data centers and ones they lease from other companies (sorry can’t list names). So that 27 millenia, yeah, it can be done in a few days or weeks depending the length of the password and complexity of the required hack.

    Reply
  10. Cyril

    It’s funny because the article is talking about about brute force attack which is the most stupid attack you can do. So yes the logic is correct but that’s not the only way to decrypt a message, you have breach in some algorithms, same of them use random numbers which is impossible with a computer (all are part if series that repeat), etc… To sum the article is correct just considering brute force attack but nsa is working on workaround to find jeys without using it!

    Reply
  11. Pingback: » Why You Should Learn to Use Encryption

Leave a Reply

Your email address will not be published. Required fields are marked *