Hacker News Reader

Comment by derefr | Hacker News Reader

> Scrypt is ... memory hard

Haven't seen the answer to this: does scrypt being "memory hard" imply that you'll need a ton of RAM for your server if you get lots of users logging in concurrently?

View on HN

Not really. In the scrypt paper, cperciva recommends parameters that allow it to do a single password hash in 64 ms, and in the process use only 4k of RAM. Nowadays, as processors are faster and ram is cheaper, you'd probably want to up the parameters a bit, so that the encryption time will be similar (between 50-100 ms) on modern hardware, and the RAM usage will scale proportionally (probably 128k, based on the ratio of RAM prices between 2002 and now). That means that you would be able to handle 10-20 logins per second per core, using no more than 2.5 MB in the process (if they were all run in parallel on separate threads and so all of that memory was needed at once; that's obviously a worst case, most likely they would be scheduled more sequentially and use proportionally less RAM as you would free the memory after finishing an encryption). On a 12 core machine, you might wind up using 30 MB at at time, to support 240 logins per second.

If you need to handle 240 logins per second (which presumably means many many more requests per second, as there are usually many requests per login), 30 MB of RAM is the least of your worries.

Note that these numbers are simply extrapolations from the ones in the original scrypt paper, I haven't actually tried this on modern hardware. Regardless, there are parameters that allow you to trade off CPU time and RAM usage, so you can tweak it to provide the level of performance that you require (with the understanding that the faster it is and less RAM it uses, the faster cracking it would be).

> If you need to handle 240 logins per second (which presumably means many many more requests per second, as there are usually many requests per login), 30 MB of RAM is the least of your worries.

Well, if you have a large system of nodes, and until now you arranged things as an SOA where there's one node-cluster in particular that serves as an authentication service, doing all the hashing and table-lookup and comparison, and handing out session tokens for your other services to use--then with scrypt, that auth service will now be have the combined "memory hard"ness of every user's login requests on it for your entire system.

With bcrypt, that level of CPU+memory load isn't so bad--but with scrypt, I think I'd think about pushing the hashing step into the client library part of that service's API, before the RPC call, so that the load gets distributed throughout the system back to where it's being "spent."

In this case, it means that lots of memory accesses are required in mostly random order. This makes parallelizing on GPU hardware much more difficult than something like an MD5 or SHA hash, which don't require much memory access during the computation.

This also boosts the cost of making dedicated cracking hardware (ASIC or FPGA type hardware)

I'm having a hard time finding actual memory usage of a single password verification though.

After a bit more reading just now, it looks like you can also adjust the memory-work-factor of scrypt as well, which doesn't appear to be available for bcrypt (very unsure on this one though, please dont' take my word on it).

Does anybody out there have a good side-by-side comparison of practicalities like "memory usage", "flexibility", "can it be parallelized on CPU/GPU/FPGA/ASIC" and so on across all the popular hashing setups?

Reply on news.ycombinator.com