-
Website
http://www.matasano.com/log -
Original page
http://www.matasano.com/log/958/enough-with-the-rainbow-tables-what-you-need-to-know-about-secure-password-schemes/ -
Subscribe
All Comments -
Community
-
-
Top Commenters
-
Popular Threads
> So, we learned that MD5 is the enemy. Also Jeff Atwood and Richard Skrenta.
To be fair to Rich, I copy-pasted his salting example, which was *not* for passwords, into my post, which *was* about passwords. So that was my mistake, not his. And yes, I completely agree that we want to use a secure crypto hash for our passwords. And a per-row salt, which I didn't do a good job of explaining.
Still, I think publicizing hashes, salts, and rainbow tables is a good thing. Just look at Reddit, who stored their passwords in PLAIN TEXT-- I swear I am not making this up-- less than a year ago (!)
http://blog.moertel.com/articles/2006/12/15/nev...
The resulting discussion is where I find I learn the most about subjects.
In a web app, you'd probably put the salt in a seperate column from the hash.
Again: if you're just MD5'ing passwords and sticking hashes in a database, don't bother. It's really that bad.
No need to apologize -- it made me laugh. I do want to defend Rich here, though. His great MD5 post I cribbed from specifically said that he supports using MD5 for *non*-secure use cases only. MD5 has a thousand and one uses, but security isn't one of them any more. That was sort of the whole point of Rich's post so I apologize for accidentally subverting that.
Usually I'm just my own worst enemy, but when I blog, I can be yours too!
> It doesn’t matter where you store it, but the scheme won’t work unless you do store it, in the clear.
I was definitely unclear on whether the salt should be a secret or not when I wrote that post. Storing the salts as a column in the table makes sense in retrospect.
However, based on the comments to my blog entry, it seems that you could opt to "hide" the salt in the code as well. Say, I could opt to run MD5 on the username, then Blowfish on the row id + the resulting username MD5, then Triple-Lutz-PHK-MD5 that plus the password. That per-row unique salting formula would only be known to someone who had the code *and* the database.
An attacker who obtained the user/hashpass table wouldn't have any idea what my per-row salts were, because they aren't stored in the table.
What are your thoughts on this? Does it matter?
This is a classic instance of attempting to use security through obscurity. Design your system assuming the attacker has the source code. See also Kerckhoffs' Principle.
I *am* already assuming the attacker can get the source code.
There is no practical difference between "put the salt in the table next to the hash" and "put the salt formula in the code". In the worst case, we have the *same exact outcome*: hashed passwords with salts right next to them.
However, when I put the salt formula in the code, that means the attacker has to do extra work. Having the table is no longer enough. S/he needs the code, too.
Why would we consciously choose to remove another potential hurdle we can put in front of attackers?
As I see it, this not a question of "security through obscurity"; it's an example of defense in depth. Sure, we could keep the two in the same place (in the hashpass/salt table), but instead we could choose to put the salt in the code, which is secured differently.
I guess it's the "let's launch a nuclear ICBM missile" theory of security. You know how in all those movies, they show two people working in the underground silo, both of whom have keys that have to be inserted and turned before the missile will launch?
I dunno, maybe I'm crazy, but it makes a modicum of sense to me.
I want to store data in cookies and be sure it hasn't been tampered with when it gets sent back by the browser.
I need a hash-mac, right?
Set-Cookie: foo=hash(secret, bar):bar
Do I also need a nonce?
What determines the strength of this, a really long/random secret?
Does the secret need to be changed frequently?
It needs to be fast.
Don't let me fuck this up.
Wikipedia says it is expired though.
http://patft.uspto.gov/netacgi/nph-Parser?Sect2...
So using hmac-sha1 for this is not stupid, right?
A good, long, random secret; sha1 or sha256; and no one's going to be writing blog post about how incredibly stupid I am..?
You are going to go through a lot more effort to get this right and probably fail than you will in solving the problem of storing stuff server-side. I highly recommend you go that route.
The problem is, crypto usually makes things less secure, not more secure. You almost never use crypto when you don't need it. You're always depending on it. You want your security to depend on as few things as you can manage.
The answer is: if you know what you're doing, crypto starts solving problems for you once you're confident that every line of the rest of your system is bug-free and secure. Before that point, crypto causes more problems.)
Doesn't knowing the salt make the hashes more vulnerable to attack, at least in theory? Doesn't the visibility of a salt plus the hash make a rainbow table attack *feasible* on a hash value, at least at the cost of generating a unique rainbow table for each user?
Whereas a hash with an unknown salt seems completely immune, to me, to any kind of rainbow table attack (assuming the salt is long enough).
Let me know if I'm misunderstanding this, which is entirely possible..
FWIW, I wrote a simple, portable Ruby gem for doing exactly this kind of thing without worrying too much about it.
http://bcrypt-ruby.rubyforge.org/
One question, though: since the login to my social lolograms tagging.NET website has to be available to essentially everyone, doesn't an intense password-guessing function open me to a serious DoS?
Or I may not have the scale of numbers right; would a scheme that takes .01 seconds to calculate still make brute-forcing it impossible, while requiring attackers to mount a hundred attacks on me a second?
If you throw away the salt, you have to guess it each time you want to verify a password, which is kind of a strange construction for key stretching.
Well, it reduces the search space from 2^10000 to 2^1000, so, yes, if someone is determined to brute-force your password, then knowing the salt will help.
The thing about "rainbow tables" is that a whole bunch of someone elses have already precomputed the list for you. People have just barely managed this for passwords in the commonly used space. If your salt has even a dozen bits, those people would've needed to make over 4000 rainbow tables. That's beyond their resources, at least for now. Even a "constant" salt, like suggested in your column, would break this.
In some cases, you may even be able to use Google as the store for your rainbow table. Google up the md5 of "password" (5f4dcc3b5aa765d61d8327deb882cf99) for some fun.
Crazy idea: after your password-verifying script generates a hash, Google for it and make sure that no pages are returned.
Fun game: after you change away from an old password that you used for a while, put it into Google to see if it ended up anywhere.
2. hash all of them
3. burn the results onto a DVD."
Where do you get your dvds?! By my calculations, you would have 62^14 password hashes. Even if we miraculously collided 999,999 out of 1,000,000 passwords (so you only have to store 1 hash out of every million passwords hashed), you're still looking at 12 exabytes of data. Do you have 12,000 terabyte DVDs?
In every discussion on this that I've read on this subject, people have drastically underestimated the search space involved.
The reason that salt values work is not because they make the password "more secret." They work because they increase the search space, making an exhaustive search infeasible.
If your passwords are one character long (for the sake of the example), and the salt is 16 characters *AND RANDOM*, the final hash will be based on a string that is 17 characters long. These 17 characters can be *anything* because the salt is random. Let's say an attacker has a rainbow table. To have calculated any given password's hash with certainty, he or she would have to had calculated *all* hashes for strings of length 17, not just those hashes for passwords of length 1.
The attacker could still brute force the part of the password that isn't the salt, but this, again, should be infeasible if your password isn't crap. You've basically removed the rainbow table from the equation.
Furthermore, if you try to "hide" the way that you generate the salt, all you're doing is shooting yourself in the foot. True, a real attacker probably would not know any of the details beforehand, making the point moot; but, if there's any order (read: un-randomness) in the way you generate your salt, it will actually REDUCE the size of the resulting search space, which weakens the scheme in theory.
Note: "5" is not a letter. ;^)
http://www.toolcrypt.org/index.html?spapwke
This does not make other points of the article - usefullness of salting and slowness of the algorithm - less valid.
source code/binaries:
http://oss.coresecurity.com/projects/pshtoolkit...
docs:
http://oss.coresecurity.com/pshtoolkit/doc/inde...
horrible plug, although it is an open source and free tool :); but delete the post if it is inappropriate, I'm just frustrated from being ignored by the 'Tools' section and editorial staff of securityfocus after 5 email messages and 10 'tool submissions' :), sorry :).
On 2007/8/30, the draft was sent to the RFC editor and it will be published as an RFC if nothing else changes. Of course, I'm not an IETF insider so no guarantees, it just seems like your position of "stay away" is a bit extreme, given the circumstances.
https://datatracker.ietf.org/idtracker/draft-ie...
> The reason that salt values work is not because they make the password “more secret.”
That's odd, because it feels like that's exactly what salts are doing for us-- taking the user's password, say "myspace1", and making it far more secure by smushing (clump of random unicode data) + "myspace1" together.
> They work because they increase the search space, making an exhaustive search infeasible
I agree, but don't very long passwords accomplish the same thing? I've been a long time advocate of passphrases for this reason. Even a trivial passphrase like "myquickbrownfoxjumpsoverthelazydog" would be pretty hard to brute force-- even if I told you in advance it was lower-case alpha only.
For the case of other accounts on the same machine -- the changing salt (unique per user) means that a single pre-processed dictionary can't be reused between accounts. The attacker's hash of "apple" under seed "XXXX" is useless to compare against account #2's password hashed with seed "YYYY".
For the case of other accounts all over the Internet (in this case, "all Windows machines"), even if YOU only have a single account, you need a salt to distinguish that password hash from every other Windows system out there, even ones that have the same password as you. Hence adding a salt.
None of this changes the strength of the password, just the feasibility of attackers reusing information against multiple accounts or multiple systems. A single pre-computed dictionary table that works against "all Windows machines" is obviously a huge population that needs some subdivision, hence salts.
Let me reiterate that everyone needs a security review, even systems designed by security experts. "Applied Cryptography" actually made this harder since suddenly everyone was an expert, without the hard lesson of learning the need for outside review. Unlike functionality bugs, security bugs are happy to lay dormant for years.
"make a “dictionary” —- say, of all combinations of alphanumerics less than 15 characters
hash all of them
burn the results onto a DVD. "
I hope you didn't read about Rainbow Tables from my article, if so I seem to have failed in explaining it.
It actually computes long "chains" of hash->password->hash->password, and only stores the start and then end. The hashes in the middle of the chain, that aren't stored, can still be searched. (I won't go into the details because I already wrote an article on it and linked to it)
It's a clever, elegant technique that's worth learning about for that reason alone.
"Here’s what you need to know about rainbow tables: no modern password scheme is vulnerable to them."
True. No modern password scheme is. Unfortunately most modern software doesn't use a modern password scheme. Take Windows XP/2000/NT, phpBB, the majority of custom password schemes; they're all vulnerable to precomputation attacks.
"Cool, huh? Yeah, and Unix crypt —- almost the lowest common denominator in security systems —- has had this feature since 1976."
Yes, but the majority of software since then hasn't had that feature, and doesn't have it to this day. Unix crypt is actually quite exceptional for a custom scheme in that it salts hashes.
Also early UNIX systems only used a 2 character salt, which doesn't protect it from a precomputation attack.
"Here’s a “state of the art” scheme from a recent blog post on rainbow tables and salts:
hash = md5('deliciously-salty-' + password)
There are at least two problems with this code. Yeah, the author doesn’t know what a salt is; “deliciously-salty-” is not a nonce"
When you deride someone for not knowing what a salt is it's a pretty good idea to know what a salt is yourself.
'deliciously-salty-' is a salt, and it will do the trick in protecting against precomputation attacks (though something a little harder to guess would definitely be better).
Nonces and salts are similar, but nonces are used as a salt and then appended to the hash, while salts are kept secret and are the same for all the hashes.
'deliciously-salty' is not a nonce, but it is a salt.
"MD5 is broken"
MD5 isn't broken for use with passwords. For digital signatures it's not recommended, but it's still perfectly fine to use for passwords.
"Speed is exactly what you don’t want in a password hash function."
It hardly matters. If you have a hash with a salt or nonce, the salt or nonce is say 15 characters = 120 bits long, the password is 5 characters = 40 bits, that's 2^160 passwords to try (let's call it 2^130, adjusting for the lack of entropy in most passwords, and let's reduce it to 2^100 to adjust for collisions).
Say you have 1000 computers that can try 100 trillion hashes per second each (for reference most modern computers can do a few billion MD5 hashes per second). It'll take ((2^100)/(100*10^12*1000)) seconds = 400 millenia.
"Modern password schemes are attacked with incremental password crackers."
The programs you make reference to just use a brute-force attack. (This seems to be what you mean by "incremental"). Unless you're only after one specific hash a pre-computation attack is far more efficient than a brute-force attack.
Depending on your desired success rate a rainbow table is typically around 60% wasted time, but because you can re-use the computed table you quickly make that time back. A brute force attack doesn't waste time, but you need to re-do the brute force attack when you have another hash to break.
"The password attack game is scored in time taken to crack password X. With rainbow tables, that time depends on how big your table needs to be and how fast you can search it. With incremental crackers, the time depends on how fast you can make the password hash function run."
The table generation relies on how fast you can run the password hash function too. Also the table size can be grown or shrunk by varying the chain length in the rainbow table, but as you increase chain length you increase collision chance and time taken to search the table.
Given a pre-computed table, the generation of which can also be parallelized, you will definitely be able to find a given hash faster than using the brute-force method.
Also "lightening-fast" doesn't cut it. See the 400 millenia calculation above.
You're really suggesting here that brute-force attacks are better than pre-computation attacks in all cases, and that brute-force attacks can be effective where pre-computation isn't. Very strange..
"How long? Your call. You can make a single password trial take milliseconds, or you can make it take hours."
This is a nice feature for allowing unsalted hash schemes to be used, but as the above calculation showed you don't need a hash trial to take more than 1 trillionth of a second to be secure, if you have a sufficiently large salt/nonce.
I'm not sure what you have against Rainbow Tables (it seems like a rather hostile article for something written in opposition to an algorithm), but at least get a better idea of what you're arguing against first.
Regards,
Kestas
I should actually qualify that by saying a long password is more secure *if you don't write it on a post-it and stick it to your monitor.*
A long password prevents rainbow table attacks just by virtue of being long. In addition, it *also* thwarts brute forcing of any particular password.
So, how long are your most important passwords? Mine are pretty short, too. As the referenced articles show, you can fit a *ton* of hashed values on a couple of DVDs. Enough to crack any password you're likely to see in the wild. The salt's purpose is to make this infeasible by requiring an attacker to bring e.g. millions of DVDs with them.
Hiding the method used to calculate the salt might make you more confident that an attacker won't determine a particular salt value, but:
a) You can't count on that.
b) Even if the attacker knows the salt value, it still serves its purpose. You could give it away, and it would still prevent rainbow-table-style attacks.
Knowing the salt used does make it easier to brute force a particular password, since you're brute forcing a shorter string; but, hiding the salt is not the way to fix that. Bcrypt for example, does the same thing, and you *can* count on it.
While I'm here, I've got to nitpick Nate's first paragraph. Salting does help, even when you're only considering one password. Let's say you've got a rainbow table that contains hashes for all passwords up to length 14. If my salt is 20 characters, guess what? You're going home. Same with *any* password in the system.
You can take that salt, and stick it into your algorithm, and begin calculating the hash of every password that begins with my salt, but this is essentially brute forcing the password portion, and takes forever when the values are not pre-computed. It will take extra forever if you use a slow hash function like the article suggests.
I would also hesitate to recommend anything other than the SHA-2 series of hashes for new implementations. There are two reasons for this;
1) It carries with it the significant weight of analysis that has been performed on the SHA series of hashes over the last decade or so. Over all of this time, no pre-image attacks have been found - which is what you need to be concerned about with regard to password security.
2) Nobody ever got fired for buying IBM. As a general rule, you should always stick to industry standards when implementing crypto-primitives. When you use a hash that is endorsed by NIST and was created by the NSA, you have some recourse to shrug off new attacks by pointing at all the smart people who are efforcing its use. When you use a different crypto primitive, you don't have this recourse, and you may very well fall foul of actual requirements that dictate the use of specific functions (eg NIST SP 800 57). I am reasonably sure that even Bruce-y baby himself (the creator of Blowfish) would not recommend Blowfish for new designs (although I am happy for Bruce to correct me in this regard).
However, I whole-heartedly agree with the idea that password hash functions should be computationally intensive. However, this can be done easily enough using multiple iterations of standard hash functions. The number of iterations is really a trade-off between your computational resources and the time budget in which you are working, and those of the attacker identified in your risk profile. Projects such as http://nsa.unaligned.org/ show why this sort of thing is necessary.
If you wanted to do something really wacky, you could modulo-exponentiate the input|salt using a modulus sized exponent before hashing it to get the final result. This would not be encryption so much as translating the input from pre-image_space to pre-image_space' using a computationally costly algorithm (but one that you will still find in normal crypto-accelerators if you find you need to scale up the login speed).
Finally, let me commend the statement:
"Let me reiterate that everyone needs a security review, even systems designed by security experts."
This is a fundamental truth that I find is well understood by people who 'grok' security, but is not well understood by most else. The initial entrants to the AES competition are excellent examples of why even smart, experienced, knowledgeable people still need others to look over their work.
I don't think it really impacts the article at all, though: the point is, web app developers read these rainbow table articles and say, "oh, I'll just use MD5 with a salt" (read the reddit and blog post comments). That's a really bad answer.
Salts are not kept secret; the original Unix crypt() implementation, where the term originates from, was public data. Shadow passwords were an innovation in the early '90s.
What I have against non-practitioners talking about rainbow tables is that the discussion ignores the real threat these applications face, which is that brute force attacks on raw MD5 are *substantially* faster than JtR runs against Unix passwords, which are already extremely fast. If you use salted raw MD5 as your scheme, you are insecure.
Errrr .... I'm confused. Where in my post did I imply that AES and hash functions are even comparable, let alone that one is stronger than the other? I would agree that an academic (collision) attack on the SHA-2 series of algorithms is more likely to happen before an academic attack on full round AES, but that is neither here nor there.
I would happily recommend the use of AES as a cryptographic primitive (along with NIST, the NSA, PCI, and pretty much every western government) - but if you are going to use it as a primitive for a hash function, I'd want to seriously examine the method you are using to turn an invertible algorithm into a non-invertible one-way-function.
When a system attempts to authenticate you, it checks the hash that's stored in the database against the hash of whatever you type in the equivalent of a "password" box.
If I find a collision, I now know a value that will hash to the same thing as your real password. As far as the system is concerned, the password that I entered is correct, since it hashes to the value that's stored in the database.
i'm going to pick a fight with your numbers. correct me if i've misunderstood something.
if you have the hash, you likely have the salt. it adds no entropy to the search. what it does do is prevent the size of the password database from decreasing the search time by forcing you to brute force individually.
while 5 bytes may cover 40 bits, for passwords we're likely limited to a typical keyboard: that means (26+10+11)*2=94 per character, for ~32.7 bits of entropy. that's being extremely generous and assuming full strength letters chosen randomly.
using your figures, we're likely to brute force the password in under 10 seconds on a single computer.
i only pick this out, because i don't want someone to read your otherwise very informative post and conclude that big salts make short passwords safer.
There are a number of ways in which block ciphers can be made to provide hash-like functionality. There are also a number of reasons why we do not do away with hash functions altogether and just use block ciphers. Your article (and the algorithm you reference) discusses the value in using Blowfish for the one way transformation from pre-image space (ie plaintext) to image space (ie 'hashed') specifically because it has a 'costly' key schedule.
How does this apply to AES?
@ mjo
The problem with collision attacks is that you (generally) have no control over the output of the collision - you just get either a block of data that hashes to the same value, or a data subset that you can place within an altered pre-image to produce the same hash.
When applied to password schemes such results are not often useful unless you can enter arbitrary binary data through the keyboard. This is not a real-world problem for password schemes, and therefore collision attacks do not reduce the security of password hashing schemes (as a pre-image attack would).
We seem to be talking past each other, or arguing for the sake of arguing, so I'll let you have the last word.
whenever a password is created-
1) generate have a 'fixed' seed table for each password char (random seeds per char... can be 2-20 seeds for a 1 char password)
2) append seed to password (in any variation)
3) generate hash, append the number of seeds used per char in clear.
4) hash with MD5 for the fun of it.
so whenever the server has to decrypt, it has to recreate the table based on number of seeds and do a brute force itself to derive at the password. }:)
Then we can simulate the web version of "Windows Loading".
RESTEKPA
it's kind of like my favorite smiths songs, but i eventually stuck with one. although i'm open to the idea of it changing again, but it hasn't changed in about 10 years
the advance in cryptography i guess would have something to do with precalculating the setup..?
i did something like that with SHA-1, see http://packetstorm.linuxsecurity.com/filedesc/s...
Thanks.
Thank you for bringing that up.
I agree 100% with Thomas's response. However, I wouldn't want to assume "attacker can read password hashes" == "attacker has 0wned the system". In particular, any "read-only" attack, e.g. a local file disclosure vuln or maybe some kinds of SQL injection, will give the attacker the password hashes without (or at least before) he 0wns the system.
[1]
Given enough Cray's and, any and I mean any p/w is cracked. I would like to thank Tom Cruise and The Church of Scientologi_crap for this inspired moment. You guys spend waaaaaay too much time debating arcana. Go for the weakest link.
p.s I am trying to take over as the kook du_jour, ffs, give me some propz
It IS a salt. And so is the password. Every input that determines the resulting hash IS a salt. Um, isn't it?
a. I'm surprised no one's mentioned PKCS#5 as a standard for generating hashes of passwords. The PKCS#5 PBKDF (Password Based Key Derivation Function) says you're supposed to pick an 8 octet salt and choose some arbitrarily large "iteration count." The algorithm hashes the password and the salt, then hashes the result of that hash, then hashes that hash again and again, hashing "iteration count" number of times. It also mentions the ASN.1 for storing / communicating iteration counts and salts and algorithms used to hash and it specifies a limited number of hashing algorithms that are suitable. Personally, I think that ASN.1 and BER are a pain in the keester and their only saving grace is that they could be worse. (So what I'm saying is look at PKCS#5 and RFC2898 for inspiration and guidance rather than an implementation template; but after you implement it yourself, always get a competent third party to check out the code. Or better yet, get a competent third party to design and implement the code.
b. The security of schemes like PKCS#5's PBKDF comes from the fact that if the server chooses a random 64 bit salt, the dictionary will be expanded 2^64 times. Iterating pass-phrases helps increase the time it takes to find a hit in the rainbow table, but yeah, iterating once isn't that great. Iterating 10,000 is a little better.
c. Salts and nonces _are_ effectively the same thing. My experience seems to be that when people are talking about octet strings they'll say "salt" and when they talk about random bit strings or numbers between 0 and N where N is some large number, the word "nonce" gets used a lot.
d. SRP _is_ covered by a patent, but Stanford's Office of Technology licensing says you can use SRP royalty free in commercial or non-commercial applications ( see http://otlportal.stanford.edu/techfinder/techno... .) I believe this means you still have to get a license, but that if you don't use SRP for bidirectional authentication (SRP-Z) you don't have to pay anything. But... I don't work for Stanford and I'm not an IP lawyer, so please contact Stanford directly if you have questions.
e. Collisions in MD5 _are_ a big deal. Well.. they can be a big deal. Consider a situation where you're an attacker with the password file for 1,000,000 accounts. You may not care which account you get into, only that you get into at least one.
f. Blowfish still scares me. No offense to Bruce, but Blowfish was designed to be a drop-in replacement for DES. It even has a 64 bit block size. If you create a password hashing scheme like crypt, but it uses Blowfish instead, you'll still have the problem that it's feasible to create a look-up table with 2^40 outputs (8 TiB). This reduces your "real" search space to 2^16, which may be practical given that since you're a bad guy you probably have a bot-net with at least 2^16 machines. I think what I'm trying to say is you can make a bad system with Blowfish. (Twofish or AES on the other hand might be a better choice...)
Collisions in MD5 _are_ a big deal ... but not for implementations that use it to secure passwords. These situations are where pre-image attacks are a problem.
The current state of the art in MD5 collisions provides a collision given two different inputs, such that two different outputs are generated that produce the same MD5 value. See http://cryptography.hyperlink.cz/MD5_collisions... and http://www.win.tue.nl/hashclash/EC07v2.0.pdf for the most recent research in this area.
An important step in producing such collisions is the knowledge of the intermediate values produced during the MD5 calculations. These values cannot be known for the password, as the attacker only has access to the final output of the MD5 calculation. Therefore, given the current mathematical knowledge, it is not possible to construct a pre-image that produces a collision with an arbitrary output hash.
Added to this is the fact that to produce a collision requires adding a value to the pre-image - and this value is generally too large to be considered for a password input. For example, in the recently published paper http://www.win.tue.nl/hashclash/EC07v2.0.pdf (which has been accepted to Eurocrypt 2007, providing some evidence of its pedigree), the production of a collision required appending 4196 bits to each of the certificates to produce the collision. Ignoring the fact that knowledge of both pre-images are required to produce such a collision, how many password systems allow for the entry of such binary strings of such length?
I agree that new systems should not use MD5 - but making links between current MD5 collision attacks and insecurity in MD5 password schemes is just plain wrong.
http://oss.coresecurity.com/projects/pshtoolkit...
Along with gsecdump.exe by johannes.gumbel@truesec.se you have one of the best threats to Windows security. Gsecdump -u will dump all the hashes of previously logged in people that have used the computer and didn't reboot after they logged out. With these hashes you can pass the hash to their systems and gain full access without ever needing to know their passord.
Yes, there was a better way to store the Windows passwords but that road was not taken so you have to live with the results.
Many of your unix admins don't know how to stop a ypcat passwd anyway or else they would stop that from leaking the unix hashes.
After 3 (or whatever) tries, lock the account for 5-15 minutes. Seems like this would be a severe deterrent to brute force/rainbow attacks. Especially if you don't inform them that the account is locked, you just keep sending "not recognized" messages.
Doesn't such a defense factor in to how "easy" these attacks are in practice vs theory?
"To make it work securely in a browser, you have to feed the login page over SSL"
How is this any different to sending the cleartext password over the same SSL connection?
http://acts-as-authentable.googlecode.com/
While reading your post, I thought of something . . . can someone who is more well versed in things than me tell me whether it's a good solution?
Basically -- generate hashes of, say, 4x as many characters as you do now. Create 3 or 4 salts and chain them together. Then, put the salts around the password before hashing.
Then -- and here's the important part: MAKE MORE THAN ONE HASH OF THE RESULT. I mean, if your hash only handles smallish strings, or if it sucks in some other way, you can still hash the strings that are formed by every second letter, letters 4-8, or some other combination. Now the attacker needs to
1) get your verification code as well as your db
2) generate rainbow tables for . . . oh wait, there are too many combinations now!! :)
Is this good?
Greg
XXXXXPasswordYYYYYY
Hash a bunch of subsets of this string, make sure they intersect pairwise.
The password has to pass ALL these hash tests. How can a rainbow table attack defeat this without growing to prohibitive proportions? I am not a security expert, but I'm a math phd guy :) So I should have SOME intuition about this :-P
-Greg
AFAICT, I can replace your advice to "use bcrypt" with "use PBKDF2" and it's still the same, right?
Or is PBKDF2 used in a different scenario?
Many thanks for a great article!
I am only here because I came across a rar 3.x file with a password on it, but gained interest in the thread and read well 9/10th's of it anyways.
But what got me thinking was when someone said "Think like the attacker".
I keep hearing iterations and hashes and rainbow tables for keysets, etc.
like 15 character passwords and the like but what I don't understand is this, expand the base character set. Umm, okay don't flame me because I admit i truly don't have any idea what i'm talking about, (really I don't).
But in my mind you could have a password of 1 character, and i have no idea how many characters are in like unicode or whatever. But say this.
Build yourself a Brute force program, and Dictionary program and 100 petabyte rainbow table dictionary "thing" and i guess use your standard keyboard as I saw someone put it, like 0123456789abcdefgh...
But if your password was iluvĈăŖŚ, they'd never get it cuz they dont' figure anyone uses ascii symbols BUT if they did, there rainbow tables would have to include all ascii symbols same with brute force attacks and the like and then things would be SEVERELY timely for them.
ok, ok, ok, I know no one is going to type ascii symbols into there password but I would (do when allowed)
Why I don't know, but a Suse Linux guru I used to work with did it and I thought it was a great idea.
Sorry for dumbing the current running IQ of your board down, but I didn't hear anyone talk about charsets enough so I thought I might say something, keep the thread going, you know :)
Have Fun everyone
Matt :-þ
The reason character sets aren't discussed is because they aren't vitally different from a somewhat longer password. After all, you could always think "iluvCgraveaacute"... instead of using the fancy ASCII characters you typed.
In the end you discuss number of bits of information content, and a larger character set simply means those bits are stored more compactly.
1. Reverse the hash before storing.
2. Salt the hash using say 100 unique salts, then server brute-force the password with those salts when validating. (Wouldn't require storing the salt)
3. Hash the password, and loop on the result as many times as you wanted, though once would suffice.
I would think that doing any one of these things would negate the flaws of MD5.
salt makes passwords stronger (more variation) and also unique (eg a rand() hashed, concated to the password and everything hashed again, then finally salt is appended to the hash so you can extract it for comparing).
and if you don't want passwords to be seen in plaint text between client and server you must use https.
well, at least that's how i see it...
The point of salting, is to make it more inconvenient for a person trying to decrypt a long series of hashed passwords.
But you haven't?
The only ways to crack these hashes are by bruteforce since dictionary attacks and rainbow tables are only used to get ridicously easy passwords. If you use good salt, there is no way to bruteforce the password. Consider the following:
MD5(MD5(PASSWORD)+PASSWORD)
This would make it impossible to bruteforce, since it will contain more than 20 different characters. And since you were mentioning that MD5 is too fast, well you can always do the following.
DO 50 Times:
PASSWORD += MD5(PASSWORD)
PASSWORD = MD5(PASSWORD)+PASSWORD
Please explain to me how that is possible..
If f1, f2 are two one-way-functions in the sense that one is satisfied they cannot be inverted within reasonable time. Then it seems to me the function x->( f1(x), f2(x) ) will not necessarily have that property.
In other words , it is dangerous to store two differently generated hashes of the same password --
Is that "true"? Are there examples from real-life?
-- Stephan
if you are using the same algorithm to get the hashes, i can't see how you can get different hashes for the same password. Hashes would be useless then. However, you could get the same hash for two different passwords, but that is highly unlikely (even more when using salts).
example code below.
when installing the software (this is web software programmed in PHP, not a PC application). a unique 64 character random string is generated. we store this as $mainSalt, and it is then written to a file with a unique encrypted filename & stored outside of the document root.
$salt is also generated with a randomly generated 64 character string.
so yes we use 2 salt keys, 1 stored outside the web root in a file with a randomly generated filename.
the 2nd salt is stored alongside the hash in the db for that particular user.
the 2nd salt key '$salt' is unique to that particular user. and is regenerated on each change of password.
so then we have our encrypt function.
function icms_encryptPass($pass, $salt)
{
$mainSalt = ICMS_DB_SALT;
$pass_hash = hash('sha256', $salt.md5($pass).$mainSalt);
unset($mainSalt);
return $pass_hash;
}
$pass = plaintext password entered by user.
$salt = a random 64 character key uniquely generated for that user (stored in the users DB table, regenerated on each change password)
$mainSalt = a randomly generated 64 character seed that is stored in a file outside of the web root in a file that has a randomly generated filename.
ICMS_DB_SALT is defined as the 64 character seed that is generated and stored in file outside the web root.
by using 2 salts (1 which is stored in a file outside web root), the 2nd being unique to each user, makes it that no 2 users will ever have the same password hash even if they have exactly the same plaintext password.
the salt keys can be upto 255 characters each.
One of the number of points the author made on which there seems full agreement is: it doesn't matter how nifty one's newly invented algorithm seems, because you're not going to know for sure until it's too late. What matters is you have a strongly reviewed system using best-practices and (in case the password is valuable elsewhere) known very secure algorithms implemented with well-proven components.
I guess it stores the salt as part of the hash, which contradicts what I've read here (eg. store the salt in a different DB column).
Can someone explain that, maybe recommend a better alternative?
sha2: 8Z1ZCnhVnFi/FnkLMUtk4DMytgGGGspGR0j0EAuBd1E=
salt (random.org): 1kfzD3z3txrp6qYs
ripemd-hmac (sha2value+salt+password): vOJaZnRsgyhJvMjgkJU/airz92U=
You don't really need this for a password system. If u want to use two, just hash password and big salt with RIPEMD-160, then hash that a bunch of times with fast one like SHA-1. Should defeat most attacks... esp brute force.
I liked the fact that the author stressed using a proven password system instead of just throwing together your own. If you provide a service that you feeling a compelling reason to provide password secured user accounts you might as well do it right. OpenId may also a good option if you don't want to have to worry about implementing managing user passwords and authentication yourself. I think in general, far too many online services require passwords and user accounts. This page did it right in not requiring me to make an account to post a comment.
In general, good article. Educational and practical.
Store the password AS IT IS, and SECURE YOUR DATABASE. It's that simple.
If the data in your database is stolen, the ADMINISTRATOR HAS already FUCKED UP.
If users care that employers see their passwords in the database, the USER HAS FUCKED UP.
You want your verification to run slower? USE FUCKING TIMER TO DELAY THE RESULT! You don't need bcrypt.
Users must use a password manager, and generate/use huge random passwords. Only retards memorize simple passwords and use them over and over again; such people deserve to have their shit stolen.
But in my experience dba's and security experts tend to over-engineer and be paranoid un-necessarily, and like to restrict other from doing useful work.
But i liked the article and it made sense to follow, except for the crypto details which went over my head.
It seems there is a lot of interest among everyone but Mr. Ptacek in designing their own system. I believe that's the tendency of smart people and they "didn't build it; can't trust it" fallacy. Sadly, that attitude is prominent among developers - perhaps the case is different in the field of "security experts?"
And the array of places where security flaws can crop up is breathtaking in its variety and depth. The various cryptographic primitives may have flaws. Their implementation in a particular language may have flaws. Their compilation and deployment on a particular computer architecture may have flaws. The security protocols that use the primitives may have flaws. Their use of the primitives may have flaws. *Their* implementation and deployment may have flaws. The security system used to protect the computing resources may (will) have flaws. The browser may (will) have flaws. Etc., etc., etc. Even the list of places to look for flaws will have flaws. The notion that any individual person, or even a small team, could have enough expertise and unflagging attention to comb reliably for all of these possibilities is laughable. It doesn't matter how intelligent or informed or educated or experienced they are. They simply won't catch everything, and everything is what needs to be caught. That's really why security through obscurity won't work. It's not just that obscurity gives you a faulty impression (though that is true, too). It's that obscurity means unresearched, and unresearched means undiscovered flaws. Until they are, with your pants down.
BTW, hi, Thomas. It's been a long while, and I don't know if you remember me. Heck, I don't even remember when we met, specifically.
Firstly, how is it the user's fault if database readers can see their password information? If your bank stored your bank password in plaintext, is it your fault? And are you actually suggesting that banks and companies like PayPal store their user credentials in plain text?
Secondly, how does a timer delay prevent delays in brute-forcing or using pre-imaging attacks offline? The assumption here is that password database has been read, and now the hashes exist on attackers machines. All the timers in the world won't help you with anything.
If you want to continue living in the fantasy land where no system every gets compromised, please have the decency to do give us your full name and the name of the company you work for, so none of us ever hire you or purchase something that may have been built from you.
And please, if you are an expert in database security, please point us to your blog so that we can share in your wisdom.