Is my developer's home-brew password security right or wrong, and why?
security.stackexchange.com
security.stackexchange.com
The OP pretends to innocently ask "Is my developer's home-brew password security right or wrong, and why?". I'm going to call BS on this. To me it's pretty clear the OP is trying to passive-aggressively bully/ridicule/shame Dave in order to get his way. And sure enough, the top ranked StackOverflow has somebody going through the code line-by-line going WTF at every opportunity. The OP isn't trying to figure out whether he or Dave is right, he's clearly already convinced he's right and wants the StackOverflow community to collectively pat him on the back. Kind of childish.
I had a different interpretation; OP is "Dave." It's sort of a time-honored tradition, on-line and off, to seek advice "for my friend."
On the internet, nobody knows you're a Dave.
Just to be sure, I ran the code twice, a few seconds apart, using "rob" and "password" for the parameters. Here's the results:
Hc3fba318ec5f25ef74e0067e27bfa187f1385d3b
He66effce74bb1ae41e3a2344b91d5fe1c6205ee0
$hash = hash_it($password, $crypt);
So it is fairly clear that $hash and $crypt would be stored in the DB. $crypt is a reasonable (but not great) salt:
crypt($user.$time.$rand);
$user is obviously known, $time is the time when the password was created - or maximum ~2000 possible values for most systems. The main part of the hash is $rand, which is 31 bits of pseudo-random entropy. So about 40 bits of entropy if I'm not mistaken? That should be enough to make it infeasible to create rainbow tables in advance.
EDIT: I'm wrong on $time - it is "mdYHis", so much more than 2000 possible values and is actually pretty decent in the salt, as it's unlikely an attacker would know which user registered when. Unless you publish the registration date as some forums do...
EDIT2: While user is known for each user, it does add extra required input for a rainbow table - if there are 1000 users and you know all of their usernames, you would still need to generate 1000x more rainbow tables (1 per known username) if you wanted to crack all 1000 passwords. Also slows down brute forcing, as you can't use the result of one 'trial' on all users at once. (Correct?)
The real main issue is the speed of brute forcing MD5/SHA1 - it's probably possible to brute force these passwords very quickly if the database is stolen. Use of bcrypt is therefore obviously preferred to slow it down - but it is also very likely that FPGAs can brute force bcrypt just as fast, so I'm not sure how much I agree with the common mantra of 'sha1 is useless, use bcrypt'. bcrypt does, after all, have a speed impact on your login requests and puts more load on your servers if you are handling thousands of logins per second...
I guess large scale FPGAs are probably only in use by NSA and some syndicates, while far more hackers have access to mass GPUs?
> ...rainbow tables...
That's not really relevant anymore. Rainbow tables aren't used, and haven't been for a while; once you start using salts of any kind, there's no point to rainbow tables.
> Also slows down brute forcing, as you can't use the result of one 'trial' on all users at once. (Correct?)
Correct, but any random salt will do. I think you'd usually be better off reading from /dev/urandom though, but for the purposes here I don't think it matters.
> The real main issue is the speed of brute forcing MD5/SHA1 - it's probably possible to brute force these passwords very quickly if the database is stolen.
Exactly. Ordinarily, what happens is a database gets ripped via an SQL injection or some other thing, and then a list of the usernames & passwords gets posted to a forum somewhere where people take turns brute-forcing them in chunks.
MD5 and SHA1 both give recognizable hash values -- you can glance at either one and usually tell which it is.
So someone with a big list of usernames and known salts and MD5s just proceeds to generate MD5s of a list of common passwords + the salt, and then compares that to the list of stolen hashes, and ends up with a pile of passwords that work.
But, there is a challenge here in GoofHash(): if only the database was stolen, and if the methods used to generate the hashes aren't known, then the hashes would be useless. Attackers could tell at a glance that they had SHA1 values, but even assuming that the "salt" was clearly labeled as such in the stolen database, brute-forcing salt + common passwords wouldn't give them the SHA1 values they're looking for.
So I'm a little circumspect about how bad this approach is. I still wouldn't hesitate to say that it's not as good as using known approaches, but if the end goal is the protection of users' passwords, this might be sort of OK -- as long as nobody knows what they're dealing with. Still though, "security by obscurity" is generally not considered to be a smart approach by people like Schneier.
edit: Oh, I meant to respond to this,
> ...but it is also very likely that FPGAs can brute force bcrypt just as fast...
I don't think so. bcrypt (or, better yet in this regard, scrypt) depend upon stretching -- hashing the hash over and over again. Standard SHA1 doesn't do that, so you're pretty much comparing "one iteration of SHA1 versus thousands of iterations of hashF()"; assuming that hashF() isn't found to be broken in some horrible way, thousands of iterations of that will always be slower, on all hardware, than a single iteration of anything else.
You mentioned earlier that rainbow tables aren't used anymore - but this is exactly what rainbow tables are. Precomputed lists of passwords + salt. That's why I was talking about the entropy in the salt earlier - the more randomness in the salt, the more infeasible it is that anybody would have your rainbow table. And you're right, /dev/urandom of a fairly large size is perfect, but the crypt($user.$time.$rand) is not all that bad either as it does have $rand in there.
I think you were agreeing with me here, and if so I'm just confirming your confirmation. ;)
>> thousands of iterations of that will always be slower, on all hardware, than a single iteration of anything else.
If your FPGA array can brute force 10 characters of bcrypt in 8 seconds and 10 characters of SHA1 in 1 second - does it really matter? If you have pushed the time to crack down into feasible time, the exact number of seconds becomes irrelevant. The hacker may have to step out for a coffee if you use bcrypt instead of getting the results right away. Hardly more secure?
Rainbow tables are precomputed lists of hashes: md5('password1'), md5('password2'), etc.
Rainbow tables are not precomputed lists of hashes with salts: md5('password1'.salt), md5('password2'.salt).
At the very least, salts will vary from database to database, so there's no reason to "precompute" anything that's salted. It doesn't gain you anything.
What we're talking about here is different, the common approach to dealing with salted hashes. You have a big list of commonly-used passwords -- "abc123", "logmein", etc. -- and you have a list of hashes from your stolen database, and a list of salts from the same. You feed all that in to a program that just computes the hash using your password list + the known salt.
If the salt varies by user, the attacker is in for a long day, but can still expect to break a lot of passwords if the database is using MD5 or SHA1.
If the salt varies by user, and the database is using bcrypt (or better yet, scrypt), then the attacker is in for a long couple of years. bcrypt with a decent work factor should take in the neighborhood of 1 cpu-second on non-specialized hardware to compute a hash. If you have a database of 15,000 passwords, you're looking at 4 cpu-hours per hash.
Compare that to GoofHash(): on my sorta-decent laptop, GoofHash() runs in 0.035s. That means that I can compare my entire password list against each user in the database in 8.75 minutes.
That's a huge difference.
These are with MD5/SHA1 style hashes, which shows that your password is pretty safe regardless of hash method (as long as it has salt) if it has enough entropy in it. Pretty interesting.
So, this also is a slightly different situation. If you are an end-user, yes, you can protect your individual password against stupid hashing schemes by using passwords with lots of entropy. (I use KeePassX for this.)
However, if you are a service provider, you have to protect your users from the stupid passwords that around 30% of them are likely to use and re-use elsewhere, and you do that by using a smart hashing scheme (like bcrypt or scrypt) that makes brute-forcing the passwords an annoying and time-consuming endeavor.
Your calculations are off by several orders of magnitude. Bcrypt can be customized to take more time, but a reasonable amount of time might be 0.1 seconds per password, or 10 passwords per second. Most users are already logged in, so logging in should not be a very common operation.
By comparison, a $500 graphics card can hash billions of SHA1 passwords per second. So what takes 1 second to brute force with SHA1 will take 100 million times as long, or over 3 years, to brute force using bcrypt.
Note that a 10 character all lowercase password has 26^10 possibilities. If we are just targeting this password it will take 19 hours at 2 billion SHA1 hashes per second (well, on average half of that, so around 10 hours), and over 447000 years at 10 bcrypt hashes per second(again, half that on average).
It seems like we have a few problems with Dave as well: NIH combined with a lack of understanding about security. These together are a great way to produce insecure systems. I don't know how you fix people like Dave and would personally find them frustrating, and perhaps that frustration is leaking out in the post.
It's clear the OP had something of a clue and thought bcrypt would be a good approach. You can call it public ridicule if you want to, but let's give him the benefit of the doubt: perhaps he simply didn't know enough about cryptography (which is very, very hard) and wanted to get a second opinion.
Personally I wouldn't fault anyone for asking advice from a public forum about some homebrew crypto code like this. It's certainly better than a lousy password hash like that going into production in place of bcrypt.
Compared to PBKDF2, bcrypt, and scrypt, this system is incredibly insecure and susceptible to brute force attacks.
My opinion of this code is it's full of nonsensical voodoo and this guy has no business writing cryptographic code of any kind.
If 95% of people believed in demonic possession, we'd all bemoan how crazy, dangerous, and fucked-up the situation is. But when a developer knows the solution recommended by real live cryptographers and chooses to discard it for his own broken version, we shrug our shoulders because, hey, everyone else gets it wrong too.
Fuck that. Bad code is bad. Bad developer attitudes are worse.
$time = date('mdYHis'); // Probably in the database somewhere too
$rand = mt_rand().'\n'; // Said to be a 31 bit number
$crypt = crypt($user.$time.$rand); // DES crypt is 64-bits output
It's reasonable to assume the attacker knows the username. If the attacker knows the time the user was created, he can easily brute force the 31 bits of $rand. PHP mt_rand is not seeded with more than 32 bits of entropy, so with knowlege of just two (username, time, seed) entries the attacker learns the values of all other mt_rand numbers (past and future) generated by this PHP process. This may have significant implications for the security of other parts of the system.
function hash_it($string1, $string2) {
// Equivalent complexity to:
return sha1($crypt, md5($password)).
}
$hash = hash_it($password, $crypt);
In my estimation, this scheme is about 0.5 bits stronger than plain SHA-1 like Linkedin was using. 90% the Linkedin passwords have been cracked. http://arstechnica.com/security/2012/12/25-gpu-cluster-crack...
No, not really. Salts are used for two main reasons:
1. So if two users have the same password, it's not obvious in the password file.
2. To thwart precomputation attacks, e.g., "rainbow tables".
Modern password cracking has all-but obsoleted both of these reasons. For (1), if two users can "choose" the same password, then it's almost certainly a weak password that the attacker can guess as well. For (2), GPUs have gotten so fast now that password crackers don't even bother much with precomputed rainbow tables.
I'm not arguing against salting, it's still good practice. I'm saying it doesn't, in reality, add much time at all to the time needed to crack a database of passwords. It's just that at the end of the day, it all comes down to the entropy content of the user's password as experinced by the attacker.
Similar to Linkedin with 6.5m, we have a real-world case study.
> Regardless of what hashing algorithm I am using, if there is no salt I just need to hash the entire password space once, where the password space could be a dictionary attack or a brute force of passwords up to length 10 of letters, digits, and symbols.
When you say "entire password space" you're implying that there's a hard upper limit on the complexity of a user's password. Many sites do indeed restrict passwords to 8 or 10 characters, but that's horrifically broken.
Any not-completely-broken system has an password space so much larger than an attacker could search that it's effectively infinite. Note that even the silly system proposed here uses MD5 which accepts password longer than would even fit into available memory.
> If there is a salt, it means that after hashing the entire key space I only have the password for 1 user rather than all of them.
As described, the "key space" is effectively infinite, but luckily for the attacker some parts of it are far more richer to mine than others. This is where the easy-to-guess passwords lie.
So the attacker won't do anything as dumb as "hashing the entire key space". The attacker will search the most rewarding parts of the keyspace first.
> It means attackers must use targeted attacks and slows them down by a factor of # of users. Rather than having all my passwords in a day, an attacker gets access to one user's password per day (over the course of a million days). (Still not a good thing to happen)
For example, recent data breaches suggest that 50% of users will choose one of the 10,000 most-common passwords. So the attacker tries this set on all 1M of your users. That's 10,000,000,000 hash operations. A typcial rate for SHA-1 is 3.8 billion per second, per GPU. http://hashcat.net/oclhashcat-lite/
So our expectation is that the easiest 500,000 of your 1M accounts will be cracked in the first 5.2 seconds by a single GPU attacker. And this is approximately what happened with Linkedin, ISTR 60% of the passwords were reported cracked that first day.
But the rate of success slows down for the attacker and the remaining passwords begin to take exponentially longer. As of today, 90% of the Linkedin database is reported to have been cracked: http://arstechnica.com/security/2012/12/25-gpu-cluster-crack... So there are really only 65,000 hashes posing any difficulty at this point.
When a fast hash function is mis-used for password hashing, salt or no salt, there's not a case where "an attacker gets access to one user's password per day". The attacker cracks the majority of passwords in the first few seconds yet a small minority will never be cracked.
Salting doesn't save the database as a whole. Salting doesn't help the users with weak passwords. Salting doesn't even help the few users with very strong passwords, they wouldn't need salt in the first place. But for the users in the 60 - 90 percentile, it might buy them a few hours or days.
Except that Linkedin's passwords weren't salted.
> When you say "entire password space" you're implying that there's a hard upper limit on the complexity of a user's password
That's why I said "where the password space could be a dictionary attack or a brute force of passwords up to length 10 of letters, digits, and symbols". I don't actually mean the whole key space, just whatever the attacker chooses to target.
> So our expectation is that the easiest 500,000 accounts will be cracked in the first 5.2 seconds by an attacker with a single GPU
OK, I concede that point that in this case the salt is not helping so much, at least for users using the 10000 most common passwords. For the few hundred thousand users users whose password lies in a larger key space (but still in the range of bruteforce), the salt still protects them.
Getting back to your original point
> Modern password cracking has all-but obsoleted both of these reasons [for having a salt]
Let's look at a better hash function - bcrypt. In this case hashing passwords is still slow enough (by design - you can slow it down to whatever you want) that rainbow tables would again be useful - to compute the hash of 10000 passwords with a difficulty such that each hash takes 1 cpu-second to compute will take almost 3 hours. Adding salts makes this a per user operation instead of a global one.
My point is that salting a fast hash function is like issuing lifevests to the passengers of the Titanic. It sounds better than nothing, but in practice it only just keeps a handful of them from drowning so they can die of hypothermia a few minutes later.
> That's why I said "where the password space could be a dictionary attack or a brute force of passwords up to length 10 of letters, digits, and symbols". I don't actually mean the whole key space, just whatever the attacker chooses to target.
Sounds like you think you get to decide what the attacker will target first and when he will give up.
> Let's look at a better hash function - bcrypt.
Agreed, bcrypt is categorically better. But note that bcrypt includes salting as an intrinsic part of its implementation. So it's not something any web programmer could say "I will/will not salt my Bcrypt thusly".
As tptacek says, "if you're typing the letters A E S or 'salting your hashes', you're doing it wrong."
NB: I thought it was funny.
P.S.: Meme pictures originated on discussion forums.
In terms of nerd culture, I guess image macros are the new version of endlessly quoting Monty Python, except the internet memes weren't even funny the first time.
Dave's primary problem is that his scheme is based on MD5 which is still well known, but can be brute forced quickly. His additional lightweight obfuscation will provide nearly zero extra protection.
Use Bcrypt with salt. End of story.
Published crypto is stronger because it's had many eyes on it, not weaker. This is pre-101 level crypto knowledge, it's like the first line in the idiot's guide. Or it should be!
(On this GPU, MD5 alone can be bruteforced at 8 billion pw/sec, and SHA1 alone at 2 billion pw/sec.)
This one flaw, by itself, makes the algorithm very bad. The developer should have used bcrypt, or scrypt, or SHA2-based Linux crypt. These are iterated by making multiple calls to a compression function to significantly slow down bruteforcing, from billions/sec down to thousands/sec.
Then, you might benefit from nobody wanting to bother to spend the energy to reverse-engineer your one-off GoofHash(). But, then again, maybe not. Maybe the fact that all of the passwords have been effectively hashed using single iterations of fast trivial algorithms like SHA1 and MD5 will mean that a ton of your users' passwords could be calculated in a short period of time.
In that scenario, you're gambling instead of relying on battle-tested approaches. Maybe the gamble will pay off, probably it won't, but when the battle-tested approaches have been examined by a lot of really smart people and found to be solid, why not use them instead?
Or, put another way: you're going to have to play a game of dice against Death. You have a choice between playing with a set of dice that thousands of people have rolled over and over again and found to be fair so far, or a set of dice that some dude just rolled for the first time a minute ago and declared to be fair. Which do you choose?
edit: I am an idiot. If someone gets the code and DB, they won't have to reverse-engineer anything; this is just a fast MD5/SHA1 combo, a bunch of passwords could be brute-forced in a short period of time.
I always liked www.amazon.com/Code-Book-Science-Secrecy-Cryptography/dp/0385495323/ as beginner introduction, before going on to more advanced books. it gives you all the basics, and the basics are imo the most important to get right (that's why they're basics), plus its a fun read
That's sort of like adding more rounds to DES.
A good reference on how to get these things right is Schneier et al's 'Cryptography Engineering'. The standard advice line here, however, is "get professional help".
The videos are probably available for download somewhere else, so you don't have to wait. Someone posted a site here on HN that saved all the coursera videos, but I can't remember the name.
Each video lasts ~20 min if I remember correctly, but they are very intensive. I never wanted to watch more than one or two per day, my mind would have blown.
Of course I did a bit of research (ok, only 30-60 minutes on Google ;)) and didn't find anything presenting a sweet and simple solution.
A user can just open your binary and flip the jump that checks if the license is good or not. Do you really want to start wasting time making your software vastly more complicated, in order to try to lock out crackers? If the software is remotely desirable or common, it'll get cracked.
If someone wants to go and disassemble the app and read all that machine code to find the bit to flip then there's not much I can do about that I think.
Are you just trying to keep honest people honest? Then just about anything will work. Are you trying to prevent hard-core hackers from cracking your work? A whole bunch of very good people have been working on that problem for a long time and failed.
It is likely that the most dangerous licensing system you can produce is one that routinely false-positives a real user as a pirate. They will cease to be real users in the future. In general, pirates weren't going to be real users anyhow. (There are some exceptions, mostly in the games world, but in general it seems to be true.)
If you can swing it, the most bang-for-the-buck you can get for protecting your work is to not actually ship all of it; provide some sort of critical element that lives on a server somewhere under your control. This can be tricky in some cases, because you really ought to be able to say with a straight face that there's some sort of value-add resulting from that. And that has availability and growth consequences as well. But it works, it's simple (relatively speaking), easy-to-understand, and extremely difficult to bypass. (Still technically not impossible, in some sense, but you've raised the bar beyond what all but the most dedicated attacker will bother with. Cracking is fun; reimplementing a backend service by examining only the data going in and out, well... I can't say that's not fun, but it's fun for a much more select group of people, most of whom are probably using those skills to make real money somewhere.)
Take a simple checking function. Check the code, if it is wrong, show a message box saying "wrong code". Well, in that case, all you gotta do is set a breakpoint and go back. Programs like OllyDbg or IDA Pro make this kind of reverse engineering absolutely trivial, and something you can accomplish after "reading a basic text".
Most likely if someone's going to "run a program", they can run a crack, too. If you can get away with a license file, then you can do RSA properly. Otherwise, end up with short RSA and hope no one really looks.
It's almost certainly the case that you're far better off improving some other aspect of your application than investing any time trying to defend against pirates.
http://www.atrevido.net/blog/PermaLink.aspx?guid=ec99e239-89...
1. People quickly figured out that the key generator just verified RSA signatures.
2. Since he implemented RSA by hand (I guess calling OpenSSL's RSA_INIT() would be too "obvious") it had bugs. Specifically, it didn't check that the signature in the key was strictly below the key modulus, meaning that given signature X, you could add the modulus to get a new valid signature.
3. Since the license keys can't be ridiculous long pieces of text, the key was not long enough. Someone went to a website online and pasted the key into a Java prime factorization applet and cracked it, posting a key generator.
There is always a tradeoff between security and usability. Unfortunately, the tradeoff here is prohibitive: if you use a 1024 bit key and base 32 encoding, your users will have to type in a minimum of 205 characters to enter the product key. Base 32 is the densest reasonable encoding for human input, or close to it.
So the lesson is that even the simple requirement "can't create a keygenerator" is an open problem.
The first third (half?) of the book is devoted to explaining (not with code) the various complex interactions between parties who need to trust one another -- lots of stuff on key exchange, and then only later on the different types of ciphers (block vs stream ciphers). The examples are clear and well-written, and VERY memorable. Bruce explains very well what the pitfalls are in each scenario, and all the ways in which malicious attackers can try to break your trust.
The second half of the book is implementation of most of the algorithms in C.
Other books may cover the topic be better, but I haven't read them. (Sorry.) I like that Applied Cryptography gives a good noob-friendly introduction, and builds from there, yet also has depth and source code.
1: http://www.amazon.com/Applied-Cryptography-Protocols-Algorit...
Agreed, it was a great course. Looking forward to the sequel in early April. https://www.coursera.org/course/crypto2
The point of bcrypt is to make it so they can't brute force at high speed. (If you choose your number well enough.)
Let's say a hacker, some how got into some non-secure services with good amount of user. And found out the username/password are not encrypted or hashed at all. He can use that list a dictionary. He can also have MD5, SHA1 hashed calculated. The same hacker got it into your secured service, who already have a dictionary to try on. He can get password from MD5 or SHA1 or any known hash, in O(1) using hash-table lookup. Normally, hackers now-a-days have the dictionary to try on, it is just the SALT and hash-algorithm is unknown to them. So, the security measures can be:
1. Protect password Hashes from theft. 2. Protect salt from theft. 3. Protect hash function from theft.
Try to protect them all. All of them can stolen, but probability of 3 theft is less than 2 theft. I agree with Dave, only if he has plan to keep hash function secret. I should not shipped inside java script, so hacker don't need to do any effort.
Cooking up goofy hashes doesn't give you any extra security in the worst case scenario (the hacker gets access to your web server and has the source code for your goofy hash). A goofy sha1/md5 based algorithm with salt can still have millions upon millions of attacks generated per second by anyone with a half-decent GPU. Your only hope once you're in this scenario is to use a big slow hash that the attacker can't run very fast -- y'know, something like bcrypt.
And if you're right that they're more likely to get the db without the source (very dubious -- web servers are a big attack surface)? Then the attacker is still completely screwed trying to break your too slow to attack bcrypt+salt passwords. You've got much better safety in every scenario, not just the "well they didn't manage to see how my goofy hash worked" scenario.
(And that's assuming you, as a non cryptographer, didn't so thoroughly screw up your implementation of goofy hash that it ended up with less entropy than even md5. But how would you know when you've kept it super-secret for l33t security?)
If the USER takes a short string, and MD5's it then sets the MD5 as their password then it is more secure, but that is only because it is a longer password to begin with.
If I'm wrong I'd be interested in knowing why.
Also, "security through obscurity" is well known as a worst practice for crypto (probability that the algorithm will be reverse engineered or disclosed is all but negligible), so definitely not a good reason to implement any new algorithm.
The salt generation looks acceptable though.
The op stated that he already created a system using bcrypt. The fact that op doesn't know what is wrong with Dave's code, and needs others to explain why Dave's code is bad, makes me lean towards op stfu and allow Dave to continue.
Op is unlikely to be any more competent compared to the somewhat incompetent Dave.
I agree that it is likely that op and Dave are one and the same, and think this mess of code is some sort of genius.
We don't publish security-related algorithms to make them stronger. We do it to weed out the weak, and it is remarkably effective at doing that. If you're not confident that your algorithm could survive in the open, then chances are it can't.
Ironically, if he would just substitute bcrypt for sha1 in his function, it would be a great crypt function!
sillysalt(user):=user+date+mersenne_twister()
sillykdf(user,password):=pbkdf2(sillysalt($user)+
shuffle(bcrypt($password)))
persist( sillysalt($user)+":"+$outer_pbkdf2_salt+":"+
$inner_bcrypt_salt+":"+sillykdf($user,$password))
His user+date+mersenne salt accomplishes the goal of (mildly) increasing the cost of precomputed attacks. He should use a CSRNG instead.
He uses existing cryptographic hash algorithms, SHA1 and MD5.
His shuffling does not add or detract from the security of the scheme.
He does not perform any significant key strengthening. Weak (most) passwords will be very cheap to brute force.
My version is not cheap to brute force, but it is silly.
Most password crackers these days are using GPUs and don't even bother with precomputed rainbow tables. So the salt is not increasing their cost at all.
> "Anyone can invent an encryption algorithm they themselves can't break; it's much harder to invent one that no one else can break" - Bruce Schneier