Bcrypt is now obsolete(daemonology.net)
daemonology.net
Bcrypt is now obsolete
http://www.daemonology.net/blog/2009-05-09-scrypt-key-derivation.html
44 comments
One of you needs to build a secret lair and plot to take over the world so that the two of you can become arch-nemeses. The Intel HT spat from a couple years back just wasn't nearly epic enough to hold my attention.
You're the only other crypto person I know on HN. What did you think about that spat?
First of all, calling me a "crypto person" is probably giving me too much credit. Two semesters of number theory (the second with an explicit crypto slant) make up the extent of my formal education on the topic. I've taught myself a fair bit beyond that, but I've never published any papers or anything.
That said, I'm mostly but not entirely on cperciva's side. At the granularity level of "disable HT" versus "put head in sand", I favor the former and think that Linux's choice of the latter was irresponsible. I also think all the ad hominems regarding self-promotion, cribbing from DJB, etc., were off the mark. However, your observation that a local privilege escalation vulnerability of any sort would be a more serious issue than the HT vulnerability, and that such is virtually guaranteed to exist, was a good one. The right answer, perhaps, would have been to disable HT in vanilla FreeBSD, and then re-enable it for PC-BSD.
That said, I'm mostly but not entirely on cperciva's side. At the granularity level of "disable HT" versus "put head in sand", I favor the former and think that Linux's choice of the latter was irresponsible. I also think all the ad hominems regarding self-promotion, cribbing from DJB, etc., were off the mark. However, your observation that a local privilege escalation vulnerability of any sort would be a more serious issue than the HT vulnerability, and that such is virtually guaranteed to exist, was a good one. The right answer, perhaps, would have been to disable HT in vanilla FreeBSD, and then re-enable it for PC-BSD.
The right answer, perhaps, would have been to disable HT in vanilla FreeBSD, and then re-enable it for PC-BSD.
I wasn't aware of PC-BSD at the time, but if someone had come to me and said "we're shipping a version of FreeBSD aimed at desktop users", I would have encouraged them to leave HT turned on by default. I always did my best to point out that this issue was not relevant to single-user systems, that all FreeBSD was doing was changing the default behaviour, and that in many cases it would make sense for system administrators to re-enable HT via the sysctl... unfortunately, the nuances tended to get lost as the story spread, so all most people heard was "Colin says that HyperThreading is evil and FreeBSD is disabling it".
I wasn't aware of PC-BSD at the time, but if someone had come to me and said "we're shipping a version of FreeBSD aimed at desktop users", I would have encouraged them to leave HT turned on by default. I always did my best to point out that this issue was not relevant to single-user systems, that all FreeBSD was doing was changing the default behaviour, and that in many cases it would make sense for system administrators to re-enable HT via the sysctl... unfortunately, the nuances tended to get lost as the story spread, so all most people heard was "Colin says that HyperThreading is evil and FreeBSD is disabling it".
I think we should do something about the bait-y titles on HN in general. Titles should be descriptive and succinct.
Maybe a better title here would have been "bcrypt's use of MD5 makes it insecure compared to scrypt". (I don't know how to best word the title; I would have not submitted the article, since I'm not an expert on security.)
Maybe a better title here would have been "bcrypt's use of MD5 makes it insecure compared to scrypt". (I don't know how to best word the title; I would have not submitted the article, since I'm not an expert on security.)
I think we should do something about the bait-y titles on HN in general. Titles should be descriptive and succinct.
Sometimes the same story is posted multiple times. One post will have a bait-y title and the other will have a boringly accurate and truthful title. Of those two, one of them always disappears with 3 or 4 votes and the other climbs the front page charts. Exhibit A:
Sometimes the same story is posted multiple times. One post will have a bait-y title and the other will have a boringly accurate and truthful title. Of those two, one of them always disappears with 3 or 4 votes and the other climbs the front page charts. Exhibit A:
A Comparison of Approaches to Large-Scale Data Analysis: MapReduce vs. DBMS
vs.
Parallel DBMSs faster than MapReduce
Long-Distance Teleportation Between Two Atoms Achieved
vs.
Scientist Teleport Matter More Than Three Feet
In case Colin's response wasn't clear enough: bcrypt doesn't use MD5 at all. It's a hack that uses Blowfish (an algorithm that is notoriously slow to "start up") where old Unix used DES, and tweaks the algorithm's startup to make it tuneably slower.
It's a hash function with a crypto-strong drag factor. A massive improvement in MD5's speed would be a win for MD5. bcrypt (and scrypt) are designed to stay on the opposite side of that tradeoff.
It's a hash function with a crypto-strong drag factor. A massive improvement in MD5's speed would be a win for MD5. bcrypt (and scrypt) are designed to stay on the opposite side of that tradeoff.
bcrypt's use of MD5 makes it insecure compared to scrypt
bcrypt is a key derivation function, like scrypt. It's openssl which bogusly uses MD5 as a key derivation function.
bcrypt is a key derivation function, like scrypt. It's openssl which bogusly uses MD5 as a key derivation function.
I don't know this guy. Probably he is really famous (?), but I'd rather wait until his scrypt sees widespread adoption before I follow his lead.
He's the dude who made all the builtin scripts on FreeBSD that are also in OS X, duh!
file /usr/bin/* | grep Bourne | cat `cut -d: -f1` | grep cperciva
file /usr/bin/* | grep Bourne | cat `cut -d: -f1` | grep cperciva
If you have the same OS X as the system I just looked at, it's just several hard links to the same script... and it's a very small script, too.
I don't know this guy.
You do now. :-)
You do now. :-)
Has anyone besides yourself yet vetted this 'key derivation function' (and perhaps you wouldn't mind shortly explaining the difference between a KDF and a cryptographic hash function)?
Has anyone besides yourself yet vetted this 'key derivation function'
Not yet.
perhaps you wouldn't mind shortly explaining the difference between a KDF and a cryptographic hash function
Cryptographic hash functions produce fixed-length collision-resistant output, ideally as fast as possible. KDFs can normally produce arbitrary lengths of output, and don't need to be fast -- in fact, being fast is a disadvantage, since secure KDFs are expensive to compute (because they need to resist brute-force attacks).
Not yet.
perhaps you wouldn't mind shortly explaining the difference between a KDF and a cryptographic hash function
Cryptographic hash functions produce fixed-length collision-resistant output, ideally as fast as possible. KDFs can normally produce arbitrary lengths of output, and don't need to be fast -- in fact, being fast is a disadvantage, since secure KDFs are expensive to compute (because they need to resist brute-force attacks).
Hello :-)
I appreciate your scepticism, but you might do some homework before revealing or announcing ignorance. cperciva is well-known in the relevant fields, and while it may yet be that scrypt doesn't get widely adopted, it won't be because it's not a secure system.
cperciva is well-known in the relevant fields, and while it may yet be that scrypt doesn't get widely adopted, it won't be because it's not a secure system.
I'm assuming what you meant to say is "it won't be because cperciva doesn't know what he's doing."
I'm assuming what you meant to say is "it won't be because cperciva doesn't know what he's doing."
That's possibly a better way of phrasing it - thank you. Crypto is notoriously difficult, and it's clearly prudent to wait and see what others say, and how it works.
It actually misses my intended point, though. This forum is generally exceptional in the quality of its submissions and comments, which is what makes it even more annoying when someone says:
It actually misses my intended point, though. This forum is generally exceptional in the quality of its submissions and comments, which is what makes it even more annoying when someone says:
I don't know this guy. Probably he is really
famous (?), but ...
No it doesn't. What I was saying is that the word of one person is not sufficient in such matters, no matter how famous the person. Hence there is (imo) no need to do homework on the popularity of the person. I could have done homework on the community opinion towards scrypt, however, I was commenting on the article (which did not cite any community opinions), not on the validity of scrypt. Therefore that kind of homework would not have been necessary in my opinion.
FWIW, I agree entirely that the word of one person isn't enough in matters of crypto and security. I probably agree entirely with most comments on the actual issues of security, etc.
However, it seemed to me from your original comment that you proclaimed ignorance and didn't do any homework. I feel that that is at odds with what is expected of this community.
Perhaps I'm wrong, and I'll say no more.
However, it seemed to me from your original comment that you proclaimed ignorance and didn't do any homework. I feel that that is at odds with what is expected of this community.
Perhaps I'm wrong, and I'll say no more.
I think no matter how well known the author, I would still wait a while. Everybody can make mistakes. Probably this scrypt thing has been tested to death by the community already, but the article doesn't give any references to such things, so how would I know?
IMO you're absolutely correct. It's generally frowned upon to select esoteric crypto algorithms of any type if another more widely tested one is available.
I have confidence in the author and high hopes for the algorithm but I believe it prudent to wait for the ink to dry before putting it anywhere it would matter. :)
I have confidence in the author and high hopes for the algorithm but I believe it prudent to wait for the ink to dry before putting it anywhere it would matter. :)
A side note: The name "scrypt" is no so good in terms of googling. A search for example for "scrypt python" brings up over 7 million hits for Python script. Maybe once more pages about scrypt exists it will stand up, but anyway the name could be more unique.
Try this.. http://www.google.com/search?q=%22scrypt%22+python
Search for "scrypt" python
Search for "scrypt" python
I know, but it brings 2710 results, and I am pretty sure the link to my and your comment (number 5 and ~15 in Google) are the only one related to this derivation function.
It's stated that scrypt is 4000 times harder to break than Bcrypt (I don't know how this is calculated, so it's probably an estimate). Given that password cracking can be easily parallelized is this enough of an improvement?
Did you read the paper? The whole point of the thing is to make it non-parallelizable. That's what makes it hard.
I did not read it, but I can't imagine what would prevent an attacker from running a parallel attack on multiple circuits/computers that aren't sharing any resources...
The idea is to make the KDF expensive in space as well as time. While bcrypt costs a few seconds of CPU time, it uses only a tiny amount of RAM, thus underutilizing the resources you have available. Thus, you can parallelize an attack using lots of specialized ASICs but only a commodity amount of storage. Scrypt would require you to purchase lots of RAM for every ASIC, making a brute force attack much more costly.
Thus, you can parallelize an attack using lots of specialized ASICs...
More to the point, you can parallelize attacks on most KDFs by building an ASIC with many copies of a password-cracking circuit. With scrypt, the vast majority of the IC area (and thus cost) is RAM.
More to the point, you can parallelize attacks on most KDFs by building an ASIC with many copies of a password-cracking circuit. With scrypt, the vast majority of the IC area (and thus cost) is RAM.
this means that a five-character password using scrypt is stronger than a ten-character password using openssl.
Not a crypto expert, but don't most people crack passwords by just running common words or every possible combination of N characters through your encryption system, therefore as long as your encryption mechanism is good enough it doesn't matter what you use?
Not a crypto expert, but don't most people crack passwords by just running common words or every possible combination of N characters through your encryption system, therefore as long as your encryption mechanism is good enough it doesn't matter what you use?
Not a crypto expert either, but I took this to mean that each attempt in a brute force attack is orders-of-magnitude more costly, so that trying all combinations of 5-character scrypt passwords takes as long as trying all 10-character combinations with bcrypt.
That's almost correct. Replace "takes as long as" with "costs as much as" and you'd be exactly right.
Basically what it comes down to is that with bcrypt (and all the other widely used KDFs) it's vastly cheaper to attack the KDF with a custom circuit than it is to buy general-purpose computers and run a software key cracker. With scrypt the advantage that TLAs with ASICs have is much smaller.
Basically what it comes down to is that with bcrypt (and all the other widely used KDFs) it's vastly cheaper to attack the KDF with a custom circuit than it is to buy general-purpose computers and run a software key cracker. With scrypt the advantage that TLAs with ASICs have is much smaller.
if scrypt is more than twice as slow as openssl, wouldn't that make it stronger?
Since you have an implementation I don't have to manually extract from a library deep inside the OpenBSD source tree I think I'm going to take a look at replacing bcrypt in an application I'm working on.
I would really like to see Bruce Schneier's opinion on this.
He called it pointless 'security theater' and recommended using a faster algorithm like MD5 to reduce delays at security checkpoints since terrorists will just print their own boarding passes anyways.
He would call it that when applying this solution to that specific problem. In general, I don't think he would say that when the proposal is that people should use scrypt to hash the passwords they store.
For those that don't know, Bruce Schneier designed http://en.wikipedia.org/wiki/Blowfish_%28cipher%29
Uh, why him in particular?
There are other competent cryptologists out there, y'know :-)
There are other competent cryptologists out there, y'know :-)
Well, if Bruce passed comment on it, it would be publicity, bringing it to the attention of many that would be interested.
Squids.
We'd use the term "adaptive hashing" or (less accurately) "key strengthening", but it wouldn't be actionable. Bcrypt is actually still current, since very few stable implementations exist for your algorithm, and you are surely not recommending people implement their own crypto.
It's good work though, and I look forward to recommending it, when it becomes reasonable to do so.