"If I had to store that much there, even temporarily, I would use a password so long it would make War and Peace look like a Twitter message." - Brilliant
It would have many collisions with many shorter passwords.
But almost certainly not any collisions with very simple and very short passwords. The hash output space is sufficiently large.
Someone who (given infinite time) found a brute-force collision would likely find one of the shorter preimages first – you aren't really gaining anything by going ever-longer, after your preimage choice has as many bits as the hash output.
But if the attacker truly needed to brute-force it over the entire 160-bit (SHA1) or larger (other hashes) output space, unconstrained by usual simple-password-like limits on what to try as preimages, that's impractical, and you've achieved your goal... even if you overdid it on the input.
I suppose the defender could have a rainbow file of his own and purposefully choose a password which didn't hash-collide with a password of < N characters.
Doubt that'd be worth the effort/storage, even in the case of a weak, unsalted hash like MD5.
Take N to be 10, assume 7 bits per character. Then all 10-character passwords fill no more than 2^70 of the 2^128 MD5 space. Any 11-or-larger character password then has a less than 1-in-2^58 chance of colliding with any shorter password. (That's how much larger the full space is, from which each longer-password hash will be drawn.) That's 1-in-288-quadrillion for us decimal apes.
The service would probably never deliver a useful warning before MD5 falls completely to a preimage attack.
The analysis for such a service only gets harsher for 160/256/512 bit hashes.
Sadly Mt Gox used salted and at one point unsalted MD5s for its passwords. Finding a collision would be far easier with that consideration taken into account.
