10

If I understand correctly, according to this: http://blog.ircmaxell.com/2014/03/why-i-dont-recommend-scrypt.html, looks like the attacker can just create an optimimized version of scrypt that produce the same ouput with extremely high effiency (e.g. with N= 2^14, p = 8, r = 1, requires only 1KB instead of 16MB to run, while increase CPU work factor by only N/2).

dnang
  • 645
  • 2
  • 6
  • 10

2 Answers2

25

The short answer is : no. That is not what I said, nor what I implied.

Using the tradeoff that I identified and talked about, you can trade memory for CPU time. So yes, you can reduce a particular derivation from 16MiB to 8KiB (approximately). However doing so will require several orders of magnitude more logic to be executed by the CPU. Some efficiency is gained by cache locality, but in general, it should be much slower. (on average, about 8,000 times slower than the 16MiB version, but as much as 16,000 times slower, depending on the exact random distributions of the algorithm).

There is a more interesting alternative though. My attack was an all-or-nothing bais. Basically, completely eliminate the V array, at the cost of increasing complexity. But you can make a more nuanced tradeoff. You can cut the array in half, and re-compute every-other value. Or cut it to every third value. Trading off storage space for CPU space. But at a varied degree. This is commonly referred to as a TMTO defeater (Time-Memory-TradeOff Defeater).

I did a more thorough analysis, including a proposed fix on this thread. It's worth noting that at least one of the proposals for the Password Hashing Competition uses my augmented algorithm.

So no, scrypt is still incredibly strong. And for its primary use case (as a KDF), it's quite a bit better than the alternatives.,

The point I was trying to make with my post, is that when not tuned optimally (used with improper settings) or with very fast settings, it can be significantly weaker than existing algorithms. Specifically for password storage. Where you know the result, and are looking for the source material (password).

ircmaxell
  • 1,416
  • 12
  • 16
  • 1
    Excellent work. Consider advising the https://wiki.ciphershed.org/Audit team of the sensitivity of your findings, they intend to use scrypt – Microsoft Developer Nov 27 '14 at 23:53
  • Although something like scrypt may make it harder to use today's off-the-shelf hardware to attack many passwords in parallel, hardware built for the purpose of cracking it could still achieve more performance per unit cost than commodity off-the-shelf hardware in production machines. An approach I've thought would seem better would be to design a password hash to benefit from GPU acceleration, such that a production machine with a GPU could use a "stronger" hash than would otherwise be possible. A commodity GPU can perform more operations per second per dollar than an FPGA, so why not... – supercat Jul 13 '15 at 21:07
  • ...have the "good guys" take advantage of that when hashing passwords? – supercat Jul 13 '15 at 21:08
2

Note that scrypt is vulnerable to Timing Attacks: Issue #18 · pbhogan/scrypt, which means that an attacker who has some access to the host you're hashing passwords on has some additional ways to figure the passwords out. So it isn't broken, but has disadvantages compared to e.g. bcrypt.

nealmcb
  • 20,544
  • 6
  • 69
  • 116
  • Side channels tend to be properties of an implementation rather than properties of an algorithm. In what way is *scrypt* vulnerable to timing attacks, as opposed to a particular implementation, or perhaps any naive implementation? – Gilles 'SO- stop being evil' Aug 10 '16 at 20:10
  • 1
    Good point and good question. I hope that the answers are at the [referenced paper](http://eprint.iacr.org/2013/525.pdf). I see e.g. "*As its core, scrypt uses the sequentially memory-hard function ROMix*" and "*Unfortunately, ROMix is vulnerable against cache-timing attacks, due to its password-dependent memory-access pattern.*" – nealmcb Aug 10 '16 at 21:28