3 ms·

So I reckon he won't use GPUs then, eh? Note that the defender pays a cost for this too though. Where he could be happily running PBKDF2 or Bcrypt in multiple

So I reckon he won't use GPUs then, eh? Note that the defender pays a cost for this too though. Where he could be happily running PBKDF2 or Bcrypt in multiple Apache process on his multicore servers, Scrypt is going to completely trash the L2/L3 caches and saturate the memory bus and make everything else on the server run like a dog. Scrypt is operating as designed, of course, but it raises the question of whether or not a defender with a busy website on a farm of multicore servers would be able to configure his work factor as high (in terms of single thread benchmark ms) with Scrypt as he would with Bcrypt or PBKDF2.

sirclueless 15y ago
I thought the definition of "better" in this case is that it requires less work to get the same computational strength with scrypt. Are you saying that the memory locality issues that scrypt causes more than cancel out the computational win?
- marshray 15y ago
  In this context, work is computational strength so what we're mainly concerned about is an attacker finding a way to do the task significantly more efficiently than the defender. E.g., if the attacker can evaluate the function with half the cost on his power bill relative to the defender, then that can be thought of as knocking off 1 bit of security off the top. The primary advantage of Scrypt over the others is that it enters a completely pathological memory locality access pattern and stays there for almost the whole function. This works to neutralize the advantage of an attacker who has a custom CPU because he probably can't also develop a custom RAM subsystem to feed it with (at least not one that's many times more efficient than what the defender has in his server). But if you've done any performance tuning on multithreaded code, you know that cache effects caused by memory access patterns very quickly begin to dominate as multiple cores and threads are added. Things that look great in single-threaded benchmarks almost never scale linearly and there's probably nothing that will scale worse on our shared-memory multiprocessors than Scrypt. It's a feature. So the defender (say, a busy website with commodity multicore servers) with Scrypt is likely not going to be able to take as good an advantage of his hardware. He won't be able to crank up the work factor quite as high as he could with Bcrypt or PBKDF2. This may represent an advantage to the attacker, who doesn't have the additional constraint of keeping the response time up on a busy webserver. This attacker's advantage is probably not significant by cryptographic standards (maybe 2 or 3 bits of security lost), but pathological multithreading could represent a big issue operationally. I'm honestly not trying to cast FUD on Scrypt here, I think it's the best function. I'm just saying like everything else multithreaded you really need to benchmark it under real-world conditions.
  - cperciva 15y ago
    scrypt's memory access pattern isn't particularly pathological; it's random, sure, but it reads large blocks. The key issue isn't the design of the RAM subsystem but instead the design of the RAM subsystem -- in particular, making sure the attacker can't "cheat" by using a smaller circuit than the defender.
Xylakant 15y ago
I've yet to see a website that get bogged down with authentication request in normal operation, even if those request measure in the multiples of 10ms. The basic idea with all those "slow" password hashes is that authentication is a pretty rare request compared to all other request. Usually authentication requires a single request, at most a handfull. If you run into trouble with bcrypt/scrypt on your webservers, you're doing things wrong. If you have that many authentication requests, direct them to a dedicated server - you'll be in the league that has a large farm running anyways. Granted, an attacker could use your slow hash for a DOS-attack, but most websites I've seen so far always had some sort of slow operation that was easily exploitable without authentication.
- marshray 15y ago
  OK, but what if you're a web app that specializes in authentication (like, say, an Oath provider) or a database server where the attacker-facing app doesn't use connection pooling? > but most websites I've seen so far always had some sort of slow operation that was easily exploitable without authentication Yes, but those things are typically easy to optimize or temporarily disable in a hurry once they come under attack. Not so much with authentication.
  - moxie 15y ago
    Yep, I work close to an extremely high traffic OAuth endpoint. I think scrypt would probably "cost" a lot more in terms of actual servers required to operate it.
    - cperciva 15y ago
      scrypt is tunable; you can make it use as much or as little CPU time as you want. For any particular amount of CPU time, scrypt will give you more security than bcrypt or PBKDF2 would give you for the same amount of CPU time.
      - marshray 15y ago
        Perhaps it's more accurate to measure scrypt in terms of cache misses rather than CPU time? This is a different resource on multicore servers with different performance implications (at least if we're down to counting 3 or 4 bits of security).
