Date: Mon, 31 Dec 2012 10:08:28 -0500 From: Matt Weir <cweir@...edu> To: crypt-dev@...ts.openwall.com Subject: Re: Intentionally Increasing Collisions in Password Hashing Algorithms In previous e-mails I went over how password hash collisions might work for a very low value site. Since I was starting out by investigating an edge case to see if hash collisions even had a chance of helping, I wasn't that concerned with modeling a more realistic level of acceptable risk vs. online attacks. To put it another way, I agree with Steven that a 15 bit hash might create unacceptable risk, and I had still used a *14 bit* hash in my examples. Rather than trust my gut when figuring out a better model of acceptable risk for online attacks, I figured I should just consult NIST’s newest version of their SP 800-63-1 Electronic Authentication Guideline. At least in the United States this is pretty much the gold standard when developing password creation policies. You can find a copy of it here: http://csrc.nist.gov/publications/nistpubs/800-63-1/SP-800-63-1.pdf You can imagine my surprise then when I looked up the requirements for a Level 1, (the lowest level), security site as seen in Table 6. Two things stand out: “The Verifier shall implement a throttling mechanism that effectively limits the number of failed authentication attempts an Attacker can make on the Subscriber’s account to 100 or fewer in any 30-day period.” “The secret provides at least 14 bits of entropy.” This means my initial assumptions about risk made in the previous examples matched NIST’s recommendations exactly for a level 1 site. I wish I could say that was planned, but I guess I was just channeling my inner NIST writer. Now there are still a lot of things to debate. For example hash collisions can hurt a user who voluntarily chooses a strong password even if the site allows them to pick a weak password. Aka the site might have a high tolerance for risk but the user might not. Then there’s all sorts of other assumptions, (for example how many sites really enforce a 100 attempt lockout policy?) But at least we have some standardized models of acceptable risk to work off of. The obvious next question then is: How do password hash collisions perform for a Level 2 site? Referring back to Table 6 in the NIST document again: “The secret provides at least 20 bits of entropy.” That makes the next step easy. All I had to do was change the rate of expected collisions from 1 for every 16,384 guesses to 1 for every 1,048,576 guesses. Plugging that number back into the Excel workbook I had posted earlier, I was able to calculate the number of expected collisions per password hash for the following hashes: Hash Type: Vbulletin Cracking Session Length: 5 seconds Percentage Cracked: 48% Expected Number of Collisions Per Hash: 9,925 Hash Type: Phpass Portable Hash Cracking Session Length: 5 minutes Percentage Cracked: 36.9% Expected Number of Collisions Per Hash: 1,083 Hash Type: BCrypt Cracking Session Length: 5 minutes Percentage Cracked: 9.3% Expected Number of Collisions Per Hash: 2 So what about higher security sites? Well there is an option for Level 2 sites where there is no account lockout, (aka the attacker can make millions of guesses if they want). In that case a secret with at least 64 bits of entropy is required. With a 64 bit hash the expected number of collisions with even a fast hashing algorithm like Vbulletin will be close to 0. Following NIST guidance, Level 3 and Level 4 sites also require the use of a secret, (in all instances), that has at least 64 bits of entropy. It should go without saying, but when talking about 64 bits of entropy NIST is no longer referring to passwords users select. Now we’re in the realm of authentication devices like RSA’s SecurID, or randomly generated passwords that are assigned to the users, (and then almost certainly written down). I’m still struggling with the question of what impact this will have on an attacker. It certainly seems to me that an expected 1k collisions per hash would significantly increase the amount of work to target password re-use across sites. With a strong hash like BCrypt though, would 2 expected collisions impact the attacker that much? I don’t know. One way to look at it is that currently an attacker only has to verify hashes they cracked. If they had stolen one-thousand BCrypt hashes, they would normally need to only try 93 base passwords against other sites, (assuming they only cracked around 9.3% of the password hashes using the previously detailed cracking strategy). With collisions they would instead have to try 2,093 base passwords, (2k collisions plus 93 that were the real passwords). It would actually be slightly higher than that, since there’s no guarantee that all the real passwords the attacker cracked were reused at the site they were targeting. If the user picked a different password, the attacker would then go back to submitting collisions vs. stopping if the user had picked the same password. Now is 2k guesses a significant impact compared to 100 guesses? Once again I don’t know. Another impact might be that a determined attacker performing a targeted attack will have a lot more uncertainty when using cracked passwords to attack other sites. Aka an attacker might be willing to spend months cracking a single BCrypt hash in the hope that they can use that password to log into a very high value account/site they don’t have access to. Normally they would spend those months cracking the hash, and if they didn't crack it, well at least they would know where they stood. If they did crack it though, they could then focus their efforts on trying that password plus assorted mangled versions of that password against the high value site. With collisions, even at two every five minutes, an attacker doesn't know if they really cracked the password until they try a guess that lets them log into the other site. They don’t know if their authentication attempts are failing because the user choose a different password or if they simply are trying a collision. In such a scenario, they now have to balance how much mangling they perform against each base password vs. trying a different base password. They also have a higher risk alerting the target or locking the account. So despite the fact that there’s still a lot of uncertainties on my part about how much impact password hash collisions will have on real life attackers, the more I look at this the more optimistic I’m becoming that this might actually be a good idea in some circumstances. Matt
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.