How big is 2**128?

Most cryptographic algorithms deal with numbers that are 128 bits or larger.  A 128-bit number has 2¹²⁸ possible values, but how big is 2¹²⁸?  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¹²⁸ possible values.  That means 2 x 2 x 2x …128 times.  We can also write this as 2⁶⁴ x 2⁶⁴ or as 2³² x 2³² x 2³² x 2³².  It’s important to understand that 2¹²⁸ is not twice as big as 2⁶⁴; it’s 2⁶⁴ times as big.  If you take 2⁶⁴ and double it, you only get 2⁶⁵.  Let’s see what these numbers look like when we write them out:

2³² = 4,294,967,296.

2⁶⁴ = 18,446,744,073,709,551,616.

2¹²⁸ = 340,282,366,920,938,463,463,374,607,431,768,211,456

2³² 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⁶⁴ 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¹²⁸ 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⁹² grams; 2¹²⁸ 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¹⁶⁶, roughly 256 billion times larger.

How long would it take to brute-force a 128-bit key?  If your PC can try 2⁴⁰ 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¹²⁸ 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⁵⁶ 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⁶⁴ 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⁷⁰ keys per day.  That’s still not close to 2¹²⁸.  Using a computer that can try 2⁷⁰ keys per day, it would take 789,672,263,429,347 years to try 2¹²⁸ keys.  Even if future advances in technology enable the NSA to build a computer that can try 2⁹⁰ 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⁶⁴ 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¹²⁸ will remain impossible.  As I discussed in a previous post, storage for rainbow tables for each of 2¹²⁸ 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⁴⁰ keys per day.  Such a computer could try about 2⁴⁹ keys per year.  In any given year, you’d only have about a 1 in 2⁷⁹ 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²⁷.  Your odds of winning Mega Millions three times in a row after buying only a single ticket each time are about 1 in 2⁸².   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⁹⁰ 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.