This question already has an answer here:

From what I understand, in most sites, passwords are stored as a hash; not in their original form. This means that if the database is hacked into, the attacker will see the (nearly) useless hashes instead of the actual passwords.

For the website to authenticate your login attempt, it hashes your attempt of a password, and checks if it matches the stored hash. If they match, it logs you in, otherwise, it denies it.

I've read on many sites though that no hash algorithm can produce 100% unique hashes; collisions will always happen.

Does that mean that, theoretically, there exists another password that will give the same hash given a hash-function, which means there is potentially more than 1 password that could be used to log in with (although the other password would probably be near-random for a complicated hash-function)?

marked as duplicate by gnat, Community Jun 28 '15 at 17:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • see also: Randomized Hash function with no collisions – gnat Jun 28 '15 at 17:37
  • The technical term for this is a "preimage attack", and yes it's possible. A hash function is considered "cryptographically secure" when it makes preimage and other attacks prohibitively difficult to carry out. If you want to learn more, there are many questions on security.stackexchange.com about which hash functions are more or less resistant to preimage attacks versus other kinds of attacks. – Ixrec Jun 28 '15 at 17:46
  • 1
    The answer to the question in the title is "Yes", but it doesn't matter. A decent hash function cannot practically be cracked by brute force, which means these alternative password cannot practically be found. – gnasher729 Jun 28 '15 at 20:54
  • @gnat The requirements for a collision resistant hash (e.g. SHA-2) and a password hash (e.g. PBKDF2, bcrypt, scrypt) are quite different. In particular the latter is slow, salted and only requires first pre-image resistance not collision resistance or second preimage resistance. So I'm not sure if it's appropriate to close a question about password hashes as a duplicate of a question about collision cryptographic/collision resistant hashes. – CodesInChaos Jun 29 '15 at 9:38
up vote 9 down vote accepted

There are in fact infinitely many passwords which produce the same hash. That is actually more or less the definition of what it means to be a hash function: reducing a larger (potentially infinite) input space into a smaller finite output space.

However, a "good" hash function will distribute the hash values among the input values in such a way that any similarity in the input does not translate into similarity in the output. For a cryptographic hash function, such as the ones used for password hashing, this requirement is even stronger.

What this means, basically, is that the passwords which have the same hash value tend to be very dissimilar. In particular, most tend to be very long, very unreadable, cryptic apparently random strings.

  • Infinity many is a bit of an exaggeration. – paparazzo Jun 28 '15 at 17:36
  • 8
    @Blam: it's no exaggeration. Strings have unbounded length, so there are countably infinite of them. Hashes have finite length, so there are finitely many. Thus, at least some hashes (all, with a "good" hash function) have countably infinite pre-images. – outis Jun 28 '15 at 17:42
  • 1
    Strings may have unbound length but passwords don't. Your typical password rule is 6 to 32. It may be 128. It will never be unbounded. You don't have unbounded bandwidth or memory. – paparazzo Jun 28 '15 at 17:45
  • 1
    The claim that infinitely many strings will produce the same hash is still accurate, even if only a finite number of those strings can be used as passwords in the real world. – Ixrec Jun 28 '15 at 17:50
  • 2
    @lxrec Maybe that is a valid statement but it is not a valid answer to the stated question. The stated question is not infinite number of strings the stated question is password. There are not infinitely many passwords as there is no authentication in practice that allows an infinitely long passwords. There is not even a computer that allows infinitely long strings. – paparazzo Jun 28 '15 at 17:59

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