<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>