Understanding Password Complexity

Question

I’m trying to understand how a program checks for passwords and how fast it iterates through a loop.

I think I understand how to calculate the minimum required strength for my password.

• Estimate that an adversary can guess one billion (10^9) combinations a second (Snowden)
• Want to make the data safe forever. Let’s define forever as one million years.
• That’s (one day $= 86,400$ seconds – say $10^5$) times $365$ (say $10^3$) times one million ($10^6$)
• At minimum my password must be greater than $10 ^{(9+5+3+6)} = 10^{23}$

OK. So far so good.

If we come up with a randomly arrived at password that requires at least 10^{23} then the password is safe.

Now let’s say that we want an algorithm that can be remembered; that can be salted and that one can make different levels of difficulty.

I understand the concept of a dictionary attack but trying to fine-tune my understanding.

• Let’s assume that we have a dictionary of words from which to compose the password.
• Let’s assume that this dictionary has a length of $1000$.
• I’m assuming that a dictionary attack simply loops through an array.

So, if we have selected four randomly selected words { CORRECT HORSE BATTERY STAPLE } from that dictionary (of a $1000$ words) ones password strength would be $1000^4$ (assuming random means one can repeat the words) or $10^{12}$.

QUESTION 1: Is each loop through the array one iteration? Does that mean that the password would be uncovered in $10^3$ seconds? (I’m assuming yes. Just affirming)

Say the attacker assumes people may substitute zeros for Os then both HORSE and H0RSE would need to be tried.

QUESTION 2: Has the time iterating through the loop doubled? Would the attacker have to evaluate STAPLE to see if, it too, had an O?

Say I add a character between each of the words { CORRECTXHORSEXBATTERYXSTAPLE } That would add very little to the difficulty, it would up the complexity by just $26$ but if I used a different letter between each word then the difficulty would increase by $26^4$.

QUESTION 3: How does one calculate the effort required by the attacker?

• Take dictionary (assume for simplicities sake)
• Iterate through first time (takes $10^{12}$ / $10^9$ seconds)
• Iterate through a second time substituting zeros for ohs. (Assume one oh per word – for simplicities sake) so that takes another $10^{12}$ / $10^9$ seconds
• Iterate through a third time substituting @ for ohs
• Iterate through a fourth time substituting ! for I
• And so on …

Even If the attacker must do $1000$ such substitutions it would turn out to be 1000 iterations. If each iteration takes $10^3$ seconds then the total time is $10^3 \cdot 10^3$ or $10^6$ seconds.

What we get from this is adding complexity by substitution is far less effective than increasing the length of the password.

If we add another dictionary entry to CORRECT HORSE BATTERY STAPLE, for example - CORRECT HORSE BATTERY STAPLE PIANO then the difficultry would have increased to $1000^5$ or $10^{15}$. $10^15/10^9$ is $10^6$. We keep things simple and have the same defense.

Is the above reasoning correct? And by the way I’m purposefully avoiding birthday attacks – that will be part of another question. :)

Moderators – I understand that this does not fit in well with the Q/A format expected by StackExchange.

Answer 1

Your counting arguments seem correct but are somewhat moot.

Note that $10^{23}\approx 2^{76}.$ Not even the most optimistic analyses of typical password entropy yield more than $2^{30}$ or so.

Plus there is the issue of what the system does with the password input. All an attacker needs is to find some input into the passwording process that gives the same output as your password.