28

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?

Henry WH Hack v3.0
  • 2,137
  • 2
  • 24
  • 37
  • 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 '16 at 14:11
  • 7
    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](https://en.wikipedia.org/wiki/Cryptographic_hash_function) work, and understand how your password is stored. – recursion.ninja Jan 12 '16 at 14:31
  • 19
    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 '16 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 '16 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: https://en.wikipedia.org/wiki/Cryptographic_hash_function#Password_verification – mostlyinformed Jan 13 '16 at 12:51

2 Answers2

44

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.

Vilican
  • 2,723
  • 8
  • 22
  • 35
CristianTM
  • 2,562
  • 17
  • 20
  • 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 '16 at 13:38
  • 12
    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 '16 at 13:44
  • Yes finding the other password would be as difficult as the first. It techicly would increase chances from try this random password method. However most people crack hashes using rainbow tables that would be no faster but depending on the charset of the rainbow table would have a better chance of being included even if it where small. – Nick Young Jan 12 '16 at 15:00
  • 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 '16 at 15:03
  • 3
    @daniel ive seen this happen before and the system was just trimming the password string before processing it :) – CristianTM Jan 12 '16 at 15:06
  • 1
    @Daniel Sounds like they were using the old DES-based [crypt](http://man7.org/linux/man-pages/man3/crypt.3.html) 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 '16 at 21:47
  • 1
    Note that the likelihood of a *specific* password hash colliding with another and the likelihood of *any two passwords of a large set* colliding with each other are very different. If you have n possible hashes and m passwords then the probability of any of the m colliding with a *specific* password are about m in n. But the probability that there are two passwords out of m that have the same hash is on the order of m in the square root of n. – Eric Lippert Jan 13 '16 at 01:41
  • is md5() considered a modern hash? – Aryeh Armon Jan 13 '16 at 11:34
  • No, not at all. Neither sha1. One should use at least sha256 and salt, and maybe more rounds of hashing, or bettrr funtions. Md5 is broken. – CristianTM Jan 13 '16 at 12:09
  • @AryehArmon - NO, no no a thousand times no. For the purposes of password hashing, PBKDF2, Bcrypt, or Scrypt, all with a sufficiently large number of iterations/work factor are considered modern. See Thomas Pornin's canonical answer to How to Securely Hash Passwords at https://security.stackexchange.com/a/31846/39623 – Anti-weakpasswords Feb 07 '16 at 23:39
10

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.

dr jimbob
  • 38,936
  • 8
  • 92
  • 162
  • 1
    About*2^256 ~ 10^76*, what does `~` mean in this context? Where does *10^76* come from? Thanks. – A.L Jan 13 '16 at 00:17
  • @A.L Roughly equals, as 2^256 has 78 digits – hkf Jan 13 '16 at 03:02
  • 1
    In this context, it means approximately equals; it has other meanings in other math contexts, see https://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 '16 at 06: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 '16 at 11:07
  • Is that merely a poorly designed forgot password feature, or is that "feature" simply the result of the horribly outdated and insecure practice of storing passwords in plaintext? – aross Jan 13 '16 at 13:02
  • @aross - It had two bad features; (1) password in plaintext/reversible encryption (forgot password features should require you to validate yourself and then set a new password), and (2) stripping out special characters from your password drastically weakens it. Take OP's pw `!78ghA,NJ58*#3&*` - 16 chars randomly chosen from 96 printable ASCII chars : ~105.4 bits of entropy (52040292466647269602037015248896 pws) - very secure. Stripping special chars makes it 59.5 bits (839299365868340224 pws) - much less secure. If numbers were also stripped its 28.5 bits (380,204,032 pws) - very weak. – dr jimbob Jan 13 '16 at 16:23
  • 3
    @A.L - I'm going to keep using tilde for approximately. It's a common succinct notation ( https://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 '16 at 16:40