Re: scrypt time-memory tradeoff

[Colin Percival <cperciva@tarsnap.com>]

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