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

[Robert J. Hansen]

On 5/14/2014 6:11 PM, Leo Gaspard wrote:
> 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".

That's why it's a homework problem.

>> 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?

$dS = \frac{\delta Q}{T}$

The Second Law of Thermodynamics says there ain't no such thing as a
free lunch.  You want to lower the heat (entropy) in one place, you have
to (a) move that entropy elsewhere and (b) pay an entropic price on top
of it.  If you're moving a million units of entropy from A to B, you're
going to be be paying at least a million and one units of energy.
That's a gross simplification, but close enough for government work.

You want to lower the temperature (heat, entropy, whatever) to 10^-10 K?
 Okay, fine: pay the price.  But you will *always* be paying more than
if you were to just run the machine at 3.2K, and that's a consequence of
$dS = \frac{\delta Q}{T}$.

To put it in terms that we all can understand -- your air conditioner
runs on electricity.  Moving heat from inside your house to outside
requires energy be added to the overall system.  The hotter the day, the
more energy your air conditioner needs to move the heat around.

> BTW: AFAICT, a nuclear warhead (depending on the warhead, ofc.) does 
> not release so much energy, it just releases it in a deadly way.

A one-megaton nuke releases a *petajoule* of energy.  That's a lot.
When people start using the phrase "peta-" to describe things, I
suddenly become very interested in their Health & Safety compliance.
This is a petawatt laser.  This is a petawatt reactor.  This is a
petajoule of energy.  This is Peta Wilson.[1]

(I trust that Ms. Wilson will forgive my asking, "uh, do we have someone
certified for operating her, and where's the nearest Health & Safety
card?" without getting too, well, petulant.[2] )

[1] http://en.wikipedia.org/wiki/Peta_Wilson
[2] http://instantrimshot.com/index.php?sound=rimshot&play=true

> * 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're beginning to make me a little irate here: the Wikipedia page
answers this in the second sentence of its first paragraph.  "Any
logically irreversible manipulation of information ... must be
accompanied by a corresponding entropy increase."

Key phrase: Entropy increase.

Layman's translation: Heat increase.

The Landauer Bound gives not just a minimum amount of energy necessary
to change a bit of information, but how much heat must be liberated by
that computation.  And I repeat, this is in the second sentence of the
first paragraph of the Wikipedia article...

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

Yeah, adiabatic computing.  Give me a call as soon as we have an
adiabatic computer: I'll be deeply fascinated.  Right now that's even
more theoretical than quantum computing -- we've actually observed
quantum computation in the lab on a small scale, while adiabatic
computing is so far a complete no-go, AFAIK.

(Then again, it's been a few years since I've dived into the literature
on it -- if you can find a paper demonstrating real-world adiabatic,
energy- and entropy-free computing, I will be deeply fascinated.  I
wasn't kidding about that.)

> information on each flipped bit. Actually, IIUC, flipping a bit is a
>  reversible operation, and so the landauer principle does not apply.

Look!  A bit of information:  ___

That's what it was before.  Of course, it's now carrying the value '1'.
So, tell me: you say bit flips are reversible, so what was the value
before it was 1?  I promise, I generated these two bits with a fair coin
(heads = 0, tails = 1).

"Reversible" means "we can recover previous state without guessing."
Current computing systems are not reversible.

> So it might be that Landauer's principle just does not apply to 
> AES-128

No.