Date: Thu, 13 Dec 2012 12:08:05 -0700 From: havoc <havoc@...use.ca> To: crypt-dev@...ts.openwall.com Subject: Re: Intentionally Increasing Collisions in Password Hashing Algorithms On 12/13/2012 09:03 AM, Matt Weir wrote: > Now one potential downside with your approach in #1 is if a site is > re-compromised after they start changing salts when users log in, then > the attacker could combine the two hashes plus related salts to > effectively eliminate most collisions, (aka treat both of them like > one single hash). That being said, I think the potential advantages > would outweigh the negatives caused by a site being re-compromised. > Aka I'd rather the attacker steal a throwaway password vs stealing two > different passwords for the same user. So once again that's a neat > idea you came up with. This is a good point, and it led me to the following: I think it is clear that increasing the number of collisions is only worth doing under the assumption that most users re-use their passwords on multiple websites and don't really change their passwords. We know that in practice the opposite is usually true. Another thing we see in the real world is that a lot of people on the same website end up using the same password. For example, the RockYou database: http://www.passcape.com/index.php?section=blog&cmd=details&id=17 The top 20 passwords were all used by more than 10,000 users. Even passwords less common (say, the top 1000) are probably used by more than one person (I haven't checked). I suspect there is a strong correlation between people who re-use passwords on different sites and their passwords being used by other users of the same service. If so, to attack the increased-collision hash list, we can assume that if the user did re-use their password on a different site, then there will be some other accounts with the same password, so we can do this: To find the password for a hash-and-salt pair H, S: 0. Initialize an empty hash table COUNT 1. For each password guess P: 2. If H = hash(P, S): 3. COUNT[P] = 0 4. For each hash-and-salt pair H', S' in the hash list: 5. If H' = hash(P, S') 6. COUNT[P] += 1 7. EndIf 8. EndFor 9. EndFor 10. Return the P for which COUNT[P] is maximal. In English: We find the candidate password that satisfies as many of the other users' hashes as possible, and the one that satisfies the most is probably the right one. Essentially, we are combining the hashes of accounts with the same password to filter out collisions. If no element of COUNT stands out, then either the password wasn't something we guessed or the password isn't used by different users, so it probably isn't re-used on other websites (by the correlation assumption), so it's smart to give up on that hash and move on to the next. -- Havoc https://defuse.ca/
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.