moxie 15y ago
I tend to think of this stuff from the cloudcracker.com perspective, which is all about cheap jobs rather than millions spent. I rarely do brute force because, honestly, it's rarely necessary. But the single biggest factor in cloudcracker.com support of a hash format really is its efficiency in GPU space. For instance, right now I'm implementing support for the modern SHA-512 crypt() variation. It doesn't translate well into GPU space at all, which will end up meaning that I can only offer dictionaries that are half a trillion words smaller than formats which are fast on GPUs. So far the data I'm seeing indicates that differences of that scale in dictionary size really do make a difference on the success rate of the job. So for what it's worth, from that perspective, it is a factor.

sirclueless 15y ago

I thought the definition of "better" in this case is that it requires less work to get the same computational strength with scrypt. Are you saying that the memory locality issues that scrypt causes more than cancel out the computational win?

marshray 15y ago
In this context, work is computational strength so what we're mainly concerned about is an attacker finding a way to do the task significantly more efficiently than the defender. E.g., if the attacker can evaluate the function with half the cost on his power bill relative to the defender, then that can be thought of as knocking off 1 bit of security off the top. The primary advantage of Scrypt over the others is that it enters a completely pathological memory locality access pattern and stays there for almost the whole function. This works to neutralize the advantage of an attacker who has a custom CPU because he probably can't also develop a custom RAM subsystem to feed it with (at least not one that's many times more efficient than what the defender has in his server). But if you've done any performance tuning on multithreaded code, you know that cache effects caused by memory access patterns very quickly begin to dominate as multiple cores and threads are added. Things that look great in single-threaded benchmarks almost never scale linearly and there's probably nothing that will scale worse on our shared-memory multiprocessors than Scrypt. It's a feature. So the defender (say, a busy website with commodity multicore servers) with Scrypt is likely not going to be able to take as good an advantage of his hardware. He won't be able to crank up the work factor quite as high as he could with Bcrypt or PBKDF2. This may represent an advantage to the attacker, who doesn't have the additional constraint of keeping the response time up on a busy webserver. This attacker's advantage is probably not significant by cryptographic standards (maybe 2 or 3 bits of security lost), but pathological multithreading could represent a big issue operationally. I'm honestly not trying to cast FUD on Scrypt here, I think it's the best function. I'm just saying like everything else multithreaded you really need to benchmark it under real-world conditions.
- cperciva 15y ago
  scrypt's memory access pattern isn't particularly pathological; it's random, sure, but it reads large blocks. The key issue isn't the design of the RAM subsystem but instead the design of the RAM subsystem -- in particular, making sure the attacker can't "cheat" by using a smaller circuit than the defender.

Xylakant 15y ago

I've yet to see a website that get bogged down with authentication request in normal operation, even if those request measure in the multiples of 10ms. The basic idea with all those "slow" password hashes is that authentication is a pretty rare request compared to all other request. Usually authentication requires a single request, at most a handfull. If you run into trouble with bcrypt/scrypt on your webservers, you're doing things wrong. If you have that many authentication requests, direct them to a dedicated server - you'll be in the league that has a large farm running anyways. Granted, an attacker could use your slow hash for a DOS-attack, but most websites I've seen so far always had some sort of slow operation that was easily exploitable without authentication.

marshray 15y ago
OK, but what if you're a web app that specializes in authentication (like, say, an Oath provider) or a database server where the attacker-facing app doesn't use connection pooling? > but most websites I've seen so far always had some sort of slow operation that was easily exploitable without authentication Yes, but those things are typically easy to optimize or temporarily disable in a hurry once they come under attack. Not so much with authentication.
- moxie 15y ago
  Yep, I work close to an extremely high traffic OAuth endpoint. I think scrypt would probably "cost" a lot more in terms of actual servers required to operate it.
  - cperciva 15y ago
    scrypt is tunable; you can make it use as much or as little CPU time as you want. For any particular amount of CPU time, scrypt will give you more security than bcrypt or PBKDF2 would give you for the same amount of CPU time.
    - marshray 15y ago
      Perhaps it's more accurate to measure scrypt in terms of cache misses rather than CPU time? This is a different resource on multicore servers with different performance implications (at least if we're down to counting 3 or 4 bits of security).

moxie 15y ago

I tend to think of this stuff from the cloudcracker.com perspective, which is all about cheap jobs rather than millions spent. I rarely do brute force because, honestly, it's rarely necessary. But the single biggest factor in cloudcracker.com support of a hash format really is its efficiency in GPU space. For instance, right now I'm implementing support for the modern SHA-512 crypt() variation. It doesn't translate well into GPU space at all, which will end up meaning that I can only offer dictionaries that are half a trillion words smaller than formats which are fast on GPUs. So far the data I'm seeing indicates that differences of that scale in dictionary size really do make a difference on the success rate of the job. So for what it's worth, from that perspective, it is a factor.