[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <50A8CAF8.9080304@tarsnap.com>
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.
