Date: Sun, 18 Nov 2012 03:48:08 -0800 From: Colin Percival <cperciva@...snap.com> To: Solar Designer <solar@...nwall.com> CC: scrypt@...snap.com, crypt-dev@...ts.openwall.com Subject: Re: scrypt time-memory tradeoff On 11/18/12 03:38, Solar Designer wrote: > On Sun, Nov 18, 2012 at 03:23:31AM -0800, Colin Percival wrote: >> You get a 2x cost reduction by trading increased time for reduced area (as >> in a previous email) and another 2x reduction by ignoring the initial setup >> (practically speaking) > > Yes, that's what I was thinking. The initial setup time becomes > negligible compared to that of the second phase - or it can even be > fully removed, but that's not optimal in practice because the Salsa20 > core has some area cost too. There's other ways the setup time can be effectively removed too -- use one CPU and O(sqrt(N)) RAM to compute and store H^(sqrt(N) i)(B) for i = 0 .. sqrt(N), then send those values over to a larger die which has sqrt(N) CPUs and O(N) RAM which fills in the full table and then does the phase-2 computation. >> but I never intended to include the setup in my >> area-time bound. > > Oh, that's nice. > > In other words, you could have killed this trade-off (by slightly > different design) and then claim 4x or 2x higher costs (depending on > whether the trade-off was accounted for in the costs or not). Yes, I think so. I liked the ROMix construction because I was able to write a formal proof about its properties; and when I turned it into the scrypt KDF I wanted to minimize the divergence from the proven-secure construction. -- Colin Percival Security Officer Emeritus, FreeBSD | The power to serve Founder, Tarsnap | www.tarsnap.com | Online backups for the truly paranoid
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.