On Wed, May 14, 2014 at 01:15:40PM -0700, Robert J. Hansen wrote: > >First, the Margolus-Levitin limit: "6.10^33 ops.J^{-1}.s^{-1} maximum" > >So, dividing the 2^128 by 6.10^33 gives me a bit less than 57000 J.s > >(assuming testing an AES key is a single operation). So, that's less than > >1min for 1kJ. Pretty affordable, I believe. > > No. But since I'm going to be giving a lot of explanation here about how > you're misusing the Landauer Bound, I'm going to leave how you're misusing > the Margolus-Levitin Limit as a homework exercise. :)
Well... Apart from the assumption I stated just below (ie. single bit flip for AES), I cannot begin to think about an error I might have done with this one, apart from misunderstanding Wikipedia's statement that "The processing rate cannot be higher than 6.10^33 operations per second per joule of energy". (I must say I was more confident about the Margolus-Levitin limit than the Landauer bound.) > >Again, assuming testing an AES key is a single bit flip > > It's not. You have to rekey the cipher. This multiplies the energy by > about a large factor. To make the math easier, let's call it a million. You may have noticed that, lower in my message, I stated the factor could be 10^5 and it would not matter much. You're calling it a million, why not? I must admit I thought I overestimated the 10^5 bit flip cost, since I thought AES-128 was like 7 rounds of something like 5 128-bit changeovers, for approx. 5000 ops in total. But I may have mixed up my recollection of AES with another algorithm. Looking up on Wikipedia : Apparently, my evaluation of rounds and changes was little off, but I think your weighty "rekey" operation might be the optimization described, that involved a 4kB table -- but it might be more energy-efficient (or even time-efficient) not to precompute the table if running through lots of different keys. > >According to Wikipedia still, the lowest temperature recorded on Earth is > >10^{-10} K. > > If you want to run the temperature lower than the ambient temperature of the > cosmos (3.2K), you have to add energy to run the heat pump -- and the amount > of energy required to run that heat pump will bring your energy usage > *above* that which you would've had if you'd just run it in deep space at > 3.2K. Sorry for my ignorance, but... if you have enough time to explain me, how do you derive this? > So multiply your previous estimate by a factor of ten billion, in order to > reflect running it at ambient temperature. > > 10^10 * 10^6 = 10^16. So far your estimate is off by a factor of a thousand > trillion. > > >So, despite bruteforcing being obviously impossible in this day and age, and > >most likely impossible in the near future, it seems to me that the following > >statement is exaggerated: "The results are profoundly silly: it’s enough > >to boil the oceans and leave the planet as a charred, smoking ruin." > > Assuming you could do AES in a single bitflip, it would require liberating > as heat as a strategic nuclear warhead. Every additional bitflip adds > another strategic nuclear warhead. By the time you're flipping 1000 bits > for each rekeying, you're basically inflicting World War Three on the earth > just to brute-force a cipher. BTW: AFAICT, a nuclear warhead (depending on the warhead, ofc.) does not release so much energy, it just releases it in a deadly way. So, I stated one could bruteforce at 10^6J (overestimated). You're adding 10^16, for a total of 10^22J. A nuclear reactor generates approx. 1000MW [1], ie. 10^9W. This makes 10^22J every 10^13s. So, 300000 nuclear reactors generate enough energy to bruteforce a key in a year. There are approx. 500 nuclear reactors active on earth (assuming those under construction in 2012 are now built). Actually, counting total energy production (13000 Mtoe [3], so 13000.10^6.11.10^6 Wh, ie. 14.10^16 Wh, that is 5.10^20 J per year), that makes a total of 20 years. Counting only 5000 bit operations per rekey (see upper for details), this "only" makes 1 year. OK, you're right. Sounds like nothing to fear (for the time being, at least -- energy production is steadily increasing). > I stand by my predictions of ecological catastrophe if anyone ever > brute-forces a 128-bit cipher. But I have a few objections of my own about your use of Landauer's principle: * You state the energy would be released (or did I misunderstand?). Wikipedia states it is a "minimum possible amount of energy required to change one bit of information" So no ecological catastrophe (not counting nuclear waste, CO2, etc) * You state it is a lower bound on the energy consumed/generated by bruteforcing. Having a closer look at the Wikipedia page, I just found this sentence: "If no information is erased, computation may in principle be achieved which is thermodynamically reversible, and require no release of heat." I do not know anything about reversible computing. But it seems to me that an AES-performing algorithm does not necessarily have to erase a full bit of information on each flipped bit. Actually, IIUC, flipping a bit is a reversible operation, and so the landauer principle does not apply. And AES being a 1-to-1 mapping (as the data to be decrypted is fixed, it is a 128-bit keyblock -- to -- 128-bit cleartext mapping), it seems to me that AES is theoretically a reversible program (even though our current implementations might not be, as they are 2-to-1 mappings, not knowing the cleartext). So it might be that Landauer's principle just does not apply to AES-128 Please note I'm not saying bruteforce is, or will ever be, technically feasible. I'm just saying your estimate might be a bit too much. (Not saying the FAQ article should be updated either, it makes a wonderful argument to bash people relentlessly talking about bruteforcing.) And, message to everyone reading: Please stop saying "Anyway I'll be dead by then". According to Ray K. (I'm not going to say what I think about him), we are all going to be immortal by 2050 (IIRC). So this is also your problem! (Or you'd better die quick.) Hoping it wasn't such a boring message, as it was already long enough, Leo [1] http://hypertextbook.com/facts/1997/JasminMarin.shtml [2] https://www.euronuclear.org/info/encyclopedia/n/nuclear-power-plant-world-wide.htm [3] http://yearbook.enerdata.net/#energy-primary-production.html _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users