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.