Is it possible for my password to have more than one password combination?

Question

Can my password have more than one password combination?

I read up on physical combination locks (the lock you open with numbers) and I learned that a combination lock can have more than one possible combinations.

Also I had my first phone, a normal Nokia phone (not a smartphone) that was password protected and I was able to open the device with a password that was not really the exact password for the phone. Like, if the password was set to 4545 and I typed 1111 the phone still unlocked. Or if the phone password was set to 4114 and I typed, let's say, 2141, the phone still unlocked.

The question is, if my password for my Laptop PC was !78ghA,NJ58*#3&*, is it possible that a next combination will work behind my back or will it work only if there is a vulnerability?

Answer 1

In most password-protected systems it usually is possible, but very unlikely.

Behind many password validation mechanisms is the use of salted hash functions. For the sake of simplicity, let's forget about salt for a moment.

When a user sets its password, hash(password) is stored in the database When the user logs in presenting password', hash(password') is compared to hash(password). If it matches, the user is allowed to log in.

Let's remember, however, that hash functions get data of unlimited length and transform it to data of limited size, ex. 128 bits. Therefore, it is not hard to understand that there can be more than one message that produces the same hash from a given function. That is called collision and it is what you are concerned about.

The thing is that hash functions are produced to be so random that you should not find or produce a collision easily. It is theoretically "possible", but practically "impossible", if you are using a good modern hash function.

Answer 2

First, by mathematical theory - yes (though in practice you can totally disregard this for modern hash functions and numbers achievable by computation in this universe). If the system doesn't store your password in plain-text or via reversible encryption, but instead hashes it (as is best practice) there are an infinity of potential passwords that will generate a hash that matches your hash (assuming an ideal cryptographic hash function).

For example, if your password was password = '!78ghA,NJ58*#3&*' and they used a salted sha256 hash (note this should be key-strengthened with many rounds to make brute-force harder) with a 3-byte salt: d7 35 e6 then your password hash would be 4fe5bbb74a21fb6d20785ce7fce1cd51d6fc87c5a55f65d75e8f37096ed54a53 (in python you can calculate this with):

>>> import hashlib
>>> salt = '\xd7\x35\xe6'
>>> password = '!78ghA,NJ58*#3&*'
>>> hashlib.sha256(salt + password).hexdigest()
'4fe5bbb74a21fb6d20785ce7fce1cd51d6fc87c5a55f65d75e8f37096ed54a53'

Note this hash is 256 bits. So there are only 2²⁵⁶ ~ 10⁷⁷ possible hashes. If the hash functions works well and selects hashes uniformly for all possible inputs (that is the hash function acts as a random oracle), once you try significantly more than 10⁷⁷ hashes, some hashes will collide (provable by the pigeonhole principle). If you tried 10⁸⁰ hashes, you should expect to find about 1000 passwords that match any given hash.

However, 10⁷⁷ is an extremely large number; it's roughly the number of atoms in the observable universe. Or if every atom in the solar system (~10⁵⁷) each calculated a hash every nanosecond it would take about 3000 years before you calculated 10⁷⁷ hashes, so this isn't something you have to worry about in practice.

(If you tried 5 billion hashes per second for 100 years, and you had some very strong password the chance of randomly finding a different password that matches your 256-bit hash is 1 in 7.4 x 10⁵⁷; this is like the odds of buying 7 powerball tickets on successive weeks and winning the jackpot the first 6 times and then playing a 7th time and matching 5 numbers (no powerball) to only win $1 million.)

---

Granted, this doesn't mean in practice your password is unique. I have personally run into a deployed Cisco VPN system in the wild that truncates a 12-character random password into 8 characters without notifying the user (I initially found out when I typed too fast and left off a character and it still worked; and then did trial and error). So as long as the first 8 characters are right, then you can type whatever you want after that and it will work.

This isn't isolated case either; e.g., Microsoft used to silently truncate Windows Live ID passwords to 16 characters though it now informs the user that it limits passwords to 16 characters:

Windows Live ID passwords were always limited to 16 characters—any additional password characters were ignored by the sign-in process. When we changed "Windows Live ID" to "Microsoft account," we also updated the sign-in page to let you know that only the first 16 characters of your password are necessary.”

It's also possible that a poorly designed authentication system will strip special characters out of the middle of your password. My friend found out that T-Mobile did this in 2011 when he used their poorly designed "forgot password" feature that sent him his password in plaintext which in his case stripped the special characters out of his password.