multiple subkeys and key transition
Robert J. Hansen
rjh at sixdemonbag.org
Fri Dec 10 03:53:31 CET 2010
On 12/9/2010 9:21 PM, Faramir wrote:
> I might be wrong, but I remember Bruce Schneier used thermodynamic to
> show it is not feasible to brute-force a 256 bits key...
He just repeated the work of Landauer, Margolus and Levitin. Basically,
for a digital computer working in base N, the amount of energy required
to clear a unit of information is kT*lnN -- the Boltzmann Constant,
multiplied by the temperature in kelvins at which the computer runs,
times the natural log of the computer's numerical base.
For a conventional digital computer, it requires about 10^-23 joules to
erase a bit. That energy must be radiated as heat. If you're going to
brute-force a 128-bit keyspace, you're going to be erasing 64 bits per
key.[*] About 10^-21 joules per key must be radiated, multiplied by the
10^38 attempts you'd have to try on average, gets you 10^17 joules of
heat... or about a 100-megaton nuclear explosion.
Since Fort Meade is not a smoking radioactive sea of glass, I conclude
the NSA is not brute-forcing 128-bit keys. :)
In reality the thermodynamic analysis is even more ridiculous than this,
since we're assuming you're not tampering with memory in any other way
than just to set bits for a key. That's wildly unrealistic.
In theory you can break the Landauer Bound with things like adiabatic
computing and supra-Turing processing, but those things are so far out
in the realm of science fiction they deserve to be called... well...
[*] You could brute-force the keyspace in a way that only requires you
to erase fewer bits per key, but then the defender would just choose a
key close to the end of your brute-force schedule. Hence, it's most
efficient to do them more or less at random...
> And a question: does the computation power required to factor RSA keys
> increase in lineal or more-than-lineal way?
Roughly logarithmic. As the moduli get larger, the number of primes get
fewer and fewer. This is why a 1024-bit key is roughly proportional to
an 80-bit symmetric key, a 2048-bit key is roughly proportional to a
112-bit symmetric key, and a 3072-bit key is roughly proportional to a
128-bit symmetric key. Three times the asymmetric key length only gives
you half-again the symmetric length.
More information about the Gnupg-users