3 ms·

> By roughly a factor of (5|4000). Do you have this written up anywhere? Link?

dhimes 15y ago
There are a couple of links on this page: http://www.tarsnap.com/scrypt.html http://www.tarsnap.com/scrypt.html
marshray 15y ago
OK, it's in the Scrypt paper. http://www.tarsnap.com/scrypt/scrypt.pdf http://www.tarsnap.com/scrypt/scrypt.pdf Here's my opinion on this: * These numbers are more appropriately expressed exponentially. I.e. "factor of 5" = 2 bits of security. * 2 bits of security is not significant at all. * The Scrypt x5000 seems to only apply when your attacker has access to a chip foundry and it buys you maybe about 12 bits of security against such an attacker. * For comparison, 128 bits of security is often considered a minimum for resisting offline bruteforce attacks (e.g. AES has a 128 bit key). Of course passwords usually don't come anywhere near close to 128 bits of effective security, so 12 bits might make the difference for some of them if you're lucky. * In a sense, table 1 in the Scrypt paper shows that the relative difference between the functions is less significant than even relatively small variations in password strength. When the defender has 100ms of CPU to spend authenticating each password, all three functions compared cost less than $200 to break an 8 letter password and more than $150M to break a 10 character password. * Very few attackers are going to actually spend $M++ trying to break your password (cue XKCD strip). A relevant exception might be botnets, the operators of which don't pay the power bill for their computations. Therefore, I conclude that for most purposes these functions are mostly equivalent and quality-of-implementation and password strength issues dominate in practice.
- JoachimSchipper 15y ago
  You're right, but don't forget Deep Crack. (FPGA-)hardware-based attacks have only become cheaper since then; I would be surprised if the NSA doesn't have a few arrays. (Also, 80 bits is usually enough to withstand attack, no?)
  - marshray 15y ago
    Yep. There are off-the-shelf FPGA arrays available. Still, bad guys would probably find it much cheaper to rent botnet time for a $0.02/(host*day) or whatever the going rate is. A solid 80 bits of security out of any of these functions might turn out to be safe forever. But, in practice, most password databases are going to have some fraction of users choosing passwords straight out of the cracker's dictionary, some fraction that will never ever be cracked, and the smallest fraction being crackable according to the defender's choice of work factor.
    - JoachimSchipper 15y ago
      COPACOBANA cost ~$10 000 and apparently is as fast as 2500 PCs for the DES cracking it's optimized for, so ~$4/PC-work-unit plus insignificant power costs. You'd need to find someone with experience with implementing crypto in hardware, though. On the other hand, botnets risk detection. (If you're buying in bulk, ASICs are cheaper, but few will be willing to pay for that much cracking power.)
      - marshray 15y ago
        Yeah, I suspect it depends on your bad guys (er, sorry, "threat model") whether or not they feel more comfortable trying to buy botnet time or acquire $10,000 worth of FPGAs in an untraceable way. If I were a bad guy, I would prefer to not have a password-cracking special-purpose supercomputer in my possession. (But I'm not a bad guy, and in fact I would love to have a few around the house. :-)
      - mukyu 15y ago
        http://events.ccc.de/congress/2010/Fahrplan/events/4203.en.html http://events.ccc.de/congress/2010/Fahrplan/events/4203.en.h... precis: exhaustive search on DES for $1000 in FPGAs from eBay, 2 years ago DES is in the range of 'costs less than a new phone/iPad' to do an exhaustive search at this point
- cperciva 15y ago
  The Scrypt x5000 seems to only apply when your attacker has access to a chip foundry If your attacker is using GPUs, scrypt probably gives you an even bigger win, due to the compute/memory balance they use.
  - marshray 15y ago
    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.

There are a couple of links on this page: http://www.tarsnap.com/scrypt.html http://www.tarsnap.com/scrypt.html

OK, it's in the Scrypt paper. http://www.tarsnap.com/scrypt/scrypt.pdf http://www.tarsnap.com/scrypt/scrypt.pdf Here's my opinion on this: * These numbers are more appropriately expressed exponentially. I.e. "factor of 5" = 2 bits of security. * 2 bits of security is not significant at all. * The Scrypt x5000 seems to only apply when your attacker has access to a chip foundry and it buys you maybe about 12 bits of security against such an attacker. * For comparison, 128 bits of security is often considered a minimum for resisting offline bruteforce attacks (e.g. AES has a 128 bit key). Of course passwords usually don't come anywhere near close to 128 bits of effective security, so 12 bits might make the difference for some of them if you're lucky. * In a sense, table 1 in the Scrypt paper shows that the relative difference between the functions is less significant than even relatively small variations in password strength. When the defender has 100ms of CPU to spend authenticating each password, all three functions compared cost less than $200 to break an 8 letter password and more than $150M to break a 10 character password. * Very few attackers are going to actually spend $M++ trying to break your password (cue XKCD strip). A relevant exception might be botnets, the operators of which don't pay the power bill for their computations. Therefore, I conclude that for most purposes these functions are mostly equivalent and quality-of-implementation and password strength issues dominate in practice.

JoachimSchipper 15y ago
You're right, but don't forget Deep Crack. (FPGA-)hardware-based attacks have only become cheaper since then; I would be surprised if the NSA doesn't have a few arrays. (Also, 80 bits is usually enough to withstand attack, no?)
- marshray 15y ago
  Yep. There are off-the-shelf FPGA arrays available. Still, bad guys would probably find it much cheaper to rent botnet time for a $0.02/(host*day) or whatever the going rate is. A solid 80 bits of security out of any of these functions might turn out to be safe forever. But, in practice, most password databases are going to have some fraction of users choosing passwords straight out of the cracker's dictionary, some fraction that will never ever be cracked, and the smallest fraction being crackable according to the defender's choice of work factor.
  - JoachimSchipper 15y ago
    COPACOBANA cost ~$10 000 and apparently is as fast as 2500 PCs for the DES cracking it's optimized for, so ~$4/PC-work-unit plus insignificant power costs. You'd need to find someone with experience with implementing crypto in hardware, though. On the other hand, botnets risk detection. (If you're buying in bulk, ASICs are cheaper, but few will be willing to pay for that much cracking power.)
    - marshray 15y ago
      Yeah, I suspect it depends on your bad guys (er, sorry, "threat model") whether or not they feel more comfortable trying to buy botnet time or acquire $10,000 worth of FPGAs in an untraceable way. If I were a bad guy, I would prefer to not have a password-cracking special-purpose supercomputer in my possession. (But I'm not a bad guy, and in fact I would love to have a few around the house. :-)
    - mukyu 15y ago
      http://events.ccc.de/congress/2010/Fahrplan/events/4203.en.html http://events.ccc.de/congress/2010/Fahrplan/events/4203.en.h... precis: exhaustive search on DES for $1000 in FPGAs from eBay, 2 years ago DES is in the range of 'costs less than a new phone/iPad' to do an exhaustive search at this point
cperciva 15y ago
The Scrypt x5000 seems to only apply when your attacker has access to a chip foundry If your attacker is using GPUs, scrypt probably gives you an even bigger win, due to the compute/memory balance they use.
- marshray 15y ago
  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.