Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

As I understand it, the main advantage of bcrypt is stretching so it becomes slower to crack overtime. But, is using a "good enough" algorithm (e.g., SHA-2 family) then stretching until it's slow enough for your liking is pretty much the same as bcrypt?

Note: I understand scrypt is superior but let's assume bcrypt is the best for now.

share|improve this question

migrated from stackoverflow.com Aug 9 '12 at 15:53

This question came from our site for professional and enthusiast programmers.

1  
Why not just use bcrypt? :) There has been some talk about adding scrypt to PHP but the scrypt author himself has said he doesn't consider it mature / well tested enough. –  Leigh Aug 8 '12 at 20:31
    
@Leigh Due to lack of native support in PHP (i.e., you need to use third-party lib or write your own custom function) and I feel lazy to add/include custom functions if the same goal can be achieved with SHA512 multiplied to millions. –  IMB Aug 8 '12 at 20:34
    
what? There is native support for bcrypt. –  Leigh Aug 8 '12 at 22:31
2  
@IMB: Yes, bcrypt is built in. You call crypt with the flag CRYPT_BLOWFISH; it's been in there since PHP 4. –  Billy ONeal Aug 9 '12 at 14:55
1  
@BillyONeal Unfortunately not, while crypt is in PHP 4, blowfish isn't, in the manual it says: 5.3.0 PHP now contains its own implementation for the MD5 crypt, Standard DES, Extended DES and the Blowfish algorithms and will use that if the system lacks of support for one or more of the algorithms. I have tested in PHP 5.2 there is no blowfish support. –  IMB Aug 9 '12 at 15:04
show 2 more comments

2 Answers 2

No, it doesn't work that way. You have to introduce memory in the equation. The whole point of bcrypt and scrypt is that they use a variable amount of memory (that cannot be optimized out) to calculate the final "hash". Often this takes the form of large lookup tables which cannot be inlined because they are accessed pseudorandomly, so you need to store them somehow.

What's the point, you will ask me? Well, look at a standard md5 hash. This requires basically no memory to implement, so you can grab a bunch of FPGA's and GPU's, make a cluster and hash a trillion passwords per second.

Now, look at your md5 variant with iterations. Ok, so now your FPGA's and GPU's have to work harder, but it's still pretty easy to implement - just add a for loop, essentially (and it's easy to change the amount of iterations). You might only be able to hash 20 million passwords a second with your cluster now, great.

Now consider bcrypt/scrypt, and have them set to require, say, 20MB of memory per hash (and be about as expensive as N rounds of md5). You attempt to implement it on your cluster, and.... BOOM! Not enough local memory to perform the hash, because now each hash iteration requires a non-negotiable 20MB of memory, and your GPU/custom chips certainly do not have that amount of memory available to them (for each hash they do in parallel, that is). Your cluster is now essentially useless - total hash rate: 0 hashes per second.

Basically, computational power can be parallelized cheaply and easily, but memory cannot. This is the cornerstone of bcrypt and scrypt. Obviously, they can still be broken by sheer brute force, and you could just use hardware with integrated memory units to circumvent the problem, but it's much harder and much, much more expensive to do so.

So overall, adding more iterations is fun and all, but it only scales linearly. Add twice as many iterations, hash half as much passwords a second. And eventually, the hash will take so long that the legitimate user will start to complain. But if you are clever and instead use the one weakness that current dedicated hardware has, you can completely wipe out a whole level of technology and force your opponents to adapt, which is much more efficient.

Of course, this is a rose-tinted vision of the real world, in practice people are still brute-forcing even those memory-hard hash algorithms, but it really is a significant improvement.

share|improve this answer
1  
bcrypt requires a constant amount of memory, and that amount is pretty small, but still a bit larger than what PBKDF2 requires. –  CodesInChaos Aug 10 '12 at 7:09
    
@CodesInChaos indeed it's scrypt that has the variable amount of memory (the next logical step to bcrypt). I'm using both of them together to save time and space :) –  Thomas Aug 10 '12 at 7:16
add comment

bcrypt operates using the Blowfish block cypher. It does not use any kind of message digest function (such as MD5, SHA1, SHA-256, etc.) internally.

Of course, I think what you really wanted to ask was, "would using a traditional message digest function with some amount of stretching give similar security to bcrypt?", and the answer to that question is probably "no". However, we can't answer that because we don't really know how you would accomplish the stretching. It's probably reasonable to say that stretching in some way would achieve similar security, but you would need to account for what bcrypt was designed to do.

bcrypt does have the advantage that it's "slower" than the message digest algorithms, but that's not it's main goal. bcrypt was designed not only to be slow, but to scale poorly on FPGA and GPU architectures. As you mentioned, modern FPGAs have gotten quite a bit better and serve as reasonable means to break bcrypt, which is why scrypt was invented in the first place.

It should be noted that what you describe with the stretching is essentially PBKDF2, which has been shown to be less secure than bcrypt.

share|improve this answer
    
By stretching I just do a poor man's stretching like this for ($i = 0; $i < 10000, $i++) $hash = hash('sha512', $pass.$salt); I agree bcrypt is probably going to do a better job but if scrypt and bcrypt is unavailable, would you recommended this poor man's alternative? Or do you have a better recommendation? –  IMB Aug 9 '12 at 12:14
1  
@IMB: I would at least recommend implementing PBKDF2 rather than rolling your own method. –  Billy ONeal Aug 9 '12 at 14:53
    
@IMB: I hope you somehow include the previous hash in the next one in your loop, otherwise it has next to no slow-down value. But really, use a standard scheme instead of rolling your own one. –  Paŭlo Ebermann Oct 22 '12 at 19:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.