Information Security Stack Exchange is a question and answer site for information security professionals. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 about 40 or more 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?

share|improve this question
    
Ive seen your edit. Please clarify the os/system used for a specific answer. Other than that, probably my answer applyes, that is, it is theoretically possible but not feasible. – CristianTM Jan 12 at 14:11
6  
For a given hash function f, there are an infinite number of character strings x such that f(x) = f("!78ghA,NJ58*#3&*"). Look at how hash functions work, and understand how your password is stored. – recursion.ninja Jan 12 at 14:31
17  
FYI - the reason why your nokia phone was able to be unlocked with 2 codes is that they had a master unlock PW based on the serial number of the phone which you couldn't change. It had nothing at all to do with the unlock code you picked. Considering how easy it is to determine the master unlock code, this was a serious security failure on Nokia's part. – NotMe Jan 12 at 16:15
    
If you worry about password hash collisions, consider that being hit by a lightning strike is more probable (and consequences are more severe). – Dmitry Grigoryev Jan 13 at 11:37
    
The two answers below are good ones. That said, I wonder if the question asker, if he or she is still reading, might be a little confused about what a "password hash" is. The thing to understand is, no responsible web site operator just stores user passwords in plaintext; if somebody with bad intentions ever managed to break into that database he or she could immediately read the password for every user(!) Instead...well, I won't try to explain in a comment. Here's a link to Wikipedia's pretty good description: en.wikipedia.org/wiki/… – halfinformed Jan 13 at 12:51
up vote 43 down vote accepted

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.

share|improve this answer
2  
The larger your resulting hash compared to your input length and the hashes possible charset compared to your passwords possible charset the less likely collisions. If you store 512 character passwords as an 8 character hash, lots of collisions, average 16 character alphanumeric + symbols in a 256 character hash, not at all likely (But the math probably meas we have at least one) – Nick Young Jan 12 at 13:38
11  
Also, finding the "other" password would be equally difficult to finding the actual password. There aren't (known) static backdoors to most modern password hashing algorithms. This doesn't preclude an intentional backdoor though, as found in various firewalls recently. – Matthew Jan 12 at 13:44
1  
I was a computer science student at a somewhat prestigious university in the United States. The CS department had a separate account server from the main university system and when logging into one's CS account, as long as the first 8 characters of the password you typed in matched the first 8 characters of the correct password, it didn't make any difference what you typed after that. I have no idea what they messed up to make that happen, but it did happen (and was like that for all 4 years I was a student at the university). – Daniel Jan 12 at 15:03
2  
@daniel ive seen this happen before and the system was just trimming the password string before processing it :) – CristianTM Jan 12 at 15:06
1  
@Daniel Sounds like they were using the old DES-based crypt function. The same thing also happened two years ago at a local VPS provider... I'd guess that this will keep happening from time to time. – Lekensteyn Jan 12 at 21:47

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 2256 ~ 1077 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 1077 hashes, some hashes will collide (provable by the pigeonhole principle). If you tried 1080 hashes, you should expect to find about 1000 passwords that match any given hash.

However, 1077 is an extremely large number; it's roughly the number of atoms in the observable universe. Or if every atom in the solar system (~1057) each calculated a hash every nanosecond it would take about 3000 years before you calculated 1077 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 1057; 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.

share|improve this answer
1  
About*2^256 ~ 10^76*, what does ~ mean in this context? Where does 10^76 come from? Thanks. – A.L Jan 13 at 0:17
    
@A.L Roughly equals, as 2^256 has 78 digits – hkf Jan 13 at 3:02
1  
In this context, it means approximately equals; it has other meanings in other math contexts, see en.wikipedia.org/wiki/Tilde#Mathematics . The main reason for not using the slightly clearer ≃ is that unicode is harder to type. As for where it comes from 2^256 = 115792089237316195423570985008687907853269984665640564039457584007913129639936 = 1.1579... x 10^77 ~ 10^77 (I originally had off-by-one typo). If you want to find what power it is you could just set 2^256 = 10^x then take the log of both sides and use well-known properties of logs to find x = 256 log(2) / log(10) ~ 77. – dr jimbob Jan 13 at 6:02
    
@drjimbob I was confused because I rode 2^256 ~ 2^76 instead of 2^256 ~ 10^76. Anyway, I suggest to replace ~ with or about in order to avoid ambiguities. – A.L Jan 13 at 11:07
1  
@A.L - I'm going to keep using tilde for approximately. It's a common succinct notation ( en.wikipedia.org/wiki/Tilde#Common_use ) for "approximately" (as a unary operator; e.g., about ~7 billion humans) or "approximately equal" (as a binary operator e.g., 2^10 ~ 10^3) and my answers already tend to be on the long side. I'd rather just explain this notation to people unfamiliar with it if they ask. – dr jimbob Jan 13 at 16:40

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.