Message-ID: <CAOLP8p7v+fha7uzJuEPTJ_BZCKCU6UZ=NdYXf7=-19TaE_LJNQ@mail.gmail.com>
Date: Thu, 6 Mar 2014 09:06:37 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Scrypt can have highest time*average memory cost

I have been using time*cost as my basic measure of memory-hard KDF
performance, but up to now I've only used peak memory usage rather
than average.  Scrypt writes memory in the first loop, then reads
memory in an unpredictable fashion in the second, while I read and
write at the same time until memory is full.  It turns out that the
Scrypt technique can achieve a higher average time*memory cost for the
entire run, by 50%, even if both ways result in the same peak memory
usage.

Peak memory usage is a very important number, but if an attacker is
using a multi-CPU system with a very large shared memory, then he
probably cares more about average memory than peak.

The advantage of reading and writing at the same time is I can make
each hashed block dependent on two prior blocks, rather than 1, as
with Scrypt.  This helps reduce time-memory trade-off options for an
attacker, which is especially important given that an attacker can
gain a 4X reduction in time*memory cost by using a small fraction of
the memory and doing recomputations as needed.  So, I think that
reading and writing at the same time is preferable.

Can anyone think of a way to fill memory with mostly writes and few
reads in a way that still creates enough data dependencies to fight
off TMTO attacks?  For example, with an unpredictable loop, I might be
able to do small block reads and hash them to create much larger
blocks.  For a cache-timing resistant loop, an attacker could just
keep the memory which is read and discard the rest.

Bill

Powered by blists - more mailing lists