# Use multiple computers for faster brute force [duplicate]

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?

## marked as duplicate by Ohnana, Mark Buffalo, Xander, tlng05, MatthewMar 7 '16 at 16:55

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 2256 possible values. That's 12✕1076, or 12 followed by 76 zeroes. If we generously assume that a computer can test a trillion (that's 1012) 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✕1076/(1012✕1012) seconds to search the entire keyspace. That's 12✕1052 seconds. As there are only 3,155,760,000 seconds in a century, it will take approximately 4✕1043 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.

• Indeed. This is why I believe the side-channel is nearly always the right approach. – Mark Buffalo Mar 5 '16 at 16:45
• @tjt263 a typical side channel attack is a wrench xkcd.com/538 – Neil Smithline Mar 5 '16 at 16:54
• @NeilSmithline Wrench-channel? :) There's almost always a way around the best encryption. With regards to communication, if you can compromise either User 1, or User 2, it's all a moot point. If you can physically access the computer of someone using FDE, or change their hardware in transit, you can silently implement a physical keylogger... for example, when they are on vacation / when they're buying hardware online (Supply Chain Interdiction). Another way would be to find a problem with the encryption's implementation. – Mark Buffalo Mar 5 '16 at 16:56
• @MarkBuffalo please. Side-channels are a well-defined construct in cryptography. You're talking about ways to not bother with crypto at all. A sidechannel is formally defined to leak some potentially helpful information upon execution of crypto (like [cache] timings and electromagnetic field changes) that if properly analyzed usually will leak secret information. Sidechannel attacks by themselves do not alter the way the crypto works. – SEJPM Mar 5 '16 at 19:07
• @SEJPM I don't see how rubber-hose cryptanalysis is excluded from that definition. Humans are part of the physical implementation of cryptography, and attacking the human-computer interface seems to perfectly fit into Mark Buffalo's definition. – March Ho Mar 6 '16 at 4:06

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 2256-1, and on average it will need to count to 2255. 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−23 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−23 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 2191. 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 2191 times, at 2.87×10−23 J/bit yields 9×1034 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×1034 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 264. Thus that counter would take 1.6×1054 J. Again, looking at Order of Magnitude (energy), we find that the total visible mass energy in the milky way galaxy is 4×1058 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=mc2), you could run a counter which could count from 0 to 2255.

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

• I was hoping that someone would mention even building a counter to enumerate all the values by flipping bits is literally impossible with the amounts of energy we can currently harness. There are some other fun physical limits to computation on Wikipedia if you're interested in this type of thing. – neocpp Mar 5 '16 at 22:15
• Cort, could I get your opinion on my answer in this thread? Considering your knowledge and interest in both physics and information security, I think this would be a good question for you. – BuvinJ Mar 5 '16 at 23:17
• Of course, there are a lot of galaxies we could convert to mass energy if we really wanted to break a key. – PyRulez Mar 6 '16 at 1:46
• @JDługosz BuvinJ actually asked about the quantum computers in another question. As for reversable computers, I think upgrading technology from technology we have right now to technology that we're not entirely positive it can be done within the limits of physical reality is beyond the scope of what the OP was asking for =) It is also entirely possible that reversible computers, while avoiding the energy costs of bit-erasing, still may not avoid the computational time costs mentioned in the winning answer. – Cort Ammon Mar 6 '16 at 17:17
• @CortAmmon Sure. But at some point you use too big a rubber hose and then try to sue Apple. – Aron Mar 6 '16 at 23:17

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"

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.

• RC5 != RSA. Please don't confuse the two. – a CVn Mar 7 '16 at 15:07
• 1999 - 2003: average processor speed was ~1Ghz. 2003-2016: avg processor speed ~3Ghz. So breaking 72-bit will take approximately: (2^(72-64)/3) * 4 years ~ 6144 years. – stackErr Mar 7 '16 at 20:36
• @stackErr You're possibly ignoring graphics cards, which have gotten much faster, larger, with better optimization and lower latency than a 3-fold jump. Plus, the number of processors available between 2003 and 2016 has jumped considerably as well. I.e., 6144 is definitely an upper bound. – Nate Diamond Mar 8 '16 at 0:40
• @NateDiamond purposely ignoring graphic cards/FPGAs/ASICs since majority of the users(I would think) are not using those to brute force this. But yes multiple processors can add another (quad core) 4x decrease in the calculations. That brings it down to 1536 years (still not feasible in a persons lifetime) – stackErr Mar 8 '16 at 5:06
• I wouldn't be so sure though. A large number of computers nowadays come with dedicated graphics cards, nor the relatively reduced cost of older generation graphics cards. Plus you're still missing that the number of available computers has increased greatly since 1999-2003. If someone gamified the inclusion such that people could let their cell phones run it overnight, the number of available users would skyrocket relative to the original period. The issue is, nobody has put in the work yet. There's little incentive. A better measure would be to equate the process to the bitcoin mining pools. – Nate Diamond Mar 8 '16 at 16:29