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!

Barbey

If the best attack is brute-force, it will take 2^128 times the time to encrypt a message. If you want us to tell you if there are better attacks than brute force, you need first to tell us what encryption algorithm you have chosen. – Blessed

You should have no reason to do this. Are you just trying to get a feel for the relative security of a particular encryption method? – Maiga

Its the A5 algorithm we are talking about. Basically the one that is used to encrypt GSM traffic. – Barbey

@Pascal Cuoq: Well, the probability of finding the key actually reaches 50% after "only" 2**127 encryption rounds ;) – Caterwaul

I believe that A5 uses 64-bit key rather than 128-bit key. See the link in my answer for understanding how A5 has already been broken. – Obryan

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.

Sticktight

I'm afraid its impossible to use Rubber-hose cryptanalysis, nor ever Thermo-rectal cryptanalysis with a soldering iron will. :))) – Barbey

Found out that we are talking about the A5 algorithm... anybody knows if there are any flows in it that might make cracking it faster? – Barbey

@Barbey GSM encryption just recently was proven to be crackable relatively easily. Not sure if this applies to encryption algorithm itself or to overall GSM encryption scheme. – Arissa

Yes, thanks. Already found a video about it "Blackhat 2010 Attacking Phone Privacy Karsten Nohl Part". Thanks again! :) – Barbey

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.

Flatware

cracked 96bit RSA key in 2.30 min – Escrow

RSA keys are not symmetric keys, cracking RSA is about integer factorization problem and does not require brute force for this. cacr.uwaterloo.ca/hac/about/chap8.pdf -> 8.2.2 – Flatware

nice bitcoin analogy; however can you check the "this site" link, I was unable to open it. – Swen

@Gregory Thank you for pointing that out. Right now, site is working fine for me. Feel free to edit my post or suggest better resource and I can add it here. – Flatware

Answer 3

In a comment, you said this was about the A5 algorithm.

First, this uses a 64-bit key, not 128-bit. Second, it has some serious flaws - it's basically broken.

Obryan

Answer 4

If the cipher is good the only way is via bruteforce - encrypt the message with each key possible in turn and find the right one. This will take up to 2¹²⁸ attempts which is very long.

However ciphers often have vulnerabilities that allow for much faster key deduction.

Fivestar

Found out that we are talking about the A5 algorithm... anybody knows if there are any flows in it that might make cracking it faster? – Barbey

Answer 5

I had this question come up in class and wanted to know everyones take on this answer.

As that a brute force attack simply asks the computer to run through all possible combinations of bits in hopes of reaching the right combination to match an encryption key. A 128 bit encryption would have 2^128 bits, or roughly 340 trillion trillion trillion possible combinations. The world’s fastest computer according to the theverge.com is the Sunway TaihuLight (as of 2016) which can handle 93 quadrillion calculations per second, also known as petaflops, a petaflop is 10^15.

Now I did this calculation on my own so it might be wrong but I would love to hear other people’s take on this. Using the fastest computer in the world you will be able to process 2.932848e+24 possible combinations per year. 930*10^15 * 60 * 60 * 24 * 365 = 2.932848e+24 If you had this super computer running all day every day to crack one single encryption key of 128 bits. I would take roughly 68.5 years to go through all the possible combinations.
2^128 = 3.4028237e + 38 3.4028237e + 38 / 2.932848e+24 = 68.470

Doriandoric

Calculation to "68.5 years" is incorrect: (2^128 operations) / (2.9e+24 operations per year) = 3.4e38 / 2.9e24 years = 1.2 e + 14. Not 68 years, but 1.17 × 10^14 years, something like 117 billions of yeras not 68.5. – Concupiscence

Answer 6

I know this is a old post but I stumbled on it looking for something else. There is a very interesting book (at least in my opinion) call Brute Force by Matt Curtin. It talks about encryption and how they cracked the government standard (at that time) of DES encryption. While interesting from that standpoint, I also learned a lot about encryption in general.

Varhol