Use multiple computers for faster brute force

Question

I've watched Mr. Robot lately and can't stop thinking why it was so hard to decrypt files encrypted using AES encryption with a 256-bit key.
Let us say the only method to find the key is through brute force.
Can't we set a computer to brute force starting from the first possible key, and another to begin from the last possible key, and perhaps a few computers to try the keys in the middle?
Wouldn't that reduce time dramatically?

Answer 1

Sure it's possible, but it doesn't really help. The number of possibilities is just too large.

Consider that a 256-bit key has 2²⁵⁶ possible values. That's 12✕10⁷⁶, or 12 followed by 76 zeroes. If we generously assume that a computer can test a trillion (that's 10¹²) possible keys a second, and that we have a trillion computers (where will we get them from?) performing the key search, it will take 12✕10⁷⁶/(10¹²✕10¹²) seconds to search the entire keyspace. That's 12✕10⁵² seconds. As there are only 3,155,760,000 seconds in a century, it will take approximately 4✕10⁴³ centuries to try all possible keys. There's a 50-50 chance that you'll find the key in only half that time.

That's the way encryption is designed. The number of possibilities are just too large to be cracked in time that is interesting for humans.

Answer 2

I did a calculation on this one once. Let's assume AES can only be broken using brute force. Clearly we are going to need a counter, which counts from 0 to 2^256-1, and on average it will need to count to 2²⁵⁵. Running this counter takes energy. How much energy does it take?

As it turns out, there is a thermodynamic limit here, Landauer's principle. At a given temperature, there is a minimum amount of energy it can take to set a bit (1 bit of entropy), because if we don't spend that much energy, we can actually decrease the entropy of the system, which is thermodynamically impossible. The energy it takes is kT ln 2, where k is Boltzman's constant (1.38×10⁻²³ J/K) and T is the temperature in kelvin. Obviously we want to do this as affordably as possible, so lets do the calculations at 3 kelvin, which is roughly the temperature of the background radiation of the universe. We can't get any cooler than that without spending more energy to cool the system than we'd have spent on flipping the bits! This pins the energy cost of flipping a bit at 2.87×10⁻²³ J/bit.

Now, how many bit flips do we need? The answer will be a lot, so to keep the energy quantities in human understandable terms, I'd like to simplify the problem. Rather than solving AES-256, let's pretend we were solving AES-192, which only requires counting to 2¹⁹¹. So how many bit flips do we need? If we counted in normal binary, we may need to flip multiple bits per increment of the counter. That's annoying to calculate, so lets pretend we could do this counter with Grey Codes, which only flip one bit per increment.

Incrementing a counter 2¹⁹¹ times, at 2.87×10⁻²³ J/bit yields 9×10³⁴ J. That's a lot of energy. In fact, if I go to one of my favorite Wikipedia pages, Order of Magnitude (energy), we see that the energy emitted by our sun every year is 1.2×10³⁴ J. That's right. Just running the counter that would be at the core of the AES breaking process would take the sum total of nearly a decade of the sun's energetic output. All of it.

Now if we revisit the original AES-256 problem, the energy costs go up by 2⁶⁴. Thus that counter would take 1.6×10⁵⁴ J. Again, looking at Order of Magnitude (energy), we find that the total visible mass energy in the milky way galaxy is 4×10⁵⁸ J. Thus, if you were to convert 0.004% of the total mass energy of the galaxy (i.e. converting all of the mass to energy using E=mc²), you could run a counter which could count from 0 to 2²⁵⁵.

This is why one never brute forces a modern crypto algorithm. The amounts of energy called for are literally at the level of "heat death of the universe."

Answer 3

It's not just possible, people have actually done this successfully. But only with very short keys.

distributed.net managed to break a 64bit RC5-encryption in 2002 by using a distributed network of computers. The computers were mostly consumer-grade PCs owned by volunteers who installed a program to crunch keys in the background. This was part of the RSA secret key challenge - a contest by RSA Labs to decrypt messages encrypted with keys far shorter than you would use in the real world.

"After over four years of effort, hundreds of thousands of participants, and millions of cpu-hours of work, Distributed.net has brute forced the key to RSA Security's 64 bit encryption challenge"

• Source: slashdot.org

They started another project to win the RSA 72-bit challenge in 2003. 13 years later, they are still calculating and have not even tested 4% of the keyspace.

Keep in mind that these are extremely simplified versions of RSA. The recommended key length for RSA-RC5 in the real world is at least 128bit. Every additional bit doubles the computation time, so these distributed approaches are still light-years away from attacking any real-world encryption.