GPG's vulnerability to brute force [WAS: Re: GPG's vulnerability to quantum cryptography]

[Leo Gaspard]

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