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

[Leo Gaspard]

On Wed, May 14, 2014 at 12:21:36PM -0400, Robert J. Hansen wrote:
> > Since the well known agency from Baltimore uses its influence to have
> > crypto standards coast close to the limit of the brute-forceable, 128
> > bit AES will be insecure not too far in the future.
> 
> No.
> 
> https://www.gnupg.org/faq/gnupg-faq.html#brute_force

I unfortunately have to object to this FAQ article. (Please note I'm not using
any information beyond what Wikipedia provides -- and I may be wrong in my
undertanding of it.)

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.

Then, Landauer's principle: "energy k T ln 2".
Again, assuming testing an AES key is a single bit flip, as k is approx.
10^{-23}, this gives an overall energy (per kelvin) of
2^128 . 10^{-23} . ln 2 J.K^{-1}, which is approx. equal to 10^16 J.K^{-1}
(overestimated, as k was underestimated).
According to Wikipedia still, the lowest temperature recorded on Earth is
10^{-10} K.
This makes for a total of 10^6 J, if the computation is done at that
temperature.
According to http://hypertextbook.com/facts/2009/VickieWu.shtml ; the human body
uses approx. 6MJ (ie. 6 . 10^6 J) per day.
As a consequence, the process would consume less than a day of a human body.

Granted, this is still far from possible : Here I assumed testing an AES key was
a single bit flip, and that the computation was entirely done at the coldest
temperature ever recorded in a laboratory. Anyway, the former is a not-so-huge
constant (ie. less than 10^5, I'm almost sure of that), and multiplying the
results by this constant still yields an "imaginably possible" lower bound. And
the latter already has been recorded, despite my believing no computation has
been done at that temperature, it is still possible in a foreseeable future.

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."

The impossibility of bruteforce, to me, lies with current physical computation
capabilities, more than with theoretical lower bounds, that are far below
current prowesses.

Hoping I didn't miscompute,

Leo