Date: Mon, 17 Dec 2012 00:19:40 -0500 From: Matt Weir <cweir@...edu> To: crypt-dev@...ts.openwall.com Subject: Re: Intentionally Increasing Collisions in Password Hashing Algorithms One of the problems I’ve been running into is I don’t have a decent model/framework to try and evaluate if increasing collisions is a good idea or not. Below is my first attempt at creating that model for a very, (very), low security case. I tried to give at least a basic justification for all the assumptions I made, but everything here is up for debate. The first step is to define the maximum amount of risk allowed due to collisions during an online attack. This will in turn determine the minimum hash length and the maximum number of collisions we can intentionally cause. Online attack threat: This site makes no attempt to stop a sophisticated attacker who performs online guessing attacks. The passwords simply have to stop unskilled attackers from logging in with someone else’s account. By this it is assumed that the attackers would manually type in the password guesses and will not devote much time to making guesses. Think of your friends logging into your account so they can change your status update to ‘butts’. Number of guesses allowed: 100 Justification: It seems like after 100 guesses someone would get tired of trying to log in. Acceptable Risk: 1% risk of someone logging in Justification: It’s rare enough that it would put a serious amount of work on an unskilled attacker for a low chance of it succeeding. Yes this is a wishy washy justification, but when have you last seen a good justification for acceptable risk? Plug those values into the equation: 2^H(x) = Number of Allowed Guesses / Chance of Success Rounding up, (since you can’t have a fraction of a bit), a 14 bit hash is the smallest hash we can use. Assuming the hash function is equivalent to a random oracle, a collision is expected to occur once every 16,384 guesses. The next step is more complicated. How much will this impact an attacker who has the goal of using this password against another site and is performing an offline attack? First we need to estimate how much effort an attacker is willing to devote to an offline cracking attack per hash. Luckily we can ignore the number of compromised users for now since it can be assumed that an unique password salt has been used. While there is some potential speedup when attacking a large number of salted hashes in GPUs, (especially with dictionary attacks where the cost of transferring a guess to the GPU is expensive), we’re not anywhere close to the point where we need to get into that level of detail. Hash Type: vBulletin (version 3.8.5) Justification: This hash is A) weak, B) widely used, and C) salted. Ideally we should be focusing on getting people to at least upgrade to phpass before we start mucking around with hash collisions, but I wanted to look at a really weak hash first. Cracking speed: 4 billion checks a second Justification: I’m basing my numbers off the following website: http://thepasswordproject.com/oclhashcat_benchmarking While an attacker can always throw more hardware at the problem, this seems like a reasonable average case. Time spent per hash before giving up: 5 minutes Justification: There’s a lot of assumptions that go into this number. My approach was to figure out how much a cracked hash is worth and then compare that to the amount of money an attacker could make mining bitcoins instead. I don’t know much about bitcoins, but according to this website: www.bitcoinx.com/profit The yield from being able to perform 1.544 billion BC hashes a second, (calculated using the above cracking setup though I might be widely off), is around twelve cents a hour. What I don’t know is the going rate for cracked password hashes at volume, (aka not a specific hash). Referring back to the InsidePro board I do see one posting for $5 per 1k salted hashes cracked, (plus a $200 bonus for cracking a large amount quickly), that received a number of replies/takers. Without the bonus, that’s about 1/2 a cent per salted hash. With the bonus it goes to 1 cent per hash. There’s a couple of other smaller postings as well for around 1 cent a hash. So the break even point between bitcoin mining and password cracking may be around 5 minutes per hash. But wait, this completely ignores the fact that if the attacker doesn’t crack the password in five minutes they get zero profit! Ideally I should factor that in as well, but that gets into more math than I’m willing to do with all the assumptions I’m already making. So I’m sticking to five minutes for now. I’d like to side track a bit and say how profoundly weird some of these results are when you follow them through. It certainly *seems* like someone’s password would be worth more than five minutes of work. Of course i’m basing this of a public forum, (which has huge risks for the seller, see the LinkedIn disclosure), so on private cracking forums the cost might be much higher. I don’t have insight into those unfortunately. Also this assumes all the crackers are intelligent actors that are constantly trying to maximize their profits using all the available information. Economists make this mistake *all* the time. People fall into habits, don’t think about what they are doing, or perhaps just prefer cracking passwords (heck I spend all this time doing independent research vs getting a second job), so these numbers might be completely bogus. As another side note, before I did the above calculations I originally had 1 hour as a placeholder so my gut feeling was *waaay* off. Expected number of collisions if the password is not cracked: =(4,000,000,000 guesses/s x 300 s) / 16,384 Which would mean the attacker can expect to generate an average of 73,242,187 collisions for each password they don’t manage to crack during their cracking session. Of course, as has been pointed out before, a significant amount of passwords would be cracked very early on. Collisions after the true password has been cracked can be ignored by an attacker because during an online attack they’ll try the guesses in the order they were cracked. For now we’ll also discount any additional effort an attacker might put into queueing up cracked hashes before testing them against other sites, (aka they might spend the full five minutes cracking a hash regardless even if they crack the real password in the first second). Unfortunately modeling password cracking attacks is fairly difficult since there isn’t one standard way people perform these attacks. Does the attacker use dictionary attacks; what dictionaries do they use; which mangling rules do they use; what type of brute force attacks do they run? The list goes on an on. Type of Attack: Bruteforce, using JtR’s Incremental mode Justification: The honest reason is I don’t want to bogged down modeling a dictionary attack right now. I can say with a straight face though that running brute force attacks against fast hashes is generally more efficient when using a GPU cracker. The reason I picked JtR’s Incremental mode vs HashCat’s BF++ is because Incremental is much more effective. A graph of running JtR’s incremental mode, (trained on a subset of the RockYou list and tested against an different 1 million password subset of the RockYou list), for 20 billion guesses, (About a 5 second cracking session, *yikes*) can be seen at the link below. Why only 5 seconds? Because my “checker” program is really slow, (and most certainly not GPU friendly). I’m going to post on the John-Users list to see if I can make better use of JtR logs directly (which are much, much faster), but I wanted to get some numbers out in the meantime. That being said, you can reasonably estimate how a five minute cracking session would fare based on the slope of the graph: https://sites.google.com/site/reusablesec/Home/pictures/Incremental_20billion_guesses_Rockyou.png So the short answer is around 48% of the passwords were cracked in a “5 second” timeframe. Could a real attacker do better? Certainly. One thing on my to-do list is to look at percentage of salted hashes cracked for money on the InsidePro forum. Still this is a starting number to work off of. For the rest of this document I’m just going to base the expected collisions for a 5 second cracking session, (vs a 5 minute cracking session). Still, since the number of new cracked passwords will fall dramatically as the cracking session goes on while the rate of collisions stays the same, the percentage of collisions per new hash cracked will rise over time. So now we know for 52% of the un-cracked passwords, around 1.2 million collisions will be generated in five seconds. Figuring out the collisions for the other 48% cracked passwords is more complicated. This is where Excel is really nice since I can simply estimate collisions at points in time based on the data. As a sanity check, my Excel document is available below so you can check my math: https://sites.google.com/site/reusablesec/Home/excel/14bithash_collisions_20billionGuesses_incremental_.xlsx So on average, for a five second cracking session, an attacker can expected to generate 635,215 collisions per hash even taking into account that collisions don’t matter after the attacker has ‘cracked’ the real password. I’d like to take a step back and say this is close to a best case scenario for the defender as we’re likely to get. Aka I started with the assumption that the original hashes were stored on a very low security site. The real goal of this whole exercise was to try to create a framework/model so that I could better define the assumptions I was making. Also this provided a quick sanity check on if creating collisions even has the possibility of being helpful. Based on the initial results, I think this is worth following up further. 635k collisions on average would be a huge cost to an attacker. Now there’s many ways an attacker can respond to this. For example limit their cracking time. Even with a brute-force session, an attacker can crack around 8% of the passwords with less than 50 collisions expected per hash; that will go down even further if a dictionary attack is used. On the plus side for the defender, if an attacker adopts this strategy, the attacker will only be cracking 8% of the passwords vs 48%. There’s another potential benefit that I didn’t think about until writing this. How would these collisions impact the password cracking market? For example, how do you go about paying people to crack passwords for you when there are a high number of collisions? Do you ask for 1k possible values per hash? How do you ensure the crackers are trying the most optimal guesses, (aka dictionary attacks or Markov enhanced brute-force) vs just running dumb bruteforce attacks (which may be faster), and selling you the collisions? Now I can start filling in more conservative values to see the effect this might have on higher security sites. I’m going to wait a little bit to post on that though because this current email has grown way to long, and quite honestly I’m interested in what everyone else thinks of the assumptions I made. 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.