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

[Leo Gaspard]

First: I agree with everything skipped in the quotes.

On Wed, May 14, 2014 at 07:31:26PM -0400, Robert J. Hansen wrote:
> On 5/14/2014 6:11 PM, Leo Gaspard wrote:
> > 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]

Well... A nuclear reactor produces 1GW, and thus produces 1PJ in 10^6 s, that is
approx. 11 days 14 hrs. Sure, you may be very interested in Health & Safety
compliance of nuclear reactors, but...

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

Well... Currently, at a French equivalent of undergrad level (CPGE), we're
learning entropy is a theoretical quantity, that has no real-world meaning --
thus not creating heat. Actually, its unit (J.K^{-1}) does seem to validate this
interpretation: contrarily to e.g. enthalpy, it's not an energy. Perhaps are we
oversimplifying, or perhaps did I completely misunderstand the teachers, but if
this is true there is no heat release. OTOH there would be heat absorption
through the need to move the entropy out of the system -- provided AES is not
reversible (see below for my case against that point).

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

Well... If the operation the bit just underwent was a bitflip (and, knowing the
bruteforcing circuit, it's possible to know that), the bit was a '0'.

I believe I must have misunderstood your challenge! (Or, just coming to my mind:
maybe was I unclear: when saying bitflip I did not mean setting a bit, but
rather setting its value as 1 - old value.)

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

I do not state that physically our processors are reversible. I do not even
state any processors might ever be, or adiabatic computers might ever exist.

I just state the theoretical application going from the set of 128-bit keys to
the set of 128-bit cleartexts (with the 128-bit ciphertext fixed) is a bijection
(or so I hope -- unless many keys produce the same ciphertext from the same
cleartext, which would be an attack on AES and ease bruteforce naturally).

As a consequence, I cannot see where a bit of information was lost, and thus
where Landauer's bound is supposed to apply. But maybe am I the one lost here!

Thanks for your previous and hopefully future answers,

Leo