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.