# Strength Analysis of Real-Life Passwords Using Markov Models
## 3 Background  
Markov model is a stochastic process where the next state of the system depends only on the present state and not on preceding states [26]. That is, only on the single present state and not the history of the states. Markov models are commonly used as a language processing tool in speech recognition systems, like in [26], but they can also be used in other fields, particularly in the context of passwords. Such Markov models have already been used before (see Section 2) as an aid to brute-force or dictionary password cracking. These models are based on the fact that particular characters or sub-strings in a particular language area have a higher frequency of occurrence than others (e.g., the string \"the\" is much more likely to occur than \"tqe\" and the letter \(e\) is very likely to follow \"th\"). This approach can be used to calculate the strength of the password, by defining a probability distribution over a sequence of characters, which constitutes the password. Such constructed Markov model assigns each password a probability \(P\), which is calculated differently based on the order of the Markov model. The general equation for calculating this probability is [12]:  
\[P(``c_{1}c_{2}...c_{l}^{\prime\prime})=P(c_{i}|c_{1}...c_{n})\prod_{i=n}^{l}P( c_{i}|c_{i-n+1}...c_{i-1}). \tag{1}\]  
and can be applied to every order of the Markov models. The models used by [PERSON] and [PERSON] are zero-order model and first-order model. Zero-order Markov model is a Markov model, where the characters are independent of each other i.e., each character's probability is calculated according to the underlying frequency distribution and independently of the previous characters. On the other hand, first-order Markov model is a Markov model, where each 2-gram (i.e., diagram, ordered pair, or a sub-string of length 2) of characters is assigned a probability by looking at the previous character. The probability assigned to a password \(``c_{1}c_{2}...c_{l}\"\) in the case of a first-order Markov model would be ([13]):  
\[P(``c_{1}c_{2}...c_{l}^{\prime\prime})=P(c_{1})P(c_{2}|c_{1})P(c_{3}|c_{2})...P (c_{l}|c_{i-1}). \tag{2}\]  
The probabilities \(P(\alpha_{j}|\alpha_{i})\) are called _conditional transitional probabilities_ and denote the probability of a transition to state \(\alpha_{j}\) when the automata is in state \(\alpha_{i}\). In the context of passwords that would be the probability of a character \(c_{i}\) following the character \(c_{i-1}\). The conditional probabilities can be easily computed with the following formula ([13]):  
\[P(c_{i}|c_{i-1})=\frac{count(c_{i-1}c_{i})}{count(c_{i-1}x)} \tag{3}\]  
where \(count(c_{i-1}c_{i})\) presents the number of occurrences of the sub-string \(c_{i-1}c_{i}\) and \(count(c_{i-1}x)\) denotes the number of occurrences of \(c_{i-1}\) when followed by another character \(x\). This character \(x\) is part of the password's alphabet \(A\), i.e., the set of distinct characters that are identified in a particular password dataset, which is also the number of possible states of the Markov model. The number of sub-strings \(c_{i-1}x\) in a particular dataset is by definition equal to: \(count(c_{i-1}x)=\sum_{c_{i}\in A}count(c_{i-1}c_{i})\). By using this substitution, the above Equation (3) takes the form:  
\[P(c_{i}|c_{i-1})=\frac{count(c_{i-1}c_{i})}{\sum_{c_{i}\in A}count(c_{i-1}c_{i })}. \tag{4}\]  
The transitional probabilities (\(P(\alpha_{j}|\alpha_{i})\)) between the states of the model (\(\alpha_{j}\) being the current state and \(\alpha_{i}\) being the previous state) are described by a matrix called _transition probability matrix_ or simply _transition matrix_. Each value \(P(\alpha_{j}|\alpha_{i})\) denotes the probability that, given the model is currently in state \(\alpha_{i}\), it will be in state \(\alpha_{j}\) in the next step. The power of Markov models lies in the ability to use the transition matrix for determining the probability of the model being in a certain state after a certain number of steps (more than one).