No Really, the NSA Can’t Brute Force Your Crypto
I’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)
Legacy comments, imported from previous version of this blog:
Dr Evil
December 13, 2013 07:13 PM
Hey, what about a quantum brute force attack?
Aaron Toponce
February 15, 2014 05:58 AM
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.
aslkjdhlakjsh
February 21, 2015 02:10 AM
Two years later...
http://www.theverge.com/2015/2/16/8048243/nsa-hard-drive-firmware-virus-stuxnet
Lourens
January 27, 2013 11:24 PM
Regrettably the NSA would probably use a .
micah
January 27, 2013 11:38 PM
:). 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.
RobJoy
January 21, 2018 12:18 PM
OR.
They could simply create a 2000+ qubit quantum computer and crack it in milliseconds.
Trust me, they are way beyond that. For NSA, there is no encryption that phases them.
Stuart
August 26, 2014 07:54 AM
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?
Adamantish
February 22, 2017 12:32 PM
It's years later but I thought it worth responding to this well reasoned fear. The seed data GPG uses comes from linux
/dev/randomwhich 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
PGP looks to be holding out: http://www.theverge.com/2014/12/28/7458159/encryption-standards-the-nsa-cant-crack-pgp-tor-otr-snowden
Adamantish
February 22, 2017 03:10 PM
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.
Sure
June 14, 2013 06:55 AM
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.
micah
June 14, 2013 09:50 AM
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.
Xezlec
September 5, 2013 06:20 PM
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...
jack
September 6, 2013 09:08 PM
We don't know that much. There's way to much conjecture.
Kenichi Mori
February 4, 2014 03:13 AM
āāāĀĀĀèèèÈÈÈÉÉÉéééȄȄȄȅȅȅȇȇȇȆȆȆĒĒĒēēēìììÌÌÌÍÍÍíííȉȉȉȈȈȈȊȊȊȋȋȋīīīĪĪĪĪÒÒÒòòòóóóÓÓÓȌȌȌȍȍȍȏȏȏȎȎȎŌŌŌōōōùùùÙÙÙÚÚÚ ÀÀÀáááÁÁÁȀȀȀȁȁȁȂȂȂȃȃȃāāāĀĀĀÈÈÈèèèéééÉÉÉȄȄȄȅȅȅȇȇȇȆȆȆĒĒĒēēēÌÌÌìììÍÍÍíííȈȈȈȉȉȉȊȊȊȋȋȋĪĪĪīīīÒÒÒòòòÓÓÓóóóȌȌȌȍȍȍȏȏȏ ŔŔŔȐȐȐȒȒȒȓȓȓȑȑȑŕŕŕčččČČČŽŽŽžžžšššŠŠŠĐĐĐđđđĆĆĆćććÌÌÌìììíííÍÍÍȈȈȈȉȉȉȋȋȋȊȊȊĪĪĪīīīĒĒĒēēēȇȇȇȆȆȆȄȄȄȅȅȅéééÉÉÉÈÈÈĀĀĀāāā ÒÒÒòòòÓÓÓóóóȌȌȌȍȍȍŌŌŌōōōÙÙÙùùùÚÚÚúúúȗȗȗȖȖȖŪŪŪūūūòòòÒÒÒĪĪĪīīīȋȋȋȊȊȊȈȈȈȉȉȉíííÍÍÍÌÌÌìììēēēĒĒĒȆȆȆȇȇȇȅȅȅÉÉÉÈÈÈ ŔŔŔȐȐȐȒȒȒȓȓȓȑȑȑŕŕŕčččČČČĆĆĆćććĐĐĐđđ𩩩šššŽŽŽ 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.,
» Why You Should Learn to Use Encryption
November 22, 2016 09:17 AM
[…] it means that you are more likely to be struck by lightening, twice, than you are of having your encryption algorithm cracked. Even then, it would likely need to have been done by an organization like the NSA, with […]
Dr Evil
December 13, 2013 07:12 PM
Hey, do a post on a Quantum Brute Force attack
jack
January 7, 2019 10:14 AM
NSA can crack the ecdsa and sha256 with their software. it's easy for them and only need 30minute to be done. They have algorithm with 512 bit technology and new generation of programing software.
Aaron Toponce
February 15, 2014 05:55 AM
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.
Scott Suhr
February 22, 2017 10:53 AM
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?
e-sushi™
August 13, 2013 08:44 AM
Let's wrap this up:
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.
smeghead
August 14, 2013 02:14 PM
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.
jack
September 6, 2013 09:08 PM
I would seriously doubt that if there were inherent issues in encryption algorithms that academia would not find them also.
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?
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.
TheSecondaryThing
December 22, 2014 11:57 AM
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.
TK-999
July 1, 2013 02:02 PM
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.
Michah
June 25, 2015 06:54 PM
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.
Stuart
August 26, 2014 08:02 AM
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.
Cyril
May 16, 2016 11:21 PM
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!