How confident can we be that nobody will crack a 128-bit key?

Question

In a context involving a block cipher like AES-128, excluding quantum computers, cryptanalytic breakthrough on AES and implementation attacks (poor TRNG, DPA..), and wrench, how confident can we be that by key search, "nobody will crack a 128-bit key" until 2100. Assume business as usual for humanity, use of 1 year worth of global production of electricity, 1 year worth of industrial production for the gear (used over a multi-year period).

Full disclosure: I'm trying to challenge my own half-baked opinion.

Updated: I leave it open if we allow multi-target attacks, where the same known plaintext is available enciphered under many random 128-bit keys. That makes a huge difference, but specifics of the block cipher become less important, which is good.

Note: we have a related question there; but it was considering a 256-bit key size, the methods adequate for that size need not be precise, and have not led to a definitive or even clear conclusion on 128-bit; plus answers are nearly 6 years old, and much more SHA-256 have been performed since then than I would have predicted at the time.

Note: We have another related question there at the 128-bit key level, but it restricts to currently available technology. Here, we must account for foreseeable technology more plausible than quantum computers usable for that cryptanalysis.

^{Note: 2100 and other limits have been set (instead of the original in the future of humanity as a species) for the sake of making a quantitative answer more falsifiable. Say, global apocalypse on that March 1 because a military subcontractor goofed on the leap year rule.}

Answer 1

This question seems to be asking us how fast will computers grow. No cryptanalytic breakthrough and no quantum computing essentially means no attack faster than brute force.

So will humanity at some point in the future with significant resources be able to brute force 128 bit key? I would answer, maybe. 256 bit key Almost definetly not.

Obviously predicting is hard especially the future but assuming humanity will not self destruct it will continue to progress and it is not unreasonable to assume it will come close to the limits of what is possible.

The main discussion on theoretical limits of brute force is in minim energy requirements. I suspect we may be short on physicists on crypto stack exchange so I will try.

Brute forcing a key requires enumerating the keys. And that requires changing bits. Each bit change erases some information and there is a minimal amount of energy required for that. Lauder's limit https://en.m.wikipedia.org/wiki/Landauer%27s_principle

For brute forcing a 128 bit at room temperature this comes out 262.7 Twh(the annual electricity consumption of Spain) that is a lot But not something humanity can't achieve. By lowering the temperature we can improve on this. And some say we could build another type of computer which doesn't erase information and this limit won't apply to it. Though such a computer might go against the spirit of the question which excluded quantom computers.

So we don't actually have any good theoretical limits to prevent humanity from brute forcing a 128 bit key eventually. Which leads to my answer. Maybe.

For 256 bits the same energy limit would put brute forcing well outside the realm of the possible.

Answer 2

I believe that I can bound the problem based on the current state of semiconductors and classical physics. I mean to exclude quantum computers and quantum devices. We have reached the point where if you want to double the speed, you need to double the power, so modern CMOS is at an end, but you still can tease through a power argument.

Let's assume that it takes a single electron to toggle a gate; however, to have "gain" in a system you need more than a single electron because transistor gain comes from channel shortening (anyone who ever drew an inverter as a resistor pair did you a disservice). For this reason, I will assume that each transistor takes 3 electrons on 1V. I will further assume a direct bandgap and an infinite capacitance to the substrate for a 1:1 coupling to instantly turn on the gate, so I'm ignoring time of substrate inversion (which is the physically limiting factor)

I now have to make a hardware assumption (sorry), and I'll use AES-128 just because I can bound the problem. I have 5 S-Boxes at 890 electrons per try each (I have an internal S-Box reference that calculates the multiplicative inversion, and I just back calculated this from the gate count). Rcon costs me 112, the another 314 for the rest of the key schedule. The mix columns and cryptoword overhead seems to be about 1480. It costs me 16384 total for the state registers. This gives me a total of 22740 electrons per round, for 10 rounds.

The result is 3.6433e-15 W per attempt. This means it requires 1.2398e+24 Watts to explore the complete key space. That's about 2 years of current world energy creation. hedging your bets that you only need 64-bits worth of attempts, that's 6.7208e+04 Watts, which is a practical value. These numbers represent the lower boundary condition with the current boundaries of classical physics. 7kW is not an intractable problem.

Answer 3

It is a 99% certainty that any AES key of any size will be cracked, perhaps within our life times.

It is complete nonsense to suggest that we'll have to boil lakes or build Dyson Spheres to recover an AES key. All those back of fag packet estimates are for brute forcing a key. It is extremely likely that we won't have to. Differential analysis came along and revolutionized cryptography. Technology and science will inevitably advance further and key recovery will become possible.

It is extremely naïve to predict the future with such blind arrogance. Do you remember those doom sayers that prophesied with such certainty that a man's lungs would explode if we travelled above 6 mph? And those German cryptographers who orchestrated the War of the Atlantic confident of total secrecy? Were they wrong!

There is a simple mathematical test to determine whether any encryption can be broken. If (message entropy) > (key entropy), the encryption can be broken theoretically. The longer the message, the greater the redundancy and the lower the theoretical security. Just because we can't recover an AES key today /tomorrow, doesn't preclude it's recovery next week or next decade. If anyone says otherwise, I suggest that they retire from poorly paid cryptography and either go into the stock market to make a killing or Tarrow card reading.

There is an interesting consequence of the breakability formula. True random number generators are relatively simple to build. When the Up side of our Dyson sphere is at war with the Down side, strategic communications may again revert to using ancient one time pads that obey the breakability equation.