[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 18 Dec 2012 12:23:52 -0500
From: Matt Weir <cweir@...edu>
To: crypt-dev@...ts.openwall.com
Subject: Re: Intentionally Increasing Collisions in Password
Hashing Algorithms
Hey Solar,
> Why look at a really weak hash first? I think it only makes sense to
> consider controversial changes such as deliberate hash collisions on top
> of state of the art setups.
I'd like to begin by saying I mostly agree with you. Referring back to
my earlier post:
>> Ideally we should be focusing on getting people to at least upgrade to
>> phpass before we start mucking around with hash collisions
The reason why I wanted to start with a fast hash like vBulletin was
twofold. First, I was trying to define an edge case, (lower bound
security), to see if this whole approach even had a chance of being
useful. To that end I wanted to model a situation where there was a
huge disparity between online and offline cracking speeds. After that
edge case was examined I could move on to more conservative setups. My
second reason gets into some issues that can stray way off topic from
the current thread, but it's due to the fact that adoption of bcrypt
and other computationally expensive hashing schemes has been very
limited. I can name three sites that I know use bcrypt: Twitter,
Cloudflare and @bitweasil's website. The number of websites I can name
that use portable phpass hashes or vBulletin is much greater. This
might be something you could shed a lot of light on for me. In your
estimation, what's the likelihood/time-frame for getting a bcrypt
equivalent strength hash as the default into phpBB3? I know phpass
supports BCrypt as one of it's modes which is why I'm specifically
wondering about its implementation in common software like phpBB3.
It's been my experience that when many people hear "computationally
expensive hashes" they immediately think that it will cause massive
performance issues or open themselves up to new types of DoS attacks.
That's why I like seeing tests/studies like those run by @DefuseSec
https://defuse.ca/website-key-stretching-feasibility.htm that
investigate, (and hopefully disprove), the worries that site admins
have. That's also part of the reason why I'm interested in hash
collisions. Since there's no real performance overhead, would it be
possible that it might be able to gain some adoption when sites were
unwilling to take a performance hit of using PBKDF2 or BCrypt with a
large number of iterations ?
To answer the question of what happens when portable phpass hashes or
Bcryt are used with collisions let me refer back to the model I
described previously. The reason why I focused on a model first was
now it's fairly easy to look at the various assumptions I made, tweak
them, and then see the results.
Let's start with portable phpass hashes, (like those used in Phpbb3).
Referring back to the previous hardware setup it can be expected than
our 'average' attacker can generate around 6 million hashes a second.
This is a huge decrees from the 4 billion hashes a second they were
getting with vBulletin hashes but that's still 1.8 billion guesses in
a five minute time-frame. Thanks to the wonders of Excel, I can simply
plug the shorter cracking session into the Excel workbook I posted
earlier, (I just ended the checks at row 16955 fwi), and I see that
69,322 collisions would be generated on average. That's taking into
account that the attacker would crack nearly 37% of all the passwords
in that time-frame.
Unfortunately, the passwordproject's webpage doesn't have benchmarks
for Bcrypt, but refering to hashcat's main webpage, (hashcat.net), an
attacker can expect to get around 8,000 c/s against BCrypt$2a$ hashes
with two hd6990 GPUs. That's about 2,400,000 guesses in a five minute
period, (and is why BCrypt is really nice). Referring back to the
Excel document, (row 2274), we are now averaging around 132 collisions
per user, with the attacker cracking 9.3% of the passwords.
What does this all mean? I'm still trying to figure that out... While
132 collisions does add additional cost to an attacker, it might not
be enough to justify it, especially considering the fact the
underlying amount of risk that's accepted in that example. That being
said, nearly 70k collisions for a popular hashing algorithm like
phpass would have a huge impact for an attacker.
In short, I'm still on the fence myself on if adding collisions is a
good idea or not, and if so when/where it would be applicable. That's
why I'm still investigating it, and why I'm very interested to hear
everyone else's opinions.
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.
