Is it possible to break a 128-bit key?

Question

I'm a programmer and relatively new to cryptography, so pardon my rookie question. :)

Let's say we have a message, both in plain text and encrypted with a 128-bit key. In theory, it possible to somehow find out the key? And, if yes, what computing time are we talking about?

Thanks!

Answer 1

Yes, it's a question of time needed - using brute force one can try each possible combination of bits and guess the right one. Maximal time would be millions and billions of years, so we can say that it can't cracked easily.

However, each algorithm has certain short circuits (for some algorithms such circuits just have not been found yet) that reduce the time needed. Also modern massive parallel computational techniques (eg. employing GPUs in graphic cards) reduce the time even more. There can be other factors that influence the time needed, such as flaws in algorithm application (eg. use of wrong encryption mode or use of short password and padding it with some character to the key length).

Then there exists Rubber-hose cryptanalysis which usually proves to be more effective, than brute force key guessing.

Answer 2

Short answer:

Taking in account only brute force checking each key is available - No

Longer Answer:

In 2007 there was estimation that cost to crack 88 bits using brute force is 300M$ if you apply Moore's law you reduce this price by factor 4 or you might get 2 extra bits by now.

So you need like 2^38 more money to crack just single 128bit key. (approx 10^20 $)

Source: http://www.seagate.com/staticfiles/docs/pdf/whitepaper/tp596_128-bit_versus_256_bit.pdf
Source 2: http://dator8.info/pdf/AES/3.pdf

From article abut 128 bit keys:

If you assume:

• Every person on the planet owns 10 computers.
• There are 7 billion people on the planet.
• Each of these computers can test 1 billion key combinations per second.
• On average, you can crack the key after testing 50 percent of the possibilities.

Then (see calculation reference in Appendix):
• The earth’s population can crack one encryption key (one drive only) in 77,000,000,000,000,000,000,000,000 years!
• In case you’re wondering, cracking the second key/drive would take another 77,000,000,000,000,000,000,000,000 years.

I just noticed, it is not calculated correct. Correct answer is 77e9 years (still bunch for our civilisation).

Extra (bitcoin based assumptions):

At this date (year 2017) we can probably take bitcoin mining system as largest known brute force machinery and take price of mining and bitcoin as baseline for our assumptions.

Checking one sha256 is roughly same complexity as trying one symmetric key like AES or something else. According to this site current rate of hashes that are tried is (D * 2**32 / 600) where D is current bitcoin difficulty (678760110082.9902)

This system produces approx 5e+18 hashes per second. Each block is produced every 10min and yields as of today 12.50 coins. Price of coin is 2.5k.

One hash thus cost.
(12.50 * 2.5e3) / (5e18 * 600) = 1.0e-17.

Cracking one 128 bit key, today (June/2017) costs approx. 1e-17 * 2^128 = 3.5e+21
This would take 2^128 / (5e18*3.14e7) = 2.1e12 years with bitcoin mining system.