# Dynamic Markov Model: Password Guessing Using Probability Adjustment Method
## 3 Method  
### Standard Markov Model  
It is impossible to accurately model the probability of a password directly. The Markov model makes a concise hypothesis for the expression of password probability, and then the password can be statistically modeled. In the Markov model, the probability distribution of characters in each state is only related to the characters in the front \(n\) state, where \(n\) is defined as the order of the model, as shown in Figure 1.  
Each character in the password can be combined with the previous \(n\) characters to form an n-gram fragment, which is denoted as \(c_{i}|c_{i-1},\ldots,c_{i-n}\) where \(c_{i}\) is the character in the \(i\)th state, and \(|\) is used to isolate the current and previous state characters, so the n-gram fragment represents the dependencies between the current and previous character. For example, a password \(P:c_{1}c_{2}\ldots c_{m}\) containing \(m\) characters can be divided into \(m\) n-gram fragments: \(c_{1};c_{2}|c_{1};\ldots;c_{m}|c_{m-1},c_{m-2},\ldots,c_{m-n}\). It should be noted that the first \(n\) n-gram fragments are not \(n\) order gram, which should strictly be 0-gram, 1-gram, n-gram. Here, we call them all n-gram fragments for convenience. Each n-gram fragment \(c_{i}|c_{i-1},\ldots,c_{i-n}\) corresponds to a conditional probability \(p(c_{i}|c_{i-1},c_{i-2},\ldots,c_{i-n})\), and these n-gram fragments are independent of each other, so the probability of password \(P\) is the product of \(m\) conditional probability values:  
\[p(c_{1}c_{2}\ldots c_{m})=\prod_{i=1}^{m}p(c_{i}|c_{i-1},c_{i-2},\ldots,c_{i-n }). \tag{1}\]  
The [PERSON] model should be trained well before generating passwords. In preparation, we have to collect a public password dataset containing quantities of real passwords as a training set. While training the [PERSON] model, we first split each training password into multiple n-gram fragments, count the occurrence frequency of all n-gram fragments, and then collect n-gram fragments that have the same conditional character; eventually we perform the probability normalization operation to obtain the corresponding n-gram conditional probability distribution. The process is depicted in Figure 2. We define the n-gram table as the set of all n-gram conditional probability distributions. After the training process succeeds, the n-gram table stores the conditional probability distribution of all characters learned by the model, and the explicitly statistical modeling of password probability is completed. When we need to generate a password, we just continuously sample the characters in the n-gram table one by one. We denote this kind of Markov model that uses random sampling as the standard Markov model in the next. Figure 1: Markov model (order of model is 2). In order to further analyze the password probability distribution, we have to make a clear definition of the support set and original probability distribution of the Markov model. We define the maximum length of the string as \(m_{MAX}\), and the character set is \(V=A,B,\ldots,Z,a,b,\ldots,z,0,1,\ldots,9,+,*,\ldots,t\). For any string \(C:c_{1}c_{2}\ldots c_{m}\) in string space \(S_{S}\), all satisfy both (1) \(m\leq m_{MAX}\), and (2) \(c_{i}\in V\), \(\forall i\). The Markov model explicitly fixes the probability of each string in string space \(S_{S}\). For part of the strings \(C\in S_{S}\), probability \(P(C)\) can be obtained by querying the n-gram table, while for another part of strings \(C^{{}^{\prime}}\in S_{S}\), some n-gram fragments do not exist in the n-gram table, which means their probability is 0. We can form a set of all strings whose probability value is more than 0, and define this set support set \(S_{M}\). Obviously, support set \(S_{M}\) is a subset of string space \(S_{S}\). The sum of the probabilities of all strings in \(S_{M}\) is 1, where high probability means the string has a higher probability of being a password, and low probability means the string is not likely to be a password.