0
$\begingroup$

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?

$\endgroup$
9
  • 2
    $\begingroup$ No, there is not. But it also can't be proven or disproven. At least not in the mathematical sense. Humans are awful at randomness - we just don't know if it's just bad or REALLY bad. $\endgroup$
    – tylo
    Jul 15, 2022 at 21:02
  • $\begingroup$ This sounds like homework. As often mentioned on this site, entropy is the result of a process. $\endgroup$ Jul 15, 2022 at 21:03
  • $\begingroup$ @AmanGrewal I don't think this is homework, or that task would be really unfair to the student. But it's from a beginner's point of view most likely. $\endgroup$
    – tylo
    Jul 15, 2022 at 21:11
  • 1
    $\begingroup$ @programmer777: 1) Have you read these answers? Do you know the meaning of entropy for password resistance? 2) In some use cases like authentication, passwords may be replaced with other technologies in the next years. $\endgroup$
    – mentallurg
    Jul 15, 2022 at 23:12
  • 2
    $\begingroup$ Is the password PJ##$DMFS%#$% secure? No, of course not, I just printed it here. What if it contains a specific word, possibly by accident? Is that secure? What if the word is in Chinese or Russian? We can see if a password generation process is secure - assuming the password is randomized - here entropy enters the mix - but that's about it. $\endgroup$
    – Maarten Bodewes
    Jul 16, 2022 at 0:19

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Well, if a person doesn't go to school, possible reason may be that the person has graduated from school perhaps is working and no more needs to go to school. So you may not belittle me because I said I don't go to school. I appreciate your feedback. However, in your answer, you make claims but you do not provide any source, authority, specific theory or concept to back the claims. This advice about password is the usual one that people know. But what theory, concept, proof etc do we use to determine that a person is right when they provide advice such as you have given? I noted the NIST link $\endgroup$ Jul 16, 2022 at 8:26
  • 1
    $\begingroup$ To provide my background, I myself, I am a software developer and I deal with password authentication in my work, algorithms and similar security matters in my work as software developer. $\endgroup$ Jul 16, 2022 at 8:29
  • 1
    $\begingroup$ "you make claims" - What claims do you mean? I said "If you wish to have 90 bits entropy..." This is not a claim, this is an example. What claims do you mean? $\endgroup$
    – mentallurg
    Jul 16, 2022 at 21:51
  • 1
    $\begingroup$ "when they provide advice such as you have given" - What advice do you mean? $\endgroup$
    – mentallurg
    Jul 16, 2022 at 21:52
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks. I am looking for the theory which support what you have said $\endgroup$ Jul 16, 2022 at 11:40
  • $\begingroup$ Thanks. I am looking for the theory which support what you have said $\endgroup$ Jul 16, 2022 at 11:41
  • $\begingroup$ @programmer777 The theory is the number of permutations. That's just maths. There's nothing else you can use. As for dictionaries, that comes down to searching password dumps. $\endgroup$ Jul 16, 2022 at 12:19
  • $\begingroup$ Also, I'd recommend zxcvbn if you want to check the strength of a password easily in software. It's by Dropbox. $\endgroup$ Jul 16, 2022 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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