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.
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!
ReplyDeletegood
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteI greatly thank you for the enlightenment. Very knowledgeable. I appreciate you.
ReplyDelete