Conversation started Aug 9, 2012 at 20:56.
Aug 9, 2012 20:56
@Iszi I thought mine did
@Gilles There are jurisdictions where "civil matters" can cost you a hand, or your neck.
That's why I answered, by the way. Lots of good advice on Thomas's answer, but the directly on-topic part was kind of buried.
@Gilles Maybe I'm not quite seeing it.
@ThomasPornin but they tend not to care about Apple's intellectual property
Anyway, time to go home.
Aug 9, 2012 20:58
ta
@Iszi “The attacker now has an easier job: he can find any password whose hash begins with 2c26b46b68ffc68ff99b453c1d304134.”
and “The only way to invert a proper hash function is by straight brute force: guess the password, compute your guess's hash, compare with the reference hash. If the reference hash is a truncation of the real hash, the attacker gains a negligible amount of time doing the comparison. For a massive brute force attack, or if you truncate the hash too much, the attacker may have its job made easier by finding a collision on the truncated hash which wouldn't have been one on the original hash.”
@Gilles Yeah, that does a good job of explaining how the attacker's job is easier. (Though, for me, there are some readability issues.) However, what I was interested to see, and @ThomasPornin did a good job of spelling out in his edit, was a direct answer to the original headline: "Does truncating the hash make the password harder or impossible to crack?" Targeting the actual password, the answer is yes.
Addressing the latter part of the question though "are there problems with this" is what most of the answers have done - and the answer to that is absolutely, because truncating the hash means that there are a whole lot of other passwords that will now be valid.
@Iszi No! The answer is no
@Gilles Oh?
Assuming the password has less entropy than the truncated hash
which is always going to be the case in practice
Aug 9, 2012 21:09
I don't follow.
Ok, then I'm not doing a good job of explaining it
One of the assumptions in the question is that it's a good hash that's being truncated
@Gilles Good hash, plus salts, etc.
@Iszi good password hash function, something like PBKDF2
but actually that doesn't matter, the answer would be the same for SHA1
The point is that the only way to find the password is by brute force
I assume that the hash function is not invertible in practice
The point of salt is to make brute force attacks harder because you can't factor the work. However this is irrelevant here.
Okay... still not seeing my flaw in logic.
So: the attacker will look for the password by making a guess, computing truncate(hash(guess)), and try again if truncate(hash(guess)) != reference_truncated_hash
the attacker stops when truncate(hash(guess)) == reference_truncated_hash
ok so far?
Aug 9, 2012 21:13
Agreed.
so now the question is whether this guess is the actual password
Exactly. Irrelevant now, from the attacker's perspective, but still part of the question.
if hash is a decent cryptographic hash function (e.g. one of the SHA), the password is memorable by a human, and the length of the truncation is decent (e.g. 16 bytes), then I claim that it is
So, you're saying that a truncated hash is, in effect, equally collision-resistant as the full-length hash?
@Iszi Not equally, but proportionally (for some approximation of proportionally)
Aug 9, 2012 21:17
@RoryAlsop had to publicly disagree with you, I think this is the 2nd time...? discuss.area51.stackexchange.com/questions/5511/…
In an ideal hash, all the bits are independent: if you have 3 bits of the hash, and you're looking for a preimage, the best you can do is discard 1 guess in 8
Interesting. I think @ThomasPornin's answer speaks contrary to that though.
For the SHA family, this is widely believed, and quantified by NIST
This is quickly getting over my head. I'm still interested to learn, but starting to get too deep.
 
Conversation ended Aug 9, 2012 at 21:18.