AES attack calculations (money and time)

[Robert J. Hansen]

> from time to time someone asks how secure (a)symmetric crypto really was and
> then our math and physics teacher Rob has his performance.

No, people ask how difficult it is to brute-force crypto.  That's a  
very narrow question and can be answered with great precision.  When  
it comes to the fuzzier question of how secure crypto is, I, like most  
people, hem and haw and start things off by saying, "Well, it really  
kinda depends, you know?"

> Of course, they say "No practical impact due to reliance on related
> keys" because they had to stay below 2^100 but considering that they refer to
> real hardware whereas here the theoretical lower energy limits are  
> used I am a bit surprised.

Why?  There's no real contradiction here.

The theoretical lower limit for brute-forcing a 128-bit cipher  
involves on the order of 10**17 joules of energy (100 megatons).   
That's not particularly high, although if you were to do it enough  
times you would significantly accelerate global climate change.

His back-of-the-envelope calculation for cryptanalysis (not  
brute-forcing!) says a sustained 4 terawatts (10**12 joules per  
second, sustained for a long period) is enough.  If you sustain  
terawatts for a long period you're going to significantly accelerate  
global climate change.  (Note: one terawatt held for 30 seconds = 100  
megatons.)

Either way, the power requirements become absurd.  As he says, "Energy  
seems to be the main bottleneck."  I haven't phrased it that way:  
usually I phrase things more like, "Extremely large amounts of energy  
are required, but those extremely large amounts of energy have side  
effects we really don't want to experience."

> Is this paper correct?

What do you mean by 'correct'?  As far as a back of the envelope  
calculation goes it seems reasonable enough, but I'm not sure I'd like  
to wager money on it being correct in each detail.

> I am not an expert in these areas. The only point that
> came to my mind is that if you need energy of the magnitude of the US overall
> electricity consumption than you cannot ignore the energy costs. :-)

4 terawatts multiplied by one year equals 35 billion megawatt-hours.   
Per Wikipedia  
(http://en.wikipedia.org/wiki/Cost_of_electricity_by_source), nuclear  
power costs $60 per megawatt-hour.  That's $2.1 trillion just to run  
the nuclear power plants to power this hypothetical computer.  That's  
a jaw-dropping number.

> Another question as I am not familiar with crypto attacks: They are talking
> about plaintext there. Does that mean they need both plaintext and ciphertext
> to tun this kind of attack? If so then I assume the real computational effort
> is higher by orders of magnitude because you have to check whether  
> each key is the right one. Is that correct?

They're talking about doing sophisticated mathematical analysis of the  
system in order to recover the key.  This isn't a brute-force setup.