Most cryptographic algorithms deal with numbers that are 128
bits or larger. A 128-bit number has 2

^{128}possible values, but how big is 2^{128}? Most people realize that it’s a “big number” but don’t comprehend exactly how big. Who can blame them? Outside of a few disciplines such as cryptography and astrophysics, most people will never encounter a number this large.
It’s important to understand this, however, because it tells
us what is and is not possible in cryptography.
Conversely, a number of inaccurate statements about cryptography arise
because of a poor understanding of this quantity. For instance, many articles I’ve read
recently claim that it is possible to use rainbow tables even for password hashing algorithms with a 128-bit salt. Others have claimed that it is or will be
possible to brute-force 128-bit keys. To
understand the problem with these claims, let’s figure out just how big this
number is.

A 128-bit number has 2

^{128}possible values. That means 2 x 2 x 2x …128 times. We can also write this as 2^{64}x 2^{64}or as 2^{32}x 2^{32}x 2^{32}x 2^{32}. It’s important to understand that 2^{128}is not twice as big as 2^{64}; it’s 2^{64}times as big. If you take 2^{64}and double it, you only get 2^{65}. Let’s see what these numbers look like when we write them out:
2

^{32}= 4,294,967,296.
2

^{64}= 18,446,744,073,709,551,616.
2

^{128}= 340,282,366,920,938,463,463,374,607,431,768,211,456
2

^{32}is only about 4.3 billion which is a little less than either the age of the Earth or the number of people alive today. It’s several times less than the amount of money that Bill Gates has made and a few thousand times less than the current U.S. national debt of about 15.8 trillion.
2

^{64}is about 18.4 quintillion which is more than a billion times our national debt. It’s 290,000 times the GDP of the entire world. 4.3 billion is big, but not unheard of. 18.4 quintillion is completely outside normal human experience.
2

^{128}is 340 undecillion and I had to look that up because I had no idea what the number is called. The mass of the earth is about 2^{92}grams; 2^{128}is almost 69 billion times larger than that. Still, it’s still quite a bit less than the number of atoms in the Earth which is about 2^{166}, roughly 256 billion times larger.
How long would it take to brute-force a 128-bit key? If your PC can try 2

^{40}keys per day, it would take you about 847,904,136,496,835,804,725,427 (848 sextillion) years in the worst case. We expect the sun to run out of hydrogen and collapse into a white dwarf in only about 5 billion years.
Clearly we can’t brute-force 2

^{128}with a PC, but what about with a supercomputer? In 1998, The Electronic Frontier Foundation built a DES cracker (http://en.wikipedia.org/wiki/EFF_DES_cracker) that could brute-force 2^{56}DES in about 4.5 days on average. This machine cost about $250k. For a million dollars or so, it would have been possible to build a machine that could crack DES in about a day. Computers have gotten much faster since 1998 so let’s assume that the current limit for a one million dollar supercomputer has increased to about 2^{64}guesses per day (256 times more). The U.S. National Security Agency can probably afford much better machines than that and may be willing to spend a quarter of a billion or so to get a computer that can try 2^{70}keys per day. That’s still not close to 2^{128}. Using a computer that can try 2^{70}keys per day, it would take 789,672,263,429,347 years to try 2^{128}keys. Even if future advances in technology enable the NSA to build a computer that can try 2^{90}keys per day, it will take millions of years to guess a 128-bit key.
Does this mean we won’t ever break a 128-bit cipher like AES? No.
Advances in cryptanalysis may eventually allow us to break AES (or any other cipher) with far
less effort than brute force. If quantum
computers become a reality, we’ll be able to break AES and other 128-bit
symmetric algorithms with about 2

^{64}effort. Right now, it’s possible to break specific implementations due to side channel attacks, bad RNG, and other problems.
Storage on the order of 2

^{128}will remain impossible. As I discussed in a previous post, storage for rainbow tables for each of 2^{128}salt values would require a storage device at least as large as the Earth. I feel pretty safe saying that isn’t going to happen. Ever.
Is it possible to get lucky?
There’s a small possibility that even with a PC you might stumble across
the right key early on. Let’s assume you
still have a PC that can try 2

^{40}keys per day. Such a computer could try about 2^{49}keys per year. In any given year, you’d only have about a 1 in 2^{79}chance of finding the correct key. The odds of winning Mega Millions with a single ticket are about 1 in 175 million or 1 in 2^{27}. Your odds of winning Mega Millions three times in a row after buying only a single $1 ticket each time are about 1 in 2^{82}. So, your odds of finding the right key in a year’s time are eight times better than winning Mega Millions three times consecutively. With a supercomputer that could try 2^{90}keys per day, the NSA would have a 1 in 753 million chance of finding the correct key in one year which is only about four times worse than the odds of winning Mega Millions with a single ticket. So, I'm saying there’s a chance.
This comment has been removed by the author.

ReplyDeleteI was led to your page when my brother-in-law bought a car that had 128 options. I was impressed to see a Web page devoted entirely to discussing the exact (theoretical) number of configurations to choose from!

ReplyDelete