[148784] in cryptography@c2.net mail archive
Re: [Cryptography] A modification to scrypt to reduce side channel
daemon@ATHENA.MIT.EDU (Bill Cox)
Fri Dec 27 22:19:39 2013
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <CAOLP8p6LArV+i_466TTrwtQ5MD5uw4-24pkH6nceidbLEYGS-g@mail.gmail.com>
Date: Fri, 27 Dec 2013 19:23:30 -0500
From: Bill Cox <waywardgeek@gmail.com>
To: Cryptography <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============0941300597761767693==
Content-Type: multipart/alternative; boundary=047d7b414f405ca01404ee8d38a8
--047d7b414f405ca01404ee8d38a8
Content-Type: text/plain; charset=ISO-8859-1
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.
--047d7b414f405ca01404ee8d38a8
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>I've come to the conclusion that bad things happe=
n when we don't hash memory based on the password. =A0From what I can t=
ell, any system that uses only the salt to determine the order of blocks to=
hash into the derived key will not be memory-hard.<br>
</div><div><br></div><div>Here's well understood "attack" on =
scrypt (not really an attack), implied in the original paper: =A0Instead of=
having external RAM, an attacker could build a chip with just enough inter=
nal memory for the state of the RNG. =A0In the case of scrypt, that's 2=
KB. =A0Whenever 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. =A0Thus, they can perform the KDF with almost no memo=
ry, but it would take a very long time, which is obviously bad for the atta=
cker. =A0Now consider a chip with say 100 such units. =A0It takes 100X more=
chip area and memory, and runs 100X faster, but it's still probably sl=
ower than just having the full external RAM. =A0Part 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 com=
plete. =A0This is expected from a memory-hard KDF. =A0The attacker can incr=
ease memory to reduce runtime, reduce memory to save on cost, but it will i=
ncreases his runtime. =A0I'm sure there is a sweet spot when attacking =
script where instead of storing hashed memory off chip, an attacker would s=
tore 2KB RNG states, but this is expected behavior that in no way violates =
the proof of scrypt's memory-hardness.</div>
<div><br></div><div>Now consider the case where the attacker can predict th=
e order memory will be read before the blocks are read and hashed into the =
derived key. =A0This is the case in any system that relies only on the salt=
to determine the hashing order. =A0Instead of having 100 generators sittin=
g 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. =A0This reduces the time of the attack considerably, violati=
ng the definition of a memory hard KDF.</div>
<div><br></div><div>There still may be ways to mitigate timing attacks, suc=
h as figuring out what blocks might still be partially cached and avoiding =
those. =A0However, I see no way around having the user's password invol=
ved in computing memory addresses. =A0I think the password simply needs som=
e decent hashing before it's used to compute addresses.</div>
<div><br></div><div>As for scrypt, the only weakness I can point to is doin=
g only one round of SHA256 on the user's password before using this int=
ermediate value to compute data stored to memory. =A0I would prefer 2048, s=
o we could start with what is normally considered decent security and impro=
ve from there, hopefully reducing some of the fear of this new algorithm. =
=A0As for improvements, I think we could have a much faster RNG than salsa2=
0/8, which would still be secure for this application, but I can't faul=
t the scrypt author for choosing instead a proven known algorithm. =A0His d=
esign rocks. =A0I only really want to change to replace "1" with =
"2048" on one line, and that's mostly just to squelch nay-say=
ers. =A0That's pretty amazing, IMO. =A0I'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. =A0I can't blame people for paranoia in cryptography.</div>
</div>
--047d7b414f405ca01404ee8d38a8--
--===============0941300597761767693==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============0941300597761767693==--
