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

Solar Designer solar at openwall.com
Thu Jun 9 20:34:18 EDT 2011


On Thu, Jun 09, 2011 at 05:22:59PM -0500, Nico Williams wrote:
> 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).

I guess Marsh's 2^32 keys per watt-second assumed a fully-pipelined
implementation of the cipher providing one output per clock cycle.
This can't be achieved in software, unless the CPU provides such an
instruction (and thus contains such an execution unit in hardware).

On a typical CPU, it'll take many cycles for one computation of AES (or
whatever we'd use in our KDF).  Thus, with stretching to one
millisecond on a CPU, we won't slow down an attacker's ASIC
implementation by six orders of magnitude (although we can get somewhat
close to that).

This is where specialized instructions help, such as AES-NI:

http://en.wikipedia.org/wiki/AES_instruction_set

These are not that fast yet, but it does make sense to build a KDF
around them, which is something I've been considering doing.

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

Right.  scrypt with something like 32 MB already makes sense, though.

> And for remote password-based authentication we'll want to start using
> ZKPPs

This doesn't prevent offline password guessing attacks after a
(temporary) server compromise.

I think there's still a need for better password hashing on servers.

Thank you for your comments.

Alexander



More information about the cryptography mailing list