[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20120910022744.GA15963@openwall.com>
Date: Mon, 10 Sep 2012 06:27:44 +0400
From: Solar Designer <solar@...nwall.com>
To: crypt-dev@...ts.openwall.com
Subject: Re: using scrypt for user authentication
On Sun, Sep 02, 2012 at 07:13:37PM +0400, Solar Designer wrote:
> We might also want to have a tradeoff-defeating variation of scrypt, as
> Anthony Ferrara suggested or otherwise.
For context, here's Anthony Ferrara's comment that I am referring to:
http://drupal.org/node/1201444#comment-4675994
Here's an attack on Anthony's tradeoff defeater ("simply writing to V_j
in the second loop"):
Assume that we don't want to use the tradeoff to its fullest, but rather
just halve our memory needs. Without the tradeoff defeater, this is
accomplished by storing every other V_j in an array that is twice
smaller than original. The odd-indexed V_j's are then recomputed as
needed from the preceding values that we did store.
Now, with the tradeoff defeater we can't recompute these values like
that because the preceding value might have been modified by prior
iterations of the second loop. Or can we? Actually, quite often we
can: by the time the second loop terminates, it will have modified only
about 63% of V elements. And only 39% when we're at N/2 iterations.
Of course, "quite often" is not sufficient for proper computation of the
entire scrypt, so we do need to store the entire V array (not just its
half) somewhere. However, we may be able to arrange things such that
one half of V is "hot" (accessed more frequently) and the other is
"cold" (accessed less frequently). The other half may then be stored in
slower memory (e.g., off-chip).
Similarly, we can't store odd-indexed modified V_j values into the hot
half (so we'll have to store/load them from the cold one). Or can we?
Actually, we can, by agreeing that the hot half stores either of the
two values in each element (and the cold half stores the other).
Overall, we need two one-bit flags per element in the hot half, or one
extra bit per V element on average (two for the hot half and none for
the cold half). The flags themselves need to be in hot memory. Yet our
overall hot memory needs have almost halved, like they would without the
tradeoff defeater.
The possible flag values may be:
00 - original even-indexed value from the first loop is stored
01 - modified even-indexed value is stored (can't use for recomputation)
10 - odd-indexed value is stored (the even-indexed one is in cold)
Does this mean that Anthony's tradeoff defeater is not worthwhile? Not
quite. The cold memory is nevertheless accessed pretty often - just not
as often as the hot portion. So there is some reduction in attack speed
due to the defeater even in this special case. Then, if we try to
reduce our hot memory needs by more than a factor of 2, the corresponding
revisions of the attack described above become a lot less efficient
(mostly in terms of frequency of accesses to the cold portion).
Yet we could enhance the tradeoff defeater to make the attack less
efficient: write into more than one V element per loop iteration and/or
write into such V elements that more of them are written to (perhaps
100% instead of just 63% by loop end).
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.
