Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20120807104645.2EC6.0@paddy.troja.mff.cuni.cz>
Date: Tue, 7 Aug 2012 10:54:36 +0200 (CEST)
From: Pavel Kankovsky <peak@...o.troja.mff.cuni.cz>
To: crypt-dev@...ts.openwall.com
Subject: Re: using scrypt for user authentication

On Thu, 12 May 2011, Solar Designer wrote:

> 1. Use such settings that scrypt doesn't use more than, say, 1 MB of
> memory.  Is 1 MB way too low?  Is scrypt at this setting significantly
> better than bcrypt or not?

According to Colin Percival's BSDCan2009 paper the amortized cost (chip 
area times time) of scrypt is (at least) 1024 N^2 r^2 p s t where 
parameters N and r determine the size of memory (1024 N r + O(r) bits), p 
is a paralellization parameter and s and t are unit costs of storage and 
computation.

The paper claims the cost of scrypt with (N, r, p) = (2^14, 8, 1) is 
approximately 35 times higher than the cost of bcrypt with cost = 11 while 
the time needed to compute both of those functions on a general-purpose 
CPU is comparable. These ratios are probably quite stable even when
hardware evolves and unit costs (s, t) change.

The aformentioned parameters (N = 2^14, r = 8) correspond to 16 MiB of RAM 
if my calculation is correct. In order to reduce memory consumption to
1 MiB you would have to reduce the product of N and r 16-fold. p can be 
increased from 1 to 16 now but the overall cost would still be reduced by 
a factor of 16 because its dependence on N and r is quadratic.

Such a change would degrade the strength of scrypt almost to the level of 
bcrypt. On customized hardware. On the other hand, it would probably use 
enough memory and memory bandwidth to choke GPUs and other hardware that 
has not been explicitly designed to crack it.

-- 
Pavel Kankovsky aka Peak                          / Jeremiah 9:21        \
"For death is come up into our MS Windows(tm)..." \ 21st century edition /




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.