Entropy of Password Generators

TL;DR

The entropy in use is min-entropy, giving a pessimistic measure of the entropy which is the desired outcome for security and cryptographic concerns

:warning: The following is a personal exploration around the theory of entropy and should probably not be cited directly.

1. Entropy of Standard Password Generators
2. Entropy of Stateful Password Generators
3. Entropy of Non-Irreducible Password Generators
4. Entropy of Potentially Non-Uniform Password Generators
5. Entropy of Stochastic Password Generators
6. Entropy of Obscure Password Generators

Entropy of Standard Password Generators

A perfect adversary knows exactly how you generated your password, even how the random numbers were generated up to and including the time of day, mac-address of your machine, and the sensory input of your mouse. They are only limited by the rate which they can attempt different passwords.

The standard secure password generators would use an alphabet $\mathcal{A} = \{a,b,c...\}$ with uniform probability of each letter, and a cryptographically secure random number generator. The adversary knows your password has $n$ letters, and so they have $B_n = |\mathcal{A}|^n$ different passwords to try and no additional hints to judge which is more likely.

With a password generator $G_{\mathcal{A}}$, the number of possibilities $B_n$ tend to grow exponentially with regards to the password-length $n$, and the base of this exponential growth then gives a measure of the entropy. In particular, the entropy is usually defined as relative to base 2, so that the exponential growth can be written in the form $2^{cn}$ for some $c$. This $c$ is then the bits of entropy inherent in the generator, which we will denote as $h(G_\mathcal{A})$ (historical note: h is for entropy, due to capital eta being written $\Eta$, which looks similar to latin H)

$h(G_\mathcal{A}) = \lim_{n\to\infty} \frac{1}{n} \log_2 B_n = \log_2 |\mathcal{A}|$

Thus the entropy of a standard password generators can be considered wholly dependent upon the number of letters available.

Now, how many attempts do they have to try before it starts becoming more likely that they have succeeded than not? They have chosen an optimal sequence of guesses, $\{g_1, g_2, g_3, ..., g_{B_n}\}$, so the number of guesses they had to make if the right password was $g_i$ is then $G_{g_i}=i$. The expected number of guesses before they succeed guessing your password $X$ is then

$E(G_X) = \sum_{i=1}^{B_n} P(X = g_i) E(G_X | X = g_i) = \frac{1}{B_n}\sum_{i=1}^{B_n}i = \frac{B_n + 1}{2}$

They are expected to try at least half the possible passwords before they succeed. Written in terms of the entropy, the formula then becomes

$E(G_X) = \frac{2^{h(G_\mathcal{A})n} + 1}{2} > 2^{h(G_\mathcal{A})n - 1}$

Note that this method of calculating expected guesses only holds for password generators with a uniform probability.

Entropy of Stateful Password Generators

Sometimes a perfect password generator is not perfect for you. Perhaps you would like a password that is easier to remember, or has a particular pattern to it. Sometimes you want stateful generators that has a slight chance of a number, but never more than one at a time.

Each choice here would reduce the entropy and require longer passwords for the same amount of security, but the trade-off can be worth it. The question then is how to find the entropy of your bespoke generator so that you are not unintentionally weakening your security for convenience.

Let's say your generator has two states: vowel and consonant. In the vowel-state, it emits a consonant and changes the state to the consonant-state, and vice versa. This generator $G_\mathcal{S}$ can be visualized as a graph:

            aeiouy
+-------+-----------------------> +-----------+
| VOWEL |                         | CONSONANT |
+-------+ <-----------------------+-----------+
            bcdfghjklmnpqrstvwxz
            

This system would emit an infinite sequence of symbols ...azucumomozyhisulujewibokydacezunanubus... and to make this a password generator, we just cut out a random section of $n$ letters. The study of such infinite sequences of symbols is a part of Symbolic Dynamics, and the space of all possible infinite sequences of a given pattern is known as a Shift Space. From the study of shift spaces, we can find a series of theorems and proposition that will help us determine the entropy of stateful password generators.

But first, let's start with our existing definition of entropy, using $B_n(G_\mathcal S)$ the number of possible passwords of length $n$:

$h(G_\mathcal{S}) = - \lim_{n\to\infty} \frac{1}{n}\log_2 B_n({G_\mathcal{S}})$

To find $B_n(G_\mathcal S)$, it can be useful to look upon the adjacency matrix of our state diagram

The number of 2-letter passwords of the starting in state $i$ and ending in state $j$ is $\sum_{k\in\mathcal S} (A_{\mathcal S})_{ik}(A_{\mathcal S})_{kj}$, otherwise known as be $(A_{\mathcal S}^2)_{ij}$. This holds in general, and $(A_{\mathcal S}^n)_{ij}$ is is excatly the number of passwords from starting in state $i$ and ending in state $j$ and so we get

