[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20121117110655.GA18313@openwall.com>
Date: Sat, 17 Nov 2012 15:06:55 +0400
From: Solar Designer <solar@...nwall.com>
To: Colin Percival <cperciva@...snap.com>
Cc: crypt-dev@...ts.openwall.com
Subject: Re: revising scrypt to use more memory per time
On Fri, Nov 16, 2012 at 08:21:12AM +0400, Solar Designer wrote:
> Besides possibly reducing the Salsa20 rounds count (which has the
> side-effect of reducing scalability for concurrent instances on
> multi-CPU systems), what do you think of reducing the iteration count of
> the second loop in SMix?
>
> Having it run for exactly N iterations appears to be arbitrary. At N,
> it uses about 63% of V elements. At e.g. N/16, it'd use about 6% of V
> elements - but the total running time of scrypt will be almost twice
> lower, thereby letting us use a twice higher N. So for the same running
> time the absolute number of N elements accessed by SMix's second loop
> would reduce by about a factor of 5 (63% to 12% of original N), but the
> memory usage would be doubled. Sounds like a good trade-off to me.
> In fact, we could probably take it further: as long as it's not known in
> advance which V elements will be needed, the attacker has to either
> consume memory to store them all or recompute them as needed from the
> elements that the attacker does store - the same TMTO that scrypt has in
> its original design.
>
> A drawback is that defeating this TMTO becomes harder.
[...]
Here's another drawback: the portion of scrypt run time that is
potentially bound by sequential memory writes (vs. random reads as the
second loop uses) increases when we decrease the second loop's iteration
count. Thus, an attacker who has e.g. high bandwidth external storage
with large block size will benefit from this change by us.
With this in mind, maybe going for N/16 and further is not great, and we
should stay e.g. at N/4 if we do reduce the second loop's iteration
count at all.
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.
