[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <50CA2795.1020404@defuse.ca>
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.
