[cryptography] Current state of brute-forcing random keys?

Marsh Ray marsh at extendedsubset.com
Thu Jun 9 14:22:16 PDT 2011


On 06/09/2011 12:14 PM, Paul Hoffman wrote:
>
> What is the current state of brute-force attacks on AES-128 blobs?
> Are there recent results where we can estimate the cost of
> brute-forcing 64-bit and 80-bit keys?

The article is behind a paywall, but Google quotes the relevant statistic:
http://scholar.google.com/scholar?cluster=14788671232027796805
"The standard-cell implementation on a 0.35 B5m CMOS process from Philips  
Semiconductors occupies an area of only 0.25 mm"

Let's assume:
* the attacker has only one file for which he wishes to find the key
* you generate the key using a method for which the attacker can do no  
better than brute force for the nominal key size.
* the attacker can do no better than brute force against AES
* the attacker has ASICs using an AES implementation similar in chip area 
to Philips' standard cell
* the attacker can run his chips at a rate of 1 GHz

The last two assumptions are probably wrong. The Philips standard cell may 
not be optimized rapid re-keying and one that is might be larger in area. 
But the estimate of 1 GHz is probably conservative and there's an inherent 
output rate vs. area tradeoff in the pipelining of the design. But I think 
these assumptions are probably within a factor of 10x, i.e., a few bits of 
key size.

So we're close to a nice round figure... 2^32 trials per mm2-second. Now  
you just have to find out how many mm2 of silicon the attacker is going to 
commit to decrypting your file! But obviously that's not the real metric, 
in large systems power and cooling is the limiting factor. How big of an 
air conditioner will he use?

Looking up a random modern Intel chip (Core i5-650 4M Cache, 3.20 GHz), it 
has a die size of 81 mm2 and a max TDP of 73 W. A recent Nvidia chip (GTX 
480) is 529 mm2 and said to be 250W TDP. The bruteforce algorithm need not 
spend any time at all waiting for data, so it seems like it could easily be 
pushing the limits of power density. 1 W per mm2 seems like a reasonable 
guess, but unless the data center will be built underwater you could 
probably double it to account for the cost of heat removal.

Which neatly fits 2^32 trials per watt-second. A real engineer would  
probably design the chips to minimize energy-per-trial, but I think our  
estimate is probably still within an order of magnitude or two.

Last I checked, in the US electric power is around $0.07 per kWh in areas 
considered "cheap". So each trial costs $4.53eb18 in electric power.

For an 64-bit key, you expect the adversary to need 2^63 trials for which 
he might pay a power bill of $597.

For an 80-bit key, you expect the adversary to need 2^79 trials for which 
he might pay a power bill of $2.7M.

For a 128-bit key, you expect the adversary to need 2^127 trials for which 
he might pay a power bill of $11.0e21.

Note that some botnet operators control millions of nodes and they do not 
usually pay their own power bills. But they probably don't have the  
efficiency of our specialized ASIC attacker either.

As others have said, you need a real key derivation function (like PBKDF2) 
with a at least a little added work factor for this. If the password is 
going to be human-chosen or human-remembered it's not likely to have even 
this much entropy in practice.

- Marsh
_______________________________________________
cryptography mailing list
cryptography at randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE





More information about the cypherpunks-legacy mailing list