Brute Forcing AES

Thanks to Paul Kehrer for reviewing! Any mistakes or oversights that are left are my responsibility.

AES's maximum key size is 256 bits (there are also 128 and 192 bit versions available). Is that enough? Well, if there is a cryptographic flaw in AES (i.e., a way to recover some bits of the key by some manipulation that takes less than 2**256 operations), then it depends on how big the flaw is. All algorithms come with the probablistic "flaw" that, on average, only 50% of the keys need to be tested -- since the right key is just as easily in the first half as the second half. This means, on average, just 2**255 operations are needed to check "all" keys.

If there is an implementation flaw in your AES implementation, then it depends on the flaw -- most implementation flaws are "game over". For example, if the radio leakage from the CPU is enough to detect key bits, the entire key can be recovered -- but that would be true (with only minor additional hardship) if the key was 4K bit long. Another example is a related subkey attack, where many messages are encrypted with keys that have a certain relationship to each other (e.g., sharing a prefix). This implementation flaw (in a different encryption algorithm) defeated the WEP WiFi standard.

What if there is none? What if actually recovering a key requires checking all possibilities? Can someone do it, if they have a "really big" computer? Or a $10B data-center?

How much is 256-bit security really worth?

Let's see!

We'll be doing a lot of unit conversions, so we bring in the pint library, and create a new unit registry.

import pint
REGISTRY = pint.UnitRegistry()

Assume we have a really fast computer. How fast? As fast as theoretically possible, or so. The time it takes a photon to cross the nucleus of the hydrogen atom (a single proton) is called a "jiffy". (If someone tells you they'll be back in a jiffy, they're probably lying -- unless they're really fast, and going a very short distance!)

REGISTRY.define('jiffy = 5.4*10**-44 seconds')

Some secrets are temporary. Your birthday surprise party is no longer a secret after your friends yell "surprise!". Some secrets are long-lived. The British kept the secret of the broken Enigma until none were in use -- long after WWII was done.

Even the Long Now Foundation, though, does not have concrete plans post-dating the death of our sun. No worries, unless the Twisted gets more efficient, the cursed orb has got a few years on it.

sun_life = 10**10 * REGISTRY.years

With our super-fast computer, how many ticks do we get until the light of the sun shines no longer...

ticks = sun_life.to('jiffy').magnitude

...and how many do we need to brute-force AES?

brute_force_aes = 2**256

Luckily, brute-force parallelises really well: just have each computer check a different part of the key-space. We have fast computer technology, and quite a while, so how many do we need?

parallel = brute_force_aes / ticks

No worries! Let's just take over the US, and use its entire Federal budget to finance our computers.

US_budget = 4 * 10**12

Assume our technology is cheap -- maintaining each computer, for the entire lifetime of the sun, costs a mere $1.

Do we have enough money?

parallel/US_budget

4953.566155198452

Oh, we are only off by a factor of about 5000. We just need the budget of 5000 more countries, about as wealthy as the US, in order to fund our brute-force project.

Again, to be clear, none of this is a cryptographic analysis of AES -- but AES is the target of much analysis, and thus far, no theoretical flaw has been found that gives more than a bit or two. Assuming AES is secure, and assuming the implementation has no flaws, brute-forcing AES is impossible -- even with alien technology, plenty of time and access to quite a bit of the world's wealth.