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

Nico Williams nico at cryptonector.com
Thu Jun 9 18:22:59 EDT 2011


On Thu, Jun 9, 2011 at 4:53 PM, Solar Designer <solar at openwall.com> wrote:
> On Thu, Jun 09, 2011 at 04:22:16PM -0500, Marsh Ray wrote:
>> 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.53e???18 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.
>
> That's scary.  Even more so if you actually multiply by $0.07, which
> gives $42.

Indeed.

> This means that for relatively small key size like this, the primary
> cost for using an ASIC implementation is in creating that implementation
> and in making it solve the specific task, not in electricity.
>
> It also means that a good KDF should not be limited to using iterations,
> but should also consume much die area - like scrypt does (requiring RAM)
> or/and through lots of parallelism (in one KDF instance).  If
> implemented in software (on CPU or GPU), it should more fully use the
> resources of that computer system (CPU/GPU execution units, RAM).

We've long known that for keys derived from passwords and passphrases
all the security resides in the KDF unless we let or tell the user to
write the passphrase down.

The KDF needs to have a short run time on mobile devices, which are at
the lower end of end-user computational power, but anything that
amounts to a millisecond of extra compute power for the attacker
greatly slows them down (from 2^32 keys per watt-second to 2^10 keys
per-watt-second, so, six orders of magnitude).  That's still a bit
scary if the keys need to be secure for a long time, or if we want KDF
run times in the <100ms range on mobile devices, so the KDF had better
be really resistant to optimization (thanks for the reference to
scrypt!).  And maybe we should aim for KDF run times in the seconds on
mobile devices.  Also, note that mobile devices typically have
relatively little free memory; to use much memory for scrypt might
require that the OS be able to kill or swap other processes out to
flash, and that might be a tall order.

And for remote password-based authentication we'll want to start using
ZKPPs or smartcards.

Nico
--



More information about the cryptography mailing list