$B_n(G_\mathcal S) = \sum_{ij} (A_\mathcal S^n)_{ij}$

While calculating this directly is possible, there is a large amount of existing theory available for us, especially if our graph is irreducible. An irreducible graph is one in which there exists a path starting at state $i$, ending in state $j$, for any two $i,j$.

Perron-Frobenius Theory tells us that any irreducible matrix $A \neq 0$ have a perron-eigenvalue $\lambda_A > 0$ such that any other eigenvalue $\mu$, $|\mu| \leq \lambda_A$.

Furthermore, an unnamed theorem tells us that for any irreducible right resolving graph $G$ with adjancency matrix $A$, we have that

$h(G) = \log_2 \lambda_A$

A right resolving graph is a graph with labeled edges, in which all edges out of a given vertex have different labels. A different theorem actually tells us that all "password generators of finite memory" (also known as sofic shifts) can be represented with a right resolving graph.

The password generators that we can generate with the the specification format as of the time of writing, belong to an even more restrictive class of shifts, namely shifts of finite type (SFT). These are the spaces that have a finite set of "forbidden" sequences, and our current window-condition for state change naturally generates such a set. This gives us an easier condition, as for an irreducible graph $G$ (with adjacency matrix $A_G$) representing a SFT, we have $h(G) = \log_2 \lambda_{A_G}$.

Now the question remains to make our password generators be irreducible, and the entropy is can be easily calculated.

Entropy of Non-Irreducible Password Generators

• Breaking down a non-irreducible password generator $A$ into irreducible components $A_i$
• Theorems showing that $\lambda_A = \max_i \lambda_{A_i}$, and that $h(G_A) = \lambda_A$ still holds for shifts in particular
• Arguing that for password generators in particular, being finite, the entropy is much more affected by the initial state than any infinitely running shift.
• Consider introducing "run-length" dependent entropy for password generators, because the shift-entropy is "infinite run-length".

Entropy of Potentially Non-Uniform Password Generators

We have now mostly dealt with entropy of password generators as if they are always equal to the entropy of the shift space from which the passwords are gathered. This is not necessarily the case, and must be investigated.

In particular, a difference between shifts and password generators is that shifts concerns themselves mostly about which (infinite) sequences are possible, while password generators need to think about which (finite) sequences are probable. While we can calculate a measure of entropy based on the number of passwords generated $B_n$, it would be more helpful to calculate the entropy as it changes for each transition between the states, how much information is added by each step. This would allow us to expand our definition of entropy into non-uniform probabilities of passwords.

Based on the work of Claude Shannon there is generally four axioms that encompass what it means to measure the information value $I$ of an event. To quote Wikipedia

1. $I(p)$ is monotonically decreasing in p: an increase in the probability of an event decreases the information from an observed event, and vice versa.

2. $I(p) \geq 0$: information is a non-negative quantity.

3. $I(1) = 0$: events that always occur do not communicate information.

4. $I(p1, p2) = I(p1) + I(p2)$: the information learned from independent events is the sum of the information learned from each event.

...

Shannon discovered that a suitable choice of $I$ is given by:

$I(p) = \log(\frac{1}{p}) = -\log(p)$

In fact, the only possible values of I are $I(u) = k\log u$ for $k<0$.

In particular, entropy $\Eta$ is generally defined as the expected value of information content, which using this formula gives us:

$\Eta(X) = E[I(X)] = - \sum_{x_i\in X} P(x_i)I(x_i) = - \sum_{x_i\in X} P(x_i)\log_b(P(x_i))$

The log-base $b$ is usually chosen as $2$, giving us bits of entropy.

We may also show that this definition is consistent with our earlier definition of entropy $\lim_{n\to\infty} \frac{1}{n} \log_2 B_n$ for certain groups of generators. Given a password generator $G$, the probability for a given password $p$ of length $n$ is $1/B_n$, which gives us:

$\Eta(G_n) = - \sum_{p\in G_n} \frac{1}{B_n}\log_2(\frac{1}{B_n}) = \log_b{B_n}$

Therefore the entropy "per character" in the generator goes to $h(G)$ as $n\to\infty$. As long as we have right resolving matrices, with uniform probability between the edges, each password of a given length remains of uniform probability and we can continue to use $\lambda_A$ to calculate the entropy as the two definitions coincide. This new definition gives us a way to adjust the probabilities of edges while still being able to judge entropy, as well as feel more certain in calculating the entropy of $n$-length passwords using $B_n = \Sigma_{ij} A^n_{ij}$

Entropy of Stochastic Password Generators

A syllabetical password generator is readable and pronouncible, and generally just fine, but what if we want more? What if instead we want to base our passwords around bigrams, in which the edges are purposely non-uniform in their distribution? Perhaps we have a strong preference for the vowel a as opposed to y? Now let's introduce probability to our edges, and explore how that affects the entropy.

There is established theory about this if we turn to Markov models, but they concern themselve smostly with the probability of the destination, and not the manner in which you arrive, and so we need to modify our graph in a particular manner. But first, let's ensure we all are operating on the definition and notation.

A topological Markov chain is a pair $(P,\pi)$ of a stochastic transition matrix $P$ and its stationary probability vector $\pi$, that is compatible with a given shift of finite type (ie. $\pi_{ij} = 0$ whenever $A_{ij} = 0$).

In the earlier sections, we defined the topological entropy on subshifts measuring variety, and the Shannon entropy on uncertain events measuring information content. For Markov models in general it more common to operate with the Kolmogorov-Sinai entropy of the Markov measure, but we are in a cryptographical context, and so there is another entropy that might be of more interest: min-entropy.

In a cryptographical context we are more concerned about being secure rather than right, and so the min-entropy can give us a better baseline on which we can build our tolerances for insecurity.

The general definition of min-entropy is not as useful to us:

$H_\infty(p) = - \log_2 max_x p (x) = min_x (-\log_2 p(x))$

This would require iterating over all possible passwords, but for Markov models, there is a better way:

$H_\infty((\pi,P)_n) = -\log_2\left(\pi\odot \underbrace{P\odot P \odot ... \odot P}_{n-1} \odot \vec 1 \right)$

Here $\odot$ is defined as a matrix multiplication, but reducing the dot-product with $\max$ instead of $\sum$, and $\vec 1_i = 1$ for all $i$.

Now the only remaining problem is that this is defined for "proper" markov models, but for computational simplicity the password generator this page is written for is based around the concept of "emission sets". With $(G, A)$ be our right resolving graph and associated adjacency matrix for our model, with edge-labels in $\mathcal A$. We define the emission sets of $\mathbb A_i$ as the disjoint sets $A_{i,x} \subset \mathcal{A_{i}}$ such that any label $\alpha_x\in A_{i,x}$ have the same probability $p_x$ and ends up in the same state $j_x$. We state $A_{ij,x}\subset \mathcal A_{ij}$ for the subsets ending in j

Let $K_ij$ be the set of states in which both $A_{ik}\neq 0$ and $A_{kj}\neq 0$

Let's define $M_{ij} = \max_{x\in A_{ij}} p_x$.

Which gives us $H_{i\to_2j} = -\log_2 M^2_{ij}$. And more in general $H_{ij}(G_n) = (\underbrace{M\odot M \odot ... \odot M}_{n})_{ij}$.

To get our actual entropy we need to have the probability of the initial positions, which for a proper Markov model would be $\pi$. However, since we are using this as a password generator, the "true" initial position is the actual initial position used. In particular, this currently is a rather simple $v_i = \frac{1}{N}$ where $N$ is the number of states. Thus, our result ends as

$H_{\tilde\infty}(G_n) = - \log_2 v\odot (\underbrace{M\odot M \odot ... \odot M}_{n})\odot u \leq H_t(G_n)$

Now this can be more easily worked with, and requires somewhere around $O(N^3n)$ operations to calculate.

Entropy of Obscure Password Generators

While non-standard password generators generally reduces the entropy, and security by obscurity is not generally considered security at all, it often feels that as long as nobody targets you specifically, a custom generator has a virtual increase in entropy. This is not the case. Ultimately, the only secure password is one with sufficiently high entropy. One should always strive to avoid any password that has ever been used before, ever. The reason being, at some point a previously used password is going to turn up in a password-leak, and thus be among the first attempted by an automated attacker. A password should strive to be universally unique.

Assume that every person ever has created one new (universally unique) password every millisecond for the duration of their lifetime. We want there to be virtually no chance that our generators generate any of these passwords. We have approximately $10^{10}$ people, and and a conservative upper bound of $1000\cdot60\cdot60\cdot24\cdot365\cdot88 = 2.8\cdot 10^{12}$ passwords generated by each person.

Therefore, if all $10^{22}$ passwords were generated with our obscure password generator, we want there to be virtually no chance of any collision what-so-ever. How much entropy do we then need? Well, it depends on what one considers 'virtually no chance', but for sake of argument let's use a winning the lottery. That is, our password generator is "sufficiently secure" if the chance for there being any collision whatsoever is similar to winning a state-lottery, which is about $10^{-7}$

... todo: calculate a proper expression of entropy limits for secure passwords given the above variables.