Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 31 Dec 2013 08:56:58 +0400
From: Solar Designer <solar@...nwall.com>
To: crypt-dev@...ts.openwall.com
Subject: Re: using scrypt for user authentication

Colin, all -

We got a curious new data point to add to this old thread:

On Sun, Sep 02, 2012 at 07:13:37PM +0400, Solar Designer wrote:
> We got a curious real-world data point due to Litecoin using scrypt with
> (2^10, 1, 1), which corresponds to 128 KiB.
[...]
> Curiously, bcrypt uses only 4 KiB, which is less than Litecoin scrypt's
> 128 KiB.  However, bcrypt's use of L1 (rather than L2) cache on CPUs
> provides an advantage to CPU implementations, and its access pattern
> (random 32-bit accesses) makes attempts to use L2+ cache or RAM (for
> many concurrent instances of bcrypt) very inefficient.  On GPUs, best
> performance at bcrypt is currently achieved by using local memory (very
> limited in size) and keeping many of the execution units idle (since
> there's not enough local memory to use them all).  Trying to use global
> memory (partially cached) slows things down.  (A local+global mixed
> implementation might be a little bit faster than local alone, though.
> This was briefly discussed on john-dev.)  Credit: the experiments with
> bcrypt on GPU were performed by Sayantan Datta.
> 
> It is plausible that scrypt at 1 MiB is comparable to bcrypt in terms of
> attacks with GPUs, but this is not certain.  scrypt at 1 MiB might as
> well be somewhat weaker than bcrypt in this respect.
> 
> Overall, I think scrypt at 1 MiB is not a good replacement for bcrypt
> currently.  We need bigger settings.  (And if we go for much bigger
> settings, this may imply a need to limit concurrency when scrypt is used
> on authentication servers.)

YACoin (or YAC for short), a new alt-coin, is using revised scrypt (with
Keccak and ChaCha20 instead of SHA-256 and Salsa20) with N increasing
over time (it's tied to real time).  Currently YAC is at N=2^15
(Nfactor=14), which means 4 MiB, and here's how it will be increasing:

https://bitcointalk.org/index.php?topic=206577.msg2162620#msg2162620

At the current 4 MiB, YAC is about as fast to mine on CPU as on GPU:

http://yacoinwiki.tk/index.php/Mining_Hardware_Comparison

In June 2014, we'll see numbers for 8 MiB there.  Indeed, we may run
benchmarks now, but maybe implementations optimized/tuned for the
increased N will appear along with the monetary incentive.  And yes, YAC
is worth some Bitcoins now, which are worth some dollars.

So it appears that in terms of attacks with current GPUs scrypt at 4 MiB
is comparable to bcrypt at 4 KiB.  In other words, defensive use of
scrypt needs 1000x more memory to provide same security against GPUs.

That's with r=1 and p=1.  With higher r, scrypt might be more
GPU-friendly (larger sequential accesses to off-chip memory).

And yes, GPUs still provide no speedup over CPUs at bcrypt cracking,
neither in absolute terms, nor per-Watt:

http://www.openwall.com/presentations/Passwords13-Energy-Efficient-Cracking/

These results (for GPUs) have been confirmed by bcrypt implementations
in hashcat and hashkill (by their respective authors), besides in JtR.

Alexander

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