multiple subkeys and key transition

[Robert J. Hansen]

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...
science fiction.

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