I am thinking on a system, which measures the complexity of a password not based on its entropy or compressibility, but with a simply sophisticated method.

The measurement of the entropy/compressibility are measuring the idea, "how hard is to build this password from bytes". I am thinking on a method, which measures "how hard could this password be build from the concepts in the mind of the crackers".

What are in the mind of the crackers? Words, and algorithms. Thus, what need to be find out: how hard is it to build from the word and algorithms living in the mind of an intelligent entity whose goal is to crack the password. They use vocabulary of course, also these words should be also viewed.

Are there some mathematical model using this concept?


There is a very well-defined concept -- its called informational entropy. While there is a relationship between entropy and compressibility, don't think of entropy as a synonym for compressibility.

Entropy is the number of 50/50 decisions (like a flip of a fair coin) needed to make a password and we call each of these 50-50 decisions a bit of entropy. If you choose a password at random from a 1024-long list of common passwords, your password has 10-bits of entropy as 210 = 1024. If you choose a password by picking 12 random letters (taken from upper-case, lower-case, and numbers - for a total of 62 characters), we know there are 6212 such passwords which involved log2 (6212) ~ 71.450 ~ 71 bits (note 271.450 ~ 6212).

Informational entropy relates to a lower-limit on how approximately long it would take the best super-sophisticated attacker to construct your password. If they knew the exact model you used to create your password (e.g., they've seen other passwords you've generated or you've leaked your method), but your password generation method required ~71 random 50/50 decisions that means they'll have to try roughly 271 ~ 2,361,183,241,434,822,606,848 different passwords (so at a billion passwords a second it would take them tens of thousands of years to break). If they don't know your model, they'll have to try many more than that. (Because they first spent time brute-forcing 6-character passwords, going through a leaked password list of 100 million common passwords, then tried 7-character passwords, etc.

Note if an attacker also tried 8,9,10,11 character passwords first it doesn't make that much of a difference to the entropy if they eventually need to try 12 character passwords. That is 6212 ~ 271.450, but 628 + 629 + 6210 + 6211 + 6212 ~ 271.474 -- thus if your effort could crack passwords up to 12 characters long it could also crack passwords that are shorter with effort thats insignificant compared to cracking the 12-character password.

If your password is not based on random things, but say based on your spouse/children/pet's names or some commonly available fact with slight substitutions then it will be much weaker. The entropy calculation could be start from number of facts about you before someone would come up with the basis of the password plus number of random alterations (similar to http://xkcd.com/938 ).

  • The goal were to find such passwords, which are easy to remember, but they can be hard to generate algorithmically. Such passwords are hard to generate - but their complexity to be genberated is maybe measurable. – peterh - Reinstate Monica May 16 '14 at 16:50

How could an attacker think?

As they want first try to understand how you think, in order to imagine which method you use to create your password...

Depending on who are attacking you...

For the most common cases, simple strong password may suffice, but for others more specific cases, you are speaking about a kind of war, where everything are permit.

The best known way to find a password stay social engineering (or maybe ask him...... not very mathematical, but efficient!)

  • Thank you your answer. I think, social engineering can in this case not modelled. I think something like a mix of the compressibility/entropy analysis, but somehow mixed with a vocabulary search as well. – peterh - Reinstate Monica May 16 '14 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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