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@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