Message-ID: <20140110103050.GA29555@openwall.com>
Date: Fri, 10 Jan 2014 14:30:50 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Cc: Anthony Ferrara <ircmaxell@...il.com>
Subject: Re: [PHC] scripting memory (not so) high

On Fri, Jan 10, 2014 at 09:35:10AM +0000, Peter Maxwell wrote:
> There's also going to be an absolute limit to how much memory can be used.
>  In many of my own setups the php memory limit is sitting somewhere between
> 64Mb and 128Mb, although sometimes a fair bit higher, e.g. I think Magento
> tends to need nearer 512Mb irrc.
> 
> However, and this is the caveat, there's going to be a significant
> proportion of that already used.  So for a portable implementation of a
> memory-hard KDF we may be talking ~15Mb that can actually be used.

Yes.  I wish we could get anywhere close to numbers like that in PHP,
while retaining reasonable running time.

> In terms of performance, PHP will be not too bad

It is not too bad in terms of performance for SHA-512, but it is in
terms of limiting us to this primitive.  Specifically, bcrypt-like small
random accesses to a smaller portion fitting in L1 cache are way too
slow to do in PHP, yet would be needed for GPU resistance at small
memory sizes like 1 MB or less.

> but there is always the
> option of coding the scheme as an extension, i.e. in C.

If we stay with pure SHA-512 for the only required primitive, in order
to be scripting language friendly, then such a native extension would
provide only a ~2x to 3x speedup currently (with 3x only possible if we
were careful to include sufficient parallelism, having considered the
tradeoff that this involves).  Yet this may be done.

> I'm not sure what
> the score is going to be with other scripting languages or if people are
> intending on having things run on mobile devices.

I think scripting language friendliness is primarily for servers and for
JavaScript.

In JavaScript, there's probably no advantage to using SHA-512 vs. the
smaller random accesses I mentioned above, though.

Anyhow, I am not happy with my current results from the smhkdf
experiment, yet I don't think we'll have anything substantially better
soon.  Currently, 1 MB with scrypt and thus almost certainly also with
smhkdf is weaker than bcrypt's 4 KB as it relates to CPU-defense vs.
GPU-attack performance.  For scrypt, these are on par somewhere at above
4 MB (yes, it needs to get 3 orders of magnitude higher than bcrypt's),
as known from YAC mining speeds.

Thus, if native code bcrypt is an option (such as via PHP's
CRYPT_BLOWFISH), I think it should remain preferable for a while longer.

Something along the lines of smhkdf at <= 1 MB may then be a fallback to
be used on PHP 5.1.2 to 5.3.6, as well as when the use of these hashes
is forced for portability to other scripting languages or/and to older
PHP, or for compliance (SHA-512 being NIST-approved, unlike the Blowfish
hack).  I guess e.g. Drupal might prefer having just the SHA-512 based
algorithm for these reasons, even if it's a few times faster to crack
than bcrypt with current GPUs at currently realistic settings.

It is a better fallback than phpass' and Drupal's current iterated
hashing that is not sequential memory-hard at all, but I'm afraid it's
not yet suitable for becoming the new default for all (with bcrypt still
being better as it relates to GPU attacks, which are still more likely
than attacks with ASICs, FPGAs, or many-core CPUs).

Alexander

Powered by blists - more mailing lists