5
$\begingroup$

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.

| improve this question | |
$\endgroup$
  • 2
    $\begingroup$ This isn't really a cryptography question, except to also exclude another computing paradigm breakthrough similar to what quantum computers may be. It's more of a matter of how long you expect humanity to last. Maybe in a few thousand years there will be beings who are still recognizable as humans and who are prepared to use a whole star's output to decrypt a message left by their great^n-parents. $\endgroup$ – Gilles 'SO- stop being evil' Sep 15 '17 at 13:43
  • 2
    $\begingroup$ A specific 128-bit key or any 128-bit key? For the first I would say that you can be confident enough, for the second not so much. blog.cr.yp.to/20151120-batchattacks.html $\endgroup$ – Rukako Sep 15 '17 at 14:37
  • $\begingroup$ Isn't this question the most absolutely quintessential example of an opinion only based question? $\endgroup$ – Paul Uszak Sep 15 '17 at 21:54
  • 1
    $\begingroup$ I suggest you shouldn't discount multi-target attacks. If the adversary is trying to infiltrate a network of humans, breaking the crypto for at least one of their (say) laptop disks or emails is likely to lead to other key material, or at least to enable spear-phishing on the rest of them. $\endgroup$ – Squeamish Ossifrage Sep 15 '17 at 22:18
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ The energy mentioned is approximately Spain's annual electicity consumption. The temperature used was room temperature, though if we ever build computers which reach these temperatures 100 times colder seem likely. Much colder than that things get difficult. Obviously calculationg something like an encryption is much more than incrementing a counter but I can't give a tight lower bound here. $\endgroup$ – Meir Maor Sep 15 '17 at 16:33
  • $\begingroup$ Note that refrigerating the computer doesn't help -- you need as much power to run the refrigerator as you gain in decreasing Landauer's limit. But cooling with a big passive radiator to deep space would help... $\endgroup$ – Gordon Davisson Sep 15 '17 at 20:33
  • $\begingroup$ BTW, I don't think the computation needs to be irreversible. Incrementing a register by one is a reversible operation. Checking a key can in principle be done reversibly by saving all intermediate results, then running the computation backward to consume those intermediate results (an approach due to Charles H. Bennett). Whether this would be faster is another question, but it does remove the theoretical limit. $\endgroup$ – Gordon Davisson Sep 15 '17 at 20:44
  • $\begingroup$ Why do you assume that we have to brute force any key? Is a genetically engineered cyber decryption chicken any less likely (or stupid) than Instagram would have been to Robin Hood? $\endgroup$ – Paul Uszak Sep 15 '17 at 21:52
  • 2
    $\begingroup$ Biological computing is an interesting idea being researched but we need a computational model for it. If you are just using neurons instead of transistors we didn't change the computational model. If you aren't providing any details on how such a new computational model might work than you are saying we will magiclly decrypt it. $\endgroup$ – Meir Maor Sep 16 '17 at 4:24
1
$\begingroup$

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 (people who draw an inverter as a resistor pair do 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. Assuming that you need $2^{127}$, tries that's a total of 6.198e+23 Watts, or one year's worth of world energy. These numbers represent the lower boundary condition with the current behaviors of semiconductors that work by classical physics.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ You seem to be mixing up energy and power which make this hard to follow. $\endgroup$ – Meir Maor Sep 16 '17 at 14:44
  • $\begingroup$ @MeirMaor You are correct. I did the first half as Columns of charge, and then I just made some assumptions that it would happen in 1sec, to get Watts. The time constraint is a major factor, which was why I specifically said I was ignoring the time required for band changes in the device. I'm pretty good at charge, I'm not terrible good at relating it anything real. :) $\endgroup$ – b degnan Sep 16 '17 at 15:02
  • 1
    $\begingroup$ Where do you get the 64 bits and 7 kW from? And aren't Watts units of instantaneous power rather than energy? $\endgroup$ – Paul Uszak Sep 16 '17 at 23:46
  • $\begingroup$ 64 bits worth of attempts? That's not even close. You'd need 127 bits worth of attempts to have a 50% chance of breaking a 128-bit key. $\endgroup$ – forest Dec 17 '19 at 9:06
  • $\begingroup$ @forest I added the issues that you pointed out. That's what I get for hastily answering something when in a boring talk at a conference. $\endgroup$ – b degnan Dec 26 '19 at 14:32
-4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ This sidesteps the intent of the question, which is not whether or not some specific cipher will stand the test of time, but whether or not 128-bit keys will be sufficient for any future cryptosystem to avoid becoming categorically broken through brute force. $\endgroup$ – Stephen Touset Sep 15 '17 at 21:58
  • 1
    $\begingroup$ @StephenTouset It's a poor question. Plus, if my cyber chicken can sidestep a brute force attack, the question becomes moot. Many empires have fallen to substitution. Brute force is unnecessary /irrelevant. $\endgroup$ – Paul Uszak Sep 15 '17 at 22:11
  • 2
    $\begingroup$ You can read the question as being about the expectation over a uniform random choice among all possible (say) block ciphers with a 128-bit key. It's specifically not about any particular such cipher. $\endgroup$ – Squeamish Ossifrage Sep 15 '17 at 22:14
  • 1
    $\begingroup$ @SqueamishOssifrage This might be the basis of a good answer illustrating that significant inroads have already been made (without resorting to domesticated or augmented fowl) $\endgroup$ – Paul Uszak Sep 15 '17 at 22:33
  • 5
    $\begingroup$ Again, you seem to be aggressively intent on misunderstanding the purpose of the question. It doesn't matter if some specific cipher has a weakness. The question is more concerned about whether or not 128 bits of strength will be enough for any cipher. $\endgroup$ – Stephen Touset Sep 15 '17 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.