Wednesday, June 27, 2012

How big is 2**128?


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

232 = 4,294,967,296.
264 = 18,446,744,073,709,551,616.
2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456

232 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.

264 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. 

2128 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 292 grams; 2128 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 2166, roughly 256 billion times larger.

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

8 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. I 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
  3. This comment has been removed by a blog administrator.

    ReplyDelete
  4. This comment has been removed by a blog administrator.

    ReplyDelete
  5. This comment has been removed by a blog administrator.

    ReplyDelete
  6. This comment has been removed by a blog administrator.

    ReplyDelete
  7. I greatly thank you for the enlightenment. Very knowledgeable. I appreciate you.

    ReplyDelete

Understanding Scope in Go

As per my New Year's resolution, I've been learning to program in Go and reading  The Go Programming Language .   On page 141 of the...