[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20130317040321.GA4848@openwall.com>
Date: Sun, 17 Mar 2013 08:03:21 +0400
From: Solar Designer <solar@...nwall.com>
To: crypt-dev@...ts.openwall.com
Subject: scrypt TMTO defeater
Colin, Anthony, all -
The message I am following up on is the one where I described an attack
on Anthony's scrypt time-memory tradeoff defeater:
http://www.openwall.com/lists/crypt-dev/2012/09/10/3
I'll skip most of its content now, and only comment on my attempt to
actually implement a time-memory tradeoff defeater of this sort (despite
of the possible attack).
On Mon, Sep 10, 2012 at 06:27:44AM +0400, Solar Designer wrote:
> 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"):
[... lots of text skipped ...]
> 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).
So I've tried to implement an enhancement like what I described above:
writing not only to V_j, but also to V_i (with another value).
Unfortunately, it turns out that BlockMix's shuffling(*) gets in the way
of efficient implementations, and _possibly_ the inefficiency mostly hurts
cleaner CPU code, as opposed to hacks and ASICs. Specifically, when the
V element we write into is or might be the same as V_j, in a clean
implementation we have to postpone those writes until the BlockMix
completes, and this means re-reading the same values from memory
(hopefully, from L1 cache) rather than simply storing register values
into two locations at once (such as X and V_j). In order to do the
latter without introducing extra checks, I had to limit the writes to
elements that are definitely not same as V_j; I chose (~j & (N - 1)) for
their indices.
(*) which I am still looking for an explanation of:
http://mail.tarsnap.com/scrypt/msg00059.html
I've attached a diff between two of my code revisions. escrypt-23
implements the official scrypt, with only some optimizations to
crypto_scrypt-sse.c. escrypt-24 renames the function to escrypt and
adds a Boolean defeat_tmto parameter. When it is zero, the function
returns the same values as the official scrypt does. When it is
non-zero, the trivial TMTO defeater as described above is enabled.
It is implemented in all three versions of the code (-ref, -nosse,
-sse), although only the -sse revision is (partially) optimized (reuses
register values instead of copying memory). (Checking defeat_tmto
outside of the loop and then using one of two specialized loop versions
is an obvious further optimization.)
I may consider adding a TMTO defeater by means of changes to the first
loop as well - an approach needed for my "ROM-port hard functions" idea
anyway, because the ROM can't be written to in the second loop.
I'd appreciate any comments.
For testing:
MD5 of output of "tests" with defeat_tmto = 0:
4455b1ce0529e7f877de53f24ff78bec
MD5 of output of "tests" with defeat_tmto = 1:
43f6df099d2d6dec402960ae41ee1d08
Alexander
View attachment "escrypt-defeat-tmto.diff" of type "text/plain" (12660 bytes)
Download attachment "escrypt-0.0.23.tar.gz" of type "application/x-gzip" (10127 bytes)
Download attachment "escrypt-0.0.24.tar.gz" of type "application/x-gzip" (10329 bytes)
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.
