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)
Subscribe to feed