[Cryptography] A modification to scrypt to reduce side channel risk

[Bill Cox]

I've come to the conclusion that bad things happen when we don't hash
memory based on the password.  From what I can tell, any system that uses
only the salt to determine the order of blocks to hash into the derived key
will not be memory-hard.

Here's well understood "attack" on scrypt (not really an attack), implied
in the original paper:  Instead of having external RAM, an attacker could
build a chip with just enough internal memory for the state of the RNG.  In
the case of scrypt, that's 2KB.  Whenever they need a block at a particular
position, the chip resets the RNG state to the beginning, and computes all
the way up through memory to the needed block.  Thus, they can perform the
KDF with almost no memory, but it would take a very long time, which is
obviously bad for the attacker.  Now consider a chip with say 100 such
units.  It takes 100X more chip area and memory, and runs 100X faster, but
it's still probably slower than just having the full external RAM.  Part of
the reason is that the attacker cannot predict what address will be read
next from RAM, and so his 100 units sit idle waiting for the hashing of the
current block to complete.  This is expected from a memory-hard KDF.  The
attacker can increase memory to reduce runtime, reduce memory to save on
cost, but it will increases his runtime.  I'm sure there is a sweet spot
when attacking script where instead of storing hashed memory off chip, an
attacker would store 2KB RNG states, but this is expected behavior that in
no way violates the proof of scrypt's memory-hardness.

Now consider the case where the attacker can predict the order memory will
be read before the blocks are read and hashed into the derived key.  This
is the case in any system that relies only on the salt to determine the
hashing order.  Instead of having 100 generators sitting idle until the
next address is known, all 100 can be working in parallel trying to get to
the address in memory where they need to be at some point in the future.
 This reduces the time of the attack considerably, violating the definition
of a memory hard KDF.

There still may be ways to mitigate timing attacks, such as figuring out
what blocks might still be partially cached and avoiding those.  However, I
see no way around having the user's password involved in computing memory
addresses.  I think the password simply needs some decent hashing before
it's used to compute addresses.

As for scrypt, the only weakness I can point to is doing only one round of
SHA256 on the user's password before using this intermediate value to
compute data stored to memory.  I would prefer 2048, so we could start with
what is normally considered decent security and improve from there,
hopefully reducing some of the fear of this new algorithm.  As for
improvements, I think we could have a much faster RNG than salsa20/8, which
would still be secure for this application, but I can't fault the scrypt
author for choosing instead a proven known algorithm.  His design rocks.  I
only really want to change to replace "1" with "2048" on one line, and
that's mostly just to squelch nay-sayers.  That's pretty amazing, IMO.  I'm
still playing with speed improvements, and I'm making some, but I'm having
to drop Salsa20/8 and am using a simpler algorithm that people will likely
not want to risk using.  I can't blame people for paranoia in cryptography.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131227/a38741f0/attachment.html>