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.