The math of password policy anti-patterns I work in Information Security and this week I encountered an interesting math case that involves a password policy.
Password policies are normally created to increase the complexity of passwords. Complexity in this context means that password properties enforce a set of potential passwords that require an impractical amount of time to iterate.
The math for policies in the form "minimal length of x with characters from set y" is easy: the amount of potential passwords is $\operatorname{length}(y)^x,$ assuming that the user chose a password of length x. One can then divide that number by cracking-attempts per second to find the maximum time it will take to crack a password.
This week I encountered software that said "no two consecutive characters are allowed". So you can't have the password "fooz", because it contains two consecutive "o"s. This is a terrible idea because it actually reduces the complexity of passwords. I want to make a nice case of a "good" vs a "bad" policy. Obviously I can't make a script to just iterate over the potential passwords to filter out passwords that match the weak policy, since this takes an impractical amount of time.
I want to make a formula for the weak policy. Excuse my math as I don't normally write like this, but here goes:
$$
A = \text{Length of set of allowed characters}\\
L = \text{Length of password}\\
PP = \text{Amount of potential passwords with a proper policy}\\
PW = \text{Amount of potential passwords with the weak policy}\\
PP = A^L\\
PW = ?
$$
I figured out that for A=L, it's:
$$
PW = A(A-1)^{(A-1)}
$$
What is the formula for arbitrary A and L? I'm guessing it's something like $PW = A(L-1)^{(A-1)}$ but I can't validate it since I can only program and I can't do math proof.
With both formulas, I can make nice tables and plots to show the impact of these policies on potential cracking time to make business cases. Note that the proper way of forming password policies is that "no sequences" should be told to the user, and "password of length x with characters y" should be enforced on the software-level.
Since this is probability a walk in the park for you guys, it would be interesting to see if one can make formulas for complex cases such as "no sequences like 1234 or abcd" or "no repeating substrings".
 A: If $n$ is a positive integer, we can consider a password of length $n,$ consisting of characters taken from a set $V,$ as a function $s \colon I_n \to V,$ where $I_n = \{1, 2, \ldots, n\}.$
If $s$ is a password of length $n,$ and $x$ is a character, i.e., an element of $V,$ denote by $s + x$ the function that agrees with $s$ on $I_n,$ and maps the integer $n + 1$ to $x.$ Then $s + x$ is a password of length $n + 1.$
Any password of length $n + 1$ has the form $s + x$ for some $s$ and some $x.$
For all passwords $s, s'$ of equal length, and all characters $x, x',$
\begin{equation}
\label{3784028:eq:1}\tag{$1$}
s + x = s' + x' \iff s = s' \text{ and } x = x'.
\end{equation}
It follows by induction on $n$ that the number of passwords of length $n$ is $|V|^n.$
It follows similarly that the number of passwords of length $n$ satisfying the weak policy is
$$
|V|(|V| - 1)^{n - 1}.
$$
Proof. When $n = 1,$ any single-character password satisfies the policy, so the number of admissible passwords in this case is $|V|,$ as stated.
Suppose that the result is true for some particular value of $n.$ A password of length $n + 1$ has the form $s + x,$ where $s$ has length $n.$ The password $s + x$ satisfies the policy if and only if (i) $s$ satisfies the policy, and (ii) $x$ is not equal to the last character of $s.$
For each admissible password $s$ of length $n,$ let $W(s)$ be the set of all admissible passwords of the form $s + x$ for some $x \in V.$ Then $|W(s)| = |V| - 1$ for all $s.$ By the inductive hypothesis, there are $|V|(|V| - 1)^{n - 1}$ sets $W(s).$ By \eqref{3784028:eq:1}, the sets $W(s)$ and $W(s')$ are disjoint whenever $s \ne s'.$ Therefore the number of admissible passwords of length $n + 1$ is
$$
|V|(|V| - 1)^{n - 1}(|V| - 1) = |V|(|V| - 1)^n.
$$
This proves the result by induction on $n.$ $\ \square$
In the notation of the question, the result is:
$$
PW = A(A - 1)^{L - 1}.
$$
So you were right in the case $A = L$ (assuming that by "$a$" in the exponent, you meant $A$), but in the general case you got $A$ and $L$ mixed up.
