[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <20121116042112.GA12087@openwall.com>
Date: Fri, 16 Nov 2012 08:21:12 +0400
From: Solar Designer <solar@...nwall.com>
To: Colin Percival <cperciva@...snap.com>
Cc: crypt-dev@...ts.openwall.com
Subject: revising scrypt to use more memory per time
Colin, all -
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. It may amount to
revising the first loop such that on one hand all intermediate values
still have to be computed, but on the other it is no longer practical to
compute one V element from another. I think this may be accomplished by
storing H2(X) instead of X itself, where H2() is some cryptographic hash
function different from H() (e.g., it can be H() applied to slightly
different input, such as with shuffling or with a constant XOR'ed in).
What do you think?
BTW, I am currently posting messages on scrypt proper to the scrypt
list, but on possible obviously incompatible changes to scrypt to this
list. Is this fine, or should I move all scrypt-related discussions,
including of obviously incompatible and major changes, to the scrypt
list? I guess that at some point the proposed changes might be so
invasive that there won't be much left from the original scrypt, making
this obviously off-topic for the scrypt list. ;-) So compatibility with
official scrypt is where I draw the line now.
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.
