[prev in list] [next in list] [prev in thread] [next in thread]
List: cryptography
Subject: Re: [Cryptography] A modification to scrypt to reduce side channel risk
From: Bill Cox <waywardgeek () gmail ! com>
Date: 2013-12-28 0:23:30
Message-ID: CAOLP8p763gBqz0VjqpesjJrGq2D-1g_ceRuZY9PO2i=L1e+PFg () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
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.
[Attachment #5 (text/html)]
<div dir="ltr"><div>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.<br> </div><div><br></div><div>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.</div> \
<div><br></div><div>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.</div> \
<div><br></div><div>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.</div> <div><br></div><div>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.</div> </div>
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic