Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 0 down vote favorite

As stated in this page large documents hashed using md5 maybe vulnerable to collision attacks. My question is even passwords of 6-30 character are vulnerable to such hash collision attacks? If yes, is there any proof available online or any example of two password phrase giving same md5 hash? I googled but of no help!.
Any how I am not going to store password hashed using md5, just asked this question out of curiosity.

share|improve this question
1  
A hash of a short character password is vulnerable to a Pre-image Attack. I suppose a collision in the password (e.g. two users both using "password" for password) is more likely than finding two different passwords hashing to the same value. – Henrick Hellström Mar 20 at 10:01
For 6 or 7 character passwords, there's no point in worrying about hash collisions. Just guessing the password would be much easier. – David Schwartz Mar 22 at 22:32
A bit of clarification for someone who's native language isn't English. You use even to denote inclusion with a bit of disbilief, not to say that the password is an even value, or it has an even number of bytes? – rath Mar 22 at 23:12
HenrickHellström and DavidSchwartz thanks for your comments. @rath I used 'even' as adverb, read more – Cyril Mar 23 at 7:06

2 Answers

up vote 3 down vote accepted

Data of more than a few dozen bytes can be vulnerable to MD5 collision attacks, but only (as far as is known) when an adversary can inject (choose) enough data of her choice in both the legitimate and forged version, which is feasible in some important scenarios, including certificate signing. There is evidence this was used by the flame malware, and plausible speculation that it went undetected for years.

No, passwords are not vulnerable to hash collision attacks in the standard use of a password hash, where the hash is stored instead of the correct password and used to test a candidate password; that's because the adversary is assumed not to know the password, and can not inject material in both hashed messages; it is thus immaterial that in such a standard password hashing application, what's hashed is generally below the threshold where MD5 collisions are known to be feasible.

However, hashed passwords can often be recovered when their hash is known, by a different attack, specifically a brute-force (first) pre-image attack: e.g. an MD5 rainbow table if the password was hashed using MD5 without salt; or, even with salt, enumerating plausible passwords using a password cracker. To defend against these attacks, one should avoid a password hash getting known, and when that can't be insured with high confidence must use a good, purposely slowed password hash, such as scrypt with salt and appropriate parameters. Improving password hashing is an active research topic.

Update: CodeInChaos rightly points in a comment below that even in the standard use of a password hash, an adversary allowed to change password (and perhaps, knowing the salt) could use a password collision so as to select a password such that another password allows access, which she could use to discredit the system to some degree.

Update: Ricky Demer rightly points in comments below that in some Password Authenticated Key Agreement (PAKE) protocols, finding collision on messages involving two different possible passwords can give a useful advantage to the adversary: the ability to check these two passwords with a single query.

share|improve this answer
1  
The adversary can inject material (though the salt might block any collision attack). But such a collision attack at best(from his point of view) allows the attacker to create an account for which he knows two different passwords. Not very useful... – CodesInChaos Mar 20 at 18:03
1  
Passwords are vulnerable to hash collsion attacks when using a hash with PAKE or augmented PAKE. $\;\;\;\;$ (In those cases, it is realistic that the adversary can inject the work factor(s) and the salt.) $\hspace{.7 in}$ – Ricky Demer Mar 20 at 18:52
1  
Suppose the attacker has password1,password2,salt,workfactor[,memfactor] such that $\:$password1 $\neq$ password2$\:$ and $\:$passwordhash(workfactor,salt,password1[,memfactor]) = passwordhash(workfactor,salt,password2[,memfactor])$\:$. $\;\;$ If the inner PAKE is augmented, then the attacker computes a verifier for passwordhash(workfactor,salt,password2[,memfactor]). $\;\;$ When the client attempts to connect, the attacker sends it salt,workfactor[,memfactor] and then uses passwordhash(workfactor,salt,password2[,memfactor]) or the verifier as its input to the inner PAKE protocol. $\;\;\;\;$ – Ricky Demer Mar 20 at 23:44
Are bruteforce or rainbow tables really first preimage attacks? – Smit Johnth Mar 23 at 14:40
1  
@Smit Johnth: Yes, rainbow tables and password search by enumeration qualify as first-preimage attacks: they start from a hash, and try to find a value that hash to that; most usually, that's using brute-force. – fgrieu Mar 24 at 7:56
show 1 more comment
up vote 0 down vote

No, they are not. Since for finding message for a hash you don't find collision but a first preimage - which has quadratic complexity compared to collision attack due to birthday paradox.

share|improve this answer
The birthday paradox applies to brute-force collision search, not to collision finding by broken hash function. So hopefully MD5 is still secure (with more than only quadratic security) against preimage attacks. On the other hand, for preimage attacks against passwords a usually quite small search space applies, so its complexity is also smaller than a generic preimage search. – Paŭlo Ebermann♦ Mar 24 at 22:39
Duadratic security is more that enough :) Even MD4 which is completely unresistant to collisions is resistant to first and second preimages - at least, no successful attacks are known. – Smit Johnth Mar 25 at 17:18
Yes, but there is no "quadratic" in there. It is not that a collision takes $x$ steps and a preimage takes $x^2$ steps, more like a collision takes $x$ steps (with a quite small $x$) and a preimage takes $x·2^{128}$ steps (or $x·N$, where $N$ is the number of passwords to check). The "quadratic" is only valid for a brute-force attack on unbroken hash algorithms. – Paŭlo Ebermann♦ Mar 27 at 0:10
Interesting. Can you provide real numbers for some hash functions? – Smit Johnth Mar 27 at 9:20
Not really, sorry. As you said, MD4 is totally broken in terms of collision resistance, so much that building a collision takes even less work than one hash operation ($x$). On the other hand, to find a preimage, you still need a brute-force search of either around half of all possible preimages (for a short password), taking $N/2·x$ work, or in average $2^{127}$ hashes (for an preimage of an arbitrary hash), costing $2^{127}·x$ work, where $x$ is the cost of one hash evaluation. (Actually, if Wikipedia is correct, there is a faster preimage attack using $2^{102}$ work – I didn't check this.) – Paŭlo Ebermann♦ Mar 28 at 21:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.