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
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.