Is there a proof that guarantees strength of password?

Question

Is there any proof that guarantees that a password with specified features (eg. with random special characters, combination of numbers & letters, some length etc) is secure? If there is such a proof, can you provide it or a link to it?

Edit: I am looking for formal proof, argument of theory that backs the choice of password -- formal proof based on which for example, I can propose advice for a government -- a formal proof with approved standard.

Edit 2: Or what concept is used to analyze password to determine that a password is either strong or weak? If you tell someone that "1234" as password is weak, what concept are you using to back your claim?

Answer 1

I have voted to close this questions. But since you don't even go to school, I explain it in simple words.

The word "proof" is not applicable for password strengths, in the usual sense.

An essential part of the modern cryptography is low probability of guessing of some data (guessing password, guessing components of the private key, etc.) To keep the probability low, high degree of randomness, in other words, high entropy, is required.

If all characters of password were chosen randomly and if there are relatively many possible passwords, the only way to break such password is to try all possible combinations of characters. Such approach is called brute-forcing. Obviously, if an attacker tries all possible combinations, then the password will definitely be found. The more passwords are possible, the more time is needed to try all of them. The performance of computers is limited. That's why the protection strategy is to have so many passwords, that trying all of them takes so much time, that the password will not be found within the time that is important for you. For instance, if you have a password of 90 bits entropy, then even with the computing power of the whole world the attacker would need many millions of years to try all possible combinations and to find the password. Again, there is no guarantee for this. It may be that password will be found within a short time. But the probability that it happens is extremely low, $2^{-90}$.

How can you reach particular entropy? There are many ways. If you use English lower and upper case English letters, use digits and some (for simplicity) 2 other characters, you have a set of 64 characters. If each character in password is chosen randomly, it gives you 6 bits entropy. If you wish to have 90 bits entropy, you need passwords of length 90 / 6 = 15. If you use lower case letters only, each gives 4.7 bits entropy, and you will need password length of 19 to get the same 90 bits entropy. You can even decide to use digits only. Each gives 3.3 bits entropy, and password of length 27 consisting only of digits will again give you the same 90 bits entropy.

Passwords don't have to be "complex" or "not spellable" by humans. You can take some 1024 simple words from dictionary. If chosen randomly, every such word will give you 10 bits entropy. To get 90 bits entropy, your password should consist of 9 words from this dictionary.

If some day quantum computers will be powerful enough, then to break the currently used encryption and hashing algorithms less time will be needed. To get the same degree of protection for such algorithms, you would need twice longer passwords, e.g. if you use lowercase letters only, instead of password length 19 you would need password length 38. But there are methods that are resistant to quantum computers, you can look up for post quantum cryptography.

And there is one important aspect in the security: Protection measures should be commensurate with risks. If you want to protect access to a web site with the pictures of your cat or dog, and give access only to 5 persons out of 100 who you know, then a password of 3-4 letters may be sufficient. If you want to protect access to a bank account, much longer password can make sense.

You should consider also the goals of password usage. What I said above is mainly relevant for cases when you encrypt file or in general some message and transfer it via insecure public channels. If you need password for authentication, then besides passwords there is multi-factor authentication, and even with relatively short and simple passwords you can reach the desired degree of security. Besides, passwords may disappear in some systems and may be replaced with passwordless authentication methods in the next years.

If you want to propose something to a government, you may want to check what the government already knows and uses. For this, you may want to start with NIST cryptography website.

Answer 2

It's all about unpredictability, the size of the character set, and the length of the password.

If you use a cryptographically secure pseudorandom number generator (CSPRNG) to generate numbers in the full character set (lowercase, uppercase, numbers, symbols) or word list (e.g. EFF's long wordlist) range, the password/passphrase will have high entropy assuming you choose a sufficient number of characters/words (e.g. ~20 characters or ~8 words). See this article for example.

Having a high entropy password can be thought of as like having a high entropy encryption key. At a certain entropy, it'll be practically or completely impossible to bruteforce, which means it's secure. The trouble is, a password/passphrase will probably be low in entropy if generated by a human, meaning passwords are generally nowhere near as strong as keys. That's because humans are bad at coming up with unpredictable passwords and want something memorable, meaning not that long.

In the case of something like 1234, that has low entropy because it's only numbers and four characters long. The number character set is 1234567890, which means 10 possible characters. As the password is only 4 characters long, that means at most 10$^4$ (10,000) possible permutations to bruteforce. That's terrible as it would take no time at all to find the right password. In contrast, a 256-bit encryption key would take at most 2$^{256}$ to bruteforce, which is 115792089237316195423570985008687907853269984665640564039457584007913129639936 possible permutations (I can't be asked to write the commas). That's outright impossible to perform, demonstrating the difference in security.

Furthermore, 1234 is definitely in password dictionaries. That can speed up attacks on certain longer/more complex passwords as well (e.g. fancy symbol substitutions for letters like p@ssw0rd). If it's a common or leaked password, it's weak because it'll be easier to guess